ソースコード一致度測定ツール

1.要件
ソースコードを解析し、その内容がどの程度他のソースコードに一致するかを測定し、その関係図を図示する。
1.1.二つのソースコードの一致度
簡易化のため、ソースコードの構文解析は行わない。まず、行単位の一致度を求める。これは、Unixコマンドのdiffのようなもの。さらに、二つの行を比較するとき、単語間のdiffも行うようにする。このときの一致度を行の一致度として取り扱う。最後に、一致度が最小となる数値の対応表を保存する。
1.2.グラフ化
数十人についてのファイルを互いに比較し、その一致度からグラフ化を行う。まずは、互いのファイルの一致度を求めて、テーブルを作成する。次に、このテーブルより何らかのグラフを抽出する。どうやってグラフとするかは、具体的なテーブルの内容を見てみないとわからないので、何とも言えない。あとは、graphvizを使って図化する。
1.3.性能についての考察
1.3.1 １行あたりの実行コスト
C言語のソースコードは１行あたり、多くても１０程度の単語しか存在しない。そして、一致度を求めるためには、ダイナミックプログラミングを用いてO(n2)だと思う。
1.3.2 ファイルあたりの実行コスト
一致度を求めるソースコードは、一ファイルあたり多くても１００〜２００行程度である。これも、ダイナミックプログラミングを用いてO(n2)ぐらいと見積もれる。
1.3.3 グラフ化あたりの実行コスト
すべてのファイル間の比較を行うと、純粋にO(n2)となる。ファイル総数は多くても４０である。おそらく比較のほうのコストに比べて、図化のコストは小さいので無視できると思う。
う〜ん、そもそも、単語と行とに分ける必要はあるのか？　分けないでやってみて、遅すぎたら分けてみるか？