テキスト差分 Wu によるO(NP) 法の Hirschberg 法化まとめ

テキスト差分アルゴリズムでは現在知られている最も高速な Wu による O(NP) 法に、 2 N の作業領域で求める Hirschberg 法を摘要した試みへのリンクをまとめます。 第一期は Ruby によるスタディで、 第二期は、 diff に準拠したコマンドを C++11 で書いたものです。 組み合わせを網羅する力任せのテストで動作確認は済んでいますが、 あらゆる場合に正しく動作するかどうかはアルゴリズムとして証明する必要がありますが、 未だにできていません。

Ruby スタディ版

Hirschberg法 - Wu による O(NP) テキスト差分の試行 その1

Hirschberg法 - Wu による O(NP) テキスト差分の試行 その 2

C++11 実装版

GitHub - tociyuki/udiff-cxx11: word based unified color differences between two texts

Hirschberg-Wu 法による diff プログラム

Hirschberg-Wu 法による diff プログラム改良版

Hirschberg-Wu 法による GNU wdiff もどきプログラム

UCD Script ごとに分離する GNU wdiff もどきプログラム

Hirschberg-Wu 法による単語 diff 形式交じり unified 形式

diff もどきの unified 形式出力を mark ベクタなしで