一種計算xml文檔相似度的方法

2023-06-01 17:32:36

專利名稱：一種計算xml文檔相似度的方法
一種計算XML文檔相似度的方法
技術領域：
本發明屬於資料庫技術領域，具體涉及一種計算XML文檔相似度的方法。背景技術：
可擴展標記語言XML已成為Web上表示和交換數據的標準格式。隨著XML相關標 準的推廣和應用，各行各業都以XML作為元語言，制定各自領域特定的子語言，用於存儲和 共享本領域所涉及的數據。在這種背景下，各個領域都會不斷湧現出大量的XML文檔。如 何從大量文檔中挖掘知識成為了當前急需解決的問題。XML數據挖掘是知識發現技術裡一 個重要的應用，而相似度計算在XML數據挖掘中起基礎性的作用。XML文檔挖掘分為內容挖掘和結構挖掘，它可以用於XML數據的提取、整合以及其 他一些應用。XML文檔是半結構化數據，因而結構挖掘尤為重要。分類、聚類是數據挖掘普 遍採用的方法，而XML文檔相似度是分類、聚類的基礎，是影響挖掘結果的一個重要因素。目前XML文檔相似度計算主要有兩類方法，基於樹編輯距離的方法和基於頻繁路 徑的方法。其中基於樹編輯距離的方法得到了普遍應用，它首先把一篇XML文檔表示為一 棵有序標籤樹，例如DOM樹。進而通過樹編輯距離來衡量XML文檔樹的相似度。基於樹編 輯距離有三種經典算法SelkoW、Chawathe和Dalamagas，但樹編輯距離算法時間複雜度普 遍較高。基於頻繁路徑的方法可以快速計算文檔相似度，但丟失所有的非頻繁路徑，從而丟 失大量的結構信息，正確率相對較低。

