蘇慧群

(湖南師范大學(xué)樹達(dá)學(xué)院，湖南長沙410012)

XML文檔數(shù)對(duì)序列模型與結(jié)構(gòu)相似度算法研究

蘇慧群*

(湖南師范大學(xué)樹達(dá)學(xué)院，湖南長沙410012)

為了更快更有效地計(jì)算XML文檔之間的結(jié)構(gòu)相似度，本文提出了一種新的數(shù)學(xué)模型——數(shù)對(duì)序列模型，同時(shí)在這個(gè)模型基礎(chǔ)上改進(jìn)了傳統(tǒng)樹模型的動(dòng)態(tài)規(guī)劃算法，并提出了一個(gè)新的更有效的算法——CA算法。實(shí)驗(yàn)證明，與傳統(tǒng)方法相比，這個(gè)算法無論在最后的準(zhǔn)確率、召回率還是時(shí)空復(fù)雜度上都有明顯的改進(jìn)。

XML;數(shù)對(duì)序列模型;相似度;算法

隨著Web網(wǎng)上信息的爆炸增長，研究半結(jié)構(gòu)化文檔(特別是HTML和XML文檔)相似度計(jì)算的問題變得越來越重要，尤其是在信息抽取、文檔聚類與信息檢索領(lǐng)域里，文檔相似度計(jì)算起了極其重要的支撐作用。本文提出了一種新的模型——數(shù)對(duì)序列模型，用于解決傳統(tǒng)算法和樹編輯距離算法時(shí)空復(fù)雜度過高的問題。在數(shù)對(duì)序列模型的基礎(chǔ)上，本文又提出多種計(jì)算XML文檔結(jié)構(gòu)相似度的算法，并進(jìn)行比較研究。實(shí)驗(yàn)結(jié)果表明，本文的方法更顯著地提高了識(shí)別具有先同結(jié)構(gòu)的XML文檔的能力，并且對(duì)文檔有很好的聚類效果。

1 數(shù)對(duì)序列模型

1.1 基本定義

1.1.1 數(shù)對(duì)序列的基本描述

定義1.1結(jié)點(diǎn)位置信息:在一個(gè)森林S中，不妨設(shè)這個(gè)森林有n棵樹依次為:T1，T2，…，Tn，一個(gè)結(jié)點(diǎn)x，若其不為樹的根結(jié)點(diǎn)，x是其父結(jié)點(diǎn)的第m個(gè)孩子，則結(jié)點(diǎn)x的位置信息為m，記seat(x)=m，如果結(jié)點(diǎn)x為森林S第i棵樹的根結(jié)點(diǎn)，則結(jié)點(diǎn)x的位置信息為i，記seat(x)=i。

定義1.2路徑位置信息:設(shè)P為樹T一條從根結(jié)點(diǎn)到葉結(jié)點(diǎn)的路徑，P上所有結(jié)點(diǎn)依次為n1，n2，…，nd，d(d≥0)為結(jié)點(diǎn)個(gè)數(shù)，則P路徑位置信息定義為一組序列，記為:seat(p)=seat(n1)，seat(n2)，…，seat(nd)。

有了上述定義，我們就可以通過增加路徑位置信息來改進(jìn)傳統(tǒng)的樹路徑模型，我們稱這個(gè)模型為樹路徑位置信息模型。

定義1.3樹路徑位置信息模型:設(shè)一個(gè)XML文檔x，其對(duì)應(yīng)的森林為S，并且S上所有從根結(jié)點(diǎn)到葉結(jié)點(diǎn)的路徑從左到右依次為:P1，P2，…，Pn(n表示路徑總數(shù))。則我們稱下式為文檔x的樹路徑位置信息模型。

定義1.4變量α編碼:變量α編碼是指對(duì)一個(gè)變量所有可能性值的集合到集合{m|m∈N∧0≤m≤2α}的映射，此映射記作codeα，某個(gè)具體可能值x的具體編碼值可記為codeα(x)，α表示的是編碼因子。

