基於語義距離模型的xml文檔關鍵字搜索聚類方法

2023-07-04 07:06:41

專利名稱：：基於語義距離模型的xml文檔關鍵字搜索聚類方法
技術領域：
：本發明屬於Web數據管理
技術領域：
，具體涉及一種基於聚類思想，對可擴充標記語言(XML)資料庫或文檔進行關鍵字搜索的方法。技術背景由於界面友好、使用簡單，關鍵字搜索在信息檢索領域取得了巨大成功，例如谷歌搜尋引擎、百度搜尋引擎等。它們的搜索對象通常是一個HTML文檔或普通文本文檔的集合，搜索的目的是査出哪些關鍵字在哪些文檔中出現，並且返回全部或部分包含關鍵字的文檔。由於XML格式數據的大量出現和廣泛應用，在XML文檔上進行關鍵字搜索的需求變得越來越迫切。近年來，XML關鍵字搜索受到工業界和學術界的廣泛關注[1][2]['，][5][6][7]。XML的關鍵字搜索不同於結構化的XML査詢(如XPath、XQuery等)，不僅易於使用，用戶不需要學習和掌握複雜的查詢語言，用戶也不需要了解XML的模式，適用於Internet上大量存在的自由XML文檔。但是，關鍵字搜索帶來的一個關鍵問題是用戶難以或無法準確表達搜索語義。因此，在XML關鍵字搜索中，如何確定關鍵字搜索的語義(即用戶的搜索意圖)以及返回什麼樣的結果給用戶則成為關鍵的技術難點。在已有的關於XML關鍵字搜索的工作中，通常都是基於最低公共祖先(LCA)模型，中一個典型的方法是最小最低公共祖先方法SLCA(MeaningfulLowestCommonAncestor)[2]。Li等人[3]將關鍵字搜索的語義定義為有意義的最低公共祖先，其本質含義與SLCA相同。SLCA方法返回的是一組最小應答子樹(smallestanswersubtree),—棵最小應答子樹被定義為包含有所有關鍵字的子樹，並且任意一棵其子樹都不包含所有關鍵字，這種子樹的根被稱作一個SLCA。SLCA方法實際上是將對一組關鍵字的搜索轉換為對這一組關鍵字的最小最低公共祖先的査找。該方法雖然能夠獲得一些關鍵結果，但同時又會丟失很多有意義的信息。例如，圖1所示是一個XML文檔樹，其中每個結點以自己的標籤作為標識，下面的數字串是該結點的Dewey編碼。假如用戶搜索的關鍵字是{J服，必'c力aeJ，few4，標籤中包含關鍵字的結點用下劃線標出。在圖1中，SLCA方法的返回結果只是一棵以結點JrWWe(O.2.2.0)為根的子樹。然而，用戶的搜索語義極有可能是"Michael和David曾經合作寫過哪些關於XML的文章"，很明顯，SLCA方法找到了文章"XML3",但將文章"XML2"漏掉了；用戶還可能有其它合理的查詢意圖，比如"Michael和David—起合作寫過哪些文章"，"Michael和David其中任一個人寫過哪些關於XML的文章"，對於這兩個詢問，文章"HTML1"和文章"XML1"也是滿足的，都應該被返回。這些搜索意圖都是很合理的，也是現實生活中非常常見的，而SLCA方法將幾個滿足這些搜索意圖的結果都丟失了。實際上,SLCA方法所做的即是根據某種規則從各種包含不同關鍵字的結點的組合中挑選出部分"最優"的包含全部關鍵字的組合，而SLCA方法認為的"最優"就是LCA相對最低，而LCA相對較高的結果則都被丟棄了，這是SLCA方法會丟失有意義的結果的根本原因。除了丟失一些有意義的結果外，SLCA方法還存在一些其它問題(l)在其計算過程中，並不是所有的結點組合都是可比較的,所有LCA之間不存在祖先後代的兩個組合，例如圖1中的組合{0.2.2.0.1.0，0.2.2.0.1.1}與組合{0.0.1.0，0.0.1.1},都不可比較，所以選出的"最優"只能是相對最優；(2)由於SLCA方法選出來的一組結果的LCA之間都不存在祖先後代關係，所以它們是不可比較的，因此也無法將它們排序，這顯然不適合結果集比較大的情況；(3)SLCA方法要求每個結果都要包含所有關鍵字，這實際是要求在作為査詢語句的所有關鍵字之間存在"與"邏輯關係，而我們現實生活中所使用的關鍵字搜尋引擎(例如谷歌)都包含了"或"關係，也就是說關鍵字可以全部或部分的存在於結果中，這使得搜索的結果能更多地滿足用戶的可能意圖，顯然更加合理，也應該被應用到XML關鍵字搜索中來。針對上述問題，本發明提出一種新的XML關鍵字搜索的處理方法。其中，提出一種新的XML關鍵字搜索的語義距離模型，綜合考慮關鍵字結點之間的距離和它們的LCA的高度；首次使用聚類算法進行XML關鍵字搜索；並提出一種排序模型對所有的搜索結果排序。
發明內容本發明的目的在於提出一種新的XML文檔關鍵字搜索方法，以便能夠搜索到更多的對用戶有意義的XML片斷。本發明提出的XML文檔關鍵字搜索方法，是基於XML文檔距離模型的XML聚類關鍵字搜索，包括用關鍵字的語義距離模型來建模用戶的搜索意圖、用聚類算法進行關鍵字搜索、支持關鍵字之間的"或"運算、並對結果進行排序，記為XKLuster。方法的具體步驟如下(1)定義用戶提交的關鍵字，並將XML文檔的關鍵字搜索語義定義為關鍵字之間的語義距離模型，並以此來表示用戶的搜索意圖；(2)將關鍵字搜索的返回結果定義為關鍵字簇的最小組成樹；(3)XML文檔樹進行預處理；(4)根據本發明提出的語義距離模型，選擇使用如下三種聚類算法之一種進行XML關鍵字搜索基於圖的聚類算法(GKSC)、核心集驅動的聚類算法(CKSC)和鬆弛的核心集驅動聚類算法(LCC)。(5)根據本發明提出的排序模型，對搜索結果進行排序。1.定義關鍵字之間的語義距離模型本發明將用戶提交的關鍵字定義為一個包含t個關鍵字的集合Z:仏Ii=l,，t}，XML文檔定義為一棵XML文檔樹，具體如下定義l.XML文檔樹。將一顆XML文檔樹(XMLDoc咖entTree)表示為一個8元組d=(F,￡,義，/a6e/(''fi0，p/(械，W2)，cfep,/j("),^cotfe(!W),/ca(7')),其中(1)K是樹上所有結點的集合，並且每個結點都有唯一的標識符和Dewey編碼；(2)￡￡Kxr，是樹上邊的集合；(3)/We/(W)為標籤函數，用來獲得標識為J'c/的結點的標籤，其中WeK;(4)Xe^是樹上所有關鍵字結點的集合，所謂關鍵字結點即標籤中包含關鍵字的結點；(5)p/(W,，/《)函數，用來取得id和^/2兩個結點之間的路徑長度，其中W和W必須具有祖先後代關係，而此函數返回的結果為它們之間的路徑上所包含的邊的個數；(6)血/^(W)函數，用來獲得標識為JW的結點的深度(樹的根的深度為1)，其中WeF;(7)/vmKfe(W)函數，用來獲得標識為W的結點的Dewey編碼，其中wer;(8)/ca(r)函數，其中^￡「是K的任意子集，函數返回r中所有結點的最低公共祖先。定義2.兩個關鍵字結點之間的最短路徑。兩個關鍵字結點&和x,的最短路徑為結點a到7caUx,，義」))的路徑加上結點^到"s(U,.,W)的路徑。同時，用函數sa/(x，》來表示結點A和^的最短路徑的長度，顯然印J0^,》=/^(乃a(Uhx,})，x.)+/^(7ca(U,.,^0))，々)。在一篇普通的文本文檔中，兩個單詞之間到底有多"近"，可以直接通過它們中間相隔的單詞數量來表示。但是在一篇XML文檔中，情況更為複雜。實際上,在現有的XML關鍵字搜索方法中，都顯示或隱式地定義了任意兩個關鍵字結點在結構上的距離。比如Hristidis等人在[l]中將兩個結點之間的距離直接定義成它們的最短路徑的長度，但沒有考慮到樹型結構層次化的特性。而在所有基於LCA的方法的主要缺陷有三一是雖然考慮到了層次的高低，但是沒有考慮結點之間的路徑長短；二是當兩個LCA之間具有祖先後代關係時，只取SLCA會導致部分有意義的結果的丟失；三是當兩個LCA之間不具有祖先後代關係時，兩個距離是不可比較的，因而無法對大量返回結果進行排序。本發明綜合考慮兩方面因素來定義兩個關鍵字之間的語義距離，即兩個關鍵字結點之間的路徑長度和它們的LCA的層次。若兩個關鍵字結點之間的最短路徑越短，則它們的語義距離越近；若兩個結點的LCA的層次越低，則它們的語義距離越近；兩個關鍵字之間的語義距離越短，則意味著它們的關係更緊密，更可能構成用戶要搜索的結果。這樣的語義距離模型避免了當兩個LCA之間不具有祖先後代關係時會丟失可能的結果；同時在存在大量返回結果時，又能夠對返回結果進行排序。定義3.兩個關鍵字結點之間的語義距離。XML文檔樹上任意兩個關鍵字結點之間的語義距離力's(A,》被定義如下後面內容將語義距離簡稱為距離。在公式(i)中，分子和分母部分分別是兩關鍵字結點間最短路徑的長度和它們LCA的高度。設樹的高度(最大深度)是力，那麼s;^(AA)的取值範圍是[O,2力]，而W))的取值範圍是[l，力]，所以力's(A，A)的值域是[O，2力]。對圖1中的所有關鍵字之間的語義距離進行計算，可以得到一個語義距離矩陣，如表1所示。由表l中可以看出，最近的幾個距離(0.40和0.67)表示的關係都是同一篇文章的兩個作者，而最遠的距離(8.00)則是相互之間沒有引用關係的兩篇文章的標題或作者，距離的遠近與實際意義相符。2.定義關鍵字搜索的返回結果定義4.關鍵字結點的簇。根據關鍵字語義距離模型，可以使用特定的方法將關鍵字結點集分成一組簇。簇的集合表示為C={GIi=1，…，歷}，其中，一個簇G是一組關鍵字結點的集合，GG義，且Gc,x。，=1設定一個距離閾值"來約束簇的大小，簇中任意兩個關鍵字結點之間的距離小於等於定義5.最優簇。給定一個距離閾值"，任一個關鍵字集合C,eX被稱為最優簇，若且唯若(1)V義,.，q滿足(//S(X、々)《0;(2)V、，x。eX且a:。gq,3x6eC,.滿足As(jc。，x6)>w。假設取距離閾值為2.0，則可知表1中的距離矩陣中只有部分距離被保留(如表1中陰影部分所示)，此時的四個最優簇分別是^，&}，"，W,ks，&力，W和U,為，將四篇文章都找出了。由於一個簇只是若干關鍵字結點的集合，若要向用戶返回有價值的信息，一種簡單的方法是對於每個簇G，返回整棵以乃a(G)為根的子樹。但存在兩個缺點其一是多個乃3(G)為根的子樹之間可能存在的包含情況，尤其當某個"s(G)的層次比較高的時候，會產生大量冗餘信息；其二是返回結果過大。因此，本發明將返回結果定義為簇的"最小組成樹"，定義如下定義6.簇的最小組成樹。C中每個簇G的最小組成樹定義為以Jca(G)為根，以A"e/^朋ts(G)中的所有結點為葉子的樹。其中c/esce/^a/7"(G)函數返回G中所有在G內不含有任何後代的關鍵字結點的集合。即就是G的最小組成樹是從乃a(G)到Gfesce"血y"(G)中所有結點的。在將每個簇的最小組成樹返回給用戶後，再為用戶提供兩個額外功能來擴大返回結果-一是對任意結點的"展開"，將原XML文檔樹中該結點的所有後代結點加入到結果中，例如在圖1中，對於簇{0.1.0.0，0.1.1.0}的最小組成樹，用戶可以展開^"t力,s(0.1.1)結點來獲得該篇文章的另一個作者/o力"(0.1.1.1);二是根結點的提高，即將當前最小組成樹根結點的父結點加入到結果中，例如對於簇{0.0.1.0，0.0.1.1}的最小組成樹，用戶可以將根結點力"t力ors(O.O.l)提高，從而得知其父結點力m'cJe(O.O)。通過這兩個功能的組合，用戶可以根據自己的需求來隨意擴展每個結果的大小，直至找到滿意的內容為止。3.XML關鍵字搜索的聚類算法的預處理在數據挖掘中，聚類是一個常用的處理方法。它將一個對象集合分成一些組，使得同一個組內對象之間的相似度達到最大，而不同組間對象的相似度達到最小。在XML關鍵字搜索的背景下，本發明的目標是將一個關鍵字結點集合按照結點間語義距離的遠近進行分組。本發明針對XML關鍵字搜索，設計了相應的的聚類算法。對於一個距離閾值"，XML關鍵字聚類搜索的目標就是找到所有的最優簇。在說明XML關鍵字聚類算法之前，先對XML文檔樹進行預處理，步驟如下(1)使用Dewey編碼為整棵XML文檔樹進行編碼；(2)為所有的關鍵字建立倒排索引表；(3)對於深度(最大高度)為力的XML文檔樹，建立一個包含有力個有序關鍵字結點列表的層次型數據結構H。其中每一個層次是將XML文檔樹上一組處於同一高度的多個結點按照文檔訪問(先序遍歷)順序組成一個序列/，A是其中的任一個結點；(4)先序遍歷XML文檔樹，每遇到一個標籤含有關鍵字的結點，將它加入相應層次的列表的尾部。當文檔遍歷結束時，可以得到一個如圖2所示的層次型數據結構//。在該結構的任一層次的列表上，結點是按照文檔訪問(先序遍歷)順序加入的，因而有如下定理定理l.在序列/中，當從結點A向左(向右)進行遍歷時，A與每次遇到的結點之間的距離非遞減增加。證明.從結點A開始，無論是向左還是向右遍歷,每次遇到的結點與A的關係總會依次是"兄弟"、"堂兄弟"，越來越疏遠，從而彼此間的最短路徑越來越長，LCA也越來越高，根據公式1可知距離越來越遠。對於文檔樹上的任意一個低(高)於/所在位置的層次，同樣按順序取任意多個結點組成序列/'，並且設/'中一個結點A是A的後代(祖先)結點(如果有多個後代結點,則任選一個；如果不存在後代結點，則在相應位置插入一個)，定理2如下定理2.在序列/'中，當從A開始向左(向右)遍歷，則A與每次遇到的結點之間的距離非遞減增加。證明.x,與序列/'中任意一個結點的最短路徑等於A和該點的最短路徑減去(加上)《和A的最短路徑，而在/'確定的情況下，x和A的最短路徑是不變的，所以A與該結點的最短路徑長度越來越短，而顯然它們的LCA的深度是減小的，所以可得證距離增加。4.基於圖的的關鍵字搜索聚類算法GKSC(Graph-basedClusteringalgorithmforXMLKeywordSearch)GKSC算法首先遍歷#，根據彼此距離是否小於等於距離閾值建立結點和結點之間的連接，從而得到一個以各個關鍵字結點為頂點的加權無向圖&再使用一個圖的分解算法來獲得一組最大完全子圖，各個完全子圖的頂點集合就是一個最優簇。GKSC算法的步驟如下(1)從上到下按層次訪問/Z中的結點，在每一層的列表中，從左到右遍歷，對於當前訪問結點，計算它和同層右邊以及下面的某些鄰居的距離。假設當前正在訪問結點A，則它和同一層次處於它左邊的鄰居結點的距離，以及和它上面的層次的鄰居結點的距離都己經被計算過了，因此只需要考慮右邊以及更低層次的結點。假設被考慮的結點是A，並且處在A的同一層次，根據定理l，隨著A的位置向右移動，Ws(A，A)—直變大。所以，當力's(x,，^)大於"時，A右邊的結點都不需要再被考慮。(2)對於更低層次的結點，首先確定有多少層次的結點需要被考慮。給定一個"，距離公式必須滿足formulaseeoriginaldocumentpage12，又由於formulaseeoriginaldocumentpage12,所以formulaseeoriginaldocumentpage12成立，也就是說formulaseeoriginaldocumentpage12，所以formulaseeoriginaldocumentpage12是formulaseeoriginaldocumentpage12A下面必須考慮的層次的數目，其中Z7oor函數表示向下取整。可以發現，即使x在第Woor(鄉晰、).的+l)個更低的層次有一個後代結點，它和該後代之間的距離也肯定超過了距離閾值。(3)計算出所需要考慮的層次數目後，對於x,下方/oor((fe/^0O.^)層中的每一層，首先找到A的後代在該層中的位置(A的後代結點不需要一定在W中存在)，再從該位置向左(向右)遍歷直至距離超出閾值，並且根據定理2，在這一層中，其它結點都不需要參與考慮。當A是所屬層中的第一個結點時，使用二分法去尋找它在/ooK鄉決(x,)w)個低層次列表中後代結點的位置，並且用指針記錄下這些位置(如圖2所示)。而當A不是第一個結點時，只從那些記錄的位置開始向右尋找後代結點的位置，之後再修改指針到當前位置。這樣做的原因是假設A和A在同一層中兩個相鄰的位置，A在A的左邊，則在更低的一個層次中，A的後代結點的位置肯定在X的後代結點位置的右邊，這樣處理的話指針只朝一個方向移動，它的變化是累加式的，比每次都用二分法尋找後代結點的位置要高效得多。(4)每次計算兩個結點的距離時，如果小於或等於距離閾值，貝ij(通過加上互相指向的指針)將該兩個結點用邊連接起來，並且記錄下距離作為該邊的權。(5)上一步結束後，可以得到一個加權的無向圖。然後再將圖分解得到所有的最大完全字圖，從而得到結果簇。算法GKSC能夠找到所有的最優簇，完全達到了聚類的目標，其不足在於效率較難控制，尤其是在距離閾值比較大的時候效率可能會比較低。因此，本發明提出另外兩個聚類算法CKSC和LCC.5.核心集驅動的聚類算法CKSC(Core-drivenClusteringalgorithmforXMLKeywordSearch)CKSC的思路則是利用分而治之的思想，首先找到一些被稱為核心集(core)的結點集。若是核心集，則在它之內的結點肯定能被聚到一起；再找到一些肯定包含最優簇的核心集的集合；最後從這些核心集集合中找到最優簇。定義7.核心集。對於距離閾值"來說，任一個關鍵字集合c。e義，如果它所包含的關鍵字結點中任意兩者之間的距離都小於或等於"，則G被稱為一個核心集(core).根據定義7，任意一個最優簇都是一個核心集。但是，一個核心集不一定是一個最優簇。引理1.設在層次型數據結構^的任一層中取^和A兩個任意結點，其中，A在A右邊。對於一個距離閾值"，若必Oc,a)s"，則從a到&這0-/+1)個結點的集合是一個核心集。證明.設從a到&這0-/+1)個結點中任取兩個結點&&並且^在工的右邊，則根據定理1可知cfo(;c。,;OS血(x。,;0《必",A)Sw，即任意兩個結點之間的距離小於等於"，得證。定義8.原始核心集。〃中的一個結點集合G'被稱為一個原始核心集(coreorigin),若且唯若(1)G'是一個核心集；(2)C/中的結點都處於V的同一層次；(3)在該層次中不存在一個核心集C。使得6TcC。。GKSC算法步驟的說明如下(1)首先遍歷//，將/Z中的結點分成一些核心集。對於//的每一層，具體的做法是創建一個空集，將該層第一個結點加入，從第二個結點開始往後遍歷，計算第一個結點與遍歷當前結點之間的距離；如果小於等於"則將之加入集合。當遇到距離超出"的第一個結點時，再創建一個空集，以該結點為集合中第一個結點繼續遍歷，直至該層中所有結點都已遍歷完。一個原始核心集所包含的是^上同一層次中相鄰的一組結點。如圖3(a)所示，假設flfe(x,';0《w，並且tfo(x,—";>:,)>0,cfe(w,)〉ffl，根據引理1可知，{x;，…，〖}是個核心集，並且對於其中的任一個結點工，必(x,—";:。)>必(;c,—,，jc,)xy，cfo(x。>&(;cr,xr+1)>，艮卩A與同一層內其它結點的距離都大於"。所以，{力，…，&}是一個原始核心集。實際上它是該層所有結點集合的一個最優簇。(2)再尋找原始核心集周圍的核心集，求出包含這些原始核心集的最優簇。如前所述，對於一個原始核心集來說，同一層次中所有其它結點都不需要再考慮，只需考慮其它所有層次的相鄰結點。如圖3(b)所示，假設當前考慮的原始核心集是/中的{力，…，W，觀察該層下面某個序列,中的結點，按照GKSC算法中尋找連接的做法可以得到一組連續的與結點^距離小於等於"的結點。將這些結點設為z/，…，力〃，將與結點A距離小於等於"的一組連續結點設為義/，…，xZ。假設k/,…，義/]與U/，…，7/]沒有交集，則,中不存在可以被加入核心集{力，…，,J以形成最優簇的結點。但如果兩者的交集如圖中所示是U/,…，z/〕，且在一個核心集內，貝1」{力，…，Wuk/，…，7/是一個核心集。另外當，{義/，…，義/]不是一個核心集的時候(義/到義/跨越多個核心集)，將它劃分成幾個核心集再予以考慮，對於每個核心集可以得到相同的結論。當找出{&，W在所有層次上需要考慮的核心集後，在每一層取一個核心集組成一個核心集的集合，顯然可以在該集合內找到包含{&，…，d的最優簇。引理2.結點集合{力，…，WuU/，…，義/是一個核心集，且除b/,…，力，之外的/'中的點都不能被加入{&…，W而成為一個核心集.證明.{力，…，&}與{義/，…，義/1本身都是核心集，所以只需證明兩個集合中各任取一個結點，距離小於等於距離閾值。設在{力，…，W中任取一個結點A，Ur'，…，義/]中任取一個結點義/，假設力'S(&,,Z)>ffl，則根據定理2，若力'S(力，則x/在該層中的祖先應該在A的左邊；若力'S(A，7/)《w,則％/在該層中的祖先應該在A的右邊；而很顯然Ws(A,義/)與力'sU。x/)都小於等於"，則義/的祖先的位置矛盾，所以力's(&，至於/'中的其它結點，則很明顯至少與力和^中一者的距離超過"，得證。顯然，同理可以證明對於/上方的任一個層次，引理2同樣成立。這實際上是相當於先從每一層中挑選部分結點，再從這些結點構成的子圖中尋找一個最大完全子圖。6.鬆弛的核心集驅動聚類算法LCC(LoosenCore-drivenClusteringalgorithmforXMLKeywordSearch)上面兩個算法雖然有時候效率會很高，但仍然存在不可準確預期的低效情況，尤其是算法GKSC強烈依賴於距離閾值對兩結點間連接數的影響。由於在大多數情況下，用戶對結果並沒有太精確的要求，因而，可以放鬆對結果集的要求，允許一些距離稍遠的結點在同一個結果中出現，以提高算法的效率。算法LCC正是基於這樣一個思想，它放鬆對每個結果集必須是最優簇的要求，取而代之的是必定包含最優簇的一個結點集合。算法LCC的步驟如下(1)算法LCC開始時處理仍然和CKSC—樣。首先遍歷層次型數據結構#，得到一組原始核心集；(2)對於/Z中的每一層建立兩個列表頭結點列表Z/AZ和尾結點列表77^。其中，/WZ和77^分別按順序存放該行中所有原始核心集的第一個和最後一個結點；(3)對於每個原始核心集G'，尋找其它所有層次中的一些原始核心集，這些原始核心集中存在結點到所有C/中結點的距離都小於等於(4)找到這些原始核心集後，不是試圖在其中尋找最優簇，而是簡單地將它們合併到C。'中形成一個結果集。7.搜索結果的排序由於考慮儘量不丟失有意義的結果，本發明設計的聚類算法有時會產生大量結果，因此，需要對搜索結果進行排序。在關鍵字搜索的現有工作中，已經提出一些排序模型。例如，有些是基於圖上的路徑[1][8][9]，有些則是借用信息檢索中的方法[5][6]。本發明針對上面設計的聚類搜索算法，設計了特定的排序方法。它考慮倆方面的因素(1)首先，結果中出現的關鍵字種類越多，排序的優先級越高；這是顯然的，如果用戶想査的一些內容都沒有在某個結果中出現，則該結果肯定不是最優的。(2)對於關鍵字出現種類相同的結果，比較它們在結構上的差別，由此引入一個結果簇的"平均距離"的概念定義8(結果簇的平均距離)。對於結果簇集合C中任一個簇G，它的平均距離^、自為它所包含的所有結點之間兩兩距離的平均值，假設歷是G所包含的結點的個數，則G的平均距離如公式(2)所示(c)二,m>12d(2)oo,m=1顯然，一個簇的平均距離越小，則說明它含有的結點在結構上越緊湊，從而說明它能構成更好的返回結果。所以排序函數實際上就是取平均距離的倒數，平均距離越小，則排的越高。整個排序的過程如下(1)首先根據每個簇含有關鍵字的情況進行分組。所有含有相同關鍵字種類個數的簇被分入一組，對組進行排序，含有越多關鍵字種類的組排得越靠前；(2)對於同一組內的簇，計算它們的平均距離。平均距離越小的簇在組內排得越靠前。對所有的簇排好序後，為每個簇生成一個最小組成樹，並按照順序將它們返回給用戶。(3)單結點簇(簇中只包含一個關鍵字結點)包含的信息量自然要少於任一個非單結點簇的最小組成樹，因此它們的平均距離定義為無窮大，所以它們會被排到整個結果序列的最後。在圖1中，當距離閾值被設定為2.0時會產生四個最優簇G=0rbG=U3,W,G=U，&&&}和6;=U,為，^}。其中，G和G包含三個關鍵字，G和G包含三個關鍵字。它們的平均距離分別為力、，(G)=0.67,力's，(G)=2.00，=1.33，力's一(G)=0.80。首先四個簇根據包含的關鍵字情況被分成兩組(G，C4},{G,G}，同一組內的簇再根據平均距離排序，最終四個簇的排列順序是:G,G,G，G。本發明針對XML關鍵字搜索，定義了XML關鍵字搜索的語義距離模型，設計了三個關鍵字搜索的算法和搜索結果的排序模型。本方法的具體操作過程包括(1)定義用戶提交的關鍵字，並將XML文檔的關鍵字搜索語義定義為關鍵字之間的語義距離模型，並以此表示用戶的搜索意圖。該語義距離模型綜合考慮了兩方面的因素來定義兩個關鍵字之間的語義距離，即兩個關鍵字結點之間的路徑長度和它們的LCA的層次。(2)將關鍵字搜索的返回結果定義為關鍵字簇的最小組成樹，其中，定義的相關概念包括關鍵字結點的簇、最優簇、簇的最小組成樹。(3)對XML文檔樹進行預處理。(4)在本發明提出的語義距離模型的基礎上，可以選擇使用如下三種聚類算法進行XML關鍵字搜索GKSC、CKSC、LCC。三個算法在執行之前都要進行預處理，包括如下步驟a)使用Dewey編碼為整棵XML文檔樹進行編碼。b)為所有的關鍵字建立倒排索引表。c)對於深度(最大高度)為力的XML文檔樹，建立一個包含有力個有序關鍵字結點列表的層次型數據結構H。d)先序遍歷XML文檔樹，每遇到一個標籤含有關鍵字的結點，將它加入相應層次的列表的尾部。用戶可以根據不同的需要，在GKSC、CKSC、LCC三個算法中間做出選擇。從結果集來看，算法GKSC它可以找到所有的最優簇；算法CKSC是由核心集驅動的，它基於一個假設，即所有最優簇必定包含最少一個原始核心集，所以它可能會丟失部分最優簇;算法LCC則不考慮最優簇的約束。從時間效率上來看,算法CKSC實際上是在算法GKSC的基礎上採用分而治之的思想，總體性能優於算法GKSC;算法LCC是在CKSC的基礎上進行了優化，時間效率要高於CKSC。從空間複雜度來看，算法GKSC需要儲存兩結點之間的連接以及距離值，所以當距離閾值比較大時需要額外0(//)的儲存空間。算法CKSC和LCC中需要記錄所有的原始核心集(也可以只記錄每個核心集的首尾兩個結點，因為原始核心集的結點都是連續的)，需要0(77)的儲存空間。另外，算法CKSC在尋找相關核心集時還需要建立"結點-原始核心集"索引表；算法LCC也需要另外兩個列表^VZ和7)VZ，所以算法CKSC和LCC又需要額外的"")的儲存空間。再加上層次型數據結構^所佔用的空間，算法CKSC和LCC所使用的空間幾乎等同，都不大於3"。算法GKSC所佔用的空間為("+)，其中後一項的具體值取決於所生成的圖中邊的個數。圖4顯示了三個算法時間複雜度的比較。(5)根據本發明提出的排序模型，對搜索結果進行排序。其中，定義了結果簇的平均距離。排序的步驟如下a)首先根據每個簇含有關鍵字的情況進行分組。b)對於同一組內的簇，計算它們的平均距離。C)對所有的簇進行排序，平均距離越小的簇在組內排得越靠前。之後，為每個簇生成一個最小組成樹，並按照順序將它們返回給用戶。圖1為XML文檔示例的樹型結構。圖2層次型數據結構H示意圖。圖3為査找核心集示意圖。圖4為三個聚類算法的時間效率比較。圖5為針對DBLP和Treebank的不同平均關鍵字結點個數的比較。圖6為針對關鍵字個數的不同，對算法時間效率的比較。其中，(a)為關鍵字個數是2時(數據集為DBLP)算法時間效率的比較。(b)為關鍵字個數是2時(數據集為Treebank)算法時間效率的比較。(c)為關鍵字個數是3時(數據集為DBLP)算法時間效率的比較。(d)為關鍵字個數是3時(數據集為Treebank)算法時間效率的比較。(e)為關鍵字個數是4時(數據集為DBLP)算法時間效率的比較。(f)為關鍵字個數是4時(數據集為Treebank)算法時間效率的比較。(g)為關鍵字個數是5時(數據集為DBLP)算法時間效率的比較。(h)為關鍵字個數是5時(數據集為Treebank)算法時間效率的比較。圖7為不同關鍵字個數的算法聚集效果的比較，其中，(a)為關鍵字個數是2時(數據集為DBLP)算法的聚集結果數量的比較。(b)為關鍵字個數是2時(數據集為Treebank)算法的聚集結果數量的比較。(c)為關鍵字個數是3時(數據集為DBLP)算法的聚集結果數量的比較。(d)為關鍵字個數是3時(數據集為Treebank)算法的聚集結果數量的比較。(e)為關鍵字個數是4時(數據集為DBLP)算法的聚集結果數量的比較。(f)為關鍵字個數是4時(數據集為Treebank)算法的聚集結果數量的比較。(g)為關鍵字個數是5時(數據集為DBLP)算法的聚集結果數量的比較。(h)為關鍵字個數是5時(數據集為Treebank)算法的聚集結果數量的比較。圖8為聚類算法與IL的時間效率比較。圖9為試驗數據的片斷樣例，其中，(a)為XMark數據(版本0.92)的DTD的片段。(b)為XMark數據(版本0.92)的文檔片段。表l為圖l的語義距離矩陣。具體實施方式本發明的核心是在基於語義距離模型的基礎上設計了三種聚類算法，具體實現的偽碼如下(1)GKSC算法Algorithm1(Graph-basedClustering)Input:ahierarchicalstructureOutput:asetofoptimalclustersC1.for(everylist/in//)〃top-down2.for(everynodein/)〃left-right3.findarightwardneighbor4.whileWs(x,，x》<=co)5.//wA:(X/,x》；〃linktwonodes6.findnextrightwardneighborx力7.for(everylist/'inyZoor(y一/7(x,).a;)layersbelow/)8.P《ywt/Z)esc屍as7tow(X/'9.traverseleftwardandrightwardfrom77untildistanceoverflowsandlinkwithneighborscloseenough;10.usegraphpartitionalgorithmtogetoptimalclusterset力W(iDesaPas7YZ0w(X/，〃findthepositionofadescendantofx,in/'1.get:c/sdescendantx乂in/';2.if(x,isthefirstelementof/)3.usebinarysearchtofindasthe/as7Y/0nofXyin/';《else5.searchrightwardsfrom/'.po/她rtofindpasthepositionofx乂；6./'./7o/w/^《7.return算法的第1至第9行是一個遍歷層次型數據結構並建立圖的過程。第10行是使用一個圖分解算法來獲得所有的最大完全子圖。一個最大完全子圖可以保證所有兩兩結點之間都有連接，並且再加入圖中任一個其它結點都不能構成一個完全子圖。所以，它的頂點集合與最優簇的定義相符。圖分解算法詳細的具體做法是從圖中任取一點，考慮與它相連的所有點是否構成一個完全子圖，如此遞歸地計算出所有包含有該點的最大完全子圖。對於找出的每個子圖上任意一點，如果它沒有連向子圖外的邊，則將它從圖中刪除。之後再任取圖中一點繼續算法，直至圖空為止。這時可以獲得一組彼此不包含的完全子圖，即最大完全子圖。算法GKSC的時間複雜度不只和關鍵字結點的個數有關，而且受距離閾值的影響很大。在一種最壞情況，即閾值"大於2力時，則在遍歷〃的過程中，每個結點都要與(/^l)個結點比較，所以時間複雜度是遍歷結束後得到的是一個全連接圖，每個結點的度都是(/^1)。雖然最終的結果是一個包含所有關鍵字結點的大簇，但由於尋找最大完全子圖本身是個NP難的問題[13]，當所有兩兩結點間都存在連接時，分解的時間複雜度會非常高歐))。(2)CKSC算法Algorithm:2(Core-drivenClustering)Input:ahierarchicalstructureOutput:asetofoptimalclustersC1.for(everylist/in7/)2.Co4"0;3.;c/《firstnodeof/;4.for(everynodein/)5.if(dis(;v,,x,))6.addintoCb;了.else8.saveCo;9.《0;11.save12.for(everycoreCo)13.OS—yw^e/她dC0—O9);14.c《OS;15.for(eachcoreCc'inCaS)16.c《c門y;7t/7e/"/^^/Cores(C力；17.addcinto1.CS《0;2.for(eachlayer/excepttheoneCbbelongsto)3.Co'《0;4.x/themostleftnodeinCo;5.:\vethemostrightnodeinCo;8.usebinarysearchtofinda:,";9.usebinarysearchtofindx/;10.if(>:/isx,〃orleftofx/")11.addnodesfrom:\:/to;c/'intoCb';12.addCo'intoCS;算法第1至第11行是尋找所有的原始核心集的過程，時間花費為0")。第12行到第17行是為每個核心集尋找最優簇。方法/y/7^fe^tec/Cor"中所使用的方法/Y/7G^ce6Wfe^Asi"OT是從GKSC算法的方法打/^fe5c屍o^'"^7變化而來。它除了可以尋找祖先結點的位置外，還有一個區別就是拋棄某些結點採取的遍歷方式而只採用二分法查找。其原因是，由於只需要找每個原始核心集的首尾結點，而它們的祖先/後代結點的位置跳動比較大。方法力'/o7fe7s"^br^的第8和第9行為尋找任一層中應該被考慮的核心集的過程。在方法/Y/7t^e^"c/Cores中，査找祖先(後代)結點位置(第6和第7行)的時間為O(bg")，第8行第9行的時間都為O(log")，第11行是0")。所以，三者總共的時間複雜度為對於每個原始核心集，尋找相關的核心集需要調用方法/i/w^7a"otbres—次；而對於找出的其它層次的核心集，為了尋找最優簇，每個最多需要調用方法打/7oye"teotbres(A-l)次，也就是總共(/!-1)2次。所以，算法CKSC的第12至17行所需的時間總共是(A-l)3.(41og"+")。由於力總是一個常數，所以複雜度仍然是W")。設原始核心集的數目是肌可知算法CC的總時間複雜度是0("+附.")，也就是O(m.")。由此可見，這與原始核心集的數量相關。與算法GKSC的情況剛剛相反當距離閾值"被設置的很小時，歷接近於"，時間複雜度趨向O(".log");而當"很大時，瓜是一個常數，則複雜度為最壞的情況為"趨向於仏複雜度為0"2).(3)LCC算法Algorithm3(LoosenCore-drivenClustering)Input:ahierarchicalstructureOutput:asetofclustersC1.findallcoresorigin;2.for(everycoreCo)3.CS<~yw襲/ate(iC騰s(Co);4.c《C&5.for(eachcoreCo'inC5)6.c《cUCo';7.addcintoC;1.CS《0;2.for(eachlayer/excepttheoneCobelongsto)3.x/—themostleftnodeinCo;4.a<~themostrightnodeinCo;5.《,WZXPcw7'ft'o"/wfflVL(x/,/);6.a&)inthenodesofrightof/,;8.findthemostrightx/satisfytodis(xr,x力>o>inthenodesoffflVLleftof/r;9.if(x/isx,"orleftofx/，10.addallcoresoriginbetweenandx/'intoCS1;其中，尋找初始核心集的過程與CKSC—樣(第1行)。方法/Y/7GWe""Gtbre5與CKSC算法中的同名算法有所改變打/7o^7ate沈bres的第5、6行分別是從J的^VZ和7)見而不是從2中尋找祖先(或後代)的位置，第7行和第8行則說明了如果在A(A)位置右邊(左邊)的某核心集的第一個(最後一個)結點與&(&)的距離超出"，則該核心集往右(往左)所有的核心集都沒有必要再考慮。可以看出方法/i/w^eJa"chores的第5到第8行，每一步的時間複雜度都是O(log")，而第10行只需記錄下相關的原始核心集，所以是常數。假設初始核心集的數量是歷，那麼顯然算法LCC的時間複雜度為0("+附.log");當辺趨向於/7時達到最壞情況O(".l0g");當歷為常數時達到最好情況O")。另外，由於不需要從一組原始核心集中找到最優簇，所以LCC調用方法/Y/w7e^^eoCbres的次數要明顯少於CC，從而它的時間複雜度擁有一個比CKSC小的常數。為了證明本發明的效果，實現了相應的原型系統，從四個方面進行了一系列實驗(1)比較在同一距離閾值下三個聚類算法的效率和結果；(2)觀察三個算法的效率和結果隨著距離閾值變化而產生的變化；(3)對比不同文檔上三個算法的效率和結果；(4)比較本發明的XKLuster方法和SLCA方法[2]的效率和結果。系統運行在CPU頻率2.8GHZ、內存2G的微機上，軟體運行環境是WindowsXP，JDK1.6和Tomcat6.0，XML解析器是Xerces。用作比較三個聚類算法的數據集是DBLP(文檔大小127M，結點總數6332225個)和Treebank(文檔大小82M,結點總數3829511)[12]。選用這兩個文檔的原因有二(1)大量的結點數可以提供更加準確的實驗結果；(2)兩個文檔的結構有很強的可比性DBLP的DTD比較簡單，因此文檔結構很規整，樹的高度也不大(最大深度為6,平均深度為2.9)，是屬於典型的"寬且平"的XML文檔，而Treebank則沒有DTD，結構很複雜，樹高也相對較大(最大深度為36，平均深度為7.9)。首先為每個數據集建立一個單詞表，其中包含有在XML文檔中出現的一些單詞，每個單詞的出現頻率在5,000到15,000之間。然後，每次隨機從單詞表中選出幾個單詞作為關鍵字，對XML文檔進行搜索，反覆運行四十次，再取結果的平均值作為實驗結果。圖5為在不同的關鍵字個數情況下文檔中平均含有的關鍵字結點總數的情況；圖6和圖7分別是三個聚類算法在兩個文檔上使用的時間效率和結果數量的比較。當距離閾值比較大時，(DBLP從6.0開始，Treebank從8.0開始)，在實驗用的硬體上運行算法GKSC無論從時間還是空間上來看己經很大，所以此時只比較算法CKSC和LCC。另外，在文檔比較大時，所以很多情況下會搜索出大量只包含有單個關鍵字結點的簇，這些簇中的結點在距離閾值內無法找到任何一個相鄰結點，為了使圖的表達更加清晰，在結果個數比較時忽略這些簇，而只考慮包含有兩個以上關鍵字結點的簇。在圖6中容易發現(1)給定關鍵字個數和距離閾值，三個算法的時間花費從大到小依次是GKSC，CC，LCC。但當距離閾值非常小時(0.0)，GKSC算法是花費最小的，(2)隨著距離閾值的增大，GKSC所花費的時間一直增大，而CKSC和LCC所花費的時間則是先增大再減小。這說明圖7中所展示的三個算法的時間複雜度的特性。在圖7(a)中，當距離閾值被設為0.0時，三個算法的返回結果都是那些標籤中含有多個關鍵字的結點。這是因為每一個這種結點都被看成是不同的幾個結點；當距離閾值為6.0時，幾乎所有的結點都被聚入了少數幾個大的簇中；而隨著距離閾值的增大，除了單結點簇外的結果數量先增大，然後再減小為l。圖7中其它部分與圖7(a)的情況基本相同。圖7還說明了GKSC和CKSC的返回結果數量相同，而LCC略少。另外還計算了所有返回的簇的平均距離，其中GKSC和CKSC的結果相同，而LCC的稍大(僅僅在小數點後四位)。所以，GKSC和CKSC返回同樣的結果(所有的最優簇)，而LCC返回了更少並且更大的結果，並與GKSC和CKSC的結果相差不大。從圖5中可以看出在關鍵字個數一定時，從DBLP中獲得的平均關鍵字結點總數要多於從Treebank中獲得的平均關鍵字結點數。但通過圖6的比較可以看出，無論使用哪種聚類算法，在相應的情況下，對於Treebank所花費的聚類時間都要大於(有些是遠大於)對DBLP所花費的時間，這說明了聚類算法的時間複雜度不只與關鍵字結點總數相關，還依賴於特定的文檔結構以及實際的關鍵字結點的分布情況。當樹的高度更大以及結構更加複雜時，聚類算法的時間花費也會增大。除此之外，在實驗中還實現了XKSearch^中尋找SLCA的算法IL(IndexedLookup),並與之進行比較。根據XKSearch，IL的算法複雜度為0(|&|.log|S|)。它將所有的關鍵字結點按照包含關鍵字的情況分為一些關鍵字結點集(具有相同關鍵字的結點在同一個集合中)；ISl是其中最小的集合的結點數，而ISl是所有關鍵字結點的總數。圖8是三個聚類算法和IL算法在DBLP上的時間花費比較(距離閾值為2.0)，在其它距離閾值下結果也類似。從圖8中可以看出，IL的算法效率比任何一種聚類算法的效率都高，原因在於這兩類算法的設計目標不同IL僅僅是從所有關鍵字結點中找出一組特殊的結點，而聚類算法的目的則是在於根據一個距離閾值找到一個特定的關鍵字結點集合的一個劃分。因為本發明支持關鍵字之間的"OR"運算，因而通常情況下會得到更多結果。為了進一步進行說明，實驗中選用特定的搜索結果來說明XKCluster和SLCA方法結果的異同。這裡使用XMarkM數據集來進行兩種方法結果的比較實驗，因為XMark數據集的DTD中包含大量的遞歸元素。圖9(a)是XMark的一個DTD片段。實驗中先使用XMark提供的文檔生成器生成一個XML文檔，然後使用兩種方法分別對該文檔進行關鍵字搜索。圖9(b)是該文檔的一個文檔片段。如果使用"M^'w"和"0^ar"作為搜索的關鍵字,，貝IJSLCA方法能夠找出一個SLCA結點"torf"，，然後可以依此返回以該結點為根的子樹(是一封郵件的正文)。SLCA方法在選取結果時認為LCA相對最低的結果最優秀，但對於得到的所有結果卻不能按照LCA的高低排序。所以即使提供了某種結果的擴展方法，用戶也很難確定對哪個結果使用該方法，所以不能得到該郵件的其它信息(比如日期)。而只要距離閾值的大小設置合理，本發明的方法可以得到"ma/r結點和"tec,"結點，從而能夠得到更多的信息。實際在現實使用的文檔中，這種情況經常發生。因為一封郵件的發送者和接收者的名字往往會在郵件正文中出現。另外，"feywoW元素會導致更多類似情況的出現，因為在DTD中，它直接指向自己形成遞歸。參考文獻[ijV.Hristidis，Y.Papakonstantinou，andA.Balmin.KeywordproximitysearchonXMLgraphs.InICDE，2003.[2jY.Xu，Y.Papakonstantinou.EfficientKeywordSearchforSmallestLCAsinXMLDatabases.InSIGMOD，2005.[3]Y.Li，C.Yu，andH.V,Jagadish.Schema-FreeXQuery.InVLDB，2004.[4jV.Hristidis，N.Koudas，Y.Papakonstantinou,andD.Srivastava.KeywordProximitySearchinXMLTrees.InIEEETransactionsonKnowledgeandDataEngineering,2006[5jS.Cohen，J.Mamou，Y.Kanza，andY.Sagiv.XSEarch:ASemanticSearchEngineforXML.InVLDB，2003.[6jL.Guo，F.Shao，C.Botev，andJ.Shanmugasundaram.XRANK:RankedKeywordSearchoverXMLDocuments.InSIGMOD，2003.[7jZ.LiuandY.Chen.IdentifyingMeaningfulReturnInformationforXMLKeywordSearch.InSIG腳，2007.[8jG.Bhalotia，A.Hulgeri，C.Nakhe，S.Chakrabaxti,andS.Sudaxshan.KeywordsearchingandbrowsingindatabaseusingBANKS.InICDE，2002.V.HristidisandY.Papakonstantinou.Discover:Keywordsearchinrelationaldatabases.InVLDB，2002.[io]S,Agrawal，S.Chaudhuri，andG.Das.DBXplorer:Asystemforkeyword-basedsearchoverrelationaldatabase.InICDE，2002.[ii]H.He，H.Wang，J.Yang，andP.S.Yu.BLINKS:RankedKeywordSearchesonGraphs.InSIGMOD，2007.[12]http://www.cs.Washington,edu/research/xmldatasets/www/repository.html[n〗T.Feder，P.Hell，S.Klein,andR.Motwani.Complexityofgraphpartitionproblems.InSIGACT，1999.[14]Xmark，http:〃monetdb.cwi.nl/xml/.表1tableseeoriginaldocumentpage24權利要求1、一種基於語義距離模型的XML文檔關鍵字搜索聚類方法，其特徵在於具體步驟如下(1)定義用戶提交的關鍵字，並將XML文檔的關鍵字搜索語義定義為關鍵字之間的語義距離模型，並以此來表示用戶的搜索意圖；(2)將關鍵字搜索的返回結果定義為關鍵字簇的最小組成樹；(3)XML文檔樹進行預處理；(4)根據本發明提出的語義距離模型，選擇使用如下三種聚類算法之一種進行XML關鍵字搜索基於圖的聚類算法、核心集驅動的聚類算法和鬆弛的核心集驅動聚類算法；(5)根據排序模型，對搜索結果進行排序。步驟(1)中將用戶提交的關鍵字定義為一個包含t個關鍵字的集合L＝{ki|i＝1，…，t}，XML文檔定義為一棵XML文檔樹，具體如下定義1.XML文檔樹，將一顆XML文檔樹表示為一個8元組d＝(V，E，X，label(id)，pl(id1，id2)，depth(id)，dwcode(id)，lca(V′))，其中(1)V是樹上所有結點的集合，並且每個結點都有唯一的標識符和Dewey編碼；(2)EV×V，是樹上邊的集合；(3)label(id)為標籤函數，用來獲得標識為id的結點的標籤，其中id∈V；(4)XV是樹上所有關鍵字結點的集合，所謂關鍵字結點即標籤中包含關鍵字的結點；(5)pl(id1，id2)函數，用來取得id1和id2兩個結點之間的路徑長度，其中id1和id2必須具有祖先後代關係，而此函數返回的結果為它們之間的路徑上所包含的邊的個數；(6)depth(id)函數，用來獲得標識為id的結點的深度(樹的根的深度為1)，其中id∈V；(7)dwcode(id)函數，用來獲得標識為id的結點的Dewey編碼，其中id∈V；(8)lca(V′)函數，其中V′V是V的任意子集，函數返回V′中所有結點的最低公共祖先；定義2.兩個關鍵字結點之間的最短路徑，兩個關鍵字結點xi和xj的最短路徑為結點xi到lca({xi，xj})的路徑加上結點xj到lca({xi，xj})的路徑；同時，用函數spl(xi，xj)來表示結點xi和xj的最短路徑的長度，顯然spl(xi，xj)＝pl(lca({xi，xj})，xi)+pl(lca({xi，xj})，xj)；定義兩個關鍵字結點之間的語義距離，XML文檔樹上任意兩個關鍵字結點之間的語義距離dis(xi，xj)被定義如下2、根據權利要求1所述的基於語義距離模型的XML文檔關鍵字搜索聚類方法，其特徵在於所述步驟(4)中，三種聚類算法具體步驟如下(一)基於圖的關鍵字搜索聚類算法的具體步驟如下(1)從上到下按層次訪問#中的結點，在每一層的列表中，從左到右遍歷，對於當前訪問結點，計算它和同層右邊以及下面的某些鄰居的距離；(2)對於更低層次的結點，首先確定有多少層次的結點需要被考慮；給定一個"，距離公式必須滿足formulaseeoriginaldocumentpage4，又由於formulaseeoriginaldocumentpage4所以formulaseeoriginaldocumentpage4成立，也就是說formulaseeoriginaldocumentpage4所以formulaseeoriginaldocumentpage4是x,下面必須考慮的層次的數目，其中Z7oor函數表示向下取整；(3)計算出所需要考慮的層次數目後，對於A下方y7oor(鄉A(;c,)w)層中的每一層，首先找到x的後代在該層中的位置，再從該位置向左遍歷直至距離超出閾值，在這一層中，其它結點都不需要參與考慮；當A是所屬層中的第一個結點時，使用二分法去尋找它在y7o。K^^0O.w)個低層次列表中後代結點的位置，並且用指針記錄下這些位置；而當義,不是第一個結點時，只從那些記錄的位置開始向右尋找後代結點的位置，之後再修改指針到當前位置；(4)每次計算兩個結點的距離時，如果小於或等於距離閾值，則將該兩個結點用邊連接起來，並且記錄下距離作為該邊的權；(5)上一步結束後，可以得到一個加權的無向圖，然後再將圖分解得到所有的最大完全字圖，從而得到結果簇；(二)核心集驅動的聚類算法的步驟如下定義核心集，對於距離閾值"來說,任一個關鍵字集合C。^X，如果它所包含的關鍵字結點中任意兩者之間的距離都小於或等於"，則G被稱為一個核心集(core);定義原始核心集，^中的一個結點集合C/被稱為一個原始核心集(coreorigin),若且唯若(l)C/是一個核心集；(2)CZ中的結點都處於^的同一層次；(3)在該層次中不存在一個核心集C。使得CcC。；(1)首先遍歷僅將〃中的結點分成一些核心集，對於^的每一層，具體的做法是創建一個空集，將該層第一個結點加入，從第二個結點開始往後遍歷，計算第一個結點與遍歷當前結點之間的距離；如果小於等於"則將之加入集合；當遇到距離超出"的第一個結點時，再創建一個空集，以該結點為集合中第一個結點繼續遍歷，直至該層中所有結點都已遍歷完;一個原始核心集所包含的是^上同一層次中相鄰的一組結點，所以，U…，W是一個原始核心集；(2)再尋找原始核心集周圍的核心集，求出包含這些原始核心集的最優簇，當找出…，W在所有層次上需要考慮的核心集後，在每一層取一個核心集組成一個核心集的集合，在該集合內尋找包含^，，；d的最優簇；(三)松馳的核心集驅動聚類算法的具體步驟如下(1)首先遍歷層次型數據結構#，得到一組原始核心集；(2)對於^中的每一層建立兩個列表頭結點列表^VA和尾結點列表77\^;其中，WZ和77^分別按順序存放該行中所有原始核心集的第一個和最後一個結點；(3)對於每個原始核心集6T，尋找其它所有層次中的一些原始核心集，這些原始核心集中存在結點到所有C。'中結點的距離都小於等於"；(4)找到這些原始核心集後，將它們合併到C/中形成一個結果集。全文摘要本發明屬於Web數據管理
技術領域：
，具體為一種基於語義距離模型的可擴充標記語言(XML)的關鍵字搜索方法，稱為XKLuster。本發明提出一種新的模型，稱為「XML關鍵字語義距離模型」。它通過更全面地考慮XML的層次結構特徵來度量XML關鍵字搜索的語義；基於本發明提出的「XML關鍵字語義距離模型」，從不同的角度，設計三種聚類算法基於圖的關鍵字聚類算法(GKSC)、核心集驅動的關鍵字聚類算法(CKSC)和鬆弛的核心集驅動聚類算法(LCC)；提出一種排序模型對所有的搜索結果進行排序，以便將搜索結果返回給用戶。與已有方法相比，本發明提出的方法可得到更加合理的返回結果。本發明可用於網際網路上的XML文檔搜索、XML資料庫的搜索等領域。文檔編號G06F17/30GK101241502SQ20081003454公開日2008年8月13日申請日期2008年3月13日優先權日2008年3月13日發明者皓朱,楊衛東申請人:復旦大學