XML Schema匹配中的元素相似性度量算法研究

茍和平，景永霞，姜永亮

(1. 瓊臺師范高等專科學(xué)校 信息技術(shù)系，海南 海口 571127;2. 海南師范大學(xué) 網(wǎng)絡(luò)中心，海南 海口 571127)

XML Schema匹配中的元素相似性度量算法研究

茍和平1，景永霞1，姜永亮2

(1. 瓊臺師范高等?？茖W(xué)校 信息技術(shù)系，海南 ?？?571127;2. 海南師范大學(xué) 網(wǎng)絡(luò)中心，海南 ?？?571127)

為了實(shí)現(xiàn)XML Schema自動匹配，解決XML數(shù)據(jù)共享問題，提出一種基于語義和結(jié)構(gòu)的模式自動匹配算法。首先采用基于單詞網(wǎng)絡(luò)(wordnet)的語義匹配算法及字符串結(jié)構(gòu)匹配(n-grams)算法計(jì)算來自兩個模式樹中節(jié)點(diǎn)對名稱相似度，然后獲取包含此節(jié)點(diǎn)對的各自路徑集，再通過計(jì)算對應(yīng)路徑集中每對路徑的最大相似度獲得此節(jié)點(diǎn)對的結(jié)構(gòu)相似度。實(shí)驗(yàn)分析表明此方法具有較好的查全率和查準(zhǔn)率。

XML Schema；模式匹配；語義；路徑相似

目前，在數(shù)據(jù)集成、數(shù)據(jù)倉庫和數(shù)據(jù)挖掘等許多數(shù)據(jù)共享應(yīng)用中，模式匹配是非常關(guān)鍵的技術(shù)之一[1]。由于數(shù)據(jù)模式多樣，結(jié)構(gòu)復(fù)雜，給數(shù)據(jù)模式的自動集成帶來很大的困難[2]。隨著XML的出現(xiàn)和廣泛應(yīng)用，XML已經(jīng)成為數(shù)據(jù)表示和交換的標(biāo)準(zhǔn)。因此，實(shí)現(xiàn)XML Schema的自動集成，是實(shí)現(xiàn)XML型數(shù)據(jù)共享應(yīng)用的關(guān)鍵。目前已經(jīng)出現(xiàn)很多的XML Schema模式匹配方案和匹配系統(tǒng)，其中，比較典型的系統(tǒng)有Cupitd、COMA/COMA++、Similarity Flooding(SF)、SMatch等[3-4]。為解決XML文檔之間的相似性，實(shí)現(xiàn)XML文檔聚類，文獻(xiàn)[5-6]把XML文檔樹表示為節(jié)點(diǎn)路徑的集合，然后通過計(jì)算路徑相似度進(jìn)而實(shí)現(xiàn)XML文檔相似性的判定。本文在此基礎(chǔ)上，提出一種基于最大公共路徑相似度匹配的XML Schema匹配算法。通過對XML Schema樹中的所有節(jié)點(diǎn)進(jìn)行語言學(xué)相似性分析，并將模式樹表示成從根節(jié)點(diǎn)出發(fā)到葉子節(jié)點(diǎn)的路徑集合，然后對路徑中的節(jié)點(diǎn)進(jìn)行相似度分析，找出待對比兩條路徑的公共最大相似子路徑，以計(jì)算節(jié)點(diǎn)之間的結(jié)構(gòu)相似性。

1 改進(jìn)的XML Schema模式匹配算法

1.1 XML Schema匹配算法的基本概念

為后續(xù)計(jì)算方便，先給出幾個相關(guān)的定義。

定義1模式樹。對于一個給定的XML Schema，將其表示成樹形結(jié)構(gòu)T={N,E}，其中N(n1,n2,…,nn)，表示模式中節(jié)點(diǎn)的集合；E{(ni,nj)|(ni,nj)∈N}，表示模式樹中邊的集合。

定義2路徑與子路徑。一條路徑p=，是由若干條邊組成的序列，其中k表示邊的條數(shù)。對于路徑pi=，如果序列是序列的子序列，則pi是p的子路徑。

定義3最大相似路徑。給定兩條包含節(jié)點(diǎn)ni、nj的路徑pi、pj，最大相似路徑P(pi,pj)是指pi、pj所有包含節(jié)點(diǎn)ni、nj的子路徑中，以節(jié)點(diǎn)ni、nj對應(yīng)起始的所有連續(xù)相似節(jié)點(diǎn)組成的路徑。

