2

各コレクション内のオブジェクトが一意である場合、関連するビジネス上の問題を解決するのに非常にうまく機能しますが、両方のコレクションに一意でないオブジェクトが多数存在する場合、奇妙な結果になる傾向があります。

Patience Diff アルゴリズム (これも Longest Increase Subsequence に基づいています) を使用するアプローチは、一意でないオブジェクトが存在する場合に必要な結果を提供するようです。ただし、Patience Diff が適しているかどうかを判断する前に、適切な場合にそれを問題に適用するには、アルゴリズムをよりよく理解する必要があります。

ステップ 1 から 3 で何が起こるかは理解していますが、ステップ 4 で何が起こるかはわかりません。次に何が起こるか -- ドキュメントの残りの最初/最後の行との一致がない場合、確かにまだ終了していません (一意の行がもうないため)。それとも、1 つの文書内の固有でないすべてのブロックを、別の文書内の固有でないすべてのブロックと比較して、何らかの方法で最適な一致を選択しますか?

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

  1. 両方の最初の行が一致する場合は一致し、ペアが一致しなくなるまで 2 番目、3 番目などと一致します。
  2. 両方の最後の行が一致する場合は一致し、ペアが一致しなくなるまで、最後から 2 番目、最後から 2 番目などと一致します。
  3. 両側で正確に 1 回出現するすべての行を検索し、それらの行で最長共通サブシーケンスを実行して、それらを一致させます。
  4. 一致する行の間の各セクションで手順 1 ～ 2 を実行します。
4

1 に答える 1

2

一意の行を使い果たしたら、別の配置アルゴリズムにフォールバックする必要があります。Git はその時点で標準の diff アルゴリズム (Eugene Myers の O(ND) アルゴリズム) を使用します。

たとえば、2 つのファイルが次の場合:

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

まず、忍耐アルゴリズムは、両方のファイルに存在する一意の行を整列させます。

a b c d
a b c d

次に、これらの行の間の各部分範囲が再帰的に調整されます。最初に忍耐アルゴリズムが再度実行され、次に忍耐アルゴリズムが一致しない場合は LCS アルゴリズムが実行されます。

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

最初のサブ範囲でeは、両方で一意になったため、2 番目の忍耐差分パスがそれを調整し、それを 2 つの新しいサブ範囲に分割します。新しい最初のサブ範囲 (12121 対 21212) には一意の線がないため、LCS アルゴリズムに合わせられます。2 番目の新しいサブ範囲 (1212 対 2121) は、LCS アルゴリズムの 2 番目のパスで行われます。

上記の 2 番目のグループ化 (ee と ye) には固有の行がないため、LCS アルゴリズムを使用して整列されます。

最終的なグループ化 (x vs なし) は、忍耐または LCS アルゴリズムを実行せずに、単に x を削除として出力します。

于 2012-04-19T15:50:05.610 に答える