c# - テキスト差分アルゴリズム

Question

2つのテキストファイルを比較してそれらの違いを強調し、（さらに良い！）意味のある方法でそれらの違いを計算できるアルゴリズムが必要です（2つの類似ファイルは2つの異なるファイルよりも高い類似スコアを持ち、「類似」という単語が必要です）通常の用語で定義されます）。実装は簡単に聞こえますが、そうではありません。

実装はc＃またはpythonにすることができます。

ありがとう。

score 30 · Accepted Answer

NeilFraserのコードと記事をご覧になることをお勧めします。

google-diff-match-patch

現在、Java、JavaScript、C ++、Pythonで利用できます。言語に関係なく、各ライブラリは同じAPIと同じ機能を備えています。すべてのバージョンには、包括的なテストハーネスもあります。

Neil Fraser：DiffStrategies-理論と実装に関する注意事項

score 26 · Accepted Answer

Pythonには、他の人が示唆しているように、difflibがあります。

difflibはSequenceMatcherクラスを提供します。これを使用して、類似度を指定できます。関数の例：

def text_compare(text1, text2, isjunk=None):
    return difflib.SequenceMatcher(isjunk, text1, text2).ratio()

score 23 · Accepted Answer

difflibを見てください。（Python）

これにより、さまざまな形式で差分が計算されます。次に、コンテキスト差分のサイズを、2つのドキュメントの違いの尺度として使用できますか？

score 12 · Accepted Answer

私の現在の理解では、Shortest Edit Script (SES) の問題に対する最善の解決策は、Hirschberg の線形空間改良を使用した Myers の「中蛇」法です。

Myers アルゴリズムについては、次のドキュメントで説明されています。

E. マイヤーズ、「O(ND) 差分アルゴリズムとそのバリエーション」、
アルゴリズム 1、2 (1986)、251-266。

GNU diff ユーティリティは Myers アルゴリズムを使用します。

あなたが話す「類似度スコア」は、文献では「編集距離」と呼ばれます。これは、あるシーケンスを別のシーケンスに変換するために必要な挿入または削除の数です。

多くの人がレーベンシュタイン距離アルゴリズムを引用していますが、これは実装が簡単ですが、非効率的であり (おそらく巨大な n*m 行列を使用する必要があります)、「編集スクリプト」を提供しないため、最適なソリューションではありません。 " これは、あるシーケンスを別のシーケンスに、またはその逆に変換するために使用できる一連の編集です。

Myers / Hirschberg の優れた実装については、以下を参照してください。

http://www.ioplex.com/~miallen/libmba/dl/src/diff.c

それが含まれている特定のライブラリはもはや維持されていませんが、私の知る限り、diff.c モジュール自体はまだ正しいです。

マイク

score 10 · Accepted Answer

Bazaarには、 patience diff（そのページのコメントに詳細があります）と呼ばれる代替の差分アルゴリズムが含まれています。これは、従来のdiffアルゴリズムよりも優れていると言われています。バザールディストリビューションのファイル「patiencediff.py」は、単純なコマンドラインフロントエンドです。

score 5 · Accepted Answer

線よりも細かい粒度が必要な場合は、レーベンシュタイン距離を使用できます。レーベンシュタイン距離は、2つのテキストをどのように類似させるかについての簡単な尺度です。
また、これを使用して編集ログを抽出したり、SOの編集履歴ページと同様に非常にきめ細かい差分を作成したりすることもできます。ただし、レーベンシュタイン距離の計算にはCPUとメモリを大量に消費する可能性があるため、ダグラスレダーが示唆したように、difflibを使用する方が高速になる可能性が高いことに注意してください。

Cf. また、この答え。

score 3 · Accepted Answer

paradojaが言及したように、レーベンシュタイン距離があると述べたように、多くの距離メトリックがありますが、NYSIISとSoundexもあります。Python の実装に関しては、以前はpy-editdistとADVASを使用していました。どちらも、単一の数値をスコアとして返すという意味で優れています。最初に ADVAS をチェックしてください。ADVAS には多数のアルゴリズムが実装されています。

score 2 · Accepted Answer

前述のように、difflibを使用します。差分出力を取得すると、さまざまな文字列のレーベンシュタイン距離を見つけて、それらの違いの「値」を得ることができます。

score 1 · Accepted Answer

Longest Common Subsequence (LCS) 問題の解決策を使用できます。このソリューションを最適化する可能な方法についての説明も参照してください。

score 0 · Accepted Answer

変更されたファイル内の新しいデータの量を計算するために、私が別の機能に採用した 1 つの方法は、おそらくあなたにも役立つ可能性があります。

おそらく同じファイルの古いバージョンと新しいバージョンの2つのファイルを取り、「違い」を計算できますが、通常の意味ではありません。基本的に、古いバージョンで実行できる一連の操作を計算して、新しいバージョンと同じ内容になるように更新します。

これを最初に説明した機能に使用し、どれだけのデータが新しいかを確認するために、操作を簡単に実行し、古いファイルから逐語的にコピーされたすべての操作、0-factor を持つすべての操作、および新しいテキストを挿入したすべての操作について調べました。 (古いファイルでは発生しなかったため、パッチの一部として配布されます) には 1 因子がありました。すべての文字にこのファクトリが与えられ、基本的に 0 と 1 の長いリストが得られました。

あとは、0 と 1 を合計するだけでした。あなたの場合、私の実装では、0 に比べて 1 の数が少ないということは、ファイルが非常に似ていることを意味します。

この実装は、変更されたファイルが古いファイルからのコピーを順不同で挿入した場合、または重複を挿入した場合 (つまり、ファイルの先頭から一部をコピーし、それを下部近くに貼り付けた場合) も処理します。古いファイルからの同じ元の部分のコピー。

コピー/貼り付け操作に何らかの「新しい要因」を与えるために、最初のコピーが0としてカウントされ、同じ文字の後続のコピーが次第に高くなるように、コピーの重み付けを実験しましたが、プロジェクトは破棄されました。

興味があれば、Subversion リポジトリから差分/パッチコードを入手できます。

score 0 · Accepted Answer

Fuzzyモジュールを見てみましょう。これは、soundex、NYSIIS、および double-metaphone 用の高速な (C で記述された) ベースのアルゴリズムを備えています。

適切な紹介は、http: //www.informit.com/articles/article.aspx?p=1848528にあります。

c# - テキスト差分アルゴリズム

11 に答える 11

Related

Reference