差分抽出

ここのところ diff というかテキストファイルの差分抽出に興味があって、Myers らの論文を見たりしてました。
・An O(ND) Difference Algorithm and its Variations
・An O(NP) Sequence Comparison Algorithm



最初、エディットグラフって何？という状態だったので O(ND) の論文を読んで、エディットグラフの概念については理解できたのですが、O(ND) の基本的なアルゴリズムについてはわかったようなわからないような。数式にだまされているような感じです(^^; 特に LCS/SES だけじゃなくてそのパスを求めたいのですが、何をどう記憶するのがいいのかさっぱり思いつきません。いや、論文には書いてあることは書いてあるんですよ。V を覚えておけってね。
で、その時点でだいぶ落ちこぼれつつあったのに、線形空間向けの改良として前と後ろの両方から探索を行うというところで、ついて行けなくなりました。
さらに、google-diff-match-patchの作者の解説を見ていると前と後ろからの探索がぶつからないパターンもあるとかでもはやちんぷんかんぷん。

一時はそこで諦めつつあったんですが、O(NP) の方が高速なくせに単純なアルゴリズムだという情報を得たので、O(ND) のことはさくっと忘れて O(NP) の方を読み始めることにしました。
こっちはわかりやすいですね。完全に理解できたかと問われると全然そうは思いませんが、少なくとも探索がどのように進むかはわかりました。あと、進み方が理解できたのでパスを記憶する方法もなんとなくわかりました。
というか、なんでこんなアルゴリズムを見つけることができますかね。なんかうまいことパズルのピースが合うような感じのムダのないものでした。