情報処理学会研究報告
IPSJ SIG Technical Report

メタヒューリスティクスを用いた集約可能コードクローン量の推定
石津 卓也1,a)

吉田 則裕2崔 恩瀞3

井上 克郎1

概要：コードクローンの集約はソフトウェア保守の対象となるソースコードを減少させる．しかし，集約に要する期間，費用の推定が困難であるために集約の計画が立ちにくいという問題がある．研究では，集約可能コードクローン量の推定が開発者の集約を支援することを目的としている．オーバーラップしているコードクローンから集約する組み合わせを推定するためにメタヒューリスティクスを用いた．
キーワード：コードクローン

メタヒューリスティクス

Estimating the amount of refactorable clones
based on metaheuristic algorithms
Takuya Ishizu1,a)Norihiro Yoshida2 Eunjong Choi3 Kathuro Inoue1

1. まえがき減らせるプログラム全体の集約可能コードクローン量がわ
かりにくかったり，その判断にかかる費用や期間が見えに

ソフトウェアの保守はソースコードの行数に依存して困くかったりするので，集約の計画が立たなくて開発を敬遠難なものになる．行数を増大させる要因の 1 つとしてコーしがちである．そこで，コードクローンに対する集約によドクローンが挙げられる [3][6]．コードクローンに対するる効果を事前に推定して集約を支援することを考える．開保守作業として集約が挙げられる．集約とは，互いにコー

発者は事前に集約可能コードクローン量を知ることで率先

ドクローンとなっているコード片の集合（以下，クローン

して集約を実行する．コードクローンがオーバーラップしセットと呼ぶ）に対して，クローンセットに含まれるコーている場合，一方のコードクローンを集約するとオーバー

ドクローンを 1 つのクラスやメソッドにまとめることであラップをしていたコードクローンはコード片が部分的に欠る [1][3]．また，集約可能なコードクローンを集約して減損するため，集約が不可能になる．よって，集約するコー

る行数を集約可能コードクローン量と呼ぶことにする．集

ドクローンの組み合わせに対して，全通りを計算して最善約を行うことで，保守の対象であるコードクローンを除去

だった順番を採用することが考えられる．しかし，実際のできる．そのため，コードクローンを集約することで，保ソースコードにおいて，コードクローンを選択する組み合

守するソースコードの行数が減少して，ソースコードの保

わせは時間的に計算するのが困難なほど現実的ではない．

守が容易になる．コードクローンが多く，開発者が判断しそこで，効率的にどのコードクローンを集約するのかを求なければならない機会が多いソースコードは，集約によりめる探索手法が必要である．本研究では，適用実験として

1

オーバーラップを考慮したコードクローンを含むソフト

2

3

a)

大阪大学
Osaka University
名古屋大学
Nagoya University
奈良先端科学技術大学院大学
Nara Institute of Science and Technology
t-ishizu@ist.osaka-u.ac.jp

c 1959 Information Processing Society of Japan

ウェアを対象にアルゴリズムを用いて集約可能なコード
クローン量を計算して，一般的にメタヒューリスティクス
で用いられる 4 つのアルゴリズムを比較している．メタヒューリスティクスであるアルゴリズムには貪欲法や山1

情報処理学会研究報告
IPSJ SIG Technical Report

登り法，焼きなまし法，遺伝的アルゴリズムが代表として挙げられる [7]．また，Edwards らは，CCFinderX のようなコード検出ツールの結果を用いて，集約可能なコードク
ローンの大きさを算出するツール CCM のアルゴリズムを考案した [2]．本研究では，メタヒューリスティクスを用いたコードクローン集約量の推定値を CCM の算出した集約量に対する近似率を求めることで，推定値がどれくらい正確なのかを調査する．

2. 背景
2.1 コードクローン

図 1 例：コードクローンの集約

Fig. 1 An Example of Refactoring Code Clone

2.1.2 コードクローンの集約

コードクローンとは，プログラムテキスト中の同一，あコードクローンの集約を行うには，コードクローンをどるいは，類似したコードの断片を意味する [6]．また，一般

こに集約するか，あるいは，変数名や変数の型，予約語と的に，同一コードクローンから構成される集合をクローンいったコードクローンの差異をどう吸収するか，開発者がセット (Cloneset) と呼ぶ．コードクローンの存在はソフト

逐一ソースコードを読んで，コードクローンが集約の対象

ウェアの保守作業を困難なものにすると言われている．例になりうるのか判断をしなければならない [3]．コードク

