一種節(jié)點加權的相似重復XML數(shù)據(jù)檢測算法

摘 要：XML類型的數(shù)據(jù)成為當前主流的數(shù)據(jù)形式，本文提出一種檢測XML數(shù)據(jù)相似性的方法，即將XML文檔轉換成樹結構的基礎上，對樹結構的節(jié)點加權，并結合樹編輯距離算法。通過XML帶權樹各屬性權值計算的相似度對數(shù)據(jù)進行粗略匹配與聚集，而在重新聚集的集合中使用樹編輯距離算法更直接的進行相似性檢測。由于XML數(shù)據(jù)集合范圍的縮小，樹編輯距離算法操作的次數(shù)減少，從而節(jié)省了一定的時間。

關鍵詞：XML數(shù)據(jù)；節(jié)點加權；樹編輯距離；相似性

中圖分類號：TP391.1

隨著網(wǎng)絡快速發(fā)展，由于結構化的XML類型數(shù)據(jù)可擴展且跨平臺而成為當前網(wǎng)絡數(shù)據(jù)的主流形式。XML文檔的迅速增多并集成統(tǒng)一平臺后，會產(chǎn)生不被需要的“臟數(shù)據(jù)”，而對這些數(shù)據(jù)的清洗變的更加重要。這些“臟數(shù)據(jù)”使輕則會使獲得的信息不準確，重則獲得完全錯誤的信息。為了使XML數(shù)據(jù)源中的數(shù)據(jù)能發(fā)揮最正確的作用，清洗平臺中的“臟數(shù)據(jù)”成為一個組要解決的問題。

非一致性轉換、相似性判定、信息抽取等3方面是當前XML數(shù)據(jù)清理的主要關注點。如韓愷等人提出的在上下文語義影響下的XML文檔的匹配方法[1]，F(xiàn)lesca等人將結構化的XML文檔與時間序列、脈沖等內(nèi)容聯(lián)系起來進行相似性檢測[2]。以上兩篇文章關于XML數(shù)據(jù)清理方法考慮了不同DTD樹間的匹配算法，其中文檔內(nèi)容提到較少，部分方法設計思想很好，但實踐可行性有限。

首先，將一個XML文檔轉化為一棵樹或一個圖，然后通過度量這兩棵樹（圖）間的距離來體現(xiàn)XML文檔間的相似度。在眾多樹相似度匹配的研究工作中，普遍接收和采用的既是樹編輯距離算法[3-6]。Tai[3]最早將編輯距離的方法應用到檢測兩顆樹間的相似性。以他的理論為基礎，提出的一系列樹編輯距離算法及相關的改進算法等。

1 相似重復記錄

信息集成中，數(shù)據(jù)清洗和提高數(shù)據(jù)質(zhì)量是檢測和消除集成數(shù)據(jù)中的相似重復記錄中最需要解決的問題之一。相似重復記錄的概念是指雖然在現(xiàn)實世界中表述的是同一個實體，但由于拼寫錯誤或表達方式的不同，而導致數(shù)據(jù)庫管理系統(tǒng)不能將其識別為重復的記錄。這些重復記錄的產(chǎn)生導致決策者在最終決策時由于依據(jù)的信息不正確而產(chǎn)生較大的影響。以此為基礎，重復記錄檢測在信息的抽取、轉換、加載的過程中顯得更加重要。目前研究的主要方向體現(xiàn)在西文、中文字符集的相似重復記錄的檢測，已有了一定研究。但對于半結構化的XML數(shù)據(jù)的重復記錄檢測算法的研究還有待進一步提高。

XML數(shù)據(jù)在網(wǎng)絡中使用的增多以及在數(shù)據(jù)庫中的使用，使得這種數(shù)據(jù)類型在數(shù)據(jù)清理中越來越重要。實際多種XML數(shù)據(jù)被認為不一致，例如拼寫錯誤等導致字符串屬性不一致，從而使得此字符串類型數(shù)據(jù)不一致。另外，實際相同的XML數(shù)據(jù)由于結構上不同被認為是不同的數(shù)據(jù)。即使數(shù)據(jù)源具有相同的DTD結構，屬性個數(shù)不同、屬性值拼寫不同均可導致XML數(shù)據(jù)不一致。

2 樹編輯距離

在XML數(shù)據(jù)的ETL中，主要摒棄其中的“臟數(shù)據(jù)”，也就是檢測出相似記錄合并，普遍采用的方式即將XML文檔轉換成樹結構，轉換的過程中要將樹中的節(jié)點與數(shù)據(jù)元素相對應，即節(jié)點名為元素標簽名。編輯距離方法分為兩種，字符串編輯距離算法用判定兩個字符串是否相似，而通過樹編輯距離方法時大家更清晰的認識到帶標號有序樹間差異。以下給出與樹編輯距離相關的概念定義。

