史濤+沈艷霞

摘要： 針對基于XML的農產品溯源平臺中的數(shù)據(jù)集成問題，提出一種XML Schema模式匹配方法。該方法同時考慮元素的語義性和結構性，結合文檔元素的名稱、數(shù)據(jù)類型以及基數(shù)約束3個方面，通過相應的度量標準計算出元素的語義相似度，實現(xiàn)語義匹配；通過計算模式樹中元素節(jié)點的祖先相似度，同時考元素本身的語義相似度，實現(xiàn)結構匹配。闡述了匹配算法的設計過程和試驗評估結果。結果表明，相比較現(xiàn)有的幾種方法，該方法能實現(xiàn)全自動化的匹配過程，提供更精確的匹配結果。

關鍵詞： 農產品；XML Schema；模式匹配；算法

中圖分類號： S126 文獻標志碼： A 文章編號：1002-1302（2016）03-0442-04

近年來，農產品質量安全問題成為國民關注的重要民生問題[1]。建立面向農產品質量溯源的公共平臺，向消費者提供農產品從生產、加工、流通到銷售的一個完整的生命周期信息，是避免有質量安全或偽劣產品流入市場，確保食品安全的重要保障[2]。

由于具有平臺獨立性、可擴展性、自描述性等特點，XML已成為農產品溯源信息網絡傳輸與交換的主要標準[3]?；赬ML的農產品溯源系統(tǒng)采用統(tǒng)一的方式來處理不同地區(qū)、不同數(shù)據(jù)源的農產品信息，屏蔽構農產品溯源信息在結構、運行環(huán)境上的差異，采用XML構造數(shù)據(jù)轉換的中間層，實現(xiàn)農產品溯源信息的無縫集成。利用XML開發(fā)的系統(tǒng)，農產品溯源信息管理員只需遵循一些基本的結構規(guī)則，就可以便捷地創(chuàng)建包含溯源信息的XML文檔，并將其存儲在分布式的計算機環(huán)境中。這些結構規(guī)則通常通過XML Schema（XSD）和文檔類型定義（DTD）得到。XSD本身就是XML 文檔，與DTD相比，在支持數(shù)據(jù)類型和空間定義方面表現(xiàn)更好，更適合為農產品溯源信息定義結構[4]。然而使用不同的XSD文檔描述的農產品數(shù)據(jù)在集成過程中會帶來相互沖突的問題，在農產品XSD文檔中，許多元素具有相同的語義，但它們的名稱和結構可能不同，相反許多元素具有相同的模型，但語義不同。因此，在農產品數(shù)據(jù)的有效集成中，主要問題之一就是如何在XSD文檔中計算出元素之間的相似度，實現(xiàn)高質量的模式匹配。

目前，關于XML模式匹配的研究已取得了一些研究成果。Kim等將樹-樹的匹配問題分步轉換成路徑-路徑、節(jié)點-節(jié)點，最終轉換成單詞-單詞的匹配問題[5]，該方法的不足之處在于語義匹配算法中沒有考慮數(shù)據(jù)類型和基數(shù)約束，匹配精度不高。Wojnar等提出了一種樹編輯距離算法，借鑒編輯距離的思想，用語言匹配計算得到元素對應的語言相似值作為輸入，計算某一元素的結構完全變?yōu)榱硪粋€元素結構的操作步數(shù)，從而計算結構相似值，其理論主要集中在結構計算[6]。Lee等通過聚合DTD的元素來計算出DTD樹之間的相似度[7]，Ye等在其聚合方法中增加了權值因素[8]。文獻[7]提出的聚合方法（XClust）允許相似的信息存儲在一起，分類信息的標準越高，聚合數(shù)據(jù)的質量就越高。然而，XClust方法主要依賴于人為判斷和結構化信息去聚合DTD元素；更重要的是，該方法沒有考慮DTD中屬性的數(shù)據(jù)類型相似度。近幾年，部分研究借鑒實體識別研究領域的思想來進行模式匹配研究，例如使用一個原型工具Dedoop（使用 Hadoop 的重復刪除技術）在大數(shù)據(jù)集中實現(xiàn)實體識別[9]。另外，基于維基百科，WordNet等的知識網絡從實例角度吸引了從事調查數(shù)據(jù)源管理研究者的興趣[10]。WordNet廣泛用于匹配系統(tǒng)[11]中，例如網絡搜索[12]和網絡查詢擴展[13]。在本研究中也使用WordNet來計算元素的名稱相似度。