えば，あるコード片を修正する場合，コードクローンに関ローンが多く，開発者が判断しなければならない機会が多しても同様の修正が行われる可能性がある．コードクロー

いソースコードは，集約により減らせるプログラム全体のンに気づかずにソースコードの修正を疎かにすると，ソー集約可能コードクローン量がわかりにくかったり，その判スコードにバグが混入する可能性がある．そのため，コー断にかかる費用や期間が予想しずらかったりするので，集ドクローンの存在を知ることはソフトウェアの保守の観点約の計画が立たなくて開発を敬遠しがちである．そこで，からすると重要なことである．しかし，ソフトウェアの規

コードクローンに対する集約による効果を事前に推定し模が大きい場合，開発者がソースコードを読んですべてのて集約を支援することを考える．開発者は事前に集約可能

コードクローンの存在を知ることは非効率的であるため，

コードクローン量を知ることで率先して集約を実行する．

一般的にはコードクローンを自動で検出するツールが用いオーバーラップを考慮したコードクローンの集約可能コー

られる．コードクローンに対する保守作業として集約が挙

ドクローン量を推定するには， 集約するコードクローンのげられる．集約とは，クローンセットに対して，クローン

順番によって集約可能コードクローン量が変化することをセットに含まれるコードクローンを 1 つのクラスやメソッ

考慮す る必要がある．理想は集約するコードクローンのドなどのサブルーチンにまとめて，コードクローンを呼び組み合わせに対して，全通りを推定して最 善だった順番を出し文に置き換えることである．図 1 は，コードクローン

採用すればいい．しかし，実際のソースコードにおいて，が 1 つのサブルーチンに集約されて，コードクローンを呼コードクローンを 選択する組み合わせは時間的に計算する

び出し文に置き換えている様子を表している．集約を行うのが困難なほど現実的ではない．そこで，集約するコードことで保守の対象であるコードクローンを除去できる．そクローンを選ぶ順番を求める問題に対して，既存の探索的して，コードクローンの除去により，ソースコードの同時手法の適用が考えられる．

修正を行う手間が省ける．そのため，コードクローンの集
約はソースコードの保守作業の労力を軽減する役割を持つ．

2.1.1 コードクローンのオーバーラップ

2.2 メタヒューリスティクス
メタヒューリスティクスとは，特定の問題に依存しない，

コードクローンのオーバーラップとは，複数のコード

組み合わせ最適化問題における， 近似解を求める解法をもクローンのコード片が部分的に重複していることを指す．

つアルゴリズムの基本的な枠組みのことである．アルゴリ

コードクローンがオーバーラップしている場合，一方のズムとし て，局所的な探索に基づくアルゴリズムや，大域

コードクローンを集約するとオーバーラップしていたコー的な，個体群に基づくアルゴリズムが挙げ られる．局所的

ドクローンはコード片が部分的に欠損するため，集約が不な探索に基づくアルゴリズムとは，現在の解から近傍を求可能になる．図 2 は任意のソースコードに含まれる 2 つのめて，現在の解を 近傍の解に更新する作業を繰り返すこと

コードクローン a1，b1 がオーバーっらぷしている例を示し

で近似解を求めるアルゴリズムである．大域的な個体群にている．青で塗られたコード片 a1 と赤で塗られたコード基づくアルゴリズムとは，解の候補を生物の個体群に見立

片 b1 はそれぞれ異なるクローンセットに属しており，2 つて最適解を求めるアルゴリズムである．このアルゴリズムのコードクローンが部分的に重複している様子がわかる．

では，個体が次の世代に生き残るのかを決定する関数を工夫して生物の生殖や自然淘汰，突然変異などを再現する．

c 1959 Information Processing Society of Japan2

情報処理学会研究報告
IPSJ SIG Technical Report

図 2 コードクローンがオーバーラップする例

Fig. 2 An Example of Overlapping Code Clones

これを繰り返して残った個体が最適解に近似する．

図 3

提案手法の流れFig. 3 An Overview of the Proposed Method

たコードクローンの集約可能 コードクローン量を比較す

本研究では，コードクローンの集約可能コードクローン

る．本手法では，比較を行うために必要なコードクローン

量をメタヒューリスティクスで一 般的に用いられる 4 つのの集約 可能コードクローン量を求める． 本研究における，アルゴリズムに適用して，それらの評価を比較する．メタ

オーバーラップを含む，クローンセット合成を行ったコー

ヒューリ スティクスで用いる 4 つのアルゴリズムとして貪

