多策略相似度整合的XML模式匹配方法*

范紅杰，柳軍飛，周魯東，麻志毅.北京大學信息科學技術學院，北京00872.北京大學軟件工程國家工程研究中心，北京0087

?

多策略相似度整合的XML模式匹配方法*

范紅杰1，柳軍飛2+，周魯東1，麻志毅1
1.北京大學信息科學技術學院，北京100871
2.北京大學軟件工程國家工程研究中心，北京100871

* The National Natural Science Foundation of China under Grant No. 61272159 (國家自然科學基金).

Received 2015-07,Accepted 2015-09.

CNKI網絡優先出版：2015-09-02, http://www.cnki.net/kcms/detail/11.5602.TP.20150902.1338.012.html

范紅杰，柳軍飛，周魯東，等.多策略相似度整合的XML模式匹配方法[J].計算機科學與探索，2016，10（1）：14-24.

ISSN 1673-9418 CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology

1673-9418/2016/10(01)-0014-11

E-mail: fcst@vip.163.com

http://www.ceaj.org

Tel: +86-10-89056056

摘要：模式匹配用于發現不同數據源中概念之間的語義對應關系，已成為數據集成、數據交換等領域的研究熱點。研究者提出了大量的基于XML模式匹配方法，從而可以識別XML中數據的語義對應關系。XML模式匹配存在著一些挑戰，例如如何將節點和結構匹配進行綜合考慮，如何有效擬合多種相似度等。面對如上問題，針對XML節點和結構兩方面進行相似度計算，得到相似度矩陣后整合這兩個方面的相似度。隨后通過多種策略組合和優化算法進行擬合，以得到優化的匹配結果。最后，通過基準測試平臺對比，該方法相比于經典的模式匹配方法具有較高的精確率和召回率。

關鍵詞：數據交換；模式匹配；可擴展標記語言（XML）；相似度度量；多策略組合

1　引言

可擴展標記語言（extensible markup language，XML）由于具有自描述能力和組織數據的靈活性，已經成為信息表示和數據交換的標準[1]，努力開發高性能的技術來有效地管理大型XML數據變得尤為重要。開發這種技術的障礙之一是有效識別和匹配節點之間的語義對應關系，這種語義識別和對應過程被稱為模式匹配。模式匹配[2-3]不但在理論研究中已經得到了廣泛的關注，而且在數據共享和數據交換的實際應用中同樣起著核心作用。例如在數據集成中多個異構模式之間的識別和表征模式之間的相互關系；在基于XML的數據轉換中來確定XML數據之間的語義對應關系，將源對象映射到目標對象。

隨著XML模式文件的不斷增多，XML模式匹配已經成為一個亟待解決的問題。由于模式匹配固有的復雜性，目前模式匹配主要依靠領域專家來手工處理，手動匹配效率往往比較低，尤其在面對大型和動態的模式匹配環境時更是如此。在這種情況下，有效、自動地實現匹配過程已成為必然趨勢。

自2001年開始，Rahm等人[4]將模式匹配作為特定領域加以研究，分析已經存在的工作，并認為可以將其他領域內的工作尤其是相似度技術結合到模式匹配中。模式匹配的相關專著[5-6]和綜述[4，7]，就匹配框架、匹配方法等進行了深入的討論。文獻[8]研究了XML樹和語法樹之間的編輯距離，并分析了算法執行的效率；文獻[9]基于TF-IDF（term frequencyinverse document frequency）信息檢索方式，將所有需要匹配的模式元素整合到不同文檔中，通過文檔內容相似度匹配方法來處理；文獻[10]將所有需要匹配的概念通過本體進行映射，完成概念之間的相似度計算。人們已經在相關系統或者平臺中提出了模式匹配算法，例如Similarity Flooding[9]、COMA++[11]等。這些系統的共同特點是它們不但考慮模式節點特征，還通過節點之間的關系來確定相似性，不同的是它們沒有利用多種組合策略來擬合已得到的相似度度量結果。模式匹配在匹配策略方面也各有不同。清華大學李涓子等人[12]使用自調整匹配策略選擇需要合并的匹配模塊，從而影響合并結果；文獻[13]將模式匹配轉換為多標記圖匹配問題，提出多標記圖的相似性度量方法；文獻[14]通過快速匹配策略消除已經不可能進行匹配的元素，從而縮小匹配搜索空間；文獻[15-16]使用先期匹配結果作為輔助信息，在后期的匹配中提高匹配效率。Algergawy等人[17]也通過不同的側面來計算相似度，例如計算文檔注釋、子孫節點等相似度，采用手工調整的方式來擬合相似度度量結果。

