1. ホーム
  2. 質問と答え
  3. ドキュメント差分アルゴリズムはどのように機能しますか？

ドキュメント差分アルゴリズムはどのように機能しますか？

2009-10-02 20 views

答えて

3

ほとんどの最適化ソリューションO(ND) Myer 's algorithmであり、ここではアルゴリズムのアプローチはこれである：ここに詳述のように、それは、文書間の「差分」する能力を持っているとして理想的には、Word自体を自動化するに見ることができます私はオフィス2007のドキュメントを比較するために実装していました。 Link to algorithm paper

出典

2009-10-03 17:34:39 SunnyShah

+4

ペーパーリンクが動作しません.. –

+2

これは私のために働いています：http://www.xmailserver.org/diff2.pdf – Zamicol

15

diffは本質的にちょうどa solutionからlongest common sub-sequence problemです。

最適な解決策は、dynamic programmingという知識が必要です。解決するのはかなり複雑な問題です。

ただし、接尾辞ツリーを構築することによっても行うことができます。両方のアルゴリズムについては、hereを概説しています。

出典

2009-10-02 15:24:13

+1

これは通常、文書が文字またはバイトのストリームであると想定しているときです。しかしここで問題は単語の文書です。そのようなアルゴリズムを実装する前に、青い8pt Verdanaの「Hello World」と赤い10pt Arialなどの「Hello World」と同じ質問をする必要があります。 – quosoo

+1

もちろん、基本的なアルゴリズムでは、違いはありますが、アルゴリズムの核心は同じです。 –

2

ベンSが示すように、差分問題は、一般的に最も長い共通サブシーケンス問題を解決することによって対処することができます。より具体的には、The Hunt-McIlroy algorithmは、問題に適用された古典的なアルゴリズムの1つです（たとえば、Unixのdiffユーティリティの実装）。

出典

2009-10-02 15:28:29

28

一般に、diffは、Longest common subsequence problemによって解決されます。またDiff上のWikipediaの記事の「Algorithm"セクションを参照してください。

差分の操作が最長共通部分列 問題を解決 に基づいています

この問題では、アイテムの2つの 配列を有し：

a b c d f g h j q z 

    a b c d e f g i j k r x y z

、あなたが ボットに存在するアイテムの最長 シーケンスを見つけたいですhオリジナルの配列は、同じ オーダーにあります。つまり、新しい シーケンスを見つけるには、 から最初のシーケンスを取得します。 アイテムを削除し、2番目のシーケンスから を削除します。 このシーケンスを まで可能にすることもできます。このすべては、テキストベースで正常に動作し、 

e h i q k r x y 
    + - + - + + + +

は言った：この場合は、最長共通部分列 それは diffのような出力を得るためだけの小さな一歩だから 

a b c d f g j z

ですドキュメント。 Word文書は効果的にバイナリ形式であり、多数の書式設定情報とデータを含んでいるため、これはもっと複雑になります。 LCSの

Microsoft Word Tip: How to compare two documents for differences

出典

2009-10-02 15:30:03 CraigTP

+0

差分アルゴリズムを実装するには、バージョン間の差分のみを格納するか、バージョン間の相違を表示するかの2つの目的があります。これらは大きく異なっています（意図しない言葉はありません）。 LCSは通常、違いを表示するためにのみ使用できますが、最適なストレージのために、より高度なアルゴリズムが必要です。たとえば、ドキュメントのあるセクションから大きな部分を切り取り、別のセクションに貼り付けると、適切な記憶アルゴリズムがその情報を検出し、それを "ここに新しいデータがたくさん登場しました"と記憶しません。 –

+2

@Lasse - 同意。元の質問者がWord文書について話していたので、私は彼らが記憶面よりもむしろdiffingの "視覚的な"面にもっと興味があると思った。しかし、ストレージ側では、デルタエンコーディング/圧縮（http://en.wikipedia.org/wiki/Delta_encoding）などを調べることになります。 – CraigTP

関連する問題

 関連する問題