ドクローンの集約可能コードクローン量の推定する手法の欲法 (Greedy Algorithm)[5]，山登り法 (Hill Climbing)[4]，

流れを説明する．

焼きなまし法 (Simulated Annealing)[8]，遺伝的アルゴリ

Step1 CCFinder のコードクローン検出結果を入力する．

ズム (Genetic Algorithm)[9] が代表的なアルゴリズムとし

Step2 入力したコードクローン間に発生したオーバーラッて挙げられる．HC や SA は局所的な探索アルゴリズムであり， GA は大域的な，個体群に基づく探索アルゴリズムである．
本研究では，遺伝的アルゴリズムとして，多目的最適化

プを抽出する．

Step3 メタヒューリスティクスなアルゴリズムを用いて，コードクローン全体の集約可能コードクローン量を推定する．

問題によく用いられる NSGAII （Non-dominated Sorting

本研究で提案する集約可能コードクローン量を推定する

Genetic Algorithms-II）アルゴリズムを使用した．多目的手法を図示した．Step1 では，コードクローンの集約可能最適化問題とは，目的関数を 2 つ以上持っている最適化問

コードクローン量を推定するソースコードに対して，字句題のことである．本研究で は，目的関数が集約可能コー

解析に基づく CCFinder によるコードクローンを検出を行

ドクローン量の 1 つしかない単一目的最適化問題を扱う

い，その出力ファイルを入力に用 いる．Step2 では，入力が，NSGAII は目的関数が 1 つでも適用可能である．ました位置情報を基に，どのコードクローン同士がオーバー

た，NSGAII アルゴリズムの 使用にあたって，Java のフ

ラップし ているかを判別する．Step3 では，検出されたすレームワークとして MOEA を利用した．MOEA では，多べてのコードクローンに対する，集約可能 コードクローン

目的最適化問題に対応する，遺伝的アルゴズムや遺伝的プ量を推定する．また，無向グラフ G をもつクローンセット

ログラミングがオープン ソフトウェアとして組み込まれての集合に対して， 各クローンセットを分割する．

いる．

3. 提案手法

3.1 オーバーラップの検出
Step1 では，集約可能コードクローン量を推定するソース

本節では，集約可能コードクローン量を推定する手法にコードに対して，コードクローンを検出を行った．本手法

ついて説明する．図 3 は，提案手法の流れを表している．

では，字句単位の解析コードクローン検出ツール CCFinder

本研究では，メ タヒューリスティクスの 4 つのアルゴリを用いた．コードクローン検出に字句単位の解析ツールをズムの中から最適なアルゴリズムを決定することを 目的用いる理由は，字句単位のような検出粒度が細かい検出法にしている．そのため，各アルゴリズムを適用して得られの方が集約可能なコードクローンを検出しやすいためであc 1959 Information Processing Society of Japan3

情報処理学会研究報告
IPSJ SIG Technical Report

図 5 集約可能コードクローン量の推定の概要

Fig. 5 An Overview of Estimating the Amount of Code Clone

約する順番を求めなくてはならない．理想的な解法としては，集約するコードクローンから構成される集合の全組み
図 4 コードクローン間のオーバーラップを表現する無向グラフの例

Fig. 4 An Example of an Undirected Graph that
Represents Overlaps Among Clone Sets

合わせに対して集約可能コードクローン量を推定して，最大の集約可能コードクローン量となる集合を解とすればよい．しかし，全組み合わせに対して，集約可能コードクロー
ン量を推定するのは現実的ではない．本研究では，そのよる．メソッド単位やクラス単位の検出では集約可能なコー

うな問題に対して，メタヒューリスティクスを用いてコー

ドクローンは発生しにくい．また，CCFinder は様々な大ドクローンの集約可能コードクローン量の推定を行う．

規模ソフトウェアに適用され, その有用性が確認されているため，本手法で使用した．

本研究では，コードクローンの集約手法について特定の手法を選択しない．いずれの集約手法を選択しても，コー
ドクローンであるコード片をプログラムに 1 つ残して，そ3.2 オーバーラップの抽出の他のコード片に関しては集約により消去されるという考

Step2 では，Step1 で検出したコードクローンをもとに，え方を適用する．そのため，特定の集約手法に依存しない，

どのコードクローン同士がオーバーラップしているかを判

コードクローンの集約可能コードクローン量を推定する．

別して，オーバーラップしているクローンセットを抽出す

集約可能コードクローン量を評価する指標として，ソーる．同時に図 4 のような無向グラフ G を構成する，クロー

