たくさんのファイルから重複した行の塊を見つける

おことわり

• この記事はJetBrains Advent Calendar 2016の25日目に飛び入り参加して書いた記事ですが、第23回【フリースタイル】PORTもくもく会のLT枠で発表した際の資料も兼ねています。
  なのでスライドモードでお送りいたします。
• IDEと直接関係のない話ですみません。でも、IntelliJ IDEA Ultimateは素敵なんで使ってみるといいですよ！

---

背景

• IntelliJ IDEA Ultimate買った！
• そしたらなんか重複したコード片を勝手に見つけて教えてくれる！
  うひょー！すげーっ！リファクタリングしたくなる！！
• あ、でもこれJavaとか特定の言語じゃないとダメなのね...。
  ちょうど手元に重複だらけのシェルスクリプト群があるんだけどなぁ

---

ないなら作ろう

• 物事を単純化するため、とりあえず行単位で重複を検出する
• 多分アルゴリズム自体はtoken単位でやっても応用可能

---

アルゴリズム

※特に本などを読まずに適当に考えたため、多分もっといい方法があります。

---

概要

1. 対象のファイルの各行がキー、各行の位置情報と「その次の行」を値にした連想配列を組み立てる
   • 対象のファイルの「最初の行」を別途記録しておく
2. 「最初の行」から初めて、連想配列に記録した情報をもとに、各行を読み取っていく

---

例

• ファイル(f1)の各行:
  • [A, B, C, D]
• ファイル(f2)の各行:
  • [B, C]

---

対象のfの各行がキー、各行の位置情報と「その次の行」を値にした連想配列を組み立てる

一行目の内容: A, B

• A:
  • (f1の1行目, 次の行はB)
• B:
  • (f1の2行目, 次の行はC)
  • (f2の1行目, 次の行はC)
• C:
  • (f1の3行目, 次の行はD)
  • (f2の2行目, 次の行はなし)
• D:
  • (f1の4行目, 次の行はなし)

---

「最初の行」から初めて、連想配列に記録した情報をもとに、各行を読み取っていく

例えば、Aから連想配列をたどる場合

1. 最初に連想配列でAを引く
   • 見つけた行の塊: (A, f1の1行目)
   • 次の行はB
2. 次の行Bを連想配列から引く
   • 見つけた行の塊:
     • (A, f1の1行目), (B, f1の2行目)
     • (B, f2の1行目)
   • 次の行はC
3. 次の行Cを連想配列から引く
   • 見つけた行の塊
     • (A, f1の1行目), (B, f1の2行目), (C, f1の3行目)
     • (B, f1の2行目), (C, f1の3行目)
     • (B, f2の1行目), (C, f2の2行目)
       • 内容が重複している塊を見つけた！

---

特徴

• 計算時間は対象のファイルの合計行数に対して O(n * log n) （のはず）
  • 使用している連想配列の実装の都合上、一行を挿入するのにそれぞれO(log n)かかるので。
  • ありふれたHash Tableベースの実装ならO(n)でいけるはず。
• 少なくとも、各ファイルのペアを1組ずつ比較する方法よりはイケてる。

---

で、ものはできたの？

できてません (>_<)
絶賛デバッグ中。GHCiのデバッガーを初めて使っているので苦戦してます...。

---

あとで教えていただいた前例

• mibk/dupl
  • まだ公開していないとは言え、名前までほぼかぶり
  • 現在Go言語専用
  • 「suffix tree」というデータ構造を作るらしい。今回とはちょっと違うアプローチ？

---

所感

• めんどい。
• 適度に難しく、それなりに実用性の高い問題に出会えてよかった
  （まだハッピーエンドじゃないけど）
• 当たり前だけど難しい問題を解く時はやっぱり中間構造が大事やね。
• IntelliJがどういうアルゴリズムを使っているかは知りませんが、やっぱりすごい。