模式樹T1、T2如圖1所示，其中待比較節(jié)點(diǎn)元素n1,n2，其相似性度量主要通過節(jié)點(diǎn)的內(nèi)部屬性和外部結(jié)構(gòu)關(guān)系來決定。內(nèi)部屬性的相似度即節(jié)點(diǎn)的語言學(xué)相似度lingSim(N1,N2)，通過計(jì)算節(jié)點(diǎn)的名稱、數(shù)據(jù)類型和基數(shù)約束等相似度獲得；外部結(jié)構(gòu)即節(jié)點(diǎn)的結(jié)構(gòu)相似度strucSim(n1,n2)，是指節(jié)點(diǎn)的祖先節(jié)點(diǎn)和孩子節(jié)點(diǎn)的相似性分析。節(jié)點(diǎn)相似度的計(jì)算如公式(1)所示。

nodeSim(n1,n2)=w1*lingSim(n1,n2)+w2*strucSim(n1,n2)

(1)

式中w1、w2分別是語言學(xué)相似度和結(jié)構(gòu)相似度的權(quán)重，w1+w2=1。同時在計(jì)算節(jié)點(diǎn)相似度時需要指定語義相似度閾值和路徑相似度閾值。

1.2 語言學(xué)相似度

對于兩個節(jié)點(diǎn)n1∈T1,n2∈T2，則其語言學(xué)相似度lingSim(n1,n2)由計(jì)算節(jié)點(diǎn)的名稱相似度(nameSim)、數(shù)據(jù)類型相似度(datatypeSim)和約束相似度(constSim)來決定，如公式(2)所示。

圖1 XML Schema模式樹

lingSim(n1,n2)=λ1*nameSim(n1,n2)+

λ2*datatypeSim(n1,n2)+

λ3*constSim(n1,n2)

(2)

式中λ1、λ2、λ3分別是對應(yīng)相似度的權(quán)重，且λ1+λ2+λ3=1。

1)名稱相似度計(jì)算

對于節(jié)點(diǎn)名稱相似度主要是從節(jié)點(diǎn)元素的name屬性，如：，屬性name的值為″res_state″。對于節(jié)點(diǎn)n1、n2的name屬性值字符串進(jìn)行預(yù)處理，主要是實(shí)現(xiàn)字符串的拆分、去除一些虛詞和特殊連字符等。分解成獨(dú)立的單詞集(tokens)T1和T2，然后進(jìn)行語義匹配和字符串結(jié)構(gòu)分析，其中語義匹配主要是采用基于wordnet[7]來計(jì)算。名稱相似度計(jì)算如公式(3)所示。

(3)

式中，sim(t1,t2)=

max(semanticSim(t1,t2),ngramSim(t1,t2))，

|T1|和|T2|為兩個名字字符串包含的獨(dú)立單詞數(shù)，字符串結(jié)構(gòu)匹配(ngramSim)采用n-grams方法[8]計(jì)算。

例如：t1=″date″，t2=″day″,采用wordnet計(jì)算語義相似結(jié)果為：semanticSim(t1,t2)=0.9176；本文采用2-gram方法計(jì)算結(jié)構(gòu)相似度，名稱date和day分別表示為{da,at,te}和{da,ay}，則

式中：a為t1中包含2-gram 的數(shù)量；b為t2中包含2-gram的數(shù)量；c為t1、t2中包含公共2-gram的數(shù)量。

2)數(shù)據(jù)類型相似度

數(shù)據(jù)類型相似度是節(jié)點(diǎn)語言學(xué)匹配的另一個主要指標(biāo)，有些節(jié)點(diǎn)雖然在語義上非常相似，但由于其數(shù)據(jù)類型不同，也可能表達(dá)完全不同的意思。因此，本文在進(jìn)行數(shù)據(jù)類型匹配時需要查詢文獻(xiàn)[6,9]提出的數(shù)據(jù)類型相似度表(如表1所示)，以獲得數(shù)據(jù)類型匹配程度。

表1 數(shù)據(jù)類型相似度表

3)基數(shù)約束相似性分析

基數(shù)約束主要是對XML Schema 模式中節(jié)點(diǎn)的minOccurs和maxOccurs兩個屬性進(jìn)行相似性判斷，minOccurs和maxOccurs取值及和DTD的關(guān)系如表2所示。其取值的相似性主要是通過與DTD中的約束關(guān)系進(jìn)行映射得到基數(shù)約束的相似度表[6](如表3所示)。本文中的基數(shù)約束相似度主要是通過查詢此相似度表獲得。

表2 XSD和DTD之間的映射關(guān)系

表3 基數(shù)約束相似度表

1.3 節(jié)點(diǎn)結(jié)構(gòu)相似度

