YAPC::Asia のハッカソンに初参加しました。今まではスピーカー(しかも年によっては選ばれた人だけ？)しか参加できなかったけど、今年はマイクロソフトさんと @myfinder さんのご好意によって、参加者でも参加できて本当に最高だと思う。

さてさて、表題の通りコピペ検出器、具体的には「似たような構造を持った Perl のソースファイルを探すプログラム」を作った。

正確には以前からいくつか試行錯誤していたけれど、なかなかうまくいかなかったのが、一応なんとか使えそうなレベルまでたどり着いた、という感じである。

基本的な考え方

ソースコードもある種の文章であり、文字列の塊である。(かどうか、本当は分からないけど、とりあえず僕はそう仮定した)。

なので、アルゴリズムとしては、「2つの文章の類似度を比較する」というのが基本戦略になる。文章あるいは文字列の類似度を比較する手段が候補になる。

候補0: mixi の Compiler::Tools::CopyPasteDetector(ダメじゃないハズなのだけど、ダメだった)

Perl プログラムのコピペの検出といえば、まず最初に候補に上がるのが、mixi さんのコピペ検出器 の Compiler::Tools::CopyPasteDetectorである。

こいつが使えれば、僕みたいな一般人が変なコード書かなくて済むので、一番良い。

ところが、、インストールは問題なくできたのだけれども、動かしてみたら、アプリのディレクトリの外のモジュールを use しているところで死んでしまい、「？？？？」となった。へーしゃのプロダクトの構成が変すぎるせいなのだろうけど、これじゃあ動かせないし、動きが分からなすぎて怖いな、と思って使用を断念した。

さらに追記:

@tsucchi なんと、モジュール動かなかったんですね…！ もしよろしければIssueを頂ければサクッと直せると思います！

— Masaaki Goshima (@goccy54) 2015, 8月 23

とのことで、作者の @goccy54さんから連絡いただきましたので、こっちも再度試してみますです。

候補1: 特徴ベクトルとコサイン類似度 (ダメだった)

既存のツールがダメなので、自分で書くしか無い。(一応調べたけど、他の事例とかプロダクトは無いハズ)

最初に検討したのが、特徴ベクトルを作って、コサイン類似度で比較する方法である。文章だと多分割と定番で、雑に作ってもそこそこ早くて精度も出る。

TF/IDF から特徴ベクトルを作って、コサイン類似度を計算する方法(定番だし、昔やったことあったので良さそうと思った)でやってみた。ソースコードはキーワードがいっぱいあるから、IDF がいい感じで効いてくれるのではないか、という期待があった。

で、やってみたところ、全然いい数字が出ない。どうしてかと思って、ベクトルを見てみたら、次元が非常に大きいのに、値はほとんど0のベクトルになっていた。これじゃぁ無理だ。。。別の方法を考えよう、と思った。(今思ったのだけど、候補2以降でやってるように、「トークン」ではなく「トークンの品詞」でやればこのアプローチも有効なのかもしれない)

候補2: 編集距離(結果は悪くなかったけど、速度とメモリ的にダメダメだった)

次に検討したのが、編集距離を比較するアルゴリズム。文字列やバイナリがどのくらい似ているか、違うかを算出するものである。「編集距離」とか「レーベンシュタインの編集距離」とかでググると色々出てくる。

簡単に説明すると、文字列を同じものにするために、何文字分の編集操作が必要かを計算するものである。

で、文字列(トークンそのもの)でやると大変そうなので、トークンの種別(たとえば「変数の宣言」)みたいな単位ごとに編集距離を出す方法でやってみた。数個のファイルで試した感じでは直感ともだいぶ一致するし、結果は概ね良好であった。

…速度とメモリ使用量以外は！

とりあえず 1ファイル分計算するのにも数秒くらいかかる。(定番で簡単なダイナミックプログラミングを使っているせいもある。論文に書いてあるような超早いアルゴリズムを使うと早くなる可能性はある)。またメモリ使用量がやばく、数GBまで達してしまう。(これもアルゴリズム変えればいけるのか？あと、現状のデータ構造がダメダメだからそれ直せばもうちょいマシになるのかも) Test::LeakTrace でリークして無いか確認したが、どうやらリークではないらしい。完全にやばい。

と、いうわけでこの方法もお蔵入りになった。(一応実装は残してある)

候補3: 出現頻度(とりあえずコレを採用している)

上記のような苦労を YAPC::Asia 以前にしていて、八方塞がりになっていたので、YAPCの終了後飲み会の道中 で @hide_o_55さんに相談してみたら、「出現頻度にして、 bigram とかコードの場所ごとに重み付けするとかやってみたら？」と言われたので、とりあえず出現頻度の bigram とかその周辺を試してみた。(これを今日のハッカソンでやっていた)

ぱっと見、編集距離とだいたい同じような結果が出て、めっちゃ早い。

trigram とか色々試したけど、あんまり代わり映えしない(速度も精度も)ので、適当でいいや、と思って出現頻度の bigram をとっている。へーしゃのプロダクトにさっきかけてみたら、数分で終わったので、これなら許容範囲である。

そもそも何でそんなもの作ったの？

基本的にはリファクタリングをちゃんとやるため、である。

Github の Ben Lavender さんの、YAPC 本編トークAdventures in Refactoringでも、冒頭で「どういうリファクタリングが良いか」みたいなことを言っていた。僕のところでも、リファクタリングが独りよがりなものにならないように、最近いくつかのメトリクスを取り始めている(行数とか複雑度とかカバレッジとか)。

で、その一環でコードのダメさの指標の一つとして、「コピペ」とか「コピペっぽさ」みたいなのを測れるといいなぁ、と思っていて、ここ1ヶ月くらい(業務の合間に少しずつ)作業していた。

で、コイツが出す数値はあてになるの？

タイトルに「オモチャ」って書いたし、あてになるわけないでしょう。こんな雑な手法でコピペが見つかるなら苦労は無いと思う。ただ、全く意味が無いかというと、そんな事はなくて、本当に完全にコピペしたら見つけれるし、コピペじゃなくても、構造が似てるやつを見つけてくれる可能性はあるから、参考にはなるはず。github の p-r フックに入れようと思っていて、その際に「既存のコレと似てるけどどうよ」って提示されて、そこで人間様がちゃんと考える事が大事だと思っている。

で、成果物は？

p5-App-CopyPasteDetector

まだまだ荒削りだし、ドキュメントとかちゃんと書いて無いけど、一応使えるはずです。(インストールすると cpd ってコマンドが入るのでそれを使う。)

会社の CI サーバとか pull request フックであれこれする物体とか、今後やっていこうと思うので、そのついでにもう少し改善されるかも。

と、いうわけで、現場からは以上です。YAPC の感想ブログ書いて無いので、まだ僕の YAPC は終わってい無いのですが、感想ブログはきっと明日以降になりそうだな。。。