發明內容本發明的目的是彌補現有技術存在的上述不足，提出一種新的計算XML文檔相似 度的方法。該方法使用BPC模型提取出XML文檔的結構信息，引入各種權重體現結構層次， 基於N-Gram劃分方式，通過一次掃描降低了 XML文檔相似性計算的時間複雜度。本發明提供的計算XML文檔相似度的方法包括如下步驟步驟1、將XML文檔定義為一棵XML文檔樹；步驟2、建立雙向路徑約束(Bidirectional path constraints, BPC)模型在步 驟1文檔樹的基礎上定義節點的BPC，一篇XML文檔包含的所有節點的BPC集合稱為雙向路 徑約束模型；步驟3、使用基於N-Gram的劃分方式計算兩個祖先路徑約束(或孩子路徑約束) 之間的相似度，統稱為路徑約束相似度；步驟4、根據步驟3得出的路徑約束相似度計算兩個節點的BPC相似度，進而把這 個BPC相似度作為這兩個節點的相似度；步驟5、最後文檔中所有節點相似度按照節點的結構層次加權求和作為兩篇文檔 的相似度。本發明的具體計算過程如下1.XML 文檔樹
將XML文檔定義為一棵XML文檔樹，具體如下定義1. XML文檔樹將一棵XML文檔樹表示為一個6元組T = (V,v0,E, E，P，lab)， 其中1)、V是文檔樹中所有節點的集合；2)、V(1是文檔樹的根節點；3)、Ea定義了父子約束集合，Ea = {(u，v) | u G V八v G V，並且u是v的父親節 點}，ES定義了兄弟約束集合，ES= {(u,v) |uG VAvG V，並且的右兄弟節點}；用 E表示約束集合，即E = Ea U Es ；4)、E是文檔樹中節點標籤的集合；5)、PA 定義了祖先路徑約束，PA = {(v0, Vl, ... , vn) | (Vi，vi+1) G Ea，0 彡 i < n} U {v0}，Ps 定義了孩子路徑約束，Ps = {(Vl, . . . , vn) | (Vi，vi+1) G Es，0 < i < n，Vl， vn分別是它們父親節點的第一個和最後一個孩子節點} U {Vl|Vl是其父親節點的唯一孩子 節點}；用P表示路徑約束集合，即P = PA U PS,PC VU V2U... U ^；6)、函數lab返回節點的標籤，即當v G V，lab (v) GE。需要說明的是，我們關注的是結構相似度，傳統的信息檢索技術已經很好的處理 了內容相似度，所以文本節點統一當做標籤值為#text的節點。另外將屬性節點看成一種 特殊的元素節點。文檔樹示例如圖1。2.節點的 BPC定義2.節點的BPC。PA(e)定義了節點e的祖先路徑約束，PA(e) = (v0, Vl， ， e) G PA，Ps(e)定義了節點 e 的孩子路徑約束，Ps(e) = (Ul，. . .，un) G Ps, (e, Ui) G Ea， cons(e)定義了節點的BPC，cons (e) = (PA(e), Ps (e)), e G V。對於文檔樹的葉節點，它的 Ps(e)為空，用e表示。通常基於樹編輯距離的方法只提取祖先路徑約束。本發明使用的BPC在原有的祖 先路徑約束的基礎上增加了孩子路徑約束。這樣更全面的獲取了 XML文檔的結構信息，可 以提高依據文檔相似度聚類結果的正確率。3.基於N-Gram思想計算兩個路徑約束之間的相似度設k為待比較的兩個路徑約束中出現的不同節點標籤的數量，將這k個節點標籤 按照字典序排列，則每個節點標籤可以依次映射為[1，k]內的一個正整數。這樣用字符串 表示的節點標籤被轉換為一個數字，相同的標籤名有相同的數字編號。那麼路徑約束最後 的表現形式是一個有順序的整數數組。定義3.基於N-Gram思想的劃分方式。它將長為n的整數數組劃分為n個子數組， 其中第i(0 < i彡n)個子數組存儲的是提取的i-Gram項，該子數組簡稱為i-Gram數組， 含有n-i+1項，其中每一項均為原整數數組中i個連續項(ai，a2，……，％)生成的結果，生 成方法如下 引入k+1是為了保證各個子數組的項的唯一性，可見，1-Gram數組有n項，2-Gram 數組有n-1項，……，(n-1)-Gram數組有2項，n-Gram數組有1項；因而所有子數組共有
項；為了簡化後面的處理，將n個子數組依次存儲在一個長為
的數組中；
待比較的兩個路徑約束，通過使用符號映射轉化為整數數組，長度分別為n和m， 它們是某兩個節點的祖先路徑約束(或同是孩子路徑約束)，根據定義3將他們依次分解成 1-Gram 數組，2-Gram 數組，......，min (n，m) -Gram 數組。定義4.兩個一維數組的相同項個數C。把數組看成集合，用兩個集合的交集表示 相同項個數C。用q表示兩個路徑約束分解後兩個i-Gram數組的相同項個數。如果在i-Gram數 組中有完全匹配項時，該項的所有子項都會匹配，這部分匹配的子項個數無形中體現了 的權重，c=UG;因此用C表示兩個路徑約束分解後的相同項個數。 1=1定義5.路徑約束相似度。根據上面的定義，路徑約束相似度公式如下所示 4. BPC 相似度為了保持原有的結構信息，本發明對XML文檔的每個節點提取了 BPC，但是祖先路 徑相似度和孩子路徑相似度對BPC的影響程度可能不一樣。引入影響因子來描述祖先約束 對BPC的影響程度。這個影響因子由程式設計師設定。一般認為祖先路徑約束對BPC有更大的影響。定義6.BPC相似度。設a為祖先路徑約束的影響因子，自然為孩子路徑約 束的影響因子，0彡a彡1，BPC相似度公式如下所示 5.文檔相似度定義7.文檔相似度。兩篇XML文檔Di和D2，節點個數分別為n和m，根據定義6 計算出Di每個節點的BPC和D2每個節點的BPC相似度形成相似矩陣後，選出Di各個節點 和D2相似度最大的節點的相似值，則文檔相似度公式如下 在XML文檔標籤樹中，節點越靠近根節點，它對文檔結構的影響就越大。引入
來描述不同節點深度的不同影響，lev(vi)為節點義的層數，根節點的層數是
0o本發明的優點和積極效果本發明提出一種新的比較XML文檔相似度的方法。該方法使用BPC模型，更全面 的提取XML文檔的結構信息，為精確計算XML文檔相似度打下了基礎。引入各種權重體現 結構層次。創新的用N-Gram思想簡化路徑相似度的度量，精確效率高。作為分類、聚類的 基礎，可以提高分類、聚類的正確率。