盡管如此，目前XML模式匹配中仍然存在著一些問題和挑戰[18]：首先大部分匹配算法主要考慮模式之間的整體相似度，忽略了獨立元素之間的相似度；其次擬合這些相似度是瑣碎的，目前幾乎所有現有的匹配系統通過簡單策略或者線性組合的方式合并，并不能充分考慮需要合并的相似度之間的相互依存關系。針對如上挑戰，本文的主要思路是首先通過不同的方式分別計算各節點和結構的相似度，得到相似度矩陣后，通過多種策略組合和優化算法進行擬合，并采用啟發式隨機搜索算法來解決大規模解空間的組合優化問題，以得到優化的匹配結果。

本文的主要貢獻是：

（1）深入研究了XML模式匹配特征，展示了不同層面的XML相似度度量方法，包括基于節點名稱、類型等多種相似度度量方法。

（2）為避免單一相似度度量方法的局限性，采用多策略相似度整合方式擬合所得到的相似度矩陣，以提高匹配質量。

（3）在整合策略中使用啟發式隨機搜索算法，解決大規模解空間的組合優化，避免了人工擬合或窮舉所有權值。

（4）通過基準測試平臺對比，相比于經典的模式匹配工具，多策略的相似度整合方法具有較高的精確度和召回率。

2　相關定義

定義1（數據交換）數據交換[3]可以描述如下：對于給定有限源實例數據I，在有限的目標實例數據J中查找的關系對滿足源對目標的函數依賴，且J自身滿足目標函數依賴，這樣的目標實例數據J被稱為源實例數據I的匹配解。換言之，如圖1所示，所有對于目標模式T的查詢都可以等價為對于源模式S的查詢。

Fig.1 General setting of data exchange圖1　數據交換通用表示

模式匹配作為數據交換的重要環節，其目的是為了確定數據交換場景中源對目標的函數依賴。因此在模式匹配中，可以弱化J自身需要滿足目標函數依賴。針對XML語境，將數據交換的雙方都替換成XML文檔，這些文檔格式可以是DTD/XSD或者其他格式。

定義2（XML模式匹配）給定三元組M＝(DS，DT，Σ)，DS為源文檔，DT為目標文檔，Σ為一系列源對目標函數依賴的集合，XML模式匹配就是在DS與DT中尋找所有相匹配的Σ。換言之，針對給定符合DS的樹t，模式匹配的解為樹t′，且t′符合如下要求：

（1）樹t′符合DT；

（2）＜t，t′＞滿足所有的源對目標函數依賴Σ，可以形式化表示為＜t，t′＞?Σ。

3　相似度度量計算框架

基于相似度度量計算的匹配框架如圖2所示。

本文將針對XML模式匹配中的節點和結構的相似度兩個方面進行計算，得到相似度度量矩陣后，再進行相似度擬合和優化。

3.1基于節點名稱的相似度度量

在缺少實例數據的情況下，節點名稱在模式匹配中被認為是一種重要的語義來源。基于節點名稱相似度度量算法有Q-gram算法[19]、Jaro-Winkler Similarity算法[20]、Smith-Waterman Similarity算法[21]、Monge-Elkan Similarity算法[22]，這些算法是基于字符相似度度量算法的典型代表。

