文章差分表示(文字単位)

文章1、文章2に、似ている文章を貼り付けてください。［比較］ボタンを押せば、2つの文章の差分を表示します。

（注意：まったく無関係の文章だと、処理にとても長い時間がかかります）

青色の部分は、文章1から削除された部分です。赤色の部分は、文章2で追加された部分です。

アルゴリズムの解説

高速とされるO(NP)のアルゴリズム（E.W.Myers 氏の論文、日本語訳）を実装した、Mashiki 氏の実装（MIT License）を、柳井が2倍ほど高速化したdiff関数をベースに、処理を工夫しています。

精度よりも速度を優先しています。そのままJavaScriptで実行すると、3KB程度のファイルの比較で1分以上かかりましたので……。

まず、「文章を初期分割数（デフォルト100）の区画程度に分割可能な文字」を探して、その文字で分割した区画で、diffの処理をします。

その際、一致しなかった領域に対して、今度は「半分の区画程度に分割可能な文字」を探して、その文字で分割した区画で、diffの処理をします。

以下、一致しなかったサイズが一定以下になるまで処理を再帰で行います。

いわゆる、分割統治という考え方です。比較する数が少ないほど高速になるので、上手い具合に分割して、比較の回数を減らしています。

この方法で、1文字単位で132万回ほど経路探索されていたファイルの比較が2万回ほどに減り、1分以上かかっていた処理が1秒未満になりました。