XQuery/XML 差异

动机

您希望找到两个 XML 文件之间的差异，并输出一个包含差异的“彩色 diff”文件。

XML 差异背景

与纯文本文件不同，在比较两个 XML 文件时必须考虑 XML 结构差异。

例如，在比较元素的两个属性时，属性在文件中出现的顺序并不重要。以下两行在技术上是相同的，即使属性的顺序不同

<myelement attr1="abc" attr2="def"/>
<myelement attr2="def" attr1="abc"/>

XML 差异也往往忽略了在缩进 XML 文件以使其更易读时使用的空格和制表符。

因此，UNIX diff、GNU diff 或 Subversion diff 等工具使用的传统最长公共子序列 (LCS) 算法通常不会给出我们想要的结果。

XML 差异算法

有很多不同的算法可以用来比较树状结构数据。由于分层数据可能非常复杂，因此每种算法都将有不同的精度和性能考虑因素。还有很多选择需要考虑。例如

• 您是否要忽略 XML 注释？
• 您是否要忽略处理指令 (PI)？
• 您是否要忽略大小写（大写/小写）差异？
• 您是否要忽略元素之间的空白符？
• 您可以假设正在比较的 XML 文档的结构是相同的，并且只有文本不同吗？
• 您是否对属性顺序的更改感兴趣？
• 您是否希望您的差异算法输出对第一个或第二个文件进行修改的更改列表？

对于我们的第一个版本，我们只会简单地扫描元素和元素内的文本。

方法

我们将创建一个递归 XQuery 函数，该函数比较 XML 文件的所有节点。

XML 差异输出格式

我们希望创建一个 XML 输出格式，允许用户使用并排文件比较方法轻松地显示输出。

例如，输出可能如下所示

<xml-diffs>
  <parameters>
      <output-format-code>xml<output-format-code>
      <show-original-indicator>false<show-original-indicator>
  </parameters>
  <diff>
    <change>...<change>
  <diff>
  <diff>
    <addition>...<addition>
  <diff>
  <diff>
    <deletion>...<deletion>
  <diff>
</xml-diffs>

为 HTML 和 CSS 格式化输出

上面的输出可以被认为是原始的语义标记，而无需考虑网站如何使用标准 HTML div 块和 CSS 来显示输出。作为第二步，我们可以将输出放置在两个 HTML <div>...</div> 块中，一个用于通常位于左侧的初始文件，另一个用于通常位于右侧的第二个文件，并使用 <div>...</div> 标记标记更改。每个 div 将具有一个 class 属性，允许 CSS 文件将输出放置在 HTML 页面上的任何位置。例如，<div class="orignal"> 可能会被放置在左侧，而 <div class="addition"> 可能会被使用绿色进行样式设置。

算法

O(ND) 差异算法最初是为使用换行符作为基本比较单位来比较文本文件而设计的。我们需要对其进行修改以递归地比较 XML 元素和属性。XML 比较也不应报告属性顺序的差异。

待续...

参考文献

{{citation}}: Empty citation (help)

• Eugene Myers 的“O(ND) 差异算法及其变体”Algorithmica 第 1 卷第 2 期，1986 年，第 251 页
• [http://www.cs.wisc.edu/niagara/papers/xdiff.pdf X-Diff：一种针对 XML 文档的有效变更检测算法 Yuan Wang、David J. DeWitt、Jin-Yi Cai、威斯康星大学 - 麦迪逊