トップC-Tips > プログラムの類似度計算

プログラムの類似度計算[2012年06月11日]

プログラムを作成するとき、非常に役に立つのは、プログラム事例である。 中でも、自分自身がこれまでに作成したプログラムが役に立つ。 Googleによるサイト内検索やライブラリ関数別索引を使用している。 このとき、問題なのは類似プログラムが多いことである。 類似プログラムの表示を抑止して、ライブラリ関数別索引をより使いやすくしたい。

1. 出現するライブラリ関数による類似度の計算

下に、各プログラムが使用しているライブラリ関数の一覧表の一部を示す。 最初の数値はその関数の出現回数である。 ライブラリ関数を使い方を調べるという観点からは、 関数の出現回数が完全に同じであれば類似度100%と考えてもよい。

プログラム別の関数出現回数を二次元配列 freq[FMAX][PMAX] で表す。 PMAX はプログラム数、FMAX は使用されている関数の総数を表す。 それぞれのプログラムでは、使われている関数はごく少数に限られているため、 freq はスパースな行列である。1000 × 1000 程度では問題ないが、 サイズが大きい時には効率的な管理方法をとる必要がある。

それぞれのプログラムは FMAX次元の値を持っている。 これをFMAX次元の空間に対するベクトルと考え、 二つのプログラムに対するベクトルのなす角度をθとするとき、 cosθの値を二つのプログラム間の類似度とする方法が広く知られている。 ただし、出現回数をそのままベクトルのある軸の値とするのではなく、 加工した値を用いるのが一般的である。 類似度を計算する上で、それぞれの関数名の重要度は同じではない。 printf関数のように、多くのプログラムで使われる関数は重要ではない。 よく使われるのが TF・IDF である。 TF(term frequency)はドキュメント(この場合プログラム)j におけるターム(この場合関数名)i の出現頻度 freq(i,j) である。

  tf(i,j) = freq(i,j)

次のように、Harmanの正規化が使われることが多い。

  tf(i,j) = log2(freq(i,j)+1) / log2(プログラムj中の関数名数)  ・・・・ (1)

一方、idf(Inverse Document Frequency) は、関数 i を含むプログラム数 Dfreq(i) の逆数 1 / Dfreq(i) である。

  idf(i) = 1 / Dfreq(i)

この場合にも、 Sparck Jonesによる正規化による以下の式が使われることが多い。Nはプログラム数である。

  idf(i) = log2(N / Dfreq(i)) + 1		・・・・ (2)

そこで、ここでは、(1)式×(2)式の値を、ベクトルの要素の値として、類似度を求めることとする。

2. IDFの計算結果

現在の326プログラムに対するIDFの計算結果の一部を下に示す。 printf や fopen はよく使うので、IDFの値は小さい。 GlobalLock や DrawIcon はそうそう使う関数ではないため、IDFの値は大きい。

3. TF・IDFの計算結果

TF・IDFの計算結果を以下に示す。 ただし、プログラムには関数を一つしか使わないものも含まれるため、0による除算を避けるために、 tfの計算は次式を用いた。 このようなプログラムは除外するやり方もあるが、類似度計算上の差異は極めて小さいので、 これを残しておくことにする。

  tf(i,j) = log2(freq(i,j)+1) / log2(プログラムj中の関数名数+1)  ・・・・ (1')

先頭の数値は出現回数で、2番目の数値が TF・IDF である。

4. 類似度の計算

類似度を計算するためには、 ベクトルの長さが1(各要素の自乗の和が1.0)になるように正規化しておく方がよい。 この結果を下に示す。 tfの計算式を (1)式としても、ここにあげた数値は完全に一致した。 (上で述べたように、関数が一つしかないプログラムでは、0除算エラーとなる)

プログラムA、Bの関数iの正規化した TF・IDF値をそれぞれ a(i), b(i) とすると 類似度はベクトルの内積

 sim(A,B) = Σia(i)・b(i) 
で計算できる。

4. 類似度によるプログラム事例の絞込み

最終的には、ライブラリ関数別のプログラム事例一覧表を作成する。 具体的には、下に示すものを HTML化する。 DLL番号順、アルファベット順にその関数を含むプログラム名、最終更新日時を出力している。 最初の数値は、それぞれのプログラムにおけるその関数の重み係数(TF・IDFを正規化した値)である。 この値が大きいほど、プログラムでその関数の占める役割が大きいと考えることができるため、 この値が大きい順に並び替えている。

一番上のプログラムは必ず事例とする。 2番目のプログラムは、1番目のプログラムと類似度が高ければ、事例としない。 この場合、先頭は無印である。類似度が小さければ、 これもプログラム事例として○印を表示している。 一般に2番目以降のプログラムは、最後にプログラム事例としたプログラムと類似かどうか調べ、 類似していない場合に、プログラム事例とする。 このような絞込みを行っても、プログラム事例数が多い関数がある。 5〜10個ほど、表示し、後はスクロールで見れるようにしたい。

  1. list.c
  2. lex.c
  3. count.c