用連連看的方法比較XML文檔

比較兩個XML文檔在語義上相等，比想的要難一點。例如，下面的兩個XML文檔

1.xml

<xml/><a><b>bb</b><c k='11'></c></a>

2.xml

<xml/><a><c k='11'></c><b>bb</b></a>

排列有些不同,但内容還是一樣的.

如果用DOM比較的話，算法基本上就是，

1 解析第一個文檔，構成一個結點樹

2 周遊第二個文檔結點，搜尋第一個文檔樹，找到對應的結點，比較。

但問題是怎麼找到對應的結點，首先是結點位置的層次問題，其次怎麼确定對應關系。

對于層次問題，我們可以标記，在同一級的兄弟結點上比較。

但就算我們縮小了範圍，對于沒有特殊标記的結點，比如<li>這樣的标簽，還是很難确定對應關系，就算是想排序都沒有關鍵字。

雖然我也知道,基于樹都可以做遞歸,去簡化設計,但真沒想出來:<

最後還是連連看的靈感。打碎再比較.

基本的思路，

把結點分成兩類,有BODY的和沒有BODY的.

比如上面的XML檔案,

就可以分成有BODY的<b>bb</b>;沒有BODY的<xml/>, <a></a>, <c k='11'></c>,這幾個結點.最終的目标就是比較這些打碎的TAG.

同時流式解析兩個XML檔案,,并為每一個檔案生成相應的一個TAG棧.

把一個TAG壓進棧,要分兩次進行,第一次,壓進<xx>,如果有BODY的話,把BODY也壓進去.第二次,壓入</xx>.

這樣我們還需要一個指針棧,标記未完全壓入棧的TAG.

同時把完全壓入棧的元素,放到一個比較隊列裡.,每完全壓入一個元素,就比較兩個棧的比較隊列.如果相同,就删除這個TAG.如果兩個XML檔案,基本相似的話,比較隊列的SIZE都會保持比較小的值.節省很多的周遊開支.

完成XML的解析後,隻要比較兩個棧中比較隊列的大小,如果都為空,那麼這兩個XML就是内容相等的.

但這個的算法,忽略了結點的位置資訊.

比如,<a></a><a></a>和<a><a></a></a>也會被等同.

這裡做了一個簡單的擴充.為每一個TAG加一個ID屬性,

第一個壓入未完全壓入棧的TAG的ID值為該TAG的<xx>和BODY字元串的hashCode值.

以後入棧的TAG的ID值是未完全壓入棧棧頂元素ID值+該TAG的<xx>和BODY的hashCode值.比較時,先比較一個ID然後再比較内容.

目前隻完成了一個很簡單的實作.還不能比較不同排列的屬性,但對于我的需求來說,已經足夠了.