顯然，由定義1.1和定義1.2易知結(jié)點(diǎn)的位置信息和結(jié)點(diǎn)的具體值范圍非常大，我們可以將其映射到一個(gè)較小的范圍內(nèi)，從而降低計(jì)算機(jī)存儲(chǔ)代價(jià)。比如，我們?nèi)ˇ翞?6，則編碼范圍只有［0，4095］，此時(shí)如果有一個(gè)結(jié)點(diǎn)有多于4096個(gè)子結(jié)點(diǎn)，則必然有兩個(gè)子結(jié)點(diǎn)編碼相同。也許，讀者會(huì)認(rèn)為編碼相同會(huì)導(dǎo)致計(jì)算結(jié)果有誤差，不過當(dāng)α取值較大時(shí)，這種誤差幾乎可以忽略不計(jì)，原因是在現(xiàn)實(shí)的XML文檔中很少會(huì)出現(xiàn)有很多個(gè)結(jié)點(diǎn)的子結(jié)點(diǎn)數(shù)都非常大的情況，就算出現(xiàn)這種情況，也不會(huì)對(duì)最終相似度計(jì)算結(jié)果有多大影響。

定義1.6序列α編碼量大小:α編碼量大小其實(shí)表示的是一個(gè)序列變量的個(gè)數(shù)，設(shè)u為一個(gè)codeα編碼值，則u的α編碼量大小為sizeα(u)=(log2u)/α。

定義1.7序列α解碼:給定一個(gè)序列的α編碼值，求解出這個(gè)序列所有變量的編碼序列，為這個(gè)序列α解碼，記為decodeα，一個(gè)具體編碼值v的α解碼為decodeα(v)。顯然decodeα(v)為一個(gè)序列，第i個(gè)元素值記作decodeα(v)［i］，由定義1.4可知:decodeα(v)［i］=?v/2α(i-1)」%(2α)其中?」表示取下整，m%n表示是m整除n后的余數(shù)。

定義1.9 α數(shù)對(duì)序列:設(shè)S為一個(gè)森林，S的所有從根結(jié)點(diǎn)到葉結(jié)點(diǎn)的路徑從左到右依次設(shè)為p1，p2，…，pi;l(l≥0)為路徑個(gè)數(shù)，則森林S的α數(shù)對(duì)序列pairsα(T)=(y1，y2，…，yl)，其中y1=pairα(p1)，1＜j＜l。

上述定義，給出了一個(gè)森林(可以是XML文檔的DOM樹)的數(shù)對(duì)序列描述，數(shù)對(duì)序列是有多個(gè)自然數(shù)對(duì)序列成，因此在實(shí)際計(jì)算中，計(jì)算代價(jià)會(huì)大大減少。

那么如何計(jì)算一棵樹的數(shù)對(duì)序列呢?實(shí)際上計(jì)算一棵樹的數(shù)對(duì)序列很簡單，只需先遍歷這棵樹的所有結(jié)點(diǎn)，計(jì)算出所有結(jié)點(diǎn)的位置信息，然后在計(jì)算出路徑位置信息以及路徑，再根據(jù)α編碼分別求出所有路徑對(duì)應(yīng)的數(shù)對(duì)，從而得到這棵樹的數(shù)對(duì)序列，顯然時(shí)間復(fù)雜度為O(|T|)，|T|表示這棵樹的結(jié)點(diǎn)數(shù)。如果要計(jì)算兩個(gè)XML文檔的結(jié)構(gòu)相似度，只需計(jì)算這兩個(gè)文檔數(shù)對(duì)序列的相似度即可。

定義1.10數(shù)對(duì)序列模型:數(shù)對(duì)序列模型是一個(gè)三元組∏=(α，code，valueweight)，其中α為編碼因子，code是編碼規(guī)則，valueweight(0≤valueweight≤1)是數(shù)對(duì)計(jì)算過程中第二個(gè)自然數(shù)所占的權(quán)重。

