文書の差分箇所を検出したい

文章の差分を検出は簡単なようで意外と考えると難しいタスクです. 文章の差分は変更が最も少ない形を見つけるようにしなくてはなりません.もし、1行最初に挿入されていた場合、以後全てずれているので差分となってしまうと使い物にならないからです.その場合は最初の行だけを差分として出すのがあるべき形です. 最も愚直にやる場合は二つの文書内の互いのすべての文と文同士が対応していた組み合わせを計算して、最も変更する箇所が少ない数を探すことになりますが、これは両文章の長さを掛け合わせたO(MN)に比例します. これはさすがに遅すぎるので別の方法が必要になります. そこでここでは, ・Myresアルゴリズム ・上記を高速化したWuアルゴリズム の二つについて簡単に紹介します.

Myersの概要だけ紹介します. MyersアルゴリズムはEdit Graphを用いて比較するもの同士の最小コストでの移動経路を求めることで、最小の差分を検出します. 単語と単語がどれだけ似ているかを示す編集距離と同じような仕組みでEdit Graphを考えて適切な差分を検出します.(文同士のときも同様の考え方です.)コストが0のパスがあるかを探し、次第にかかってもよいコストをあげていき最小の差分を検出するようにするアルゴリズムです.

WuアルゴリズムはMyersアルゴリズムのときにおいて考慮していない文章同士の長さの差分から生じる大きさを考慮して探索範囲をさらに絞った方法です.

右のリンク等に詳しい解説があるので参考にしてください.