忍耐差 - 一意でない行の最後の段階では正確に何が行われますか？

Question

は、私は、各コレクション内のオブジェクトが一意である、関連するビジネスの問題を解決するために非常にうまく動作しますが、両方のコレクションに存在する多くの非ユニークなオブジェクトがあるとき、奇妙な結果を与える傾向があるサブシーケンスを増やす最長に基づくアルゴリズムを持っています。

忍耐強さアルゴリズム（最長増加サブシーケンスにも基づいている）を使用するアプローチは、一意でないオブジェクトが存在するときに必要な結果を提供するように見えます。しかし、Patience Diffが適切かどうかを知るには、適切であればそれを私の問題に適用するために、アルゴリズムの理解を深める必要があります。

私は手順1〜3で何が起こるかを理解し、私は1〜3の後のステップ4で何が起こるかについては明らかではないよ、今は可能な一致を持たないユニークなライン、および非ユニークなラインのブロックが残っています。次に何が起こるか - 文書の残りの最初/最後の行との一致がないと仮定しますが、確かに（それ以上の固有の行がないので）すでに終了していませんか？あるいは、ある文書内の非固有ブロックと他の文書内のすべての非一意ブロックとを比較して、何らかの形で最良の一致を選択しますか？

http://bramcohen.livejournal.com/73318.html

1. マッチ両方それらが同じなら、2番目に一致し、第三、等の最初の行のペアが一致しなくなるまで。
2. 両者の最後の行が一致する場合は一致させ、次に一致する場合は最後に一致させ、次に一致するまで一致させるなどします。
3. 両側で一度だけ発生するすべての線を見つけ、それらの線上で最も長い共通部分列を行い、それらを一致させます。
4. Doがマッチしたラインあなたは別のアライメントアルゴリズムにフォールバックする必要があるユニークなラインを使い果たしたら

Answer 1

の間、各セクションに1-2を繰り返します。 Gitはその時点で標準diffアルゴリズムを使用します（Eugene MyersのO（ND）アルゴリズム）。

は例えば、2つのファイルがある場合：これらの行の間

a b c d 
a b c d 

各サブレンジは次のようになります。

a 12121 e 1212 b ee c x d 
a 21212 e 2121 b ye c d 

まず、忍耐アルゴリズムは、両方のファイルに一意であり、存在する任意の行を揃えます最初に忍耐アルゴリズムをやり直してから、忍耐アルゴリズムが何にもマッチしないならば、LCSアルゴリズムを実行します。最初のサブレンジで

1212 e 121 | ee | x 
2121 e 2  | ye | 

、e第忍耐差分パスは、2つの新たな部分範囲にそれを分割し、それを整列するように今の両方でユニークです。新しい最初の部分範囲（12121 vs 21212）は一意の線を持たないため、LCSアルゴリズムと位置合わせされます。第2の新しい部分範囲（1212対2121）は、LCSアルゴリズムの第2のパスで行われる。

（がた対EE）上述した第2のグループは、任意のユニークなラインを持っていないので、彼らは同様にLCSアルゴリズムを用いて整列されます。

最後のグループ化（x vs nothing）は、忍耐またはLCSアルゴリズムを実行せずに、xを削除として出力するだけです。