Fig.2 Matching framework based on combining similarity measure圖2　基于相似度度量計算的匹配框架

（1）Q-gram算法

首先把要匹配的字符串分割為有許多連續N個字符組成的集合，通過找兩個字符串σ1和σ2中公共Q-gram串來計算相似性[19]。計算方法為：

（2）Jaro-Winkler Similarity算法

Jaro-Winkler Similarity算法主要是針對兩個短字符串的相似度距離計算[19]，是Jaro Similarity算法[23]的變種。計算公式為：

其中，simJaro(σ1，σ2)＝；M為σ1和 σ2匹配字符數；t為換位數目；pref(σ1，σ2)為兩個字符串σ1和σ2的最長公共前綴；參數?為常數，假定?為0.1。

（3）Smith-Waterman Similarity算法

Smith-Waterman Similarity為動態規劃算法，主要用以比較所有可能長度的字符串片段，并且對相似度進行了優化[21]。計算公式為：

其中，S1、S2為字符串，m＝|S1|，n＝|S2|；H(i，j)為S1第i個字符和S2第j個字符的最大相似度；w(x，y)代表間隙得分（gap scoring）。

（4）Monge-Elkan Similarity算法

Monge-Elkan Similarity度量算法作為混合相似度度量算法，結合了多種字符串相似度度量算法，該算法使用函數sim′(t1，t2)來計算[22]。計算公式為：

字符串相似性計算方法眾多，本文選擇以上4個作為節點名稱相似度計算方法，是因為XML文檔節點名稱多為短字符串。

根據上面所有基于節點名稱的相似度，結合決策樹算法思想，可以構建相似度匹配決策子樹。決策樹算法是一種逼近離散函數值的方法，是一種典型的分類方法，本質上是通過一系列規則對數據進行分類的過程，它代表的是對象屬性與對象值之間的一種映射關系。

如圖3所示，通過構建決策樹來處理相似度，是因為以上計算如果每個方法都要處理一遍，必然會增加計算時間，而且內存等計算資源的使用也會增加。因此，使用決策樹方法計算相似度具有以下優點：

（1）不會降低匹配質量，相反在一定程度上可以提高匹配質量；

（2）節省匹配時間，提高匹配效率。

Fig.3 Constructing decision tree of similarity matching圖3　相似度匹配決策子樹構建

3.2基于節點類型的相似度度量

節點名稱的相似度雖然重要，但映射結果中可能會存在錯誤的匹配，或者相似度結果不足以完全體現真實匹配。在此情況下，數據類型成為提高匹配質量的另外一個可以考慮的方面[24]。

XML模式中具有原子類型和復雜類型兩種，其中原子類型包括string等基本數據類型，復雜類型為多個原子類型的組合。在此，可以通過如下相似度計算規則進行處理：

（1）原子類型與復雜類型的相似度simdt＝0；

（2）復雜類型與復雜類型的相似度simdt＝1；

（3）原子類型與原子類型的相似度simdt可以參照約定的相似度度量表。

從表1中可以發現，如果兩者類型一致，那么simdt＝1；如果兩者類型不一致但可以相互轉換，那么simdt＝0.8；如果兩者類型不一致但可能相互轉換，那么simdt＝0.2；如果兩者類型不一致且不能相互轉換，那么simdt＝0。

Table 1 Similarity matching based on data type表1　數據類型相似度匹配

通過對照以上類型相似度匹配表的規則設置，可以得出兩個節點屬性的相似度。

3.3基于節點約束的相似度度量

XML模式使用minOccurs和maxOccurs定義了模式中節點的出現次數。因此，節點的基數約束信息可以成為節點相似度匹配中又一個重要的方面。

節點的基數表示方法有4種形式：“*”、“+”、“?”、“none”[24]。將4種表示之間的相似度約定為特定的相似度度量，如表2所示。

Table 2 Similarity matching based on data constraint表2　數據約束相似度匹配

