類似度メトリクスを用いた Javaソースコード間類似度測定ツールの試作

Presentation on theme: "類似度メトリクスを用いた Javaソースコード間類似度測定ツールの試作"— Presentation transcript:

1 類似度メトリクスを用いた Javaソースコード間類似度測定ツールの試作
小堀一雄，山本哲男，松下誠，井上克郎（大阪大学）

2 背景（1/2） ソフトウェア開発効率を飛躍的に向上するための手法として 再利用が注目されている
再利用とは新規のソースコードを書く際に，既存のソースコードを参照し，一部手直しをして用いること 再利用を活用するためには，過去に開発されたソースコードに関する情報を入手することが必要

3 背景(2/2） インターネットの普及により大量のソースコードが 比較的容易に入手可能となった これらのソースコードは，開発者にとって
有益な再利用部品である可能性がある

4 SPARS-J（1/2） SPARS-J 利用実績に基づくソフトウェア部品検索システム システムの特徴 対象：Javaプログラムソースコード
（Software Product Archiving, analyzing ,and Retrieving System for Java） システムの特徴 対象：Javaプログラムソースコード 利用実績に基づいた評価値(Component Rank*)を計算し，　ランク付けを行う事で，利用実績の高い部品をユーザに提供可能 * Katsuro Inoue, Reishi Yokomori, Hikaru Fujiwara, Tetsuo Yamamoto, Makoto Matsushita, Shinji Kusumoto: "Component Rank: Relative Significance Rank for Software Component Search", to be appeared in Proceedings of 25th International Conference on Software Engineering (ICSE 2003), Portland, Oregon, 2003.

5 これまでは，ソースコードの文字列比較を行う事で，類似部品を判定していた
SPARS-J（2/2） Component Rankの計算では，部品間のコピー関係を把握するために類似度を測定している 類似部品を一つの部品群として扱い，利用関係を合成する 評価値にコピー関係を反映させることが可能 B D B D 類似 合成 + 部品A 部品A´ 部品群A C E F C E F これまでは，ソースコードの文字列比較を行う事で，類似部品を判定していた

6 既存の手法の問題点 文字列比較を用いた類似度測定手法の問題点 類似度測定の一回当たりの計算コストが高い
類似度測定の回数が膨大（毎回、全部品総当り） JDK430クラスの類似分類に23秒程度かかる SPARS-Jのような大量の部品を扱うシステムにおける類似度測定には不向き もっと低コストな類似度測定手法が必要

7 研究の目的 メトリクスを用いた類似度測定手法の提案 提案手法を実装したツールの試作 類似度メトリクス：類似判定の定量的な基準（数値）
ソースコードの静的特性をメトリクスとして抽出 メトリクスを用いた類似比較を実現 提案手法を実装したツールの試作 JDKのJavaソースコードに対し適用実験を行う 解析精度，コストの評価を行う

8 提案手法の特徴 比較一回当たりのコストの低下 比較回数の低下 ソースコードの静的特性をメトリクスして抽出する
メトリクスの比較のみを用いて類似判定を行う 文字列比較より数値比較の方が低コスト 比較回数の低下 明らかに「類似でない」ものは比較対象から排除する 事前に主要なメトリクスによる分類を施す 事前排除した部品は類似であってはならない

9 比較一回あたりのコストを下げる手法 2つの視点から類似度メトリクスを計測する 複雑度 トークン構成
類似度メトリクス：類似判定の定量的基準（数値） 2つの視点から類似度メトリクスを計測する 複雑度 メトリクス：クラス内のメソッド数, サイクロマチック数（分岐数）etc ソフトウェア部品の構造的特徴を表す トークン構成 メトリクス： ソースコードにおける各トークンの出現数 トークン ＝ 予約語 + 記号 + 演算子 + 識別子 （96種） （49種） （9種） （37種） （１種） ソフトウェア部品の表層的特徴を表す

10 メトリクス抽出の流れ 複雑性 値 interfaceの数 2 トークン 値 サイクロマチック数 メソッド宣言数
public class sample{ int a,b,s; char c; public void main( ){ c = ‘m’; if(c = = ‘m’){ s = sum(a, b); } else{ s = a + b; public void sum(int p, int q){ return( p + q ); 2 ・・・ トークン 値 int void identifer Ttotal ・・・

11 メトリクス抽出の流れ 複雑性 値 interfaceの数 2 複雑性 メトリクス 2 トークン 値 サイクロマチック数 メソッド宣言数
public class sample{ int a,b,s; char c; public void main( ){ c = ‘m’; if(c = = ‘m’){ s = sum(a, b); } else{ s = a + b; public void sum(int p, int q){ return( p + q ); 2 複雑性 メトリクス ・・・ 2 ・・・ トークン 値 int void identifer Ttotal ・・・

12 メトリクス抽出の流れ 複雑性 値 interfaceの数 2 2 トークン 値 3 サイクロマチック数 メソッド宣言数
public class sample{ int a,b,s; char c; public void main( ){ c = ‘m’; if(c = = ‘m’){ s = sum(a, b); } else{ s = a + b; public void sum(int p, int q){ return( p + q ); 2 ・・・ 2 ・・・ トークン 値 int void identifer Ttotal 3 ・・・

13 メトリクス抽出の流れ 複雑性 値 interfaceの数 2 2 トークン 値 3 2 サイクロマチック数 メソッド宣言数
public class sample{ int a,b,s; char c; public void main( ){ c = ‘m’; if(c = = ‘m’){ s = sum(a, b); } else{ s = a + b; public void sum(int p, int q){ return( p + q ); 2 ・・・ 2 ・・・ トークン 値 int void identifer Ttotal 3 2 ・・・

14 メトリクス抽出の流れ 複雑性 値 interfaceの数 2 2 トークン 値 3 2 トークン構成 メトリクス 23 75
サイクロマチック数 メソッド宣言数 interfaceの数 public class sample{ int a,b,s; char c; public void main( ){ c = ‘m’; if(c = = ‘m’){ s = sum(a, b); } else{ s = a + b; public void sum(int p, int q){ return( p + q ); 2 ・・・ 2 ・・・ トークン 値 int void identifer Ttotal 3 2 トークン構成 メトリクス ・・・ ・・・ 23 75

15 類似度判定法（複雑性メトリクス） 各メトリクスの差分が対応する閾値以内に全て収まったら類似 メトリクス名 閾値 サイクロマチック数
メソッドの宣言数 1 メソッド呼び出し数 2 ネストの深さ classの数 interfaceの数

16 類似度判定法（トークン構成メトリクス） ∑ diff(A,B) ( ) Amk Bmk 部品A,Bの各トークンの差分の和 ＝ ＝ トークン
値 int void identifer Ttotal トークン 値 int void identifer Ttotal 3 m１ 4 2 m２ 2 ・・・ ・・・ 23 ・・・ ・・・ ・・・ 25 m96 75 76 部品A 部品B 96 ∑ diff(A,B) ( Amk Bmk ) 部品A,Bの各トークンの差分の和 ＝ ＝ k=1

17 類似度判定法（トークン構成メトリクス） D(A,B) ＜ 0.03 diff(A,B) min(Ttotal（A）, Ttotal（B）)
値 int void identifer Ttotal トークン 値 int void identifer Ttotal 3 m１ 4 2 m２ 2 ・・・ ・・・ 23 ・・・ ・・・ ・・・ 25 m96 75 76 部品A 部品B ■部品Aと部品Bの非類似度を D(A,B) とする diff(A,B) D(A,B) ＜ 0.03 min(Ttotal（A）, Ttotal（B）)

18 類似度判定法（総合） どちらの類似度においても，類似であると判定されなくてはならない and 部品A，Bは類似部品
この判定法は数値比較しか用いていない 比較一回当たりのコストを下げることが可能

19 提案手法の特徴 比較一回当たりのコストの低下 比較回数の低下 ソースコードの静的特性をパラメータ化して抽象化する
パラメータの比較のみを用いて類似判定を行う 文字列比較より数値比較の方が低コスト 比較回数の低下 明らかに「類似でない」ものは比較対象から排除する 事前に主要なパラメータによる分類を施す 事前排除した部品は類似であってはならない

20 比較回数を減らす手法 いくつかの主メトリクス値のハッシュキーを部品に持たせる ハッシュキーの値の差が主メトリクスの閾値を超える部品
主メトリクス：類似判定の必要条件となるメトリクス ハッシュキーの値の差が主メトリクスの閾値を超える部品 ＝明らかに｢類似でない｣部品 これらを比較対象から排除することにより，比較回数を減らすことが可能となる

21 ハッシュによる事前分類 DB メトリクス計測時に、いくつかの主メトリクスでハッシュキーを作成する 新しく類似測定をしたい部品Pが入ってきた時
主メトリクス[A,B,C]の閾値＝[0.0.1] ハッシュキー (24bit) ＝ 8bit 8bit 8bit 主メトリクスA 主メトリクス B 主メトリクス C [ ] [ ]　この３つのキーをひく [ ] ハッシュキーと部品を対応させたハッシュテーブルを構築する 類似比較の対象となるのは部品A，B，Cの3つに絞り込める [ ]= null [ ]= 部品A [ ]= 部品B，部品C [ ]= null [ ]= 部品Z ・ ・ ・ DB 解析精度を落とさずに 比較回数を減らす ・ ・ ・

22 主メトリクスの候補 主メトリクス：類似判定の必要条件，閾値を持つ 主メトリクスとして，複雑性メトリクスしか採用しない場合
複雑性メトリクス：各々のメトリクスが閾値を持った類似判定の必要条件 　　　　　　　　　　　そのまま主メトリクスとして適用可能 トークン構成メトリクス：各々のメトリクスは類似判定の必要条件ではなく， 　　　　　　　　　　　　　　 非類似度を算出する要素に過ぎない 主メトリクスとして，複雑性メトリクスしか採用しない場合 単純な構造の部品が同じ分類に入り、大きく偏る

23 主メトリクスの候補 トークン構成メトリクスに関する類似判定の条件 ⇔ diff(A,B) トークン構成の差分が Ttotalの3％未満
＜ 0.03 min(Ttotal（A）, Ttotal（B）) 部品A 部品B Ttotal（B） Ttotal（A） この部分が全てdiffになる ⇔ Ttotalの差が3％以上の部品は 比較対象から排除できる

24 主メトリクスの候補 トークン構成メトリクスに関する類似判定の条件 ⇔ diff(A,B) トークン構成の差分が Ttotalの3％未満
＜ 0.03 min(Ttotal（A）, Ttotal（B）) 部品A 部品B Ttotal（B） Ttotal（A） この部分が全てdiffになる ⇔ Ttotalの差が3％以上の部品は 比較対象から排除できる Ttotalは閾値３％の主メトリクス

25 比較回数を減らす手法 複雑性メトリクス+トークン構成メトリクスの両面から主メトリクスを
採用することにより効率的に事前分類することが可能となった 主メトリクス値の閾値以内の全キーを引き，部品を絞り込む 比較回数を低下させることが可能 閾値が大きいと，キーを引く回数（DBアクセス回数）が増加する

26 DBアクセスに関するコスト問題 DBアクセス回数は閾値に比例して増加する DB DB 主メトリクスの閾値 ＝ [0.0.1]
主メトリクスの閾値 ＝ [0.0.5] DB [ ]= null [ ]= 部品H [ ]= null [ ]= null [ ]= 部品A [ ]= 部品B [ ]= 部品C，部品D [ ]= null [ ]= 部品E [ ]= null [ ]= null [ ]= 部品F,部品G [ ]= 部品Z ・ DB [ ]= null [ ]= 部品A [ ]= 部品B，部品C [ ]= null [ ]= 部品Z ・ DBアクセス回数 ＝ （閾値A×２ +１）×（閾値B×２ +１）×（閾値C×２ +１）

27 マッピングによる解決法 主メトリクス値をマッピングして閾値を1にする DB 主メトリクス値 ＝ 主メトリクス値 / 閾値 閾値＝5
[ ]= null [ ]= 部品H [ ]= null [ ]= null [ ]= 部品A [ ]= 部品B [ ]= 部品C，部品D [ ]= null [ ]= 部品E [ ]= null [ ]= null [ ]= 部品F,部品G [ ]= 部品Z ・ DB [ ]= null [ ]= 部品H,A,B [ ]= 部品C,D,E [ ]= 部品F,G [ ]= 部品Y,Z ・ 閾値＝5

28 マッピングによる解決法 主メトリクス値をマッピングして閾値を1にする DB 主メトリクス値 ＝ 主メトリクス値 / 閾値 閾値＝5
[ ]= null [ ]= 部品H [ ]= null [ ]= null [ ]= 部品A [ ]= 部品B [ ]= 部品C，部品D [ ]= null [ ]= 部品E [ ]= null [ ]= null [ ]= 部品F,部品G [ ]= 部品Z ・ DB [ ]= null [ ]= 部品H,A,B [ ]= 部品C,D,E [ ]= 部品F,G [ ]= 部品Y,Z ・ 閾値＝5

29 マッピングによる解決法 主メトリクス値をマッピングして閾値を1にする DB 主メトリクス値 ＝ 主メトリクス値 / 閾値 閾値＝5 閾値＝１
[ ]= null [ ]= 部品H [ ]= null [ ]= null [ ]= 部品A [ ]= 部品B [ ]= 部品C，部品D [ ]= null [ ]= 部品E [ ]= null [ ]= null [ ]= 部品F,部品G [ ]= 部品Z ・ DB [ ]= null [ ]= 部品H,A,B [ ]= 部品C,D,E [ ]= 部品F,G [ ]= 部品Y,Z ・ 閾値＝5 閾値＝１

30 閾値とDBアクセス回数 閾値が３％の場合（トークン構成メトリクス） Ttotal = 40 ⇒ 39～41 Ttotal =180 ⇒
175～185 DB [ ]= null [ ]= 部品A [ ]= null [ ]= null [ ]= 部品B [ ]= 部品C [ ]= 部品D，部品E [ ]= null [ ]= 部品F [ ]= null [ ]= 部品G [ ]= 部品H,部品I [ ]= 部品Z ・ DB [ ]= null [ ]= 部品A [ ]= 部品B，部品C [ ]= null [ ]= 部品Z ・ 閾値 ＝ １ 閾値 ＝ 5

31 h(Ttotal)は，閾値1の主メトリクスとして機能する
マッピングによる解決法 マッピング関数 h(Ttotal) =　logｒ（Ttotal） (r＝1 / 0.97) h(Ttotal)は，閾値1の主メトリクスとして機能する h(Ttotal) 6 5 4 3 2 1 Ttotal

32 実験結果 文字列比較を用いた類似度測定ツールの計算コスト：24.35（sec） DB SPARS-Jの類似度測定部「Luigi」として実装
対象 ： JDK431クラス 文字列比較を用いた類似度測定ツールの計算コスト：24.35（sec） 主メトリクス 類似クラスタ 最終クラスタ 計算コスト(sec) 未使用 1 278 05.02 [ C ] 21 00.56 [ C,M ] 85 00.29 [ C,M,T ] 232 00.16 DB [ ]= null [ ]= 部品A [ ]= 部品B，部品C [ ]= null [ ]= 部品Z ・ C：サイクロマチック数 M：宣言メソッド数 T : 全トークン数

33 SPARS-Jの類似度測定部「Luigi」として実装
実験結果 SPARS-Jの類似度測定部「Luigi」として実装 対象 ： JDK431クラス 文字列比較を用いた類似度測定ツールの計算コスト：24.35（sec） 主メトリクス 類似クラスタ 最終クラスタ 計算コスト(sec) 未使用 1 278 05.02 [ C ] 21 00.56 [ C,M ] 85 00.29 [ C,M,T ] 232 00.16 C：サイクロマチック数 M：宣言メソッド数 T :全トークン数 トークン構成度+複雑度の両方で類似と判定され、最終的に類似と判定された部品群の数

34 SPARS-Jの類似度測定部「Luigi」として実装
実験結果 SPARS-Jの類似度測定部「Luigi」として実装 対象 ： JDK431クラス 文字列比較を用いた類似度測定ツールの計算コスト：24.35（sec） 主メトリクス 類似クラスタ 最終クラスタ 計算コスト(sec) 未使用 1 278 05.02 [ C ] 21 00.56 [ C,M ] 85 00.29 [ C,M,T ] 232 00.16 C：サイクロマチック数 M：宣言メソッド数 T :全トークン数 類似度の測定精度を落とすことなく 効率だけが上がっている

35 SPARS-Jの類似度測定部「Luigi」として実装
実験結果 SPARS-Jの類似度測定部「Luigi」として実装 対象 ： JDK431クラス 文字列比較を用いた類似度測定ツールの計算コスト：24.35（sec） メトリクス比較により，コストは1/5 主メトリクス 類似クラスタ 最終クラスタ 計算コスト(sec) 未使用 1 278 05.02 [ C ] 21 00.56 [ C,M ] 85 00.29 [ C,M,T ] 232 00.16 C：サイクロマチック数 M：宣言メソッド数 T :全トークン数

36 SPARS-Jの類似度測定部「Luigi」として実装
実験結果 SPARS-Jの類似度測定部「Luigi」として実装 対象 ： JDK431クラス 文字列比較を用いた類似度測定ツールの計算コスト：24.35（sec） 主メトリクス 類似クラスタ 最終クラスタ 計算コスト(sec) 未使用 1 278 05.02 [ C ] 21 00.56 [ C,M ] 85 00.29 [ C,M,T ] 232 00.16 ハッシュキーにより，コストは1/30 メトリクス比較により，コストは1/5 C：サイクロマチック数 M：宣言メソッド数 T :全トークン数

37 SPARS-Jの類似度測定部「Luigi」として実装
実験結果 SPARS-Jの類似度測定部「Luigi」として実装 対象 ： JDK431クラス 文字列比較を用いた類似度測定ツールの計算コスト：24.35（sec） トータルでコストは1/150 主メトリクス 類似クラスタ 最終クラスタ 計算コスト(sec) 未使用 1 278 05.02 [ C ] 21 00.56 [ C,M ] 85 00.29 [ C,M,T ] 232 00.16 メトリクス比較により，コストは1/5 C：サイクロマチック数 M：宣言メソッド数 T :全トークン数 ハッシュキーにより，コストは1/30

38 実験結果（スケーラビリティ） 主メトリクスとして [C,M,T] を用いた場合の実験結果

39 まとめと今後の課題 まとめ 今後の課題 メトリクスを用いた類似度測定手法を提案した
比較一回当たりの低コスト化 ハッシュキーを用いることによる類似度測定回数の効率化 SPARS-Jにおける類似度測定部「Luigi」として実装し，適用実験を行い，有効性を検証した 既存の文字列比較による類似度測定手法に比べ，十分低コストかつ効率的な手法であることを確認した 今後の課題 類似度判定精度の向上 Java以外の言語への対応