大きな変化が加えられたType-3クローンを検出するツールLVMapperの論文．

large-gapped cloneを検出するツールとしてCCAlignerが有名だが， CCAlignerはギャップが一箇所のみの場合にしか強くなく，かつスケーラビリティが低いという問題があった． そこで，複数箇所に大きなギャップが存在してもクローンを検出できる手法を提案している． この論文では，そのようなクローンをLVクローン（large-variance clone）と呼んでいる． LVクローンの定義は以下のとおり

• コード片の大きさの比率が0.7以内
• 複数箇所にギャップが存在する

手法はLocate，Filter，Verifyの3段階で構成されている． まず初めにソースコード中からブロックを抽出し，pretty-printした上で3行ずつハッシュ値（シードと呼ばれている）をとる．

Locate

Locateでは，それぞれのブロックに対して，クローンになる可能性があるブロックを特定する． 対象のブロックのシードと同じシードを含むブロックを持ってくる．

Filter

Filterでは，特定したブロックのうち，クローンでなさそうなものを排除する． 二つのブロックに対して，シードを共有している割合が閾値以上ならVerifyに進む．

Verify

Verifyでは，二つのブロックで順番を保ったまま共通している行を計算し， 共通行数 / 小さい方のブロックの行数 が閾値を超えていればクローンとする． この閾値は，行数が多いほど小さくなるように動的に変化する．

• 10行以下 0.7
• 10行以上20行未満 1 - 0.03 * 行数
• 20行を超過 0.4

また，このような共通行数はLCSを用いて計算できるが，LCSの計算量は行数がそれぞれMとNの時O(MN)になる． そのため，経験則を用いてO(M + N)まで落とす．

経験則

1. 片方のブロックの行を順番に上から見ていく（行1）
2. もう片方のブロックの内，行1と同じ行（行2）を探す． 見つからなければ1.に移る．
3. 行1と行2を基点として，連続して一致する最大の行数を探す．
4. 上の行数が2以上，つまり行1と行2以降も連続していれば，その行数を一致行として加える． そして，また1に移る． この時，ここで発見した連続して一致する行の最終行以降から行2の探索する．

実験結果から，LVMapperはSourcererCCやCCAlignerと比較してLVクローンを検出するのに長けていることを示した． また，それなりに高いrecallと，許容できるprecision(88.5%)，それなりに高いスケーラビリティを示した．