節(jié)點(diǎn)結(jié)構(gòu)相似度主要是計(jì)算兩個節(jié)點(diǎn)所對應(yīng)的路徑相似度。這樣能夠避免由于本來不應(yīng)匹配的元素由于語義相同而匹配在一起。對于節(jié)點(diǎn)n1∈T1,n2∈T2，則n1、n2的結(jié)構(gòu)相似度計(jì)算如下:

1)分別計(jì)算包含節(jié)點(diǎn)n1、n2的路徑集P1={pi}(i=1,2,…,m)，P2={pj}(j=1,2,…,n),其中，m、n分別指P1、P2中所包含的路徑個數(shù)。

2)對于P1中的路徑pi，分別計(jì)算與P2中的各個路徑pj的最大相似度MSP(pj,pi)。

3)對于P2中的路徑pj，分別計(jì)算與P1中的各個路徑pi最大相似度MSP(pi,pj)。

4)計(jì)算機(jī)兩個節(jié)點(diǎn)的結(jié)構(gòu)相似度。

計(jì)算方法如公式(4)所示。

(4)

式中，最大相似度MSP(pi,pj)的計(jì)算過程如下：

設(shè)pi=={a,b,c,d,e,n1,f,g,h,i,j,k},pj=={1,2,3,4,5,n2,6,7,8}兩條路徑中包含n1、n2兩個待計(jì)算結(jié)構(gòu)相似度節(jié)點(diǎn)，如圖2所示。

根據(jù)圖2所示，以(n1,n2)節(jié)點(diǎn)對為初始點(diǎn)，分別向前和向后比較兩個路徑中的節(jié)點(diǎn)對。在上例中，向前比較，則先比較(f,5)，如果(f,5)的語言學(xué)相似度大于指定的語言學(xué)相似度閾值，則將此節(jié)點(diǎn)的語言學(xué)相似度加入到MSP(pi,pj)中，分別移動兩路徑的指針，進(jìn)行下一輪比較，即(e,4)節(jié)點(diǎn)對的比較，直到其節(jié)點(diǎn)對語言相似度小于指定閾值時，向前比較停止，然后繼續(xù)后向節(jié)點(diǎn)對的比較，即開始比較節(jié)點(diǎn)對(g,6)等，方法同前向比較。具體計(jì)算算法如下：

圖2 路徑最大相似度計(jì)算示例

輸入：待計(jì)算的兩條路徑pi、pj

輸出：路徑最大相似度MSP(pi,pj)

elea[]=pi.split(″/″);

eleb[]=pj.split(″/″);

numa=elea.length;

numb=eleb.length;

m=k=location(pi,n1);

n=l=location(pj,n2);

while(m>0 &&n>0){

sim=lingSim(elea[m-1],elea[n-1]);

if(sim>0)eachpathsim=eachpathsim+sim;

else break;

m--;

n--;

}

while(k

k++;

j++;

sim=lingSim(elea[k],elea[l]);

if(sim>0)eachpathsim=eachpathsim+sim;

else break;

}

max=(numa>numb? numa:numb);

MSP(pi,pj)=eachpathsim/(max-1);

2 實(shí)驗(yàn)分析

根據(jù)圖1所示的XML Schema模式樹，將其進(jìn)行節(jié)點(diǎn)和路徑序列化后，得到模式樹中的節(jié)點(diǎn)集N和路徑集合P。其中路徑主要是從根節(jié)點(diǎn)出發(fā)到達(dá)各個葉子節(jié)點(diǎn)的路徑，路徑集如表4、表5所示。

表4 模式T1的路徑集P1

表5 模式T2的路徑集P2

根據(jù)文獻(xiàn)[1]中算法的匹配參數(shù)選擇辦法，選用其相應(yīng)的參數(shù)為：權(quán)重值w1=0.5、w2=0.5、λ1=0.8、λ2=0.1、λ3=0.1及語義和路徑相似度閾值γ1=0.3、γ2=0.3，則模式樹T1和T2的節(jié)點(diǎn)語義相似度矩陣和結(jié)構(gòu)相似度如圖3和圖4所示，其最終的節(jié)點(diǎn)匹配結(jié)果如圖5所示。

圖3 模式樹T1和T2的節(jié)點(diǎn)語義相似度矩陣

圖4 模式樹T1和T2的節(jié)點(diǎn)結(jié)構(gòu)相似度矩陣

圖5 模式樹T1和T2的節(jié)點(diǎn)匹配相似度矩陣

通過上述XML Schema模式節(jié)點(diǎn)的語言學(xué)和結(jié)構(gòu)匹配算法和圖5所示的計(jì)算結(jié)果，獲得兩個模式中所匹配的節(jié)點(diǎn)如表6所示。