2.1 基本概念

目前對于數(shù)據(jù)相似性的檢測主要采用編輯距離的方式，而此方式又分為兩種，字符串編輯距離主要用于字符串領域，樹編輯距離主要應用于兩棵樹或圖的差異檢測，以下給出具體概念描述。

（1）字符串編輯距離：定義字符串S1、S2，當S1轉換為S2時所需要的編輯操作的最小數(shù)目，此轉換指單個字符上的轉換，而操作主要指插入、修改、刪除。此概念普遍應用于字符串的相似性檢測。

（2）樹編輯距離：定義兩棵樹T1、T2，當T1轉換到T2時所需要的書編輯操作的最小代價，此轉換指節(jié)點的轉換。而節(jié)點的插入、刪除、修改三種操作稱為樹編輯操作：

1）修改（替換）：節(jié)點改變；

2）刪除：刪除某一節(jié)點的同時，將該節(jié)點的兒子節(jié)點重新定義為兄弟節(jié)點并插入到其父節(jié)點的子樹中；

3）插入：插入某一節(jié)點的子節(jié)點，而該節(jié)點的原部分子節(jié)點轉換為新插入節(jié)點的子節(jié)點。

2.2 樹編輯距離的相似性檢測

樹編輯距離體現(xiàn)了在兩個樹轉化的過程中樹編輯操作的最小次數(shù)，而實際編輯操作次數(shù)計算方式可以通過映射這一概念來體現(xiàn)，將整個求解過程解釋為樹之間的映射過程，稱為編輯映射。

（1）樹編輯距離算法：定義兩個樹T1和T2，在兩個樹之間建立一映射，直接體現(xiàn)了樹與樹節(jié)點間的對應關系。在樹與樹之間建立映射需要滿足一系列的條件，首先給出兩組對應關系屬于此映射，分別為（i1，j1），（i2，j2），其中1≤i、j的值≤樹的節(jié)點數(shù)，則，當且僅當j1≤j2時，i1≤i2；另外當且僅當節(jié)點j1是節(jié)點j2的祖先是，節(jié)點i1是節(jié)點i2的祖先，從而將樹編輯距離的計算轉換為映射的計算，在計算過程中，最好的結果即是所付的代價最小。

（2）樹編輯距離相似性檢測：XML類型數(shù)據(jù)相似性的檢測可以分兩步走，首先計算文檔轉換為樹結構時，數(shù)據(jù)所對應的節(jié)點元素字符串間的差異，然后把字符串差異的計算合并到樹編輯距離的計算之中來。樹編輯距離的值越小，則兩顆XML樹越相似，此過程中給出閾值的概念作為評判的標準，當值小于設定的閾值時，認為兩個XML數(shù)據(jù)相同。

3 優(yōu)化的XML相似重復數(shù)據(jù)檢測算法

時間復雜度體現(xiàn)了完成操作所需要付出的代價，而針對上述的樹編輯距離算法其時間復雜度跟樹的節(jié)點數(shù)以及樹的高度有直接的關系。因此，當XML文檔的數(shù)據(jù)量足夠大的時候，計算代價會成倍增長，這在實踐過程中是無法忍受的，因此，必須采用優(yōu)化措施來減少樹編輯距離計算。本文優(yōu)化樹編輯距離算法，在整個過程中，首先通過樹節(jié)點的權值進行第一次匹配，將相似性更大的數(shù)據(jù)聚集到一個集合中，在此集合中采用樹編輯距離方法進一步匹配，從而減少時間復雜度。

3.1 帶權樹的生成

由于XML文檔可以轉化為多種樹表示形式，針對XML文檔通過SAX（Simple API for XML）解析器進行解析，將XML文檔轉化為XML樹結構，并具有相應的可行匹配方法。根據(jù)解決問題的側重點不同，XML帶權樹的屬性在XML文檔中具有不同的重要程度。通過XML帶權樹的權值的大小來表示屬性的重要性。根據(jù)權值本身的設置特點，在帶權樹中，設置相同根節(jié)點的同一層次上的節(jié)點權值之和等于1。

3.2 相似性粗略匹配

針對完全展示XML文檔的信息的帶權樹，通過權值的不同體現(xiàn)每個元素重要程度的不同。通過權值進行粗略匹配主要體現(xiàn)在XML樹的屬性相同時，權值是否相同，權值差異越小，則判斷樹的相似性越高。在整個判斷的過程中，還需要考慮到屬性的多少，即樹分支數(shù)目。

