7

私はFlex/AS3で（簡単にするために）XMLエディターで作業しています。元に戻す/やり直し機能を提供する必要があります。

もちろん、1つの解決策は、編集のたびにソーステキスト全体を保存することです。ただし、メモリを節約するために、代わりにdiffを保存したいと思います（これらのdiffは、自動保存のために更新をサーバーに送信するためにも使用されます）。

私の質問は、これらのXMLの変更を追跡するためにプレーンテキストのdiffアルゴリズムを使用できますか？

インターネットでの私の調査は、私がそうすることができないことを示しています。しかし、私は明らかに何かが欠けています。平文diffは、次のような機能を提供します。

diff(text, text') -> diffs
patch(text, diffs) -> text'

XMLは単なるテキストですが、なぜdiff（）とpatch（）を使用してテキストを確実に変換できないのでしょうか。

例：私が詩人だとしましょう。詩を書くときは、ファンキーな句読点をたくさん使います... <、/、>のように。（これでどこに行くのかわかるかもしれません...）diffを使用して元に戻す/やり直し機能を提供するアプリケーションで詩を書いている場合、編集を元に戻す/やり直すと詩が文字化けしますか？ただのテキストです！なぜそれがアルゴリズムに違いをもたらすのですか？

私は明らかにここで何かを得ていません...説明してくれてありがとう！:)

アップデート：

平文アルゴリズムを使用したXMLの差分に関して私が遭遇したいくつかの議論：

また、コマンドパターンがUndo/Redoを実装するためのより良い方法である可能性が高いことを理解しています。簡単にするためにユースケースを簡略化しましたが、それでもXML差分が最善のアプローチだと思います。

4

4 に答える 4

14

私はGoogleのプレーンテキストのdiff/match/patchライブラリの作成者です。

重要な問題は、パッチが正確かどうかです。理想的な世界では：

  diff(old_text, new_text) -> edits
  patch(edits, old_text) -> new_text

ベーステキスト（old_text）は両方の操作で同じであることに注意してください。この理想的なケースでは、コンテンツのタイプに関係なく、単純なプレーンテキストの差分とパッチが完全に機能します。このケースが当てはまる場合は、これで完了です。

問題はファジーパッチにあります。対応する例を次に示します。

  diff(old_text, new_text) -> edits
  patch(edits, old_forked_text) -> new_forked_text

ベーステキストは両方の操作で同じではないことに注意してください。それらは似ているはずですが、パッチ操作は今、それが何をすべきかについて「判断」を使用する必要があります。編集で指定されたとおりに完全に適合するパッチもあれば、位置を微調整する必要があるパッチもあれば、コンテキストを変更するために微調整する必要があるパッチもあります。まったく適合しないため、削除する必要があるパッチもあります。パッチ適用アルゴリズムが決定を行うときにXMLの構造を認識していない場合は、XMLの不正が発生する可能性があります。サンプルは次のとおりです。

  old_text = Jabberwock<SPAN>Hello<SPAN>World</SPAN></SPAN>
  new_text = Jabberwock<DIV>Hello<SPAN>World</SPAN></DIV>
  diff(old_text, new_text) -> edits
  edits = ["SPAN" -> "DIV" @ character 11,
           "SPAN" -> "DIV" @ character 41]
  old_forked_text = <SPAN>Hello<SPAN>World</SPAN></SPAN>
  patch(edits, old_forked_text) -> new_forked_text
  new_forked_text = <SPAN>Hello<DIV>World</SPAN></DIV>

これを注意深く見てみましょう。元の差分は2つの編集を返し、最も外側のSPANをDIVに変更します。簡単な変更。残念ながら、この編集が適用されているテキストは元のテキストから変更されています。「Jabberwock」という単語は削除されました。これで、最初のSPAN-> DIVの変更は、最初のタグではなく、2番目のSPANタグと一致します。パッチアルゴリズムはXMLの規則を認識しないため、タグが不正にネストされます。

プレーンテキストパッチを使用するときに有効なXMLを保証できるハックがいくつかありますが、柔軟性が失われます（元の質問には、これについて書いたwikiページへのリンクが既にあります）。XMLにパッチを適用するための究極のソリューションは、もちろん、XML対応の差分およびパッチアルゴリズムを使用することです。これらは非常に複雑で高価ですが、存在します。Googleは、XML分野で（特にDocEngに関して）行った素晴らしい仕事にちなんで、TancredLindholmとSebastianRönnauという名前を付けました。

他に追加できるものがあれば教えてください。

-ニールフレイザー

于 2010-03-12T09:15:28.603 に答える
1

私は常にBeyondCompareを使用してXMLドキュメントを比較しています。XMLをある程度理解します。

テキストを比較して可能な限り最高の仕事をするために、2つのドキュメントを前処理する必要があるかもしれません。たとえば、一部のXMLドキュメントでは、一部の要素の順序は重要ではない場合があります。それは確かにあなたのdiffツールにとって重要です！ソートされた2つのファイルを比較する前に、これらの要素を両方のファイルで共通の順序にソートするXML変換を使用してXMLを前処理する必要がある場合があります。

また、両方のドキュメントに同じインデントを使用する必要があります。各要素を新しい行で開始し、各レベルにスペースを使用して同じ量のインデントを使用すると便利です。ドキュメントが非常に深くなる場合は、比較が画面に収まるように、レベルごとに1つまたは2つのスペースのみを使用することをお勧めします。1行に1つの属性を使用することもできます（属性を共通の順序に並べ替えることもできます）。

于 2010-03-12T02:31:02.597 に答える
1

元に戻る/やり直しポイント間のデータの唯一の「所有者」である場合は、もちろん、それらにプレーンテキストの差分を使用できます。ご指摘のとおり、これは一連の変換に相当します。

ただし、提供する操作によっては、プレーンテキストの差分が元に戻る/やり直しの記録にリモートで最適に近くない場合があり、特定の場合に特化する必要がある場合があります。わずか数バイトのオーバーヘッドに加えて検索と置換の文字列であるReplaceAllコマンドを記録することを想像してみてください。これにより、大量の平文の差分が生成される可能性があります。

より広い文脈では、これらのドキュメントの外部編集を許可し、サーバーにデルタを保存する方法についてもっと考えている場合は、gitまたは他のバージョン管理システムを模倣しています。コマンドを記録するだけでは明らかに変換の唯一のソースではないため、何らかの差分アルゴリズムを使用する必要があります。この時点で、元に戻る/やり直しとバージョン管理を組み合わせ始めているので、ユーザーにとってこれらの概念を混乱させることについて真剣に考えたいと思うかもしれません。

編集セッション内と同じように元に戻す/やり直しを続け、ファイルが開いている間は外部編集を禁止します。これにより、前述のように、幅広いケースに合わせてコマンドの記録を最適化できます。

それを超えて、従来のバージョン管理（gitのラッピングを検討）を使用するか、エディターの外部で変更されたファイルに対処する独自の方法を実装します。

于 2010-03-12T02:43:44.577 に答える
-1

特に人間がxmlを1行ずつ書き込む場合は、xmlにtextdiffを使用できると思います。それができないと言っている情報はわかりませんが、スペース文字（スペース、タブ、改行など）は、プレーンテキストファイルの場合とは多少異なるという事実に基づいていると思います。 XMLの観点からは2つの異なるテキストファイルが同一になる可能性があります。しかし、繰り返しになりますが、人間を対象とした編集者にとって、なぜできないのかわかりません。

于 2010-03-12T02:27:42.620 に答える