3

我正在使用由嵌套字符串列表组成的数据类型的在线编辑器。请注意，如果我要在每次更改单个值时传输整个结构，流量可能会变得难以忍受。所以，为了减少流量，我考虑过应用差异工具。问题是：如何找到并报告两棵树的差异？例如：

["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"在树的深处。大多数 diff 工具都适用于平面列表、文件等，但不适用于树。我找不到有关该特定问题的任何文献。报告这种变化的最小方法是什么，找到它的有效算法是什么？

4

3 回答 3

3

XML is a tree-like data structure in common use, often used to describe structured documents or other hierarchical objects whose changes over time need to be monitored. So it should be unsurprising that most of the recent work in tree diffing has been in the context of XML.

Here's a 2006 survey with a lot of possibly useful links: Change Detection in XML Trees

One of the more interesting links from the above, which was accompanied by an open source implementation called TreePatch, but now seems to be defunct: Kyriakos Komvoteas' thesis

Another survey article, by Daniel Ehrenberg, with a bunch more references. (That one comes from a question on http://cstheory.stackexchange.com)

Good luck.

于 2013-10-08T19:41:17.643 回答
2

找到两棵树之间的差异看起来有点像在树中搜索。您知道的唯一区别是您必须深入了解它们。您可以同时搜索两棵树，当您发现差异时，将一棵更改为另一棵（如果这是您的目标 - 最终得到相同的树，而不是每次都发送一棵）。

我在 diff'ing 2 树上找到的一些链接：

我如何区分两棵树以确定父母的变化？

检测树结构之间的差异

差异算法

希望这些链接对您有用。:)

于 2013-10-08T20:16:24.540 回答
2
  1. 您可以使用任何通用的 DIFF 算法，找到现成的库不是问题。
  2. 如果您可以使用 ZLIB 库，我可以建议另一种解决方案。通过一些技巧，可以使用这个库在两个任意二进制文件之间发送非常压缩的差异，我们称它们为 A 和 B（以及差异 Bc）。

第 1 面：

  1. 初始化 ZLIB 流
  2. 使用 Z_SNC_FLUSH 压缩 A->Ac（我们不需要结果，因此可以释放 Ac）
  3. 使用 Z_SNC_FLUSH 压缩 B->Bc
  4. Deinit ZLIB 流

我们首先使用特殊标志压缩块 A，强制 ZLib 处理和输出所有数据。但它不会重置压缩状态！当我们压缩块 B 时，压缩器已经知道 A 的子序列，并且会非常有效地压缩块 B（如果它们有很多共同点）。Bc 是唯一要发送的数据。

第二面：

  1. 初始化 ZLIB 流
  2. 使用 Z_SNC_FLUSH 压缩 A->Ac
  3. Deinit ZLIB 流

我们需要解压缩与压缩完全相同的块。这就是我们需要Ac的原因。

  1. 再次初始化 ZLIB 流
  2. 使用 Z_SNC_FLUSH 解压缩 Ac->A
  3. 使用 Z_SNC_FLUSH 解压缩 Bc->B
  4. Deinit ZLIB 流

现在我们可以解压Ac-A（我们必须解压，因为我们是在另一边解压的，它有助于解压器学习块A的所有子序列），最后是Bc->B。

ZLib的使用有点不寻常和棘手，但是在这种情况下Bc不仅仅是压缩块B，它实际上是块A和B之间的压缩差异。如果ZLIB字典的大小与块的大小相当，那将非常有效A. 对于巨大的数据块，它不会那么有效。

于 2013-10-08T20:31:52.323 回答