XML Schema匹配的評價標(biāo)準(zhǔn)主要是查準(zhǔn)率(precision)、查全率(recall)和F-measure，計(jì)算如公式5所示。

(5)

式中：A表示本來相似但沒有識別出匹配的節(jié)點(diǎn)；B表示識別出的正確匹配的節(jié)點(diǎn)；C表示識別出的錯誤匹配的節(jié)點(diǎn)。

表6 模式樹中的節(jié)點(diǎn)匹配映射表

本文同時實(shí)現(xiàn)了文獻(xiàn)[1]中提出的XML Schema匹配算法，對于上述實(shí)驗(yàn)案例，在相同的權(quán)重與相似度閾值的條件下，其與本文算法的查準(zhǔn)率(precision)、查全率(recall)和F-measure的值比較如圖6所示。實(shí)驗(yàn)結(jié)果表明，本文算法的F-Measure的值比文獻(xiàn)[1]提出算法的值高，表明此算法能夠較好地識別不同模式中的相似節(jié)點(diǎn)對。

圖6 算法性能比較

3 結(jié)束語

本文提出的一種基于節(jié)點(diǎn)元素的語言相似度和結(jié)構(gòu)相似度的模式匹配算法，主要是針對節(jié)點(diǎn)元素在語言相似度大于指定閾值的前提下進(jìn)行節(jié)點(diǎn)的結(jié)構(gòu)匹配。結(jié)構(gòu)匹配主要是計(jì)算節(jié)點(diǎn)的路徑相似度，通過找出包含待對比節(jié)點(diǎn)的所有路徑集，對于路徑集中的每對待匹配路徑計(jì)算出其最大相似度作為結(jié)構(gòu)相似度。實(shí)驗(yàn)結(jié)果表明，本文提出的算法具有較好的可行性，但由于在算法中采用了wordnet單詞網(wǎng)絡(luò)計(jì)算語義相似度，致使計(jì)算時間增加。如何采用一種自翻譯的技術(shù)來實(shí)現(xiàn)語義相似度計(jì)算，將是今后的努力方向。

[1]Algergawy A,Nayak R,Saake G. XML Schema Element Similarity Measures:A Schema Matching Context[C].In:On the Move to Meaningful Internet Systems:OTM 2009,Vilamoura,Portugal,1-6,2009:1-6.

[2]李君君.信息集成:基于XML Schema 的模式匹配[J].情報科學(xué),2006,24(11):1696-1699.

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

[4]Giunchiglia F,Shvaiko P,Yatskevich M.S-Match.an algorithm and an implementation of semantic matching[C].Also:In Proceedings of the European Semantic Web Symposium,LNCS 3053,2004:61-75.

[5]Nayak R,Tran T.A Progressive Clustering Algorithm to Group the XML Data by Structural and Semantic Similarity[J].International Journal of Pattern Recognition and Artificial Intelligence,2007,21(4):723-743.

[6]王大剛,謝榮傳,彭俊.基于XML Schema 的數(shù)據(jù)匹配方法的研究[J].計(jì)算機(jī)技術(shù)與發(fā)展，2008,18(6):28-31.

[7]George M,Christiane F.WordNet:An Electronic Lexical Database[M].cambridge:MIT Press,1998:23-46.[8]Nayak R,Tran T.A progressive clustering algorithm to group the XML data by structural and semantic similarity[J].International Journal of Pattern Recognition and Artificial Intelligence,2007,21(4):723-743.

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

StudyonElementSimilarityMeasureinXMLSchemaMatching

GOU Heping1,JING Yongxia1,JIANG Yongliang2

(1. Department of Information Technology,Qiongtai Teachers College,Haikou 571127,China;2. Network Center,HaiNan Normal University,Haikou 571127,China)

Order to realize the XML schema matching and to solve the difficulty of XML data sharing,an approach based on semantics and structure is presented in this to achieve automatic schema matching.Semantic measure based on wordnet techniques and syntactic measure based on n-grams are proposed to find similarity degree among schema tree element names.The structural similarity among two different XML schema elements is measured by finding the maximum similarity in which each pair path includes the two elements respectively.Experimental results indicate that the proposed method has high precision and recall.

XML Schema;schema matching;semantics;path similarity

2014-03-24

國家自然科學(xué)基金項(xiàng)目(71361008)；海南省自然科學(xué)基金項(xiàng)目(612136)；海南省高等學(xué)校科學(xué)研究項(xiàng)目(Hjkj2013-53)

茍和平(1978—)，男，副教授，研究方向：信息集成、數(shù)據(jù)挖掘。

1003-1251(2014)05-0015-06

TP311.5

A

馬金發(fā))