6

私は、2つの類似したソースコードファイルを比較するための差分テキストツールを作成中です。

そのような「差分」ツールはたくさんありますが、私のものは少し改善されるでしょう：

一連の行が両側で（つまり、両方のファイルで）不一致であることがわかった場合、それらの行を強調表示するだけでなく、これらの行の個々の変更も強調表示します（ここではこの行間比較と呼びます）。

私のやや機能するソリューションの例：

代替テキストhttp://files.tempel.org/tmp/diff_example.png

現在行われていることは、不一致の行のセットを取得し、それらの単一の文字をもう一度差分アルゴに通して、ピンクのハイライトを生成することです。

ただし、「元の2」を含む2番目の不一致のセットにはさらに作業が必要です。ここでは、最初の2つの右側の行（「追加された行a / b」）が追加され、3番目の行は左側の変更されたバージョンです。私のソフトウェアが、可能性のある変更と可能性のある改行の間のこの違いを検出することを望みます。

この単純な例を見ると、このケースをかなり簡単に検出できます。

レーベンシュタインのようなアルゴリズムでは、3から5のセットのすべての右の行の中で、5行目が左の3行目に最もよく一致することがわかりました。したがって、右側の3行目と4行目が追加されたことを差し引いて、インターを実行できます。 -左の行3と右の行5の行の比較。

ここまでは順調ですね。しかし、私はまだこれをこの目的のためのより一般的なアルゴリズムに変える方法に固執しています。

より複雑な状況では、一連の異なる線が両側に線を追加し、その間にいくつかの密接に一致する線がある可能性があります。これは非常に複雑になります。

左側の最初の行を右側の最良の行に一致させるだけでなく、その逆も同様に、他のすべての行と一致させる必要があります。基本的に、左側のすべての行を右側のすべての行と一致させる必要があります。最悪の場合、これにより交差が均等になる可能性があるため、新しく挿入された行と変更された行が簡単に明確になりません（注：実際に単純化されない限り、このようなブロックで移動された可能性のある行を処理したくありませんアルゴリズム）。

確かに、これが完璧になることは決してありませんが、私は今よりも良くしようとしています。あまり理論的ではないが実用的である（抽象的なアルゴリズムをよく理解していない）提案はありがたいです。

アップデート

私はLCSアルゴがどのように機能するかさえ理解していないことを認めなければなりません。文字列の2つの配列をフィードするだけで、一致しないシーケンスのリストが表示されます。私は基本的にここからのコードを使用しています：http：//www.incava.org/projects/java/java-diff

コードを見ると、2行が一致するかどうかをアルゴリズムに伝える役割を担う1つの関数equal（）が見つかります。Pavelが提案したことに基づいて、それが私が変更を加える場所であるかどうか疑問に思います。しかし、どのように？この関数はブール値のみを返します。一致の品質を識別できる相対値は返しません。そして、同様の線がまだ等しいと見なされるかどうかを決定する固定のレーベンシュタイン配給を単純に使用することはできません-問題の線のセット全体に自己採用するものが必要になります。

つまり、基本的に言っているのは、（完全に）一致しない線の相対的な類似性に関連するファジー値をどこに適用するかがまだわからないということです。

4

3 に答える 3

3

レーベンシュタイン距離は、ある文字列を別の文字列に変換する「編集スクリプト」の概念に基づいています。これは、ギャップ文字を挿入してDNA配列を整列させるために使用されるニードルマン-ブンシュアルゴリズムと非常に密接に関連しています。このアルゴリズムでは、動的計画法を使用してO（ nm ）時間でスコアを最大化する整列を検索します。文字間の完全一致はスコアを上げますが、不一致または挿入されたギャップ文字はスコアを下げます。AACTTGCCAとの配置例AATGCGAT：

AACTTGCCA-
AA-T-GCGAT
(6 matches, 1 mismatch, 3 gap characters, 3 gap regions)

一番上の文字列は、一番下の「最終」シーケンスに変換している「開始」シーケンスであると考えることができます。下部にギャップ文字が含ま-れている各列は削除であり-、上部にが付いている各列は挿入であり、異なる（ギャップのない）文字が含まれている各列は置換です。上記のアラインメントには2つの削除、1つの挿入、1つの置換があるため、レーベンシュタイン距離は4です。

これは、同じレーベンシュタイン距離での同じ文字列の別の配置です。

AACTTGCCA-
AA--TGCGAT
(6 matches, 1 mismatch, 3 gap characters, 2 gap regions)