現(xiàn)階段的一些研究方法只考慮元素的名稱相似度或者結構相似度的計算[5-6]，雖然有些研究已經都考慮語義和結構[7]，但其度量標準中的部分因素需要通過人為判斷來確定。針對農產品溯源信息的XML數(shù)據(jù)量巨大，且包含對于數(shù)據(jù)類型和基數(shù)約束的多種定義，需要更標準的度量標準得出精確的相似度值。因此，本研究綜合考慮元素的語義匹配和結構匹配，提出一種新的XML Schema模式匹配方法。語義匹配中，綜合考慮元素的名稱、數(shù)據(jù)類型以及基數(shù)約束，提出相應的度量標準計算相似度，無需人為判斷，提高匹配精度和效率；結構匹配中，考慮元素中節(jié)點的祖先相似度，同時將語義相似度作為計算的參數(shù)之一，提高結構匹配的精確度。通過性能研究以及同相關方法對比實現(xiàn)對本研究方法的評估，可以從XSD農產品溯源數(shù)據(jù)中通過全自動化的方式計算出元素之間的語義和結構相似度，實現(xiàn)模式匹配。

1 模式匹配概念

模式是代表一件設計物的一個比較正式的結構，如XML模式、SQL模式和實體-關系模式等[14]。對于任意的模式S1和S2，模式S1中的某些元素映射到模式S2中的某些元素，其中的映射元素又稱為匹配元素對，映射叫匹配結果。模式匹配的目標是利用模式間的所有可用信息，得出模式間最匹配的元素。

模式匹配定義：模式匹配定義為一個函數(shù)，輸入值為2個模式，輸出值為模式之間的相似度計算結果。

相似度計算：對于模式S和T，元素s∈S，t∈T。相似度計算表示一個函數(shù)，輸入值為s和t，輸出值為s和t之間的相似度sim（s，t），其中0≤sim（s，t） ≤1。

相似度表示2個元素之間的相似性，為了精確地評估一個元素對的相似度，相似度計算應該充分考慮元素的特征以及其結構。相似值的大小范圍是[0，1]，0代表2個元素基本不相似，1代表2個元素相似度極高甚至是完全相同。

2 匹配算法設計

2.1 語義匹配

概念的語義性在文本文檔的集成過程中具有重要的作用[14]。XML Schema的語義包含詞匯、內容模式以及數(shù)據(jù)類型。通常來說，XML Schema使用標準的命名空間（xs或xsd）和對應的統(tǒng)一資源標識符（URI）作為文檔開頭；利用XML Schema，可以定義文檔中元素可能出現(xiàn)的次數(shù)，分別表示為maxOccurs和minOccurs 2種屬性；更重要的是，簡單類型和復雜類型元素幫助區(qū)分元素中2種屬性類型的數(shù)據(jù)類型相似度[15]。

本研究中，對于任意2個元素s1∈T1，s2∈T2，其語義相似度綜合考慮元素名稱、數(shù)據(jù)類型和基數(shù)約束3個方面，如公式（1）所示：

式中：Sesim為語義相似度；α和β為程序設定的權值；Namesim（e1，e2）、Dsim（d1，d2）、Csim（e1，e2）分別為名稱相似度，數(shù)據(jù)類型相似度以及基數(shù)約束相似度，具體計算分3步驟完成。

