一般社団法人 電子情報通信学会
THE INSTITUTE OF ELECTRONICS,
社団法人 電子情報通信学会
INFORMATIONAND COMMUNICATION ENGINEERS

信学技報
IEICE Technical Report
信学技報
SS2021-1,KBSE2021-13(2021-07)

THE INSTITUTE OF ELECTRONICS,
INFORMATION AND COMMUNICATION ENGINEERSTECHNICAL REPORT OF IEICE.

抽象構文木を用いた差分検出手法の活用による
Git のファイル追跡機能改善の試み
藤本 章良†

肥後 芳樹†

楠本 真二†† 大阪大学大学院情報科学研究科〒 565-0871 大阪府吹田市山田丘 1-5
E-mail: †{a-fujimt,higo,kusumoto}@ist.osaka-u.ac.jp
あらましソフトウェア開発においては，バージョン管理システムが頻繁に利用されている．バージョン管理システムの一つである Git は，変更の履歴を個別のファイルごとに辿ることができ，ファイル名が変更された場合でもファイル内
容の類似度をもとに変更前のファイルを特定し，追跡を行うことが可能である．ファイル内容の類似度は，全行数のうち変更が行われた行数の割合で計算される．しかし，行単位による比較はソースコードの構造的特徴を考慮しておらず，粒度も粗いため，変更前のファイルの特定を誤ったり追跡が途切れたりする可能性がある．提案手法では，これらの問題の改善に向けて抽象構文木を利用した差分検出手法を利用し類似度を算出する．197 個のオープンソースプロジェクトに対して実験を行った結果，ファイル名変更の検出数が 3.3%増加し，行単位の比較による手法と出力が異なるファイルの変更履歴について平均で 1.37 倍追跡できるコミット数が増加した．また，精度を調査したところ F 値が最大で 0.943となり，既存手法の最大値である 0.926 を上回った．
キーワード

Git，ファイル追跡，抽象構文木

ルを行単位で比較する場合，ソースコードの構造的特徴は考慮

1. ま え が きされておらず比較の粒度も粗い．そのため，変更前のファイル

ソフトウェア開発においては，バージョン管理システムが頻の特定を誤ったり追跡が途切れてしまったりする可能性がある．

繁に利用されている [1]．バージョン管理システムを利用するこ

例えばファイル名の変更に伴い，クラス名やメソッド名，変数名とで，過去のバージョンとして記録された状態に戻す，バージョが変更されただけの場合であっても行全体の変更とみなし，そのン間の差分を確認する，複数の開発者で並行して開発を進めると

結果類似度が低下し追跡が途切れるおそれがある．

いった行為が容易に実現できる．さらに蓄積された変更履歴は，そこで本研究では，Git のファイル追跡機能の改善のために，開発者がソフトウェアの振る舞いや変更目的を理解するために

抽象構文木を利用した差分検出手法を用いて類似度を算出する

役立つ [2]．加えて，研究分野での利用もなされており，バグを手法を提案する．抽象構文木はソースコードの構造そのものを含むモジュールの予測 [3] や変更パターンの検出 [4] といった研表現しており，これらの差分から類似度を算出することでファイ究が広く行われている．

ルの追跡を改善できると著者らは考えた．

バージョン管理システムの一つである Git は，リポジトリ全体

提案手法の有用性を評価するために，197 個のオープンソースの変更履歴の他に個別のファイルに対して行われた変更履歴だ

プロジェクトに対して複数の実験を行った．まず，ファイル名変けを抽出して出力可能である．特定のファイルについての変更

更の検出数を調査したところ，提案手法はファイル名の変更を

履歴を出力するために，ファイル名を利用して対象のファイルが3.3%多く検出した．次に，目視で精度を確認したところ，行単変更されたコミットを特定し履歴を出力する．ファイル名が変位の比較により類似度を算出する手法（以下，既存手法）と比べ更された場合でも変更前のファイルを特定し，それ以前の履歴は再現率が大きく上回った．F 値も既存手法よりも高くなり，閾