圖1為一篇XML文檔和它對應的XML文檔樹。圖2為使用N-Gram思想提取路徑約束6 — 3 — 4 — 5 — 3中的N-Gram信息，此圖包括由a到e的五個過程，因為出現的最大整數為6，提取過程中使用的是七進位。其中，(a)為掃描路徑的第一個元素後填充第一個1-Gram的示意圖。(b)為掃描路徑的第二個元素後填充第二個1-Gram，第一個2-Gram的示意圖。(c)為掃描路徑的第三個元素後填充第三個1-Gram，第二個2-Gram，第一個 3-Gram的示意圖。(d)為掃描路徑的第四個元素後填充第四個1-Gram，第三個2-Gram，第二個 3-Gram,第一個4-Gram的示意圖。(e)為掃描路徑的第三個元素後填充第五個1-Gram，第四個2-Gram，第三個 3-Gram,第二個4-Gram，第一個5-Gram的示意圖。圖3為文檔相似度算法流程圖。
具體實施方式N-Gram(N是元數)是大詞彙連續語音識別中常用的一種語言模型。該模型基於 這樣一種假設，第N個詞的出現只與前面N-1個詞相關，而與其它任何詞都不相關，整句的 概率就是各個詞出現概率的乘積。這些概率可以通過直接從語料中統計N個詞同時出現的 次數得到。常用的是二元的Bi-Gram和三元的Tri-Gram，已經廣泛應用於自然語言處理。 N-Gram的意思可以理解為N個詞構成的序列。實施例1 基於XML文檔樹構建BPC模型的具體方法，描述如下1.根據本發明提出的將XML文檔定義為一棵XML文檔樹，並在此文檔樹基礎上對 每個節點建立BPC模型。圖1顯示了一篇XML文檔和它對應的XML文檔樹，表1以圖1文 檔樹為例列舉各個節點的BPC模型。實施例2 基於N-Gram思想計算文檔相似度的具體方法，描述如下算法1.根據兩個相鄰i-Gram項生成i+1-Gram項的方法CreateGram輸入itemi，item2 /*用正整數表示的兩個相鄰i_Gram項*/t /* 進位 t*/輸出item /*用正整數表示的(i+1)-Gram項*/① item: = item! X t+item2% t ；②.RETURN item ；③.算法結束該算法是根據兩個相鄰i-Gram項生成(i+l)-Gram項。算法中的進位t為待比較 的兩個路徑約束中不同標籤數目總數加1。對於同一個路徑約束，引入進位t，當i卓j時， 可以保證i-Gram項所在的整數域和j-Gram所在的整數域沒有交集。算法2.路徑約束中N-Gram信息的提取方法PathDecomposition輸入Path[l，2， ，!!] /*映射為正整數數組後的路徑約束*/t/*進位t，意義同算法1*/ /*需要提取的最大的N-Gram項，即提取的k-Gram 子數組中，k ( n0*/輸出
提取的 N-Gram信息 */①.pos[l，2，…，n]；
/*pos [i]記錄路徑約束Path的每個i-Gram數組在NGram數組(i = 1,2,……，Path. Length)中的起始位置 */
「…「1r.i 2ni - 2n + 3i _ i2② ③.FOREACH member IN Path④.i : = member 在 Path 中的下標；⑤.NGram[i] = member /* 填充第 i 個 1-Gram 項 * /⑥.j = 2 ；/*j表示待填充的j-Gram項*/⑦.IF j 彡 i&&j 彡 n0THEN⑧.item!: = NGram[pos[j-l]+i-j+l]；(9).item2: = NGram[pos[j-l]+i_j+2]；⑩.NGram[pos[j]+i-j+l] : = CreateGram(item1, item2, t)；/* 根據(j-1) -Gram 項填充第 i_j+l 個 j-Gram 項 */ .j++ ； .GOTO ⑦ .END IF .END FOREACH .RETURN NGram ； .算法結束該算法的主要目的是通過掃描一次數組Path，提取出該數組包含的所有的 i-Gram項，並填充到NGram數組的相應位置裡。每個i-Gram的長度確定，用pos數組存儲 每個i-Gram在NGram的起始位置。根據i，填充方式如下i = 1 填充第 1 個 1-Grami = 2 填充第 2 個 1-Gram，第 1 個 2-Grami = 3 填充第 3 個 1-Gram，第 2 個 2-Gram，第 1 個 3-Gram............i = n 填充第 n 個 1-Gram，第 n_l 個 2-Gram，......,第 1 個 n-Gram由此發現，當已知Path的當前掃描位置i和待填充項屬於j-Gram，結合數組 pos可以計算出待填充項在NGram中的存儲位置。算法的第⑧至⑩步調用了算法1，利用 (j-1)-Gram的第i_j+l和i_j+2項，生成j-Gram的第i_j+l項。路徑數組Path掃描結 束，它對應的N-Gram信息數組NGram填充完整。如圖2為使用N-Gram思想提取路徑約束 6 — 3 — 4 — 5 — 3 填充的 N-Gram 信息。算法3.路徑約束之間相似度計算PathSimilarity輸入StringPathJl，〗，…，n]，StringPath2[1，2，…，m]/* 字符串形式的路徑 約束*/輸出pathSim /*路徑相似度*/ . Dictionary [1,2,…，k]；/*數組Dictionary為輸入的兩個路徑約束中包含的所有標籤按照字典序排好的詞典，相同的字符串只佔詞典中的一項；IiSstringPathdnstringPath2中不同節點標籤的數量*/②.Path1: = Mapping (StringPath1, Dictionary)； /*函數Mapping返回將字符串數組StringPath1中的字符串都轉化為 在Dictionary中該字符串的下標而形成的一個整形數組*/③.Path2: = Mapping(StringPath2, Dictionary)；(4). minLength: = min (StringPath1. Length, StringPath2. Length)；(5). DecPath1 = PathDecomposition (Path1, k+1, minLength)；/*根據算法2，提取路徑約束中的N-Gram信息*/(6). DecPath2 = PathDecomposition (Path2, k+1, minLength)；(7). pathSim: = !DecPath1 Π DecPath2I ；⑧.RETURNpathSim ；⑨.算法結束算法的目的是計算兩個路徑約束的相似度。k為待比較的兩個路徑約束中出現 的不同節點標籤的數量，將這k個節點標籤按照字典序排列，則每個節點標籤可以依次映 射為[1，k]內的一個正整數。這樣用字符串表示的節點標籤被轉換為一個數字，相同的標 籤名有相同的數字編號。那麼路徑約束最後的表現形式是一個有順序的整數數組。採用t =k+Ι作為進位，從而達到算法1引入該參數的目的。表2示例說明待比較的兩個約束 BOOK — SECTION — TITLE, BOOK — SECTION — FIGURE — CAPTION 各個字符串的映射信息。算法4. BPC 相似度 BPCSimilarity輸入節點θι的BPC,節點e2的BPC輸出BPCsim /*BPC相似度，也即節點相似度*/①.α = 0.6 ;/*參數α是祖先路徑約束在BPC約束中所佔的比重，α越大，祖先路徑約束對BPC相似度的影響越大，孩子路徑約束對BPC相似度的影響越小；反之，α越小，孩子路徑約束對BPC相似度的影響越大，祖先路徑約束對BPC相似度的影響越小*/②.BPCsim: = α XPathSimilarity (P^e1), PA(e2)) +(1-α ) XPathSimilarity ( Ps(ei),Ps(e2))③.RETURNBPCsim ；④.算法結束算法的目的是計算兩個節點的BPC相似度。引入影響因子來描述祖先路徑約束對 BPC相似度的影響程度。這個影響因子需要根據具體的應用而設定，一般情況下認為祖先路 徑約束比孩子路徑約束對BPC相似度具有更大的影響，S卩α >0.5。算法5. XML文檔相似度輸入XML文檔樹D1和D2輸出documentSim /*文檔D1和D2的相似度*/①.遍歷文檔樹D1和D2,建立對應的BPC模型；
②.s[nXm]；/*BPC相似矩陣，設文檔D1節點數為n，文檔D2節點數為m*/③·siJ: = BPCSimi Iarity ((PA (ei), Ps (ei)), (PJej)，Ps (ej)))；/*根據算法4，Sij存儲的是節點ei與節點e」之間的相似度，其 中節點ei屬於文檔D1，節點ej屬於文檔D2*//*函數w(e)獲得節點e的權重，且w(e) = 2_lev(e)*/算法的目的是計算兩篇XML文檔的相似度。由於BPC相似矩陣滿足關於矩陣主對 角線對稱，具體操作時可只計算矩陣的上三角形，再複製到下三角形，計算次數減少一半。 如圖3為文檔相似度算法流程圖。表1列舉了圖IXML文檔樹各個節點的BPC 表2示例說明待比較的兩個約束Β00Κ — SECTION — TITLE,BOOK — SECTION — FIGURE — CAPTION各個字符串的映射信息
權利要求
一種計算XML文檔相似度的方法，其特徵在於該方法包括如下步驟步驟1、將XML文檔定義為一棵XML文檔樹，並表示為一個6元組；步驟2、建立雙向路徑約束Bidirectional path constraints，BPC模型在步驟1文檔樹的基礎上定義節點的BPC，一篇XML文檔包含的所有節點的BPC集合稱為雙向路徑約束模型；步驟3、使用基於N-Gram的劃分方式計算兩個祖先路徑約束或孩子路徑約束之間的相似度，統稱為路徑約束相似度；步驟4、根據步驟3得出的路徑約束相似度計算兩個節點的BPC相似度，進而把這個BPC相似度作為這兩個節點的相似度；步驟5、最後文檔中所有節點相似度按照節點的結構層次加權求和作為兩篇文檔的相似度。
2.根據權利要求1所述的方法，其特徵在於步驟1所述的XML文檔樹的定義如下定義1. XML文檔樹將一棵XML文檔樹表示為一個6元組T = (V，v0, E，E，P，lab)，其中1)、V是文檔樹中所有節點的集合；2),v0是文檔樹的根節點；3)、Ea定義了父子約束集合，Ea= {(u，v) | u e V A v e V，並且u是v的父親節點}， Es定義了兄弟約束集合，Es = {(u，v) | u e V八v e V，並且v是u的右兄弟節點}；用E表 示約束集合，即E = Ea U Es ；4)、E是文檔樹中節點標籤的集合；5)、PA定義了祖先路徑約束，PA= {(v0,vi,... ,vn) | (vi,vi+1) GEa，0彡 i<n} U {v0}, Ps 定義了孩子路徑約束，Ps = {(Vi，. . . , vn) | (Vi，vi+1) G Es，0 < i < n，Vl，vn 分別是它們 父親節點的第一個和最後一個孩子節點} U {Vl|Vl是其父親節點的唯一孩子節點}；用P 表示路徑約束集合，即P = PA U Ps，FU F2U ... U ^；6)、函數lab返回節點的標籤，即當vG V, lab (v) GE。
3.根據權利要求1所述的方法，其特徵在於步驟2所述的節點的BPC定義為定義2.節點的BPC :PA(e)定義了節點e的祖先路徑約束，PA(e) = (v0, Vl,. . . , e) G PA, Ps(e)定義了節點 e 的孩子路徑約束，Ps(e) = (Ul, ，un) G Ps，(e, Ui) G Ea，cons (e)定 義了節點的BPC，c0nS(e) = (PA(e),Ps(e)),e G V ；對於文檔樹的葉節點，它的Ps (e)為空， 用e表示。
4.根據權利要求1所述的方法，其特徵在於步驟3所述的使用基於N-Gram的劃分方式 計算兩個路徑約束之間的相似度的方法是設k為待比較的兩個路徑約束中出現的不同節點標籤的數量，將這k個節點標籤按照 字典序排列，則每個節點標籤可以依次映射為[1，k]內的一個正整數；這樣用字符串表示 的節點標籤被轉換為一個數字，相同的標籤名有相同的數字編號；那麼路徑約束最後的表 現形式是一個有順序的整數數組；定義3.基於N-Gram思想的劃分方式它將長為n的整數數組劃分為n個子數組，其中 第i(0 < i≤n)個子數組存儲的是提取的i-Gram項，該子數組簡稱為i-Gram數組，含有 n-i+1項，其中每一項均為原整數數組中i個連續項(ai，a2，……，％)生成的結果，生成方法如下 弓丨入k+1是為了保證各個子數組的項的唯一性，可見，1-Gram數組有η項，2-Gram數組 有n-1項，……，(n-D-Gram數組有2項，n-Gram數組有1項；因而所有子數組共有^^項；為了簡化後面的處理，將η個子數組依次存儲在一個長為Mf的數組中；待比較的兩個路徑約束，通過使用符號映射轉化為整數數組，長度分別為η和m，它們 是某兩個節點的祖先路徑約束或同是孩子路徑約束，根據定義3將他們依次分解成I-Gram 數組，2-Gram數組，……，min (n，m) -Gram數組；定義4.兩個一維數組的相同項個數C 把數組看成集合，用兩個集合的交集表示相同 項個數C ；定義5.路徑約束相似度根據上面的定義，路徑約束相似度公式如下所示 ；定義6. BPC相似度設α為祖先路徑約束的影響因子，自然l-α為孩子路徑約束的影 響因子，O彡α彡1，BPC相似度公式如下所示
5.根據權利要求1所述的方法，其特徵在於步驟5所述的文檔中所有節點相似度加權 求和作為兩篇文檔的相似度的方法是定義7.文檔相似度兩篇XML文檔D1和D2,節點個數分別為η和m，根據定義6計算出 D1每個節點的BPC和D2每個節點的BPC相似度形成相似矩陣後，選出D1各個節點和D2相 似度最大的節點的相似值，則文檔相似度公式如下 在XML文檔樹中，節點越靠近根節點，它對文檔結構的影響就越大；引入對…力『」來 描述不同節點深度的不同影響，Iev(Yi)為節點Vi的層數，根節點的層數是O。
全文摘要
本發明屬於資料庫技術領域，建立一種XML文檔約束模型，稱為雙向路徑約束模型。基於這種模型提出一種新的計算XML文檔相似度的方法。它通過節點的雙向路徑約束更全面的提取XML文檔的結構信息，有利於更精確的衡量XML文檔之間的相似度。本發明引入自然語言領域中非常成熟的N-Gram思想，將基於N-Gram的劃分方式應用在路徑約束相似度計算中。最後本發明巧妙地運用正整數和權值簡化了N-Gram信息的提取和運算。本發明可用於XML文檔分類、聚類以及模式提取等領域。
文檔編號G06F17/30GK101876995SQ20091024490
公開日2010年11月3日 申請日期2009年12月18日 優先權日2009年12月18日
發明者廉鑫, 林偉堅, 汪陳應, 袁曉潔 申請人:南開大學