2.1.1 步驟1名稱匹配 語義相似度計算中的關鍵因素是元素本身的語言相似度。在實際的農產品溯源XML Schema文檔中，表示同一對象的元素可能出現(xiàn)縮寫，帶有連接符號等形式，導致基于語言本身的差異。首先進行3個預處理步驟：（1）使用符號分析器，將復合詞組拆分為獨立的單詞；（2）通過查找WordNet，將縮寫的單詞還原成詞匯本體；（3）刪除慣詞、介詞等修飾詞。預處理完成后，利用表格中的算法對元素e1和e2進行名稱相似度的計算。其中，在WordNet中e2的同義詞庫中，利用深度優(yōu)先搜索算法查找是否含有e2的同義詞，直到e2被匹配。如果沒有匹配結果，則語言相似度返回0，否則其值為0.9distance。具體算法如表1所示。

2.1.2 步驟2數(shù)據(jù)類型匹配 在XML Schema文檔，每個元素都是簡單類型或者復雜類型。如果2個元素有相同的名稱，且數(shù)據(jù)類型屬性是相同的，二者之間的語義相似度可能高于其他情況。對于2個葉元素，考慮其數(shù)據(jù)類型描述。由于數(shù)據(jù)類型伴隨著屬性元素，數(shù)據(jù)類型相似度的計算僅適用于2種元素都為屬性的情況。當2種元素，其一為復雜類型而其二為簡單類型，則二者的數(shù)據(jù)類型相似度為0。

不同于文獻[16]提出的方法，數(shù)據(jù)類型相似度值通過用戶判斷決定，本研究探索每個數(shù)據(jù)類型的內部特征，并比較數(shù)據(jù)類型之間的關聯(lián)性，通過具體的公式計算實現(xiàn)?；谖墨I[17]關于XML Schema數(shù)據(jù)類型的總結，本研究對數(shù)據(jù)類型的各個約束方面求出數(shù)據(jù)類型相似度。在此，將其命名為Dsim，由以下公式得出：