スコードの行数やトークン数が候補として挙げられる．本ンセット S1 から S6 までを頂点とし，各頂点間に接続する研究では，開発者が集約の実行を率先して実行するかどう

無向辺に対して，隣接する 2 頂点はオーバーラップの関係かを判断する基準としてコードクローンの集約可能コードにある．例えば，図 4 の場合，クローンセット S1 は 2 つ

クローン量を推定する．そのため，開発者が直感的に数値のクローンセット S2 ，S3 とオーバーラップしていることで評価しやすいと考えられるソースコードの行数を評価のがわかる．

指標とする．

2 つのコード片 a1 ，a2 が重複する条件は次の 2 つであ

任意のクローンセット Sk に関して， Sk 内に含まれる

る．ただしコード片 a1 の開始行番号はコード片 a2 の開始

集約可能なコードクローンの個数を n，i 番目のコードク

行番号より先にあるものとする．

ローンを ck,i とする．またコードクローン ck,i のコード片( 1 ) 2 つのコード片が同一ファイル内に存在する．

の行数を t(ck,i ) とする．

( 2 ) コード片 a1 の行番号 ≤ コード片 a2 の行番号 ≤ コー
ド片 a1 の終了行番号を満たす．

クローンセット Sk の集約を考える．コード片 1 つを残してその他のコード片を消去するのだから，クローンセッ

以上，2 つの条件を満たす 2 つのコード片 a1 ，a2 はオー

ト Sk の集約可能コードクローン量 L(Sk ) は次のように推バーラップしている．また，2 つのコード片 a1 ，a2 に関し定される．

て，a1 ∈ S1 ，a2 ∈ S2 を満たすクローンセット S1 ，S2 が存

n−1 X
t(ck,i )nn

在するとする．このとき，S1 6= S2 ならば 2 つのクローン

L(Sk ) =セット S1 ，S2 はオーバーラップしている．また S1 = S2

i=0ならば，そのクローンセットは自分自身とオーバーラップ

図 5 はサブルーチンに集約されるコードクローンの行数がしている．無向グラフ G に属する任意のクローンセットt(ci ) で与えられている様子を表している．ただし，本研究は，無向グラフ G に属する他のクローンセットの少なくとでは，呼び出し文の行数を考慮していない．これは，集約

も 1 つ以上とオーバーラップしている．

可能コードクローン量が集約される行数だけではなく，集約されるトークン数を表すこともあるためである．

3.3 集約可能コードクローン量の推定
オーバーラップしているコードクローンに対して，集約可能コードクローン量を推定する場合，最大の集約可能
コードクローン量を推定するためにはコードクローンを集

c 1959 Information Processing Society of Japan

3.4 オーバーラップを含む集約可能コードクローン量の推定
複数のクローンセットのオーバーラップしている状態は4情報処理学会研究報告
IPSJ SIG Technical Report

図 4 のような無向グラフによって表現できる．クローン
セット S1 から S6 までを頂点とし，各頂点間に接続する無向辺に対して，隣接する 2 頂点はオーバーラップの関係にある．例えば，図 4 の場合，クローンセット S1 は 2 つのクローンセット S2 ，S3 とオーバーラップしていることがわかる．
図 4 のような無向グラフで隣接する複数のクローンセッ
トからなる集合を G とする．また，集合 G に含まれる任意のクローンセットに関して，互いにオーバーラップしないようにクローンセットを選択してなす集合を H とする．
すなわち，集合 H に含まれるクローンセットに対する無向グラフでは，無向辺を持たない．例えば，図 4 の場合，
集合 G と，集合 H の一例として挙げる H1 ，H2 は次のよ
うになる．

図 6

クローンセットの合成例

Fig. 6 An Example of Marging Clone Sets

G = {S1 , S2 , S3 , S4 , S5 , S6 }H1 = {S1 , S4 , S6 }ト A，B を合成して新たなクローンセット C を作る様子を示している．クローンセット A はクローンセット B とH2 = {S3 , S5 , S6 }ファイル B 上でオーバーラップしているために集約ができ

2 つの集合 H1 ，H2 に含まれるクローンセットは互いにオーなかった．そこで，クローンセット A の各コードクロー

バーラップしていないので，クローンセット Sk の集約可ンに関して，クローンセット B とオーバーラップしてい能コードクローン量を L(Sk ) とすると，2 つの集合の集約る部分としていない部分に分割する．こうすることで，ク

可能コードクローン量 L(H1 )，L(H2 ) は次のようになる．

