蘇慧群

(湖南師范大學樹達學院，湖南長沙410012)

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

蘇慧群*

(湖南師范大學樹達學院，湖南長沙410012)

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

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

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

1 數(shù)對序列模型

1.1 基本定義

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

有了最基本的Common操作后，下面定義三個基本操作，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ù)對α Delete，Insert，Update值，具體計算方法為:

1.2 CA算法

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

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

目的:計算兩個數(shù)對序列的相似度

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

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

2 實驗與結(jié)論

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

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

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

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

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

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

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

圖2.2 前進率對結(jié)果的影響

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

3 結(jié)束語

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

［1］孫建軍，成穎等.信息檢索技術(shù)［M］.北京:科學出版社，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-)，女，湖南師范大學樹達學院助教。