変更前のファイル名で追跡する．ファイル名が変更された場合，値を 40%に設定した時 0.943 で最大となり既存手法の最大値で変更前のファイルを特定するためにファイル内容の比較を行う．

ある 0.926 を上回った．また，出力される履歴の長さを調査し，変更前にのみ存在するファイルの中から 1 つファイルを選択し，既存手法と出力が異なるファイルのみに注目したところ，出力さ追跡中のファイルと比較する．2 つのファイル間で一致する行数

れる変更履歴のコミット数が 1.55 倍に増加した．最後に，実行の割合を類似度として算出し，類似度が一定の閾値を超えていれ

時間を比較すると提案手法は実行時間が 1.71 倍増加した．実行ばファイル名の変更が行われたとみなす．

時間短縮のためにヒューリスティックを適用すると，実行時間と追跡精度の間にトレードオフが存在するという結果が得られた．

しかし，類似度の算出方法には課題が存在する．2 つのファイ

-1-

—1—
This article is a technical report without peer review, and its polished and/or extended version may be published elsewhere.
Copyright ©2021 by IEICE

A1

変更前のファイル

変更後のファイル

0

0

追跡中の
ファイル

80%

65% 50%

各ファイル間で行単位の類似度を計算
マッチング

削除された
ファイル

1
D1

D2

D3
• 閾値以上• 最も類似度が高い

3

2 “Gum”
4

4

変更前のAST
D1を追跡

削除

2. 準

挿入

“Gum”

移動

ノードの値
更新

ノードはメソッド名や変数名を値として保持する．

2. 3 GumTree [6]2. 1 Git のファイル追跡

GumTree は，AST の差分を検出するツールである．GumTree

Git では––follow オプションを用いることで，特定のファイは変更前後のソースファイルを入力として受け取り，それぞれにルを追跡して変更履歴を表示することができ，ファイル名が変更対応する AST を生成する．2 つの AST の違いを AST のノーされても追跡可能である．追跡しているファイルのファイル名

ド単位の編集スクリプトとして出力する．編集スクリプトとは，が変更された場合，変更前のファイルを特定し，それ以前のコ

変更後の AST を得るために変更前の AST に適用された編集操

ミットに対しては変更前のファイル名で追跡を行う．ファイル

作の列である．GumTree が出力する編集スクリプトは，挿入・名が変更されたコミットにおける Git のファイル追跡のプロセ

削除・移動・更新の 4 つの操作から構成される．

スを図 1 に示す．Git では，それぞれのコミットについて削除さ

図 2 に GumTree の動作を示す．木構造の差分を計算するた

れたファイルと追加されたファイル，内容が変更されたファイル

めに変更前後のファイルから生成した AST に対してマッチングの情報を記録している．ファイル名の変更を検出するために，追を行う．マッチングとは変更前後における AST のノード間に対跡中のファイルとそのコミットで削除されたファイル間で，ファ

応づけを行う処理である．マッチングされたノードは，変更のイル内容の類似度を計算する．閾値を超えたファイルの組み合

前後で同じノードとして扱われる．マッチングの結果と AST をわせをファイル名の変更が行われたファイルの組とみなす．閾

参照し，Chawathe らのアルゴリズム [7] を用いて変更前の AST値を超えたファイルの組が複数存在する場合，最も類似度が高いに対して操作が行われたノードを得る．この例では，3 番のノー組をファイル名の変更が行われたファイルの組とみなす．

ドは変更前にのみ存在するため削除，5 番のノードは変更後にのある 2 つのファイルの類似度 S は，2 つのファイル内容を行み存在するため挿入，4 番のノードは親のノードが変化したため単位で比較し，以下の式で算出される．length(f ) は，ファイル移動と出力される．また，2 番のノードは変更前後の両方に存在

f の行数であり，common(f1 , f2 ) は一致する行数である．
common(f1 , f2 )× 100
max(length(f1 ), length(f2 ))5

図 2 GumTree の差分検出

備

S(f1 , f2 ) =“Tree”

