テキスト差分アルゴリズム
https://stackoverflow.com/questions/145607
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
2つのテキストファイルを比較し、それらの違いを強調し、（さらに良いことに）意味のある方法で違いを計算できるアルゴリズムが必要です（2つの類似したファイルは、2つの異なるファイルよりも高い類似度スコアを持つ必要があります） 「類似」は通常の用語で定義されています）。実装は簡単に聞こえますが、そうではありません。
実装はc＃またはpythonで可能です。
ありがとう。
解決
Pythonには、 difflib があり、他の人も示唆しています。
difflib は SequenceMatcher クラスを提供します。類似率を与えるために使用できます。関数の例：
def text_compare(text1, text2, isjunk=None):
return difflib.SequenceMatcher(isjunk, text1, text2).ratio()
他のヒント
Neil Fraserのコードと記事をご覧になることをお勧めします。
現在Javaで利用可能、 JavaScript、C ++、およびPython。とにかく 言語の各ライブラリは、 同じAPIと同じ機能。 すべてのバージョンには包括的な テストハーネス。
Neil Fraser：Diff Strategies -理論と実装に関するメモ
difflib をご覧ください。 （Python）
これにより、さまざまな形式で差分が計算されます。次に、コンテキストdiffのサイズを、2つのドキュメントの違いの尺度として使用できますか？
Bazaar には、 patience diff （そのページのコメントに詳細があります）は、従来のdiffアルゴリズムよりも優れていると主張されています。 bazaarディストリビューションのファイル「patiencediff.py」は、単純なコマンドラインフロントエンドです。
現在の理解では、Shortest Edit Script（SES）問題の最善の解決策はMyers＆quot; middle-snake＆quot;です。ヒルシュベルク線形空間精密化による方法。
Myersアルゴリズムの説明は次のとおりです。
E。マイヤーズ、「An O（ND）Difference」 アルゴリズムとそのバリエーション」、
Algorithmica 1、2（1986）、251-266。
GNU diffユーティリティはMyersアルゴリズムを使用します。
「類似度スコア」あなたが話すのは「距離の編集」と呼ばれます。文献では、1つのシーケンスを別のシーケンスに変換するために必要な挿入または削除の数です。
多くの人々がレーベンシュタイン距離アルゴリズムを引用しているが、それは実装が容易ではあるが、非効率的であり（おそらく巨大なn * m行列の使用を必要とする）最適解ではないことに注意してください「スクリプトの編集」これは、1つのシーケンスを別のシーケンスに、またはその逆に変換するために使用できる編集のシーケンスです。
優れたMyers / Hirschberg実装については、次を参照してください。
http://www.ioplex.com/~miallen /libmba/dl/src/diff.c
含まれる特定のライブラリは維持されなくなりましたが、私の知る限り、diff.cモジュール自体は依然として正しいです。
マイク
線よりも細かい粒度が必要な場合は、レーベンシュタイン距離を使用できます。レーベンシュタイン距離は、2つのテキストが似ているかどうかの簡単な尺度です。
また、これを使用して編集ログを抽出し、SOの編集履歴ページにあるような非常にきめの細かい差分を作成することもできます。
ただし、レーベンシュタイン距離は計算にかなりCPUとメモリを消費する可能性があるため、ダグラス・レーダーが示唆したように、difflibを使用するとより高速になる可能性が高いことに注意してください。
Cf。また、この回答。
パラドジャで言及されているように、レーベンシュタイン距離がありますが、もあります。 NYSIIS および Soundex 。 Pythonの実装に関しては、 py-editdist および ADVAS 以前。どちらも、スコアとして単一の数値を取得できるという意味で優れています。最初にADVASをチェックしてください。それはたくさんのアルゴリズムを実装しています。
前述のとおり、difflibを使用します。差分出力が得られると、異なる文字列のレーベンシュタイン距離を見つけることができます「値」どれだけ違うのか。
Longest Common Subsequence（LCS）問題の解決策を使用できます。このソリューションを最適化する方法についての説明も参照してください。
変更されたファイルの新しいデータの量を計算するために、私が別の機能に使用した1つの方法は、おそらく同様に機能します。
2つのファイル（おそらく同じファイルの古いバージョンと新しいバージョン）を取得して「差分」を計算できるようにするdiff / patch実装C＃がありますが、通常の意味ではありません。基本的に、古いバージョンで実行できる一連の操作を計算して、新しいバージョンと同じ内容に更新します。
これを最初に説明した機能に使用し、新しいデータの量を確認するために、単純に操作を実行し、古いファイルからコピーしたすべての操作、0ファクターを持つ操作、および挿入された新しいテキスト（古いファイルでは発生しなかったため、パッチの一部として配布された）には1要素がありました。すべてのキャラクターにこのファクトリが与えられ、基本的に0と1の長いリストが与えられました。
その後、0と1を集計するだけでした。あなたの場合、私の実装では、0に比べて1の数が少ないということは、ファイルが非常に似ていることを意味します。
この実装は、変更されたファイルが古いファイルのコピーを順不同で挿入した場合や、重複した場合（つまり、ファイルの先頭から一部をコピーして下部近くに貼り付けた場合）も処理します。両方とも古いファイルの同じ元の部分のコピーになります。
最初のコピーが0としてカウントされ、コピー/貼り付け操作に「新しい係数」を与えるために、同じ文字の最初のコピーが次第に高い係数を持つように、コピーを計量して実験しましたが、プロジェクトが廃棄されたため終了しました。
興味がある場合は、Subversionリポジトリからdiff / patchコードを入手できます。
ファジーモジュールをご覧ください。 soundex、NYSIIS、ダブルメタフォン用の高速（Cで記述された）ベースのアルゴリズムがあります。
良い紹介は、 http：//www.informitにあります。 com / articles / article.aspx？p = 1848528
