[解決済み] Diff Algorithm? [クローズド］

質問

効率的に動作するdiffアルゴリズムの解説を夢中で探していました。

一番近いのは RFC 3284へのリンクです。 (Eric Sink のブログ記事より) は、完全に理解しやすい言葉で データ形式 を作成し、diffの結果を保存しています。しかし、プログラムがdiffを実行中にどのようにその結果に到達するかについては、まったく触れられていません。

diffのアルゴリズムを実装する際にはトレードオフがあるはずなので、個人的な好奇心でこれを調査しようとしているのですが、diffを見ていると、「なぜdiffプログラムはあれではなくこれを変更点として選んだのだろう？

VCDIFFを出力する効率的なアルゴリズムの説明はどこにあるのでしょうか？

ちなみに、SourceGear の DiffMerge で実際に使用されているアルゴリズムの解説があれば、なお良いですね。

注： longest common subsequenceはVCDIFFで使われているアルゴリズムではないようで、使用しているデータ形式からすると、もっとスマートなことをしているようです。

どのように解決するのですか？

O(ND) 差分アルゴリズムとそのバリエーション は素晴らしい論文なので、そこから始めるとよいでしょう。この論文には、疑似コードと、diffを実行する際のグラフのトラバースを視覚化した素晴らしい図が含まれています。

第4章 この論文では、このアルゴリズムを非常に効果的にするためのいくつかの改良が紹介されています。

これをうまく実装することで、あなたのツールボックスにとても便利なツールを手に入れることができます（そしておそらく素晴らしい経験にもなるでしょう）。

必要な出力形式を生成するのは難しい場合もありますが、アルゴリズム内部を理解していれば、必要なものを出力することができるはずです。また、出力に影響を与えるヒューリスティックを導入し、特定のトレードオフを行うことも可能です。

以下はページです。 には、ちょっとしたドキュメントが含まれています。 ソースコード と、前述のアルゴリズムのテクニックを使ったdiffアルゴリズムの例です。

は ソースコード は、基本的なアルゴリズムに忠実に従っているように見え、読みやすいと思います。

入力の準備についても少し書いてあるので、参考になると思います。文字で差分する場合とトークン（単語）で差分する場合では、出力に大きな差が出ます。

がんばってください。