変更後のASTn ASTノード

図 1 Git におけるファイル名の変更検出

2

1

し親も変わらないが，値が変化したため更新と出力される．

3. 研 究 動 機(1)

図 3 は ，AndroidBootStrap プ ロ ジ ェ ク ト で 発 生 し た

行単位の差分を検出するために，Myers [5] や Histgram，ハッDimenUtils.java についての変更を示している．この変更で

シュを用いたアルゴリズムが利用される．

2. 2 抽象構文木

は，プロジェクト構造の変化によりパス名が変更されている．同

抽象構文木（以下，AST）は，ソースコードを構文解析して得時にメソッドの追加と Javadoc の追加も行われているが，変更られる木構造のデータである．1 つのソースファイルから 1 つのの前後では同一のファイルと考えられる．しかし，この 2 つのAST が生成される．AST のエッジは，その両端のノードに直接ファイルの類似度を 2. 1 節 (1) 式に基づいて計算すると，25%の親子関係があることを示す．AST の各ノードは以下の 5 つのとなる．Git における類似度の閾値のデフォルト値は 50%であ要素から構成される．

り，これらのファイルは同一でないファイルとして扱われるた

ID 各 AST 内で固有の識別子

め，この変更以前の履歴を追跡することが不可能となる．

親ノード

同一のファイルであるにもかかわらず類似度が低下する原因

AST の各ノードは，親ノードへの参照を持つ．ただは，行単位による比較ではソースコードの構造を考慮できていな

し，根ノードの親は存在しないので何も保持しない．
子ノード

いからである．例えば 1 行目を比較すると，パッケージ名の一

AST の各ノードは，子ノードへの参照を持つ．ただ部のみが変更されているが，パッケージ文全体が削除・挿入されし，葉ノードの子は存在しないので何も保持しない．

if 文や変数宣言といった文法上の型を表す．

たとして類似度が計算される．同様に削除行 6 行目と挿入行 16

値 各ノードが持つラベル以外の情報である．例えば，識別子の行目を比較するとメソッド名のみが変更されているが，行全体の

ラベル

-2-

—2—

