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、威斯康星大學 - 麥迪遜