diffのアルゴリズム - Plan9日記ふと見つけた「あなたが一番好きなアルゴリズムを教えてください。また、その理由やどんな点が好きなのかも教えてください」を読んで、diffのアルゴリズムを調べてみた。2つのファイルの違いを見つけるには、共通する部分が最長になるペアを見つければよい。これはLCS (Longest Common Subsequence)問題と呼ばれる。LCS問題の最適解は動的計画法を用いて求めることができるが、計算時間、メモリ使用量ともにO(MN)になる*1。これより早く、また小メモリで実行できるようにいろいろなアルゴリズムが提案されている。 テキストを比較するdiffというUnix系のコマンドがありますが、これは実は高度に数学的なエディットグラフというアルゴリズムが使われています。 [1] E.W.Myers, "An O(ND) difference algorithm and its variations"