1.1.2 數(shù)對(duì)序列的基本操作

與樹模型相似的是，本文也對(duì)數(shù)對(duì)序列定義了三組最基本的操作Delete，Update，Insert。定義這三個(gè)基本操作之前，首先定義兩個(gè)權(quán)值seatweight、valueweight和一個(gè)更基本的函數(shù)Common，其中seatweight表示位置權(quán)重，valueweight表示值權(quán)重，這兩個(gè)權(quán)重滿足seatweight+valueweight=1

定義1.13最前公共最前子序列與Common值:設(shè)兩個(gè)序列P1和P2，P1的序列為n1，n2，…，nl，P2的序列為，則P1和P2的最前公共子序列為n1，n2，…，nr其中r是指使等式都成立的最大的i，同時(shí)r即為這兩個(gè)序列的Common值，記為。

定義1.14自然數(shù)n1，n2的α Common值:是指將自然數(shù)n1，n2進(jìn)行α解碼后得到兩個(gè)序列的Common值。Commonα(n1，n2)=Common(decodeα(n1)，decodeα(n2))。

定理1.2自然數(shù)n1，n2的α Common值可以用以下公式求得:

Commonα(n1，n2)=?f(|n1-n2|)/α」，其中f(x)表示x二進(jìn)制式末尾0的個(gè)數(shù)，例如f(1010100000B)=5。證明比較簡單略。

定理1.3數(shù)對(duì)α Common值定理

有了最基本的Common操作后，下面定義三個(gè)基本操作，Delete，Insert，Update。

定義1.15序列P1和P2的Delete值:表示序列P1轉(zhuǎn)換為P1和P2最前公共最前子序列，所需的刪除元素(變量)數(shù)，顯然Delete(p1，p2)=size(p1)-Common(p1，p2)。(1.1.2.4)

定義1.16序列P1和P2的Insert值:表示P1和P2最前公共最前子序列轉(zhuǎn)化為P2所需的增加元素(變量)數(shù)，顯然Insert(P1，P2)=size(P2)-Common(P1，P2)。(1.1.2.5)

定義1.17序列P1和P2的Update值:Update(p1，p2)=Delete(p1，p2)+Insert(p1，p2)。(1.1.2.6)

根據(jù)1.11同理可以定義自然數(shù)和數(shù)對(duì)α Delete，Insert，Update值，具體計(jì)算方法為:

1.2 CA算法

在本節(jié)中，本文提出了CA算法，進(jìn)一步提高了計(jì)算效率，查全率與查準(zhǔn)率。

算法:μ逐對(duì)比較β衰減算法(CA算法)

目的:計(jì)算兩個(gè)數(shù)對(duì)序列的相似度

輸入:P=(p1，p2，…，pm)，Q=(q1，q2，…，qn)，衰減因子β(0≤β≤1)，步長μ(表示要尋找匹配范圍的大小)，前進(jìn)因子λ((0≤λ≤1))(用于根據(jù)被匹配的下標(biāo)計(jì)算出具體尋找匹配的范圍)。