ローンセット A を分割でき集約が可能になる．このようなクローンセット A の集約はクローンセット B とのみオー

L(H1 ) = L(S1 ) + L(S4 ) + L(S6 )L(H2 ) = L(S3 ) + L(S5 ) + L(S6 )バーラップしている想定で行われている．しかし，仮にク
ローンセット A がクローンセット B 以外の他のクローンセットとオーバーラップしている場合も考えられる．その一般化すると，集合 H の集約可能コードクローン量 L(H)

ような場合でも，クローンセット A の図 6 のような分割はは次のようになる．

クローンセット B の間しか行らないため，分割後のクローX

L(H) =

L(Si )Si ∈H

集合 G の集約可能コードクローン量 L(G) について，

L(G) の数値が最大となるようなクローンセットの選び方
として集合 Hmax が存在する．集合 H の集合を M とした
場合，集合 G の集約可能コードクローン量 L(G) は次のように表す．

ンセット A を独立したクローンセットにするのではなく，
オーバーラップしていたクローンセット B と合成した新たなクローンセットを作成する．また，本研究では．クローンセット A とオーバーラップしているクローンセットが 1
つではない場合，クローンセット A が合成を行う対象はただ 1 つのクローンセットとしている．そのクローンセット
はクローンセット A と合成して最大の集約量になるようなクローンセットを選択する．クローンセット SA とオー

L(G) = L(Hmax ) = max {L(H)}H∈M

3.5 クローンセットの合成
オーバーラップする 2 つのクローンセットのコードク
ローン集約量は，一方のクローンセットの集約を行い，もバーラップしているクローンセットの集合 GA について，

SX (∈ GA ) を考える．このとき，クローンセット A とのご異性による集約量は次の数式で求められる．

L(SA ) + L(SX ) −X(cAi ∩ cXj )0≤i≤|SA |0≤j≤|SX |

う一方のクローンセットの集約は行わないことで求めることができる．しかし，集約を行わないクローンセットはこの式で求められた集約量が最大となったクローンセット

オーバーラップをしているコード片を除けば，残ったコー

SX をクローンセット A と合成する．

ド片を組み合わせることで新たなコードクローンを作り，集約することが可能になる．本研究では，2 つのクローン

3.6 探索的手法への適用

セットを合成することでコードクローン集約量を求めるこ

集約可能コードクローン量を決める集約の順番を求めとにした．図 6 は 2 つのオーバーラップしたクローンセッ

るために，SBSE を用いる．そのために，Representation，c 1959 Information Processing Society of Japan5

情報処理学会研究報告
IPSJ SIG Technical Report

Operators，Fitness Function を定義する必要がある．Step3
で，検出されたすべてのコードクローンに対する，集約可能コードクローン量を推定するアルゴリズムは Greedy，HC，SA，GA の 4 つである．
3.6.1 Representation
集約可能コードクローン量を推定する N 個のクローン

図 7 クローンセット集合の場合の Representation ト

セット全体に対して，i 番目のクローンセット Sk の状態

Fig. 7 Representation for a Set of Clone Sets

S(i) を次のように表す．ただし，i は N ≥ k を満たす整数で，クローンセット同士を互いに識別するための ID で淘汰，突然変異を起こすことで残る次の世代である．

ある．

R(k + 1) = Opr(R(k)) = Opr(H(k))S(i) = Overlap(i) = p, q, r
HC

Overlap(i) は i 番目のクローンセット Si とオーバーラッ

R(k) の近傍を選ぶアルゴリズムは以下のとおりでプしているクローンセットの ID 集合を返す．例の場合，

ある．

p，q ，r 番目のクローンセットはそれぞれ i 番目のクロー

Step1R(k) の要素の中から任意の，0 である i 番目の要素を選ぶ．

ンセットとオーバーラップしている．このとき，クローンセット Si は無向グラフ G に属しているものとする．ただStep2i 番目の要素を 1 にする．

し，無向グラフ G に属する任意のクローンセットは，無向Step3i 番目の要素とオーバーラップしているクローンセッ

グラフ G に属する他のクローンセットの少なくとも 1 つ

トと対応している要素のうち，1 である要素すべてを以上とオーバーラップしている．無向グラフ G から任意0 にする．

のクローンセットを適当に選択し，それらのクローンセッ

Step4R(k) の要素の中から，集約しても他のクローンセッ

トを要素に持つクローンセットの新たな集合 H を考える．

トとオーバーラップしないクローンセットに対応す
る要素をすべて 1 にする．

