diffのアルゴリズム
ふと見つけた「あなたが一番好きなアルゴリズムを教えてください。また、その理由やどんな点が好きなのかも教えてください」を読んで、diffのアルゴリズムを調べてみた。2つのファイルの違いを見つけるには、共通する部分が最長になるペアを見つければよい。これはLCS (Longest Common Subsequence)問題と呼ばれる。LCS問題の最適解は動的計画法を用いて求めることができるが、計算時間、メモリ使用量ともにO(MN)になる*1。これより早く、また小メモリで実行できるようにいろいろなアルゴリズムが提案されている。
テキストを比較するdiffというUnix系のコマンドがありますが、これは実は高度に数学的なエディットグラフというアルゴリズムが使われています。
[1] E.W.Myers, "An O(ND) difference algorithm and its variations", Algorithmixa, 1 (1986), pp.251-266こちらに日本語の解説がありました。
http://hp.vector.co.jp/authors/VA007799/viviProg/doc5.htm
テキストを比較するのなんて簡単なんじゃないか？と思いますが、実際にプログラムを組もうとすると頓挫します(笑) この解説を読むと、とてもシンプルですばらしく数学的な発想の転換が用いられていることがわかり「数学的な感動」があります。
エディットグラフの原理は、たとえばカーナビの最短経路検索などでも使われています。
今回調べた対象は、
結論から言うとMyersのアルゴリズムが使われているのはGNU diffだけで、それ以外はHarold Stoneのアルゴリズムが使われている。というか、冒頭のコメントを読む限り、Doug McIlroy*2がUNIX 5th edで実装したdiffから派生したコードみたいね。
* Uses an algorithm due to Harold Stone, which finds * a pair of longest identical subsequences in the two * files.
McIlroy diffのアルゴリズムについては、次の論文に詳しい。
- J. W. Hunt and M. D. McIlroy, An Algorithm for Differential File Comparison, Bell Telephone Laboratories CSTR #41 (1976)
GNU diffに関しては、akrさんが「diff は近似アルゴリズムがいい?」で書いてらっしゃるように、Myersのアルゴリズムを基に、Paul Eggertさんがワーストケースを抑える改良を加えているようだ。
アルゴリズム以外の工夫では、各行を比較するときに、生データを使うのではなく、初期化時にハッシュ値を求めておいて、これを用いて比較するとかもやっている。これはどちらの実装でも同じ。
（追記：2010-01-11）id:cubicdaiyaさんの発表資料「diff」にはSubversionなどで使われているWuのアルゴリズムの解説がある。