在XML文檔中，并非所有的約束表示都如上，例如minOccurs＝2且maxOccurs＝5，在此情況下，可以通過如下方式來解決：

3.4基于節點結構的相似度度量

XML文檔可以形式化地抽象為樹型結構，因此在進行相似度度量時可以考慮基于結構的度量方法。

如圖4所示，在基于結構的相似度度量方法中，主要是針對XML文檔樹中的祖先節點和兄弟節點兩個方面進行考慮。為此，采用祖先相似度繼承映射（descendant’s similarity inheritance，DSI）方法[11]和兄弟相似度貢獻映射（sibling’s similarity contribution，SSC）方法[25]進行處理。

Fig.4 Computing similarity between C and c圖4　計算節點C與c相似度

（1）DSI映射方法

DSI映射方法在基于語言分析的基礎上，將樹型結構中的父親節點和祖先節點信息納入到計算中。實現這種方法的前提是假設父親節點和祖先節點能對該節點的相似度產生影響，就是說兩個節點的祖先節點相似度越大，這兩個節點的相似度也越接近。計算方式為：

節點無祖先節點時，simDSI(σ1，σ2)＝simling(σ1，σ2)。

（2）SSC映射方法

SSC映射方法也是基于語言分析的基礎，將樹型結構中的兄弟節點信息納入到計算中。實現這種方法的前提假設是兄弟節點能對該節點的相似度產生影響，也就是說兩個節點的兄弟節點相似度越大，那么這兩個節點的相似度也越接近。計算公式為：

節點無兄弟節點時，simSSC(σ1，σ2)＝simling(σ1，σ2)。

4　多策略相似度整合

第3章已經計算了所有種類的相似度，但在模式匹配中，上述的相似度度量算法并不能充分反映節點之間的相似性，例如基于節點名稱的相似度僅能反映節點之間的名稱特性。因此，有必要將多種策略應用到以上所有計算得到的節點相似度矩陣中，通過多方面相似度矩陣整合，以得到優化結果。基于多策略的相似度整合框架如圖5所示。

Fig.5 Combining similarity measures圖5　相似度度量整合

通過以下不同的合并策略來整合相似度度量，最后得到模式匹配的相似度立方體。

（1）Max合并策略

Max策略是一種積極的相似度合并策略，這種策略的核心思想就是在各個相似度矩陣中選擇最高的度量值，不考慮其他值的計算結果。這種合并策略簡單，在某些特定場景下可能會有較好的表現。計算公式為：

（2）Average合并策略

Average策略作為加權平均組合策略的特例，對所有參與組合的相似度給予相同權重。這種組合策略假設合并之前相似度普遍較高的節點在平均之后的效果也良好。計算公式為：

（3）Sigmoid合并策略

Sigmoid函數是一個良好的閾值函數，具有平滑連續、嚴格單調的特性，合并中權值的選擇可以使參與計算的相似度值緊密結合起來。計算公式為：

其中，a為傾斜參數，影響函數的形狀，文中可以設定為1。Sigmoid函數對應幅值區間為（0，1）。因此，在合并相似度中，這種合并策略實際上將較高相似度賦予高權重比例，將較低相似度賦予低權重比例，實現相似度歸一化。結合Sigmoid函數，所有參與相似度組合的計算公式為：

（4）Nonlinear合并策略

Nonlinear相似度合并策略是擴展了的加權組合策略，此策略的主要思想是將相似度之間的相互依賴關系合并到綜合計算中。計算公式為：

公式的第一部分是不同相似度擬合，第二部分反映的是節點和結構之間相似度相互依賴關系，通過參數λ來合并這兩部分的計算結果。之所以使用Nonlinear相似度合并策略，是因為基于這樣的假設，即如果節點相似度越高，則節點越相似，從而不必要增加這兩部分之間的相互依賴關系；相反則需要減少這兩部分之間的依賴關系。第一部分和第二部分通過調整參數λ來擬合相似度，確保最后得到的相似度計算結果在[0，1]之間。