ただし，集合 H に含まれる任意のクローンセットは，集合

H に含まれるクローンセットとオーバーラップしていない

Step5得られた近傍の中から Fitness Function の評価に従い，R(k + 1) を返す．

ものとする．

R は図 7 のようにバイナリ表現で考える．無向グラフ

Step1 で選択される要素は，R(k) 中の要素 0 の数だけ

G に含まれる n 個のクローンセットをそれぞれ R で表さ存在する．また，Step3 の実行により，オーバーラッ

れるバイナリの各位置に対応付ける．集合 H に含まれるプしているクローンセットは解消される．Step4 はクローンセットに対応する位置を 1，含まれないクローン

Step3 により 0 になった要素とオーバーラップしていセットに対応する位置には 0 を表示する．

たクローンセットが集約可能になっている可能性があInitial Representation

るためである．ただし，1 つのクローンセットの集約を解除することで 2 つ以上のクローンセットが集約

Greedy 法の初期値の決定は次の手順で行う．すべてのクローンセットを集約可能コードクローン量の大き可能になっていた場合，2 つ以上のクローンセット同い順番にソートして，集約可能コードクローン量が大士がオーバーラップする可能性がある．このとき，ク

きいクローンセットから優先的に集約をしていく．たローンセット間でオーバーラップが発生しないようなだしすでに集約したクローンセットとオーバーラップ

クローンセットの全組み合わせを近傍として与える必要がある．

していたために集約不可なクローンセットは集約しない．本研究におけるメタヒューリスティクスの初期SA

値は Greedy 法で決定した集約の順番と同じとする．

R(k) の近傍の選択は HC と同じでアルゴリズムを用

これは Greedy と比べて他のアルゴリズムの集約可能いる．ただし Step1 に対して，SA は乱数を用いて，たコードクローン量がどれだけ増加するのかを比べるただ 1 つの要素を選択する．また，Step5 に対して，SAめである．

では遷移確率というパラメータを用いる．遷移確率と3.6.2 Operators

は R(k) が次の状態 R(k + 1) に遷移する際に，最適解集合 H(k) に対する操作 Opr は次のように表せる．

に比べて評価値が離れた場合でも，より悪い状態を採集合 H(k) に対する集合 H（k+1）の選び方はアルゴリ

択する確率である．本研究では，遷移確率は 0.1 からズムに依存する．例えば，山登り法の場合，集合 H(k + 1)

0.9 までを 0.1 刻みで実行した．4 章で示す SA の集約

は集合 H(k) の近傍である．または，遺伝的アルゴリズム

可能コードクローン量は，本実験では遷移確率によるの場合は，集合 H(k + 1) は集合 H(k) を基に，生殖や自然

大きな差異はないためそれらの平均値としている．

c 1959 Information Processing Society of Japan6

情報処理学会研究報告
IPSJ SIG Technical Report

ローン，クローンセットの個数をまとめている．ApacheGA
MOEA は Java のフレームワークで広く用いられるた

Ant はコードクローン数，クローンセット数ともに 3 つのめ，GA には多目的最適化問題に対して有効な，MOEA

中で最小で，クローンセットを分割するとおよそ 2 倍ほどに搭載されている NSGAII アルゴリズムを使用する *1 ．

に増える．コードクローン数，クローンセット数ともに最変更可能なパラメータは評価回数，個体群数，交叉率，

大は ArgoUML で，クローンセットを分割するとおよそ 3

突然変異率の 4 つである．評価回数は個体群が世代交倍ほどに増える，Xerces も同様に，クローンセットを分割代を再現する回数のことである．本研究では，2000 回するとおよそ 3 倍ほどに増える．

で実行した．個体群数とは，1 世代に生存している個体群の数である．本研究では MOEA フレームワークのデフォルト値である 100 とした．次に，交叉率とは4.2 各アルゴリズムによる集約可能コードクローン量推定結果の比較

世代交代の際に個体群を交配するかしないかを決める

各アルゴリズムごとの集約量コードクローン量について

確率のことである．本研究では，デフォルト値である比較する．SA，GA は評価回数に応じて集約可能コード

1.0 とした．最後に，突然変異とは個体群に含まれる個

クローン量が変化するので，SA，GA の評価回数 2,000 回

体を突然変異させる確立である．本研究では，デフォを実行する．また，表 2 は，CCM の各プロジェクトに対ルト値である突然変異率は無向グラフ G に含まれるク

する集約量の結果である．表 3 は，本研究の集約量の各ア

