3

ネストされた文字列のリストで構成されるデータ型のオンライン エディターで作業しています。単一の値が変更されるたびに構造全体を転送しようとすると、トラフィックが耐えられなくなる可能性があることに注意してください。そこで、トラフィックを減らすために、差分ツールを適用することを考えました。問題は次のとおりです: 2 つのツリーの差分を見つけて報告するにはどうすればよいですか? 例えば：

["ah","bh",["ha","he",["li","no","pz"],"ka",["kat","xe"]],"po","xi"] ->
["ah","bh",["ha","he",["li","no","pz"],"ka",["rag","xe"]],"po","xi"]

そこでは、唯一の変化は"kat" -> "rag"木の奥深くにあります。差分ツールのほとんどは、フラット リスト、ファイルなどで機能しますが、ツリーでは機能しません。その特定の問題に関する文献は見つかりませんでした。そのような変化を報告するための最小限の方法と、それを見つけるための効率的なアルゴリズムは何ですか?

4

3 に答える 3

3

XML は、一般的に使用されるツリー状のデータ構造であり、構造化されたドキュメントや、経時変化を監視する必要があるその他の階層オブジェクトを記述するためによく使用されます。そのため、ツリーの差分に関する最近の作業のほとんどが XML のコンテキストで行われたことは驚くべきことではありません。

これは 2006 年の調査で、役立つ可能性のある多くのリンクがあります: Change Detection in XML Trees

TreePatch と呼ばれるオープン ソースの実装を伴っていた、上記のより興味深いリンクの 1 つですが、現在は廃止されているようです: Kyriakos Komvoteas の論文

Daniel Ehrenbergによる別の調査記事には、さらに多くの参照が含まれています。(それはhttp://cstheory.stackexchange.comの質問から来ています)

幸運を。

于 2013-10-08T19:41:17.643 に答える
2

2 つのツリーの違いを見つけることは、ツリー内を検索するようなものです。あなたが知っている唯一の違いは、両方の底にたどり着かなければならないということです。両方のツリーを同時に検索し、違いが見つかったら、一方を別のツリーに変更することができます (それが目標の場合 - 毎回 1 つを送信せずに同一のツリーになるようにする)。

2 つのツリーの比較で見つけたいくつかのリンク:

親の変更を判断するために 2 つのツリーを比較するにはどうすればよいですか?

ツリー構造間の違いを検出する

差分アルゴリズム

これらのリンクが役に立つことを願っています。:)

于 2013-10-08T20:16:24.540 に答える
2
  1. 任意の一般的な DIFF アルゴリズムを使用できます。すぐに使用できるライブラリを見つけることは問題ではありません。
  2. ZLIB ライブラリを使用できる場合は、別の解決策を提案できます。いくつかのトリックで、このライブラリを使用して、2 つの任意のバイナリ間の非常に圧縮された差分を送信することができます。それらを A と B (および差分 Bc) と呼びましょう。

サイド 1:

  1. ZLIB ストリームの初期化
  2. A->Ac を Z_SNC_FLUSH で圧縮します (結果は必要ないので、Ac を解放できます)
  3. Z_SNC_FLUSH で B->Bc を圧縮
  4. ZLIB ストリームの初期化解除

最初にブロック A を圧縮し、ZLib にすべてのデータの処理と出力を強制する特別なフラグを付けます。しかし、圧縮状態はリセットされません! ブロック B を圧縮するとき、コンプレッサーは既に A のサブシーケンスを認識しており、ブロック B を非常に効率的に圧縮します (共通点が多い場合)。送信するデータは Bc のみです。

サイド 2:

  1. ZLIB ストリームの初期化
  2. Z_SNC_FLUSH で A->Ac を圧縮
  3. ZLIB ストリームの初期化解除

圧縮したのとまったく同じブロックを解凍する必要があります。それがAcが必要な理由です。

  1. ZLIB ストリームを再度初期化する
  2. Z_SNC_FLUSH で Ac->A を解凍
  3. Z_SNC_FLUSH で Bc->B を解凍
  4. ZLIB ストリームの初期化解除

これで、Ac-A を解凍できます (ブロック A のすべてのサブシーケンスを解凍するのに役立ちます)。最後に Bc->B を解凍します。

ZLib のちょっと変わったトリッキーな使い方ですが、この場合の Bc は単に圧縮されたブロック B ではなく、実際にはブロック A と B の圧縮された差分です。ZLIB 辞書のサイズがブロックのサイズと同程度であれば、非常に効率的です。 A. 巨大なデータ ブロックの場合、あまり効率的ではありません。

于 2013-10-08T20:31:52.323 に答える