由于每一個相似度對于平均數的貢獻并不是相同的，其重要程度也是不同的，可以使用加權平均方法將計算后的不同相似度以一定權重進行配比。例如在本文的場景中，基于節點名稱的相似度可能比基于節點類型的相似度貢獻更大，因此權重配比也可能更高。加權平均的計算方式為：

從上述公式不難發現，不同的權重會直接影響最后的相似度計算結果。而擬合這些權值工作又是瑣碎的，因此權重的具體計算可以采用模擬退火算法[26]思想進行處理。模擬退火算法是一種隨機搜索算法，可以解決大規模解空間的組合優化問題。算法對當前解重復“產生新解→計算目標函數差→接受或舍棄新解”過程。算法除了接受較優的解外，還以一定的概率來接受一個比當前解要差的解，這樣有可能會跳出這個局部的最優解，直至得到求解問題的全局最優解。

Fig.6 Achieving global optimum圖6　尋找全局最優解

如圖6所示，從A開始模擬退火算法得到局部最優解B后，會以一定的概率接受到C的移動，經過幾次不是局部最優解的移動后會到達E點，這樣就跳出了局部最大值B。

模擬退火算法框架如圖7所示。

在此，狀態轉移概率（接受概率）通常采用Metropolis接受準則，即：

準則保證在高點時可接受與當前態差值較大的新狀態，在低點時只接受與當前態差值較小的新狀態。

基于上述思路，將退火算法應用到Nonlinear相似度合并策略中擬合計算參數。算法描述：

Fig.7 Framework of simulated annealing algorithm圖7　模擬退火算法框架

使用模擬退火算法計算加權平均中的權值具有以下優點：

（1）算法的解與初始解狀態無關；

（2）算法具有漸近收斂性，并已在理論上被證明以概率1收斂于全局最優解；

（3）算法可以并行處理。

5　實驗結果與分析

本文使用Java實現上述算法，實驗硬件環境為2.93 GHz Intel Core 2 CPU，2 GB內存；操作系統為Ubuntu 14.04 LTS（64位）。數據集采用XbenchMatch Benchmark[27]模式文件和Clio原型測試文件（http:// dblab.cs.toronto.edu/project/clio/），選擇以上數據集是因為它們分別來自不同的應用領域。數據集的基本統計信息如表3所示。

Table 3　Data set details表3　數據集描述

模式匹配的有效性評估中，分別使用準確率(P)、召回率(R)和F值(F-measure)表示匹配算法的正確程度、完善程度和權衡結果，計算公式表示為：

如圖8所示，在結合準確率和召回率后得到F值，表示匹配結果中錯誤匹配與丟失正確匹配的比值，較客觀、全面地評價了最后的匹配質量。

Fig.8 Matching result statistic圖8　匹配結果統計

圖9是單一相似度度量算法的匹配結果，從實驗結果中可以發現，匹配效果不是十分理想。這是因為單一的相似度度量算法，并不能很好地體現模式匹配整體的相似性。匹配結果中，基于名稱的相似度度量算法表現良好，在個別數據集上的F值也可以達到0.7以上，但是畢竟沒有融合其他特征信息，總體效果不十分理想。單一的基于節點類型、基于約束的算法效果較差，其原因是兩個XML文檔中匹配的大部分節點的類型使用String類型，約束則使用常用的約束限制，minOccurs＝0且maxOccurs＝unbound，從而無法準確區分哪些節點是精確匹配。

Fig.9 Matching results based on single similarity measure algorithms圖9　單一相似度度量算法結果

由此可以看出，基于節點名稱、基于節點類型、基于約束和基于結構的相似度度量算法，它們僅僅反映了元素的內部或外部特性，特征表現單一、模糊，不能全面體現元素節點的特征，最后結果表現一般。