ローンセット数の逆数とした．個体群数，交叉率，突ルゴリズムごとの結果と表 2 の結果に対する近似率を表し

然変異率に対して，デフォルト値を使用した理由は，ている．表 3 をみると，いずれの近似率も 90%を超えてこれらの値を動かしてもあまり結果に影響せず，代表いることがわかる．また，最も高い近似率を算出したのはとしてデフォルト値を使用しても問題がなかったため

遺伝的アルゴリズムである．プロジェクト Apache Ant，である．

ArgoUML，に対して最も高い近似率を表した．また，最も低い近似率を表したアルゴリズムは Greedy であった．

3.6.3 Fitness Function
集合 H(k) に属するクローンセット全体の集約可能コー

Xerces に対して 91.3%であった．これは，ソースコードに

ドクローン量が大きいほど，より多く集約されたと見做含まれるコードクローン間に発生しているオーバーラップせる．そのため，評価値は集合 H(k) に属するクローンの数が多いことを示している．また，クローンセットの合

セット全体の集約可能コードクローン量とする．評価関数

成であっても完全にはコードクローンを集約しきれていな

F (R(k)) は，集合 H に属するクローンセット Si の集約可いことを示している．

能コードクローン量の総和である．

F (R(k)) = F (H(k)) = L(H(k)) =X

表 1 各プロジェクトの概要

L(Si )

Si ∈H

4. 適用実験

Table 1 Statistics of each project
Apatch Ant

ArgoUML

Xerces

ソースコードの行数

265828389915238183

コードクローンの行数

23278(8.76%)

59787(15.33%)

51731(21.72%)

13442(5.06%)

41434(10.63%)36697(15.41%)

5785

21427

17249

クローンセット数 (マージ無)

1740

4795

3792

クローンセット数 (マージ有)

3552

15142

10341

本章では，本研究の手法に適した，最大の集約可能コー

オーバーラップしている

ドクローン量を示すアルゴリズムが何であるのかを確認す

コードクローンの行数
コードクローン数

るために，適用実験を行った．

4.1 対象データ
本研究では，3 つのプロジェクト Apache Ant，ArgoUML，

The Apache Xerces(以下 Xerces) のソースコードに含まれ

表 2 CCM が計測したコードクローン集約量

Table 2 Amount of Refactorable Code Clones by the CCM

るコードクローンに対して集約可能量を推定した．3 つのプロジェクトは広く知られるオープンソースウェアで，CCM

Apache Ant

ArgoUML

Xerces

9667

26901

24336

コードクローンに関する研究の対象プロジェクトとしてよく用いられる．各ソースコードの行数と，含まれるコード

表 3 各アルゴリズムによるコードクローン集約量の推定クローンが占める行数とオーバーラップしているコードク

Table 3 Estimating the Amount of Refactorable Code Clones

ローンが占める行数，また，それらが占める割合を表 1 にまby each Algorithm

とめた．最もコードクローンが占める行数が多いプロジェ
クトは ArgoUML で，最も少ないプロジェクトは Apache

Apache Ant

ArgoUML

XercesGreedy9389(97.1%)

25614(95.2%)

22220(91.3%)

HC9521(98.4%)

26372(98.0%)23309(95.7%)

Ant である．また，各ソースコードで検出されたコードク

SA9576(99.0%)

26591(98.8%)

23417(96.2%)*1GA9590(99.2%)

26787(99.5%)23384(96.0%)

http://moeaframework.org/

c 1959 Information Processing Society of Japan7

情報処理学会研究報告
IPSJ SIG Technical Report

4.3 考察
各アルゴリズムの推定に対する振る舞いを考察する．
アルゴリズムの比較：Greedy Algorithm法を利用した．また，HC や SA，GA などメタヒューリス
ティクスを，実行時間やコードクローン集約可能コードク
ローン量を対象に性能を比較した．また，CCM と近似率

Greedy アルゴリズムは他 3 つのアルゴリズムに比べを比較して推定の正確さを示した．最大の集約可能コードて，集約可能コードクローン量が最小であった．また，クローン量を示したのは GA で，次いで SA だった．しか実装がもっとも単純なアルゴリズムである．コードク

し、その差は小さく、適応するソフトウェアのオーバーラッ

ローン間でオーバーラップを発生していない場合のプの状態にもよるところが大きいと考えられる．今後の課集約可能コードクローン量は Greedy で得られる集約

題として本研究で対象にしたソースコードから検出された可能コードクローン量に一致する．そのため，対象のコードクローンが一般的なソフトウェアのコードクローン