ただし、ギャップの数は同じですが、ギャップ領域が1つ少ないことに注意してください。生物学的プロセスは、複数の個別のギャップよりも広いギャップを作成する可能性が高いため、生物学者はこの調整を好みます。プログラムのユーザーも同様です。これは、計算するスコアのギャップ領域の数にもペナルティを課すことによって実現されます。長さnおよびmの文字列に対してこれを実現するためのO（nm ）アルゴリズム1982年に後藤によって「生物学的配列を照合するための改良されたアルゴリズム」と呼ばれる論文で与えられました。残念ながら、論文の無料の全文へのリンクは見つかりませんでしたが、「シーケンスアラインメント」と「アフィンギャップペナルティ」をグーグルで検索すると、役立つチュートリアルがたくさんあります。

一般に、一致、不一致、ギャップ、およびギャップ領域の重みを選択すると、配置が異なりますが、ギャップ領域のスコアが負の場合は、上部の配置よりも下部の配置が優先されます。

これはすべてあなたの問題と何の関係がありますか？ 適切なギャップペナルティ（いくつかの経験的テストで得られた）を使用して個々の文字に後藤のアルゴリズムを使用すると、与えた例のようにひどい見た目の配置の数が大幅に減少するはずです。

効率に関する考慮事項

理想的には、文字に対してこれを実行し、行を完全に無視することができます。アフィンペナルティは、可能な限り多くの行にまたがるブロックに変更をクラスター化するために機能するためです。ただし、実行時間が長いため、最初に行をパスしてから、同一ではないすべての行を入力として使用して、文字に対してアルゴリズムを再実行する方が現実的です。このスキームでは、同じ線の共有ブロックは、一致する重みが膨らんだ単一の「文字」に圧縮することで処理できます。これにより、「交差」が表示されなくなります。

于 2010-02-10T10:53:46.523 に答える
0

これが、他の誰かが私に気づかせた解決策の1つです。

私の元々のアプローチは次のようなものでした。

  1. テキストを別々の行に分割し、LCSアルゴリズムを使用して、一致しない行のブロックがある場所を特定します。
  2. いくつかのスマートアルゴ（この質問について）を使用して、これらの行のどれが厳密に一致するかを把握します。つまり、これらの行がリビジョン間で変更されたことを示します。
  3. 一致しない行を完全に新しいものとしてマークしながら、LCSを使用して、これらの厳密に一致する行を1行ずつ比較します。

これにより、ソースコードのリビジョンを比較するときに変更をより視覚的に表示できるようになりますが、通常ははるかに単純なアプローチで十分であることがわかりました。それはこのように動作します：

  1. 同上。
  2. 一致しない行の左右のブロックを取得し、それらの行を連結して、トークン化します（言語固有のトークン/単語、または1文字のみ）
  3. トークンの2つの配列にLCSアルゴリズムを適用します。

私の最初の質問に答えた人は、私がいつもこれを行うことを知っていると思っていたのかもしれませんが、私は行ごとの比較に非常に重点を置いていたので、それらを連結して行のセットにLCSを適用することはありませんでした、行ごとに処理する代わりに。

したがって、このアプローチでは、当初の意図ほど詳細な変更情報は提供されませんが、この質問を書いたときに昨日始めたものよりも結果が改善されます。

この質問はもうしばらく開いたままにしておきます-おそらく他の誰かがこれをすべて読んでも完全な答えを提供できます（Pavelとrandom_hackerはいくつかの提案を提供しましたが、まだ完全な解決策ではありません-とにかく、有益なコメントをありがとう）。

于 2010-02-10T12:23:23.687 に答える
0

レーベンシュタインのようなアルゴリズムでは、3から5のセットのすべての右の行の中で、5行目が左の3行目に最もよく一致することがわかりました。したがって、右側の3行目と4行目が追加されたことを差し引いて、インターを実行できます。 -左の行3と右の行5の行の比較。

決定したら、同じアルゴリズムを使用して、これら2つのチンクのどの線が互いに一致するかを決定します。ただし、わずかな変更を加える必要があります。アルゴリズムを使用して等しい行を一致させると、行が一致する場合と一致しない場合があり、使用したテーブルのセルに0または1が追加されました。

1つのチャンク内の文字列を比較する場合、それらの一部は他の文字列よりも「同等」です（Orwellに確認）。したがって、これまでに最も一致するシーケンスを検討するときに、0から1までの実数をセルに追加できます。

このメトリック（0から1）を計算するために、遭遇する文字列の各ペアに適用できます...そうです、同じアルゴリズムをもう一度（実際には、レーベンシュタインアルゴリズムの最初のパスを実行したときにすでにこれを実行しました）。これにより、LCSの長さが計算され、2つの文字列の平均の長さに対する比率がメトリック値になります。

または、diffツールの1つからアルゴリズムを借りることができます。たとえば、vimdiff必要な一致を強調表示できます。

于 2010-02-09T21:05:30.427 に答える