本文采用的多策略相似度整合算法，彌補了單一匹配算法的局限性，并且在個別算法中采用了優化方法，提高了相似度度量計算中的匹配效果。本文實驗與經典的模式匹配算法Similarity Flooding[9]和COMA++[11]進行了對比。

圖10、圖11和圖12分別是基于多策略相似度整合的XML模式匹配方法與COMA++和Similarity Flooding模式匹配算法在準確率、召回率和F值的實驗對比。

Fig.10 Precision among all matching algorithms圖10　各匹配算法精確率比較

Fig.11 Recall among all matching algorithms圖11　各匹配算法召回率比較

通過圖10、圖11和圖12發現，基于多策略相似度整合的匹配算法中，Nonlinear合并策略整體表現良好。這是因為在該合并策略中，權重的計算采用了模擬退火算法思想進行處理，可以解決大規模權值空間的組合優化問題，從而尋找最適當的擬合參數。Nonlinear合并策略也不是在所有數據集都十分出色，但總體而言，Nonlinear策略匹配性能良好，如圖12所示。在多策略匹配方法中，Average合并策略和Sigmoid合并策略的表現也較為突出，雖然整體效果比不上COMA++（如圖13所示），但在部分測試數據集中匹配效果不錯。表現較差的是Max合并策略，盡管在部分數據集上召回率較高，造成這種結果的原因是此策略作為一種積極的相似度合并策略，在各個相似度矩陣中選擇最高的度量值，并不考慮其他值的計算結果，在這種情況下，直接過濾了矩陣中相似度度量結果為Top-2至Top-k的匹配對。

Fig.12 F-measure among all matching algorithms圖12　各匹配算法F值比較

Fig.13 F-measure among all measure algorithms圖13　各度量算法平均F值比較

綜合以上各算法的平均F值，發現基于多種組合策略的相似度度量算法，其整體匹配質量要比單一的相似度度量算法出色。Nonlinear合并策略和Average合并策略表現出色，Max策略簡單，展示結果遜于其他策略（與文獻[28]的結論相同），在某些場合中可能會有比較好的結果。當然，針對不同的數據集，各種策略的表現也有差異，因此在模式匹配中，可以考慮結合多種匹配策略，得到合適的匹配結果。

6　結束語

模式匹配用于發現不同數據源中概念之間的語義對應關系，成為數據集成、數據交換等領域的研究熱點。由于模式匹配存在固有的復雜性，目前模式匹配工作主要是依靠領域專家來手工完成。本文針對目前XML模式匹配的挑戰，深入研究了XML模式匹配特征，展示了不同層面的XML相似度度量方法，包括基于節點名稱、類型等多種相似度度量方法，得到相似度度量矩陣。為避免單一相似度度量方法的局限性，采用多策略相似度整合方式擬合所得到的相似度矩陣，并且使用啟發式隨機搜索算法，避免人工擬合或窮舉所有參數。最后，通過基準測試平臺對比，部分策略相比于經典的模式匹配工具具有較高的精確度和召回率。

在未來工作中，考慮重用先期的匹配工作，避免在后續處理中重復計算相同內容。在組合策略中，可以考慮使用機器學習或神經網絡中更復雜的優化策略，進一步提高匹配質量。

References:

[1] Gou Gang, Chirkova R. Efficiently querying large XML data repositories: a survey[J]. IEEE Transactions on Knowledge and Data Engineering, 2007, 19(10): 1381-1403.

[2] Fagin R, Kolaitis PG, Miller R J, et al. Data exchange: semantics and query answering[C]//LNCS 2572: Proceedings of the 9th International Conference on Database Theory, Siena, Italy, Jan 8-10, 2003. Berlin, Heidelberg: Springer, 2003: 207-224.

[3] Arenas M, Libkin L. XML data exchange: consistency and query answering[J]. Journal of the Association for Computing Machinery, 2008, 55(2): 13-24.

[4] Rahm E, Bernstein PA. A survey of approaches to automatic schema matching[J]. VLDB Journal, 2001, 10(4): 334-350.