通過實際情況分析推測出重復記錄相似度的計算方法如下：帶權樹Ta和Tb，N代表兩樹所有節(jié)點的個數(shù)，a1 a2 … aN，b1 b2 …bN分別代表權值，其體現(xiàn)了屬性的重要程度。另外，當某一屬性僅存在于一棵樹中時，則設定此屬性的權值為0，相似度的計算公式見（1）[7]：

S（Ta，Tb）=（N-（︱a1-b1︱+︱a2-b2︱+ … +︱aN-bN︱））/N

=1-（ （︱ai-bi︱））/N （1）

上述公式作為相似度計算的工具，可以很好的計算出任意XML帶權樹之間的相似性，通過具體的數(shù)據(jù)來體現(xiàn)差異的大小，從而進行簡單的匹配，節(jié)省時間。

根據(jù)以上描述給出XML類型數(shù)據(jù)相似性檢測的偽代碼算法描述如下：

（1）將輸入的XML數(shù)據(jù)集轉換為XML帶權樹；

（2）通過節(jié)點權值來計算兩棵帶權樹間的相似度，從而粗略匹配數(shù)據(jù)；

根據(jù)上述思想給出粗略匹配的偽代碼描述。

（a）從所有的XML樹中任取其中一棵樹；

（b）以所取樹為基準，通過相似性度量公式計算基樹與其它樹之間的相似度，目的為了得到所有的相似度值；

（c）將上述相似度值與系統(tǒng)輸入的相似度量λ進行比較，若大于等于λ；

（d）將相似度值大于等于λ的XML樹聚合成新的集合C1；

（e）任取一不在集合C1中的帶權樹Tb；

（f）重復執(zhí)行步驟（b）；

（g）直到所有的帶權樹均存在于一個集合中。

（3）在經(jīng)過第（2）步聚集的所有新集合中使用樹編輯距離算法，當計算后的距離值小于給定的閾值δ時，認為兩個是相似的XML數(shù)據(jù)。

4 結束語

本文首先介紹了一系列概念定義，包括相似重復記錄，兩種編輯距離，并詳細描述了樹編輯距離相似性檢測算法及相關問題。在此基礎上，提出一種檢測XML數(shù)據(jù)相似性的方法，即將XML文檔轉換成樹結構的基礎上，對樹結構的節(jié)點加權，并結合樹編輯距離算法。通過XML帶權樹各屬性權值計算的相似度對數(shù)據(jù)進行粗略匹配與聚集，而在重新聚集的集合中使用樹編輯距離算法更直接的進行相似性檢測。該方法可以大大減少不必要的樹編輯距離操作。

參考文獻：

[1]韓愷，岳麗華等.基于上下文的異構文檔類型定義匹配[J].小型微型計算機系統(tǒng)，2005，26（02）：256-260.

[2]Flesca S，Manco G，Masciari E et al. Detecting structural similarities between XML documents.In：Fernandez MF，Papakonstantinou Y，eds.Proc.of the Int’l Workshop on the Web and Databases（Web DB）.2002：55-60.

[3]Tai K C.The tree-to-tree correction problem. Journal of the ACM， 1979，26（03）：422-433.

[4]David T. Barnard，Gwen Clarke et al.Tree-to-tree Correction for Document Trees，1995.

[5]Zhang K，Shasha D.SIMPLE FAST ALGORITHMS FOR THE EDITING DISTANCE BETWEEN TREES AND RELATED PROBLEMS，1989，18（06）：1245-1262.

[6]Zhang K.Algorithms for the constrained editing distance between ordered labeled trees and related problems，1995，28（03）：463-474.

[7]江曼，陳繼明，潘金貴.基于XML的層次式過濾研究[A].2006年全國體育儀器器材與體育系統(tǒng)仿真學術報告會論文集[C].2006.

作者簡介：孫娜（1984-），女，遼寧海城人，2009年畢業(yè)于沈陽航空工業(yè)學院，專業(yè)計算機應用技術，教師，助教，碩士，主要研究方向：管理信息系統(tǒng)與數(shù)據(jù)庫；吳蘭蘭（1983-），女，滿族，遼寧海城人，2010年畢業(yè)于沈陽航空工業(yè)學院，專業(yè)計算機應用技術，教師，講師，碩士，主要研究方向：個性化推薦技術。

作者單位：沈陽航空航天大學北方科技學院，沈陽 110136