Dsim（d1，d2）=∑i|{cfi|d1[cfi]=d2[cfi]，1< （2）

式中：d1和d2為表1中的任意數(shù)據(jù)類型；cfi為數(shù)據(jù)類型約束方面的列表，其中包括長度、最小長度、最大長度、模式、枚舉數(shù)、空格數(shù)等等；ncf為約束方面的總個數(shù)，本例中ncf為12。

表2顯示了XML Schema中6種典型屬性類型的數(shù)據(jù)類型相似度結果。表中的具體值由公式（2）計算得出。在表1中，整數(shù)型與小數(shù)型2者之間的相似度大于其他類型。當2種元素數(shù)據(jù)類型相同時，二者相似度最高，為1.0。

2.1.3 步驟3基數(shù)約束匹配 基數(shù)約束可以描述為XML Schema文檔中minOccurs（最小可能）和maxOccurs（最大可能），分別定義1個元素在XML文檔中出現(xiàn)次數(shù)的最小值和最大值。

定義Csim（e1，e2）為元素d1和d2之間的基數(shù)約束相似度。不同于文獻[15]提出的約束表格需要通過人為判斷得出，本研究通過具體公式來計算約束相似度。對于具體的minOccurs和maxOccurs值，使用公式（3）計算基數(shù)約束相似度：

式中，min和max分別為minOccurs和maxOccurs的縮寫。一般情況下，minOccurs被指定為0或1，而maxOccurs被指定為1或無窮大。為了計算出具體Csim的值，參考文獻[18]的分析，使用公式如下：

結合公式（3）和（4），可以計算出屬性基數(shù)約束的相似度，如表3所示。其中unbound=5。

2.2 結構匹配

在樹結構中，2個元素節(jié)點的結構相似度取決于二者在樹中的所處位置。即使2個元素節(jié)點的語義相似，也無法得出它們各自的祖先相似；但僅僅考慮元素的祖先相似度并不可取，原因在于可能存在2個節(jié)點結構相同但語義完全不同。本研究采取計算節(jié)點的祖先相似度，同時考慮節(jié)點的語義相似度的方法，提高結構匹配的精確度。

范數(shù)定義：設V=[x1，x2，…，xn]為一個向量，且V∈Rn，則其范數(shù)（歐幾里得距離）表示為‖V‖=2∑n i=1xi2。

利用范數(shù)可以更有效地運用權值概念。舉例說明，如果S=（a，b，b，a，c，b，c）為一組節(jié)點，其中a，b，c的權值分別為2，3，2。因此，如果將這些權值保存在如N=[2，3，2]的向量中，則S的范數(shù)為‖S‖=222+32+22=217。該范數(shù)將起到相似度值的規(guī)范化作用。

設T1和T2分別表示XML Schema文檔的2棵樹，提出其相似度計算如公式（5）所示：

式中：Sesim（e1i，e2j）為元素e1i和e2j的語義相似度值（由公式（1）計算得到）；PCC（r1→e1i，r2→e2j）（Path Context Coefficient）表示分別從根節(jié)點r1和r2到e1i和e2j的路徑相似度。實際上，PCC（r1→e1i，r2→e2j）為元素e1i和e2j的祖先相似度；當2個節(jié)點在語義上相同或者高度相似時，只要節(jié)點的祖先不相似，則二者不相似。PCC（r1→e1i，r2→e2j）的具體計算公式如下：

式中：Sesim（n1k，n2l）為節(jié)點n1k和n2l的語義相似度值；節(jié)點n1k和n2l分別屬于路徑r1→e1i和r2→e2j；p和q分別為2條路徑上的節(jié)點數(shù)目；P1和P2為2個向量，其值分別表示為從屬于2條路徑上的節(jié)點權值。

原則上，公式（7）應該適用于所有節(jié)點；然而，假設元素e1i和e2j中至少一個為根節(jié)點，則其很明顯沒有祖先。因此，該相似度計算在系統(tǒng)上存在偏差。為了彌補系統(tǒng)偏差，當出現(xiàn)上述情況時，令PCC（r1→e1i，r2→e2j）=1。

2.3 元素匹配

本研究同時考慮XML Schema樹中元素的結構性和語義性。因此，2個XML Schema中的元素相似度可以由上述2個部分計算得到：

當計算得到2個XML Schema中所有的元素對的相似度，可以計算出2個XML Schema的相似度。2棵XML Schema樹的相似度由下式計算可得：

3 試驗評估

為了驗證此方法的有效性，將本研究方法與現(xiàn)有的2種方法，即XClust[7]和XMLSim[19]進行試驗對比。試驗數(shù)據(jù)源選用超過20組的XML Schemas（以及對應的DTDs）。試驗采用的硬件環(huán)境為Intel Core i3 CPU，內存為4GB，操作系統(tǒng)為Windows 7，測試平臺是Altova Spy和Microsoft Visual Studio 2010標準環(huán)境，系統(tǒng)代碼通過C#實現(xiàn)。試驗中選取的權值分別為α=0.3，β=0.3，δ=0.6，ε=0.6。通過上述3種匹配算法得到的結果顯示在表4中。

如表4中所示，XMLSim匹配率最低，原因在于XML文檔中的實例數(shù)目是可變的，且各文檔之間大多不相同。當文檔中的節(jié)點與另一個文檔中的節(jié)點匹配成功后，算法開始計算下一對節(jié)點。因此，如果2個文檔中的節(jié)點數(shù)目不同時，匹配值將會下降。

為了更好地評價3種匹配方法，本研究使用Do H-H[20]提出的評價標準，分別為查準率（precision）、查全率（recall）、F_measure，如下公式：

試驗在相同的權值和相似度閾值的條件下，得出本研究方法Esim與XMLSim以及XClust方法的計算結果，如圖1所示。

試驗結果表明，本研究方法的匹配質量高于XMLSim和XClust這2種方法。原因在于，XClust方法沒有考慮元素之間的數(shù)據(jù)類型相似度，然而一些元素對可能有同樣的名稱，但數(shù)據(jù)類型不同。XMLSim方法過于重視信息本身內容的相似度，而沒有考慮元素之間的數(shù)據(jù)類型和基數(shù)約束相似度，匹配質量最低。

4 結論

本研究針對基于XML的農產品溯源信息平臺中異構源XML數(shù)據(jù)集成問題，提出了一種基于元素語義性和結構性的模式匹配方法。語義性方面，綜合考慮數(shù)據(jù)名稱、數(shù)據(jù)類型以及基數(shù)約束3個方面，通過研究分析推斷出具體計算公式，無需人為判定；結構性方面，同時考慮元素的祖先相似度與語義相似度，提高相似度計算精度。通過試驗比較目前的相似度計算方法，本研究提出的方法計算精確度更高，具有較好的可行性。本方法實現(xiàn)了完全自動化轉換，大大減少了人工勞動，提高了效率，具有一定的研究意義。下一步，結合本研究的模式匹配算法，將對農產品溯源信息平臺的異構XML數(shù)據(jù)集成模塊進行研究設計。

參考文獻：

[1]白紅武，孫愛東，陳 軍，等. 基于物聯(lián)網的農產品質量安全溯源系統(tǒng)[J]. 江蘇農業(yè)學報，2013，29（2）：415-420.

[2]毛 林，程 濤，成維莉，等. 農產品質量安全追溯智能終端系統(tǒng)構建與應用[J]. 江蘇農業(yè)學報，2014，30（1）：205-211.

[3]楊信廷，錢建平，趙春江，等. 基于XML的蔬菜溯源信息描述語言構建及在數(shù)據(jù)交換中的應用[J]. 農業(yè)工程學報，2007，23（11）：201-205.

[4]Amano S，David C，Libkin L，et al. XML schema mappings：data exchange and metadata management[J]. Journal of the ACM，2014，61（2）：488-507.

[5]Kim J，Peng Y，Ivezic N，et al. An optimization approach for semantic-based XML schema matching[J]. Int J Trade Econ，F(xiàn)inance，2011，2（1）：78-86.

[6]Wojnar A，Mlnková I，Dokulil J. Structural and semantic aspects of similarity of Document Type Definitions and XML schemas[J]. Information Sciences，2010，180（10）：1817-1836.

[7]Lee M L，Yang L H，Hsu W，et al. XClust：clustering XML schemas for effective integration[M]. ACM Press，2002：292-299.

[8]Ye Y，Li X，Wu B，et al. A comparative study of feature weighting methods for document co-clustering[C]. IJITCC，2011：206-220

[9]Kolb L，Thor A，Rahm E. Dedoop：efficient deduplication with Hadoop[J]. Proceedings of the VLDB Endowment，2012，5（12）：1878-1881.

[10]Tagarelli A. Exploring dictionary-based semantic relatedness in labeled tree data[J]. Information Sciences，2013，220：244-268.

[11]Shvaiko P，Giunchiglia F，Yatskevich M. Semantic matching with S-Match[M]. Semantic Web Information Management：A Model-Based Perspective，2010：183-202.

[12]Pyshkin E，Kuznetsov A. Approaches for web search user interfaces：how to improve the search quality for various types of information[J]J Conver，2010，1（1）：1-8.

[13]Klyuev V，Yokoyama A. Web query expansion：a strategy utilizing Japanese WordNet[J]. J Conver，2010，1（1）：23-28.

[14]Agreste S，de Meo P，F(xiàn)errara E，et al. XML matchers：approaches and challenges[J]. Knowledge-Based Systems，2014，66：190-209.

[15]Gong J，Cheng R，Cheung D W. Efficient management of uncertainty in XML schema matching[J]. The VLDB Journal，2012，21（3）：385-409.

[16]Algergawy A，Nayak R，Saake G. Element similarity measures in XML schema matching[J]. Information Sciences，2010，180（24）：4975-4998.

[17]Dan V. XML schema-data types quick reference[EB/OL]. [2015-04-01]. http：//www.xml.dvint.com.

[18]Thu P T T，Lee Y K，Lee S. Semantic and structural similarities between XML Schemas for integration of ubiquitous healthcare data[J]. Personal and Ubiquitous Computing，2013，17（7）：1331-1339.

[19]Resnik P. Semantic similarity in a taxonomy：An information-based measure and its application to problems of ambiguity in natural language[J]. Journal of Artificial Intelligence Research，1999，11：95-130.

[20]Do H H. Schema matching and mapping-based data integration[D]. University of Leipzig，2005.