ソースコードから検出したコードクローンの数やオー量に比べて小さいため，より大規模なソフトウェアを対象

バーラップの発生が少ない場合には，最適なアルゴリにした実験が必要になる．
謝 辞 本 研 究 は JSPS 科 研 費 25220003，26730036，
15H06344 の助成を受けたものです．また，大阪大学 Ali
Ouni 特任助教には本研究で多くの御助言をいただきましたこと，心より感謝します．

ズムだと考えられる．反対に，Xerces や大規模な商用ソフトウェアのようにオーバーラップしているコードクローンが多いと，Greedy で推定される集約可能コー
ドクローン量の誤差は大きくなると考えられる．
アルゴリズムの比較：HC

HC アルゴリズムは Greedy アルゴリズムより推定さ

参考文献
[1]

れる集約可能コードクローン量が多く，しかし SA やGA に比べると少ないアルゴリズムである．HC は評
価関数が凸関数にできれば大きな効果を持つ，局所的[2]な探索が得意なアルゴリズムである．しかし，極大値にはまると，それを大域的な最大値として推定してしまう弱点がある．本研究のようなクローンセットを集[3]

約する順番を 1 つ変えるだけで評価値が大きく変動してしまう問題を抱えるため，SA に比べてあまり良い[4]

結果を出すことができなかったと考られる．
アルゴリズムの比較：SA[5]

SA アルゴリズムは評価回数を基準にした場合，Xercesを対象とした場合，最大の集約可能コードクローン量を示したアルゴリズムである．HC と同様に，SA は極大値にはまると，それを大域的な最大値として推定

[6]
[7]

してしまう弱点がある．しかし，本研究では GA と比較しても，わずかに下回るかほぼ同数の集約量を示す結果となった．Apatche Ant と Xerces ではほぼ同数であったが，ArgoUML ではやや大きく集約量に差が[8]あったと考え，GA を週力量の推定に最も適したアルゴリズムだとした．
アルゴリズムの比較：GA

GA ア ル ゴ リ ズ ム は 本 研 究 で Apatche Ant と Ar-[9]

Bouktif, S.，Antoniol, G.，Merlo, E.，Neteler, M.：A novel
approach to optimize clone refactoring activity, Proceedings of the 8th annual conference on Genetic and evolutionary computation GECCO ’06, pp. 1885–1892 (2006).
Edwards III, B., Wu, Y., Matsushita, M. and Inoue,K.: Estimating Code Size After a Complete Code-Clone
Merge, 情報処理学会研究報告， Vol. 2016-EMB-41, No. 3,
pp. 1 – 8 (2016).
肥後芳樹，楠本真二，井上克郎：コードクローン検出とその関連技術，電子情報通信学会論文誌，Vol. J91-D, No. 6,
pp. 1465–1481 (2008).
Hiroi, M.: Algorithms with Python ヒューリスティッ
ク 探 索.
http://www.geocities.jp/m_hiroi/light/
pyalgo28.html(2016 年 2 月 16 日).
Hiroi, M.: 欲 張 り 法 (greedy strategy). http://www.
geocities.jp/m_hiroi/light/pyalgo22.html(2016 年
2 月 16 日).
井上克郎，神谷年洋，楠本真二：コードクローン検出法，コンピュータソフトウェア，Vol. 18, No. 5, pp. 47–54 (2001).
O’Keeffe, M.，Cinneide, M. O.：Search-based refactoring:an empirical study, Journal of Software Maintenance andEvolution: Research and Practice - Search Based Software Engineering [SBSE], Vol. 20, No. 5, pp. 345–364(2008).
輪 湖 純 也：Simulated Annealing/SA-概論-.
http://mikilab.doshisha.ac.jp/dia/research/person/
wako/(2015 年 1 月 31 日).
同志社大学 知的システムデザイン研究室 遺伝的
ア ル ゴ リ ズ ム 研 究 グ ル ー プ：遺 伝 的 ア ル ゴ リ ズ ム 概
要. http://mikilab.doshisha.ac.jp/dia/research/
pdga/research.html(2016 年 1 月 31 日).

goUML で最大の集約可能コードクローン量を示したアルゴリズムである．本研究の集約可能コードク
ローン量の推定にメタヒューリスティクスを適用した場合，局所的な探索手法よりも大局的な探索手法が優れていることを示した．

5. まとめと今後の課題
本研究では，オーバーラップを考慮したコードクローンの集約可能コードクローン量を推定するために，探索的手

c 1959 Information Processing Society of Japan

8