上述算法時(shí)間復(fù)雜度大大減低，僅為O(μ(m+n))其中μ為步長因子，即每次尋找匹配范圍的大小。如果將其應(yīng)用到求解兩個(gè)XML文檔的相似度，則時(shí)間復(fù)雜度為O(|T1|+|T2|+μ(L1+L2))，L1，L2分別為XML文檔轉(zhuǎn)換為DOM樹的葉子個(gè)數(shù)，大大低于樹模型的時(shí)間復(fù)雜度O(|T1||T2|min(|D1|，|L1|)min(|D2|，|L2|)。

2 實(shí)驗(yàn)與結(jié)論

數(shù)對(duì)模型的CA算法有多個(gè)參數(shù):編碼因子α，衰減因子β，步長μ，前進(jìn)因子λ，還有valueweight(注seatweight=1-valueweight)，下面我們用實(shí)驗(yàn)研究一下，這幾個(gè)參數(shù)對(duì)準(zhǔn)確率和召回率的影響。不妨這些參數(shù)的默認(rèn)值為:α=2，β=0.8，μ=20，λ=0.8，valueweight=0.5。

從圖2.1可以看出，衰減因子過小或過大，結(jié)果均不理想，在0.8到0.9之間比較合理。

從表2.1可以看出，步長取值太小，會(huì)影響召回率，太大又會(huì)增加時(shí)間消耗。

從圖2.2可以看出，前進(jìn)率取0.7到0.8是比較合理的選擇。

可以看出，準(zhǔn)確度隨valueweight增大而減小，而召回率確恰恰相反，為取得一個(gè)綜合性較好的結(jié)果，valueweight取0.5至0.8是個(gè)比較合理的選擇。

表2.1 步長μ對(duì)結(jié)果的影響

圖2.1 衰減因子取值對(duì)結(jié)果的影響

圖2.2 前進(jìn)率對(duì)結(jié)果的影響

圖2.3 取值對(duì)結(jié)果的影響

3 結(jié)束語

本文提出了一個(gè)優(yōu)化的新模型——數(shù)對(duì)序列模型，同時(shí)給出一個(gè)更有效的新算法——CA算法。數(shù)對(duì)序列模型與CA算法解決了傳統(tǒng)算法時(shí)間復(fù)雜較高、重復(fù)結(jié)點(diǎn)未被考慮、兄弟結(jié)點(diǎn)信息丟失的問題。再者，數(shù)對(duì)序列模型通過數(shù)字化編碼，降低了時(shí)空開銷，提高了存儲(chǔ)計(jì)算效率。實(shí)驗(yàn)結(jié)果表明，新模型與新算法在準(zhǔn)確率與召回率上也均有所提高。當(dāng)然，在數(shù)對(duì)序列模型下有沒有計(jì)算XML相似度更快更有效的算法，是值得我們以后再做進(jìn)一步的研究與探索的問題。

［1］孫建軍，成穎等.信息檢索技術(shù)［M］.北京:科學(xué)出版社，2004.

［2］Monika Henzinger.“Finding Near-Duplicate Web Pagess:A Large-Scale Evaluation of Algorithms”.In the Proceeding of ACM SIGIR Conference，pages 284-291，2006.

［3］Zheng Chen，Wei-Ying Ma，Jinwen Ma.Learning to Cluster Web Search Results［A］.In proceeding of the 27th Annual International ACM SIGIR Conference［C］.Sheffield，South Yorkshire，UK，July 2004，210-217.

［4］Sachindra Joshi，Neeraj Agrawal，Raghu Krishnapuram and Sumit Negi.A Bag of Paths Model for Measuring Structural Similarity in Web Documents.SIGKDD＇03，August 24-27，2003.

［5］Prasanna Ganesan，Hector Garcia-Molina and Jennifer Widom Exploiting Hierarchical Domain Structure to Compute Similarity.ACM Transaction on Information Systems.Jan，2003.

［6］Braha D，Elovici Y，Last M.A theory of actionable data mining with application to semiconductor manufacturing control［J］.International Journal of Production Research，2007，45(13):3059-3084.

Abstract:In order to get the computation among the XML document faster and efficient，this paper mentioned a new mathematical model of sequence number the model based on improved traditional model of dynamic programming algorithm，and proposes a new algorithm is more effective-CA algorithm.Experiment proves，compared with traditional methods，this algorithm in the accuracy，recalling rate or space complexity significantly improved.

Key words:XML，model，similarity，algorithm

XML Sequence Model and Similarity Structure Algorithm

SHU Hui-qun

TP311.132

A

1009-5152(2010)03-0079-06

2010-06-09

蘇慧群(1979-)，女，湖南師范大學(xué)樹達(dá)學(xué)院助教。