2
1 3 4 6 5
T
totalDepartment of Computer Science, Graduate School of Information Science & Technology, Osaka University 84
ハッシュ関数を用いた解決法
ハッシュ関数 h( T
total) を用いた加工
｜ h( T
total) － h( T
total×0.97 ) ｜≦ １
｜ h( T
total×1.03 ) － h( T
total) ｜≦ １
h( T
total)
T
total2
1 3 4 6 5
T
total×0.97 T
total×1.03
Department of Computer Science, Graduate School of Information Science & Technology, Osaka University 85
ハッシュによる類似判定の効率化
現状の問題点
類似判断には９６（トークン構成）＋６（複雑度）＝１０２種類のメトリク 用いて比較を行っている。スを
新しい部品が入ってきた場合、全部の既存部品と
102
種類のメトリクスの 比較を行なわないとならない アイデア
下記のような部品を比較対象から除外することで、さらに高速化できないか
？
1.
トークンの総出現回数が0.97
倍未満or 1.03
倍超である部品2.
複雑度メトリクスが閾値を超える部品 実現方法
最終的な類似判断結果に直接影響を与えるメトリクス（＝主メトリクス）を キーとしたハッシュを利用し、事前に分類をしておく．
Department of Computer Science, Graduate School of Information Science & Technology, Osaka University 86
類似判定の効率化
メトリクス計測時に、いくつかの主メ トリクスでハッシュキーを作成するハッシュキーと既存登録部品を 対応させた表を構築しておく
DB [ 0. 0. 0]= null
[ 10. 62.124]=
部品A [ 10. 62.125]=
部品B
，部品C
[ 10. 62.126]= null
[255.255.255]=
部品Z
・・
・・
・
・
8bit 8bit 8bit
主メトリク ス
A
ハッシュキー ＝
(24bit)
新しく類似測定をしたい部品
P
が追加 される
部品P
のハッシュキー＝[10.62.125]
主メトリクス[A,B,C]
の閾値＝[0.0.1]
最終結果を変えずに解析コスト を下げることが可能
102
種のメトリクスを用いた類似判定 の計算を行うのは、部品A
，B
，C
の3
つのみとする主メトリク ス
B
主メトリク ス
C
Department of Computer Science, Graduate School of Information Science & Technology, Osaka University 87
ハッシュ関数を用いた解決法
ハッシュ関数 h( T
total) を用いた加工
｜ h( T
total) － h( T
total×0.97 ) ｜≦ １
｜ h( T
total×1.03 ) － h( T
total) ｜≦ １
h( T
total)
T
total2
1 3 4 6 5
T
totalDepartment of Computer Science, Graduate School of Information Science & Technology, Osaka University 88
ハッシュ関数を用いた解決法
ハッシュ関数 h( T
total) を用いた加工
｜ h( T
total) － h( T
total×0.97 ) ｜≦ １
｜ h( T
total×1.03 ) － h( T
total) ｜≦ １
h( T
total)
T
total2
1 3 4 6 5
T
total×0.97 T
total×1.03
Department of Computer Science, Graduate School of Information Science & Technology, Osaka University 89
ハッシュ関数を用いた解決法
ハッシュ関数 h( T
total) を用いた加工
｜ h( T
total) － h( T
total×0.97 ) ｜≦ １
｜ h( T
total×1.03 ) － h( T
total) ｜≦ １
h( T
total)
T
total2
1 3 4 6 5
T
totalDepartment of Computer Science, Graduate School of Information Science & Technology, Osaka University 90
ハッシュ関数を用いた解決法
ハッシュ関数 h( T
total) を用いた加工
｜ h( T
total) － h( T
total×0.97 ) ｜≦ １
｜ h( T
total×1.03 ) － h( T
total) ｜≦ １
h( T
total)
T
total2
1 3 4 6 5
T
total×0.97 T
total×1.03
Department of Computer Science, Graduate School of Information Science & Technology, Osaka University 91
ハッシュ関数を用いた解決法
ハッシュ関数 h( T
total) を用いた加工
｜ h( T
total) － h( T
total×0.97 ) ｜≦ １
｜ h( T
total×1.03 ) － h( T
total) ｜≦ １
h( T
total)
T
total2
1 3 4 6 5
h( T
total)
は，閾値1
の主メトリクスとして機能するDepartment of Computer Science, Graduate School of Information Science & Technology, Osaka University 92
実験結果
主メトリク
ス 類似クラス
タ 最終クラス
タ 計算コスト
(sec)
未使用
1 278 05.02
[ C ] 21 278 00.56
[ C,M ] 85 278 00.29
[ C,M,T ] 232 278 00.16
C
：サイクロマチック数M
：宣言メソッド数T : f( T
total)
対象 ：
JDK1.3
431
クラス 文字列比較を用いた類似度測定ツールの計算コスト：24.35
（sec
）DB [ 0. 0. 0]= null
[ 10. 62.124]=
部品A [ 10. 62.125]=
部品B
，部品C
[ 10. 62.126]= null
[255.255.255]=
部品Z
・・
・
・・
・
SPARS-J の類似度測定部「 Luigi 」として実装
Department of Computer Science, Graduate School of Information Science & Technology, Osaka University 93
実験結果
主メトリク
ス 類似クラス
タ 最終クラス
タ 計算コスト
(sec)
未使用
1 278 05.02
[ C ] 21 278 00.56
[ C,M ] 85 278 00.29
[ C,M,T ] 232 278 00.16
C
：サイクロマチック数M
：宣言メソッド数T : f( T
total)
文字列比較を用いた類似度測定ツールの計算コスト：
24.35
（sec
）トークン構成度
+
複雑度の両方で類似と判定 され、最終的に類似と判定された部品群の数SPARS-J の類似度測定部「 Luigi 」として実装
対象 ：
JDK1.3
431
クラスDepartment of Computer Science, Graduate School of Information Science & Technology, Osaka University 94
実験結果
主メトリク
ス 類似クラス
タ 最終クラス
タ 計算コスト
(sec)
未使用
1 278 05.02
[ C ] 21 278 00.56
[ C,M ] 85 278 00.29
[ C,M,T ] 232 278 00.16
C
：サイクロマチック数M
：宣言メソッド数T : f( T
total)
文字列比較を用いた類似度測定ツールの計算コスト：
24.35
（sec
）類似度の測定精度を落とすことなく 効率だけが上がっている
SPARS-J の類似度測定部「 Luigi 」として実装
対象 ：
JDK1.3
431
クラスDepartment of Computer Science, Graduate School of Information Science & Technology, Osaka University 95
実験結果
主メトリク
ス 類似クラス
タ 最終クラス
タ 計算コスト
(sec)
未使用
1 278 05.02
[ C ] 21 278 00.56
[ C,M ] 85 278 00.29
[ C,M,T ] 232 278 00.16
C
：サイクロマチック数M
：宣言メソッド数T : f( T
total)
文字列比較を用いた類似度測定ツールの計算コスト：
24.35
（sec
）
メトリクス比較により，コストは1/5
SPARS-J の類似度測定部「 Luigi 」として実装
対象 ：
JDK1.3
431
クラスDepartment of Computer Science, Graduate School of Information Science & Technology, Osaka University 96
実験結果
主メトリク
ス 類似クラス
タ 最終クラス
タ 計算コスト
(sec)
未使用
1 278 05.02
[ C ] 21 278 00.56
[ C,M ] 85 278 00.29
[ C,M,T ] 232 278 00.16
C
：サイクロマチック数M
：宣言メソッド数T : f( T
total)
文字列比較を用いた類似度測定ツールの計算コスト：
24.35
（sec
）
メトリクス比較により，コストは1/5
ハッシュキーにより，コストは1/30
SPARS-J の類似度測定部「 Luigi 」として実装
対象 ：
JDK1.3
431
クラスDepartment of Computer Science, Graduate School of Information Science & Technology, Osaka University 97
SPARS-J （ 2/2 ）
Component Rank の計算では，部品間のコピー関係を把握す るために類似度を測定している
類似部品を一つの部品群として扱い，利用関係を合成する
評価値にコピー関係を反映させることが可能
部品
A + 部品 A´
部品部品群A A
これまでは，ソースコードの文字列比較を行う事で，類似部品を判定していた
類似
合成
⇒
Department of Computer Science, Graduate School of Information Science & Technology, Osaka University 98
T total をハッシュキーに適応するときの問
題点
類似判定の条件
diff( A,B )
min(T
total（ A ） , T
total（ B ）
＜) 0.03
トークンの差分が
T
total の3 ％
以内DB [ 0. 0. 0]= null
[ 10. 62. 29]=
部品A [ 10. 62. 30]=
部品B
，部 品C
[ 10. 62. 31]= null
[255.255.255]=
部品Z
・・
・
T
total=30
⇒DB
[ 0. 0. 0]= null
[ 10. 62.145]=
部品A [ 10. 62.146]= null
[ 10. 62.147]= null [ 10. 62.148]=
部品B [ 10. 62.149]=
部品C
[ 10. 62.150]=
部品D
，部品E [ 10. 62.151]= null
[ 10. 62.152]=
部品F [ 10. 62.153]= null [ 10. 62.154]=
部品G
[ 10. 62.155]=
部品H,
部品I [255.255.255]=
部品Z
・・
・
・・
・
T
total=150
⇒145
～155
29
～31
・・
・
Department of Computer Science, Graduate School of Information Science & Technology, Osaka University 99