(

ebfb0d4753392ad00a5866e368cd0357aec12947 api tidy up- .../src/main/java/com/beardedhen/androidbootstrap/support/DimenUtils.java+ .../src/main/java/com/beardedhen/androidbootstrap/utils/DimenUtils.java
1
2
3
4

5
6

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

7 17
8 18
9 19
20
21
22
23
24
25
26
27
28
29
30
31
10 32

S(t1 , t2 ) =- package com.beardedhen.androidbootstrap.support;+ package com.beardedhen.androidbootstrap.utils;
import android.content.Context;
import android.content.res.Resources;
import android.support.annotation.DimenRes;+ /**+ * Utils class for resolving color resource values.
+ */public class DimenUtils {public static float textSizeFromDimenResource(Context context,@DimenRes int sizeRes) {+/**+* Resolves a dimension resource that uses scaled pixels+*+* @param context the current context+* @param sizeRes the dimension resource holding an SP value+* @return the text size in pixels+*/+
public static float pixelsFromSpResource(Context context,@DimenRes int sizeRes) {final Resources res = context.getResources();return res.getDimension(sizeRes) / res.getDisplayMetrics().density;
}
+
/**
+
* Resolves a dimension resource that uses density-independent pixels+*+* @param context the current context+* @param res
the dimension resource holding a DP value+* @return the size in pixels+*/+
public static float pixelsFromDpResource(Context context,@DimenRes int res) {+return context.getResources().getDimension(res);
+
}
+
+
}

GumTree)× 100 (2)

変更前後のファイルの内容が類似しているほど，編集スクリ
プトが短くなるため，類似度が高くなる．この類似度が閾値を超えたファイルを，ファイル名が変更されたファイルとし追跡を行う．
図 3 の例に対し提案手法を用いて類似度を算出する．変更前
後のファイルから生成した AST のノード数はそれぞれ 53 と 103
であり，GumTree の出力する編集スクリプトの長さは 52 である．(2) 式を用いて計算した結果，類似度は 66.7%となりファイル名が変更されたとみなし，追跡を続ける．
編集スクリプトの操作に重みはなく，どの操作が行われても長さは 1 だけ加算される．GumTree の出力する編集スクリプトに含まれる操作のうち，挿入と削除は操作対象が単一の AST ノードであるのに対し，移動は操作対象が AST の部分木である．あるソースコードが挿入または削除された場合，その各ノードに対

図 3 類似度が低く追跡が途切れる変更
入力

length(editScript(t1 , t2 ))1−
treeSize(t1 ) + treeSize(t2 )して操作が行われたと扱われ，編集スクリプトの長さはノードの数になる．一方で，移動は部分木に対しての操作であるため編集

出力

スクリプトの長さは 1 である．従って，挿入と削除は移動より

変更前の
ファイル
差分
計算
変更後の
ファイル

も編集スクリプトが長くなる．ソースコードの削除・挿入よりも類似度計算

移動の方が機能差が小さいと考えられるため，移動が発生した時65%の類似度が高くなるよう，GumTree 出力した編集スクリプトに編集スクリプト

操作ごとに重みをつけずそのまま利用する．
AST

なお比較対象のファイル少なくとも一方が，テキストファイ
ルのように AST を生成できないファイルである場合や，文法的図 4 提案手法の概要

エラーにより AST の生成に失敗する場合，既存の行単位による比較から類似度を算出する．

削除と挿入となりこのメソッド全体の 25%が変更されたこととなる．また Javadoc はプログラムの機能を変化させないが，こ5. 評 価 実 験の例では挿入された 24 行のうち Javadoc が 17 行を占めており提案手法の評価のために，Git の Java 実装である JGit（注 1）の類似度を低下させる大きな要因となっている．
そこで，ソースコードの構造を考慮した上で類似度の計算を

一部を改変し，提案手法を実装し実験を行った．GumTree は行うことで，追跡の精度が向上するのではないかと著者らは考えJava で実装されており API も公開されているため，JGit に組た．ソースコードの構造を考慮するため，AST を利用した類似み込むのが容易だったからである．この評価実験では度の計算手法を提案する．AST の利用により，行単位による比•

ファイル名変更の検出数

較よりも粒度を細かくすることができ，Javadoc やコメントのよ•追跡可能な変更履歴の長さ

うな類似度を計算する上でノイズとなりうる成分の割合を削減

•

追跡精度

することができる．

•

実行時間の 4 つの項目について，既存手法と提案手法をそれぞれ適用し4. 提 案 手 法

た JGit を用いて比較を行った．

5. 1 実 験 対 象

提案手法では，Git のファイル追跡プロセスのうち変更前後
におけるファイルの類似度の算出方法を改善する．提案手法の実験対象として，Borges のデータセット [8] から 197 個の Java

概要を図 4 に示す．類似度を算出したい変更前後のファイルをプロジェクトを選択した．このデータセットは GitHub でスター

GumTree の入力として与える．GumTree はそれぞれのファイ数の多い 2,279 個のプロジェクトから構成されている．データ

ルから AST を生成し，差分を計算する．そして GumTree から

セットには Java プロジェクトが 202 個含まれているが，GitHub

出力された編集スクリプトを元に，類似度を算出する．t1 ，t2 をで公開されていないプロジェクト（2 個）と GumTree の実行にそれぞれ変更前後のファイルから生成した AST とした時，類似失敗するプロジェクト（3 個）を除外した．

度 S を次のように定義する．treeSize(t) は，AST t に含まれる

5. 2 ファイル名変更の検出数

ノード数を表す．editScript(t1 , t2 ) は，t1 ，t2 を GumTree に与類似度の閾値を変化させ，ファイル名変更の検出数の変化を既えた時に出力される編集スクリプトである．

（注 1）：https://www.eclipse.org/jgit/

-3-

—3—

600000

1
0.95

ファイル名の変更数

5000000.9
0.854000000.8
0.75

3000000.7
0.652000000.6
0.55

100000

0.5
10

15

20

25

30

35

0

40

45

50

55

60

65

70

75

80

85

90

95

類似度の閾値(%)
10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 90 95 100

類似度の閾値(%)
既存手法のみが検出

提案手法のみが検出

提案手法-適合率

提案手法-再現率

提案手法-F値

既存手法-適合率

既存手法-再現率

既存手法-F値

両手法とも検出

図 6 手法別による適合率・再現率・F 値

図 5 手法別によるファイル名変更の検出数の合計

た，手順 3. でファイル名の変更の数が一致しなかったプロジェ

存手法と提案手法の間で比較する．各プロジェクトの全てのコ

クトは 5 つあり，著者らの間で合意をとった．

ミットに対し，ファイル名変更の検出を実行する．ファイル名の変更数を計測し，全プロジェクトで合計した結果が図 5 である．
両手法ともに検出するファイル名の変更が大部分を占めている

適合率，再現率を算出するために，各手法が出力した履歴のうちファイル名変更の検出数と，上記手順で作成したデータセットのファイル名の変更数を比較する．各手法のファイル名変更のが，提案手法のみが検出するファイル名の変更は，既存手法のみ

検出数はが検出する変更数を上回っており，平均で 3.3%，最大で 13.1%

jgit log -p -U 15 -M -Mscore threshold ––follow path

上回っている．特に，閾値が 90%以上の場合，提案手法のみが検出するファイル名の変更が増加することがわかる．変数名や| grep "^rename from|^copy from"

メソッド名のみの変更のような僅かな変更に対して，既存手法で| wc -lで計測する．

は行全体の変更となり一致部分が少なくなる一方で，提案手法でファイル名変更の検出に必要な類似度の閾値を 5%ごとに変更

は対象の AST ノードだけに対する変更となるため算出される類

し，それぞれの場合の適合率，再現率および F 値を求めた結果

似度が高い値となりやすい．そのため，90%以上の高い閾値におが図 6 である．

いて，提案手法のみが検出できるファイル名の変更が増加したと適合率に注目すると，閾値 40%以上では既存手法と提案手法考えられる．

はほとんど同じ値を取っている．一方，閾値 40%以下の場合提5. 3 追 跡 精 度
各手法によって出力された履歴が実際に正しいかを調査する．
ファイル名の変更がない場合は追跡が正しく行われるのは自明

案手法が既存手法を下回っていることから，低い閾値の場合に限り提案手法は必要以上に追跡する可能性がある．続いて再現率に注目すると，どの閾値を設定しても提案手法が既存手法を上であるため，変更履歴中のファイル名の変更を正しく検出できるかを確認する．ファイル名の変更検出のための閾値を変えて，適合率，再現率，F 値がどのように変化するかを調査する．
まず，各プロジェクトから 1 つのファイルを無作為に選択し，それらのファイルについて正しい変更履歴のデータセットを作回っている．すなわち，提案手法は既存手法よりも長くファイルの追跡が可能であり，類似度を高く設定しても追跡が途切れる
ことが少ないといえる．また，提案手法の F 値は閾値 40%の時に 0.943 で最大となり，全ての閾値における既存手法の F 値を上回っている．以上の結果より，追跡精度は提案手法が優れてい成する．しかしファイル名の変更時に，削除されたファイルと追るといえる．

加されたファイルの全ての組み合わせを確認し，正解のデータ

5. 4 追跡可能な変更履歴の長さ

セットを作成することは現実的でない．そこで以下の手順で正この実験では，––follow オプションを利用してファイルの変解のデータセットを作成した．

更履歴を追跡した時，出力されるコミット数を既存手法と提案手
1. jgit log -p -U 15 -M -Mscore 10 ––follow path（注 2）
法とで比較する．各プロジェクトに含まれる全ての Java ファイを実行し，出力された履歴を目視で確認する．検出したファイル
ルから取得した変更履歴について，1 ファイルあたりの変更履歴
名の変更のうち，正しく検出した個数を計測する．閾値を 10%におけるコミット数の平均値をプロジェクトごとに算出し，箱まで下げ，できるだけ多くの変更を確認する．
ひげ図として図 7 に表す．プロジェクトに含まれるファイルは，
2. 2 人の著者の間で独立に 1. の手順を行う．
HEAD コミットに存在しているファイルだけではなく，過去に
3. 2. の結果を照合し，一致しなかったファイルの変更履存在する全てのファイルを対象とした．また類似度の閾値は，追歴については，著者らで議論を行い判断を行う．
跡精度の実験の結果から提案手法において最も F 値が高くなる
HEAD コミットにおいて Java ファイルが含まれていない 640%とした．
個のプロジェクトは除外し，合計で 191 個のプロジェクトを対象
それぞれの手法を比較すると，提案手法の方がわずかではあとした．手順 1. では，提案手法を実装した JGit を利用した．まるが長く履歴を追跡していることがわかる．中央値を比較すると，既存手法は 8.37，提案手法は 8.49 であり全体として追跡で（注 2）：-Mscore は閾値を変更するために実装したオプションである．

-4-

—4—

0

5

10

15

20

25

30

35

40

45

50

0

図 7 手法別による追跡できる履歴の長さ

1

2

3

4

5

6

7

(s)

8

9

10 11

図 9 それぞれの手法による実行時間の比較
12

10

0

実行時間(s)8

10 20 30 40 50 60 70 80 90 100 110 120 130

64

図 8 手法によって出力が異なるファイルのみに注目した時に追跡できる履歴の長さ2

060 65 70 75 80 85 90 95 100

きる履歴のコミット数が 1.5%増加した．

60 65 70 75 80 85 90 95 100

パス類似度の閾値(%)
ヒューリスティックなし

次に，提案手法と既存手法で出力する履歴が異なったファイ

Jaro-Winkler距離を利用

Levenshtein距離を利用

図 10 ヒューリスティックを利用した場合の実行時間の比較

ルのみに注目し，各プロジェクトごとに 1 ファイルあたりのコミット数の平均値を算出した場合の箱ひげ図が図 8 である．プ
ロジェクトに含まれるファイルのうち，提案手法と既存手法の実験結果を図 9 に示す．それぞれの手法について各ファイル

出力が異なるファイルを含んでいたプロジェクトは，合計で 150の追跡にかかった時間を測定し，箱ひげ図として表現している．

個であった．出力が異なるファイルのみを比較した場合，提案提案手法では AST を構築し差分を検出しているため計算量が増手法が既存手法よりもかなり長く変更履歴を追跡していること

加し，全体に既存手法よりも追跡に必要な時間が増加している．

が明らかとなった．中央値を比較すると，1.37 倍追跡可能なコ

中央値を比較したところ，提案手法は既存手法の 1.71 倍の時間

ミット数が増加している．これは，既存手法では途切れてしまっを要していた．

ていた変更履歴の追跡が，提案手法によってより長く追跡可能に

続いて，提案手法の適用時に計算時間を削減するためのヒューなったことが要因であると考察される．

リスティックを利用した場合，どの程度効果があるか実験を行っ

また，既存手法の方が 1 ファイルあたりのコミット数の平均がた．計算時間と追跡精度について調査する．2. 1 節で述べたよう長いプロジェクトは合計で 12 個あった．それらのプロジェクトにファイル名の変更を検出するために，削除されたファイルと追について比較したところ，コミット数の差は最大で 7 であり平跡中のファイルの間で類似度の計算を行うが，類似性の低いファ

均で 1.27 であった．一方で，提案手法がより長く追跡できるプ

イル同士の比較も多く含まれている．そこで，ファイルのパス名

ロジェクトは 138 個であり，長さの差の平均は 6.56 であった．

に着目する．経験的にパスの類似度が高ければ類似したファイ

以上のことから，提案手法は既存手法よりも長く変更履歴を追跡

ルであり，パスの類似度が低ければ無関係なファイルであると考することが可能であり，既存手法の方が提案手法よりも長く履歴えられる．ファイル間のパス名の類似度がある閾値を超えていを追跡できるプロジェクトは存在するが，その場合におけるコ

れば，類似している可能性の高いファイルとみなし，AST を用

ミット数の差は大きくないことが明らかとなった．

いてファイル内容の類似度を算出する．これにより，ファイル内

5. 5 実 行 時 間

容の比較回数を削減し実行時間の短縮を図る．

手法の違いによって，履歴の追跡に必要な時間がどの程度変化

パスの類似度は，Levenshtein 距離 [9] と Jaro-Winkler 距離 [10]するかを調査する．各プロジェクトから 1 つのファイルを選択の 2 通りの計算手法を用いて算出する．距離を [0,1] の間で正規し，それぞれの手法を用いて以下のコマンドを実行した時，ファ化し，値が高いほど類似性が高いとみなす．ファイル内容の比イルの履歴の追跡にかかる時間を測定する．

較を行うために必要なパスの類似度の閾値を 5%ずつ変化させ，

jgit log -M -Mscore 40 ––follow path

それぞれの結果を比較する．また，提案手法のみにヒューリス

類似度の閾値は，履歴の長さの調査時と同じく 40%とした．

ティックを適用し実験を行った．その結果が図 10 である．

また 5. 4 節の実験と同様に，HEAD コミットに Java ファイル

どちらの計算手法においても，パスの類似度の閾値を高く設が含まれる 191 個のプロジェクトが対象である．

定するほど実行時間が短縮していることがわかる．このことか

実験では，CPU: Ryzen Threadripper 3960X(24C/48T)，メら，狙い通りファイル内容の比較を行う組み合わせが限定でき

モリ: 128GB を搭載した Ubuntu 上で行った．また，JGit に対ていると考えられる．また Jaro-Winkler 距離を利用する手法としてファイル追跡の最適化とマルチスレッドへの対応を行なっ

Levenshtein 距離を利用する手法を比較すると，同じ閾値の場合ている．

は Levenshtein 距離を利用した方が実行時間は短縮される．

-5-

—5—

ファイル名変更の検出数の割合(%)

100

増加することがわかった．今後の課題として以下が挙げられる．

90

類似度の算出手法の検討

80

提案手法では，AST のノード数と編集スクリプトの割合か

70
60
50

ら類似度を算出する．さらに多くの変更を検出できる，または

40

追跡の精度が高くなるような算出方法を検討することが大き30

な課題である．例えば，編集操作あるいは AST のノードの種20

類によって重み付けを行うことにより，ファイル追跡をさらに

10
0
60

65

70

75

80

85

90

95

改善できる可能性がある．

100

パス類似度の閾値(%)
Jaro-Winkler距離を利用
Levenshtein距離を利用

類似度算出の高速化実験結果から提案手法は既存手法よりも実行時間が長くな

図 11 ヒューリスティック適用時に検出するファイル名の変更数の割合ることが判明した．AST の差分検出に多くの時間がかかっているため，この部分の最適化が課題となる．類似度の算出手法

精度についても調査を行った．パスの類似度の閾値を変化さの検討と合わせ，計算に必要な項目を AST から効率的に抽出

せ，ファイル名の変更をどの程度検出できるかをヒューリス

することで高速化できると考えられる．

ティック適用前と比較する．その結果が図 11 である．図 11 中

Git の履歴を利用する研究・ツールへの適用の縦軸はヒューリスティック適用前に検出したファイル名の変更

Git の変更履歴を利用する研究およびツールに対し，提案の個数とヒューリスティック適用後の検出数の割合である．こ

手法を適用するとより良い結果が得られる可能性がある．例との割合から，Levenshtein 距離を利用する手法の場合早い段階かして開発履歴に基づいてバグの発生箇所を予測するツールにら検出数が低下することが明らかになった．また Jaro-Winkler

適用する場合，より高い精度で予測できることが期待される．

距離を利用する場合，パスの類似度の閾値が 85%まではファイル名変更の検出の割合が約 90%と高いが，そこから類似度を高くすると検出の割合は急激に低下している．

謝辞

本研究は，日本学術振興会科学研究費補助金基盤研究（B）（課題番号：20H04166）の助成を得て行われた．
文

実行時間の計測結果（図 10）とファイル名変更の検出の割合

献[1] B. De Alwis and J. Sillito, “Why are software projects movingfrom centralized to decentralized version control systems?,”
ICSE Workshop on Cooperative and Human Aspects on Software Engineering, pp.36–39, 2009.
[2] L. Hattori, M. D’Ambros, M. Lanza, and M. Lungu, “Software evolution comprehension: Replay to the rescue,” IEEE
19th International Conference on Program Comprehension,
pp.161–170, 2011.
[3] H. Hata, O. Mizuno, and T. Kikuno, “Bug prediction based
on ﬁne-grained module histories,” Proceedings of the 34th international conference on software engineering, pp.200–210,
2012.
[4] S. Negara, M. Codoban, D. Dig, and R.E. Johnson, “Mining ﬁne-grained code changes to detect unknown change patterns,” Proceedings of the 36th International Conference on
Software Engineering, pp.803–813, 2014.
[5] E.W. Myers, “Ano (nd) diﬀerence algorithm and its variations,” Algorithmica, vol.1, no.1-4, pp.251–266, 1986.
[6] J.-R. Falleri, F. Morandat, X. Blanc, M. Martinez, and M.
Monperrus, “Fine-grained and accurate source code diﬀerencing,” Proceedings of the 29th ACM/IEEE international
conference on Automated software engineering, pp.313–324,
2014.
[7] S.S. Chawathe, A. Rajaraman, H. Garcia-Molina, and J.
Widom, “Change detection in hierarchically structured information,” Acm Sigmod Record, vol.25, no.2, pp.493–504,
1996.
[8] H. Borges, A. Hora, and M.T. Valente, “Understanding thefactors that impact the popularity of github repositories,”
IEEE International Conference on Software Maintenance andEvolution, pp.334–344, 2016.
[9] V.I. Levenshtein, “Binary codes capable of correcting deletions, insertions, and reversals,” Soviet physics doklady,
vol.10Soviet Union, pp.707–710 1966.
[10] M.A. Jaro, “Advances in record-linkage methodology as applied to matching the 1985 census of tampa, ﬂorida,” Journal of the American Statistical Association, vol.84, no.406,
pp.414–420, 1989.

（図 11）を同時に比較すると，実行時間と検出精度にはトレード
オフの関係があることが明らかになった．どちらの手法が特に優れていることはなく，例えば Levenshtein 距離を利用する手法は実行速度は速いがその分精度は劣る．

6. 妥当性の脅威
提案手法は特定のプログラミング言語に依存しない．したがって GumTree を適用可能なプログラミング言語全てに対して適用可能である．評価実験では Java ファイルのみを対象として実験を行ったが，他の言語のファイルを対象とした場合に同様の結果が得られるとは限らない．
追跡精度の調査において，Git の追跡結果を利用してファイル
名変更の正解のデータセットを用意した．本来であれば，ファイル名の変更が行われたコミットで全てのファイルの組み合わせを確認し，最も適した組み合わせを正解とする必要がある．したがって，作成したデータセットが精度評価に影響を与えている可能性がある．

7. あ と が き
本研究では，Git のファイル追跡改善のために AST を用いた差分検出手法を利用して類似度を算出する手法を提案した．提案手法では，GumTree を利用し出力された編集スクリプトから類似度を算出する．評価実験として，197 個の Java プロジェク
トを対象に，ファイル名変更の検出数・追跡可能な変更履歴の長さ・追跡精度・実行時間について調査を行った．その結果，提案
手法は既存手法よりも多くファイル名の変更および変更履歴を追跡することができ，より高い F 値が得られた．また，実行時間は-6-—6—