XML 版本控制算法

Question

我正在寻找一种高效的方法来比较和获取两个基于XML的解析树之间的差异。

您认为存储这些差异的最佳方式是什么？我会这样做：

XML A:

<w:p>
  <w:pPr>
    <w:spacing w:after="1"/>
  </w:pPr>
  <w:r>
    <w:t>World</w:t>
  </w:r>
</w:p>

XML B:

<w:p>
  <w:pPr>
    <w:spacing w:after="1"/>
  </w:pPr>
  <w:r>
    <w:t>ASDF</w:t>
  </w:r>
</w:p>

该算法确定“World”已经改变为“ASDF”，然后存储：

div: <w:p><w:r><w:t>World</w:t> -> <w:p><w:r><w:t>ASDF</w:t>

这是否足以涵盖所有可能出现的情况？

有人知道一个好方法吗？任何帮助都将不胜感激！

- Chris

Answer 1

可能会变得更加困难。看看这个例子：

<w:p>
  <w:pPr>
    <w:spacing w:after="1"/>
  </w:pPr>
  <w:r>
    <w:t>World</w:t> <-- Case 1: this changes to <w:t>ASDF</w:t>
    <w:t>World</w:t> <-- Case 2: this changes to <w:t>ASDF</w:t>
  </w:r>
</w:p>

为了能够识别这两种情况，您需要将其中一种情况存储为。

 div: <w:p><w:r><w:t>World</w:t> -> <w:p><w:r><w:t>ASDF</w:t>

另一个则是

 div: <w:p><w:r><w:t>World</w:t><w:t>World</w:t> -> <w:p><w:r><w:t>World</w:t><w:t>ASDF</w:t>

或者类似的东西（你可能还想在两个标签中添加"w:p"闭合标签，使它们成为有效的XML子树）。

一般来说，这样的程序可能会变得非常复杂，因此我不建议您创建全新的内容，而是使用现有的差异算法（大多数即使没有解析XML结构也足够好）或修改其中一个以满足您的需求。

- schnaader

Answer 2

XMLDiff：

本文介绍如何使用XML Diff和Patch工具，该工具比较两个XML文件并生成差异的XML输出，通过一个典型的场景，读者可以将其应用到自己的应用程序中。

- Mitch Wheat

Answer 3

如何使用简单的深度优先搜索来查找共同部分呢？也就是说，进行深度优先搜索，一旦遇到差异，就将其存储并开始回溯。构建输出的上下文部分所需的附加信息可以轻松地存储在“回溯堆栈”中。

- mweerden

Answer 4

当你想要比较两棵树之间的差异并从该比较中产生“差异”时，你基本上在寻找一种变体的树编辑距离问题。作为入门，可以查看this paper。

更常见的“编辑距离”问题是字符串的编辑距离问题。像CVS或SVN这样使用“增量编码”来存储文件所做的更改的版本控制软件使用字符串编辑距离算法的变体来计算增量。树的情况不太常见，但绝对很有趣。

- antti.huima