XML の変更を追跡するためにプレーンテキスト diff アルゴリズムを使用できますか?

https://stackoverflow.com/questions/2430083

19-09-2019
|

質問

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

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

私の質問は、これらの XML 変更を追跡するために平文 diff アルゴリズムを使用できるかということです。

インターネットでの調査によると、私は できない そうする。しかし、明らかに何かが欠けています。プレーンテキスト diff は、次のような機能を提供するとされています。

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

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

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

ここでは明らかに何かがわかりません...説明してくれてありがとう!:)

アップデート：

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

また、元に戻す/やり直しを実装するには、コマンドパターンの方が適している可能性が高いことも理解しています。わかりやすくするためにユースケースを簡略化しましたが、XML の差分計算が最良のアプローチであると今でも考えています。

解決

私はGoogleからのプレーンテキスト差分/マッチ/パッチライブラリの作者です。

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

  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の構造を認識していない場合、あなたは非常によくmalfromed 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>

のは、慎重にこの1を見てみましょう。オリジナルのdiffはDIVに最も外側のSPANを変更、2本の編集を返されました。簡単な変更。残念ながら、この編集が適用されているテキストは、オリジナルから変更されています。単語「とかげ」は削除されました。今最初SPAN-> DIVの変更は、第二のSPANタグではなく、最初の1にまで一致しています。パッチアルゴリズムは、XMLのルールを認識していないので、それは違法ネストされたタグになります。

があり、プレーンテキストのパッチを使用するときに有効なXMLを保証することができ、いくつかのハックがありますが、それらは、（元の質問は、すでに私はこれについて書いたWikiページへのリンクがあります）柔軟性のある損失をもたらします。 XMLのパッチ適用のための究極のソリューションは、XML-のdiffとpatchアルゴリズムを使用することはもちろんです。これらは、はるかに複雑かつ高価であるが、彼らは存在しています。グーグル、彼らは（特にDocEngに関して）XMLフィールドで行われてきた偉大な仕事の名前タンクレードリンドホルムとセバスチャンRönnauます。

私は追加することができない何かがあるかどうか私に教えてくださいます。

- ニール・フレーザー

他のヒント

私は超えては、XML文書を比較するために、すべての時間をの比較使用しています。これは、ある程度、XMLを理解しています。

あなたは、可能な限り最高の仕事をするためのテキスト比較のためのために、2つの文書を事前処理する必要があるかもしれません。例えば、いくつかのXML文書では、いくつかの要素の順序は重要ではないかもしれません。それは確かにあなたの差分ツールには関係します！次の2つのソートされたファイルを比較する前に、両方のファイルに共通するために、これらの要素を並べ替えを変換XMLを使用してXMLを事前処理する必要がある場合があります。

また、両方の文書に同じインデントを使用するようにするつもりです。私はそれが便利な新ライン上の各要素を開始するために、各レベルのために、スペースで、インデントの同じ量を使用することを見つけます。あなたの文書は非常に深い取得する場合は、画面上のフィットを比較するように、レベルごとに1つまたは2つのスペースを使用したいと思います。あなたも、1行に1つの属性を使用して（と、共通の順序に属性をソートする）必要があります。

あなたはもちろん、あなたのアンドゥ/リドゥポイント間のデータの唯一の「所有者」であれば、

あなたは彼らのために平文差分を使用することができます。あなたが指摘するように、それは変換の集合になる。

あなたが提供する操作に応じて、しかし、平文diffは/リドゥを元に戻すと、あなたは、特定の場合を専門とする必要があるかもしれませ記録のためにリモートでほぼ最適ではないかもしれません。ただ検索に加えて、わずか数バイトのオーバーヘッドなると、文字列を置換する可能性がでReplaceAllコマンドの記録を想像してみてください。これは、大規模な平文差分を生成することができます。

より広い文脈で、あなたはこれらの文書の外部編集を可能にし、あなたはgitのか、他のバージョン管理システムを模倣している、サーバー上のデルタを保存する方法についての詳細を考えている場合。あなたは自分のコマンドを記録することは、明らかに変換する唯一の源ではないので、差分アルゴリズムのいくつかの種類を使用する必要があります。この時点で、アンドゥ/バージョン管理をやり直し、あなたのユーザーのためにこれらの概念を混乱についてハード考えたくも混在し始めています。

私は、編集セッション内としてアンドゥ/リドゥを維持し、ファイルが開いている間、外部の編集を禁止します。それは私が上記の言ったように、あなたが広範囲の場合のために、あなたのコマンドの記録を最適化することができます。

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

私は人間がラインでXMLラインを書き込む場所あなたが特にあなたの場合には、XMLのテキスト差分を使用することができると思います。私はあなたがそれを行うことができないと言ってしまったどのような情報を知らないが、私はその文が空白文字（スペース、タブ、改行が...）彼らは、プレーンテキストファイルであることを多少異なっているという事実に基づいていたと思い、その二つの異なるテキストファイルをもたらす可能性がXMLの観点から同一です。なぜあなたはできませんが、再び、人間をターゲットエディタのため、私は表示されません。

ライセンス： CC-BY-SA と帰属

所属していません StackOverflow