[5] Bellahsene Z, Bonifati A, Rahm E. Schema matching and mapping[M]. Berlin, Heidelberg: Springer, 2011.

[6] Euzenat J, Shvaiko P. Ontology matching[M]. Berlin, Heidelberg: Springer, 2007.

[7] Shvaiko P, Euzenat J. Ontology matching: state of the art and future challenge[J]. IEEE Transactions on Knowledge and Data Engineering, 2013, 25(1): 158-176.

[8] Xing Guangming. Approximate matching of XML documents with schemata using tree alignment[C]//Proceedings of the 2014 ACM Southeast Regional Conference, Kennesaw, USA, Mar 28-29, 2014. New York, USA:ACM, 2014: 43.

[9] Melnik S, Garcia-Molina H, Rahm E. Similarity flooding: a versatile graph matching algorithm and its application to schema matching[C]//Proceedings of the 18th International Conference on Data Engineering, San Jose, USA, Feb 26-Mar 1, 2002. Piscataway, USA: IEEE, 2002: 117-128.

[10] Lambrix P, Tan He, Xu Wei. Literature-based alignment of ontologies[C]//Proceedings of the 3rd International Workshop on Ontology Matching Collocated with the 7th International Semantic Web Conference, Karlsruhe, Germany, Oct 26, 2008.

[11] Peukert E, Massmann S, Konig K. Comparing similarity combination methods for schema matching[C]//LNI 175 Service Science: GI-Workshop, Informations Integration in Service-Architekturen, Leipzig, Germany, 2010: 692-701.

[12] Li Juanzi, Tang Jie, Li Yi, et al. RiMOM: a dynamic multistrategy ontology alignment framework[J]. IEEE Transactions on Knowledge and Data Engineering, 2009, 21(8): 1218-1232.

[13] Zhang Zhi, Shi Pengfei. An efficient greedy algorithm for schema matching[J]. Journal of Computer Research and Development, 2007, 44(11): 1903-1911.

[14] Ehrig M, Staab S. Quick ontology matching[C]//LNCS 3298: Proceedings of the 3rd International Semantic Web Conference, Hiroshima, Japan, Nov 7-11, 2004. Berlin, Heidelberg: Springer, 2004: 683-697.

[15] Do H H, Rahm E. Matching large schemas: approaches and evaluation[J]. Information System, 2007, 32(6): 857-885.

[16] Saha B, Stanoi I, Clarkson K. Schema covering: a step towards enabling reuse in information integration[C]//Proceedings of the 26th International Conference on Data Engineering, Long Beach, USA, Mar 1-6, 2010. Piscataway, USA: IEEE, 2010: 285-296.

[17] Algergawy A, Nayak R, Saake G. Element similarity measures in XML schema matching[J]. Information Sciences, 2010, 180(24): 4975-4998.

[18] Agreste S, De Meo P, Ferrarac E, et al. XML matchers: approaches and challenges[J]. Knowledge Based Systems, 2014, 66: 190-209.

[19] Ullmann J R. A binary n-gram technique for automatic correction of substitution, deletion, insertion and reversal errors in words[J]. Computer Journal, 1977, 20(2): 141-147.

[20] Winkler W E. String comparator metrics and enhanced decision rules in the Fellegi-Sunter model of record linkage[C]// Proceedings of the Section on Survey Research Methods, 1990: 354-359.

[21] Smith T F, Waterman M S. Identification of common molecular subsequences[J]. Journal of Molecular Biology, 1981, 147(1): 195-197.

[22] Monge A, Elkan C. The field matching problem: algorithms and applications[C]//Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining, Oregon, USA, 1996: 267-270.

[23] Jaro MA.Advances in record linkage methodology[J]. Journal of the American Statistical Association, 1989, 84(406): 414-420.

[24] Nayak R, Tran T. A progressive clustering algorithm to group the XML data by structural and semantic similarity[J]. Schema Recognition and Artificial Intelligence, 2007, 21(4): 723-743.

[25] Sunna W, Cruz I F. Structure-based methods to enhance geospatial ontology alignment[C]//LNCS 4853: Proceedings of the 2nd International Conference, Mexico City, Nov 29-30, 2007. Berlin, Heidelberg: Springer, 2007: 82-97.

[26] Kirkpatrick S,Gelatt C.Optimizationbysimulatedannealing[J]. Science, 1988, 220(4598): 671-680.

[27] Fabien D, Bellahsene Z, Hunt E. XBenchMatch：a benchmark for XML schema matching tools[C]//Proceedings of the 33rd International Conference on Very Large Data Bases, Vienna, Austria, Sep 23-27, 2007: 1318-1321.

[28] Do H H, Rahm E. Matching large schemas: approaches and evaluation[J]. Information Systems, 2007, 32(6): 857-885.

附中文參考文獻：

[13]張治,施鵬飛.一種有效的貪婪模式匹配算法[J].計算機研究與發展, 2007, 44(11): 1903-1911.

FAN Hongjie was born in 1984. He is a Ph.D. candidate at Peking University. His research interests include data exchange technology and schema matching, etc.

范紅杰（1984—），男，浙江湖州人，北京大學博士研究生，主要研究領域為數據交換技術，模式匹配等。

LIU Junfei was born in 1965. He is a professor and Ph.D. supervisor at School of Electronics Engineering and Computer Science, Peking University. His research interests include software engineering, information exchange technology and smart city, etc.

柳軍飛（1965—），男，湖南人，北京大學信息科學技術學院教授、博士生導師，主要研究領域為軟件工程，信息交換技術，智慧城市等。

ZHOU Ludong was born in 1991. He is an M.S. candidate at Peking University. His research interests include information exchange technology, software engineering and machine learning, etc.

周魯東（1991—），男，山東臨沂人，北京大學碩士研究生，主要研究領域為信息交換技術，軟件工程，機器學習等。

MA Zhiyi was born in 1963. He is an associate professor at Peking University. His research interests include software modeling technology and model driven development, etc.

麻志毅（1963—），男，內蒙古赤峰人，北京大學信息科學技術學院副教授，主要研究領域為軟件建模技術，模型驅動開發方法等。

XMLSchema Matching Based on Multi-Strategy Similarity Integration*

FAN Hongjie1, LIU Junfei2+, ZHOU Ludong1, MAZhiyi1
1. School of Electronics Engineering and Computer Science, Peking University, Beijing 100871, China
2. National Engineering Research Center for Software Engineering, Peking University, Beijing 100871, China
+ Corresponding author: E-mail: liujunfei@pku.edu.cn

FAN Hongjie, LIU Junfei, ZHOU Ludong, et al. XMLschema matching based on multi-strategy similarity integration. Journal of Frontiers of Computer Science and Technology, 2016, 10(1)：14-24.

Abstract:Schema matching, as finding the semantic correspondence of concepts between different data sources, becomes the hot topic of data integration, data exchange and other areas. Researchers have proposed a number of matching methods, which make it possible to identify and discover the semantic correspondence between the XML data. But XML schema matching has some challenges, such as how to consider the variety of similarity, and how to integrate the similarity so as to make the optimum matching results. In order to improve the quality of XML matching, firstly this paper calculates the similarity of XML nodes and structure from the different levels, gets the similarity matrix, and integrates the similarity measure between these two aspects effectively. Then, this paper fits through a variety of strategies combination and optimization algorithms to make the final matching result achieve global optimum after the effective integration of these two aspects of similarity measure. Finally, compared with the classic schema matching tool, this method has a higher precision and recall rate through the benchmark platform.

Key words:data exchange; schema matching; extensible markup language（XML）; similarity measure; multi-strategy integration

文獻標志碼：A

中圖分類號：TP311

doi:10.3778/j.issn.1673-9418.1507071