模式匹配查詢算法研究

摘 要：本文針對XML文檔樹設計了模式匹配查詢算法，該算法包括XML文檔樹轉換成為三層子樹和利用各種操作進行結構匹配。在轉換成為三層子樹的時候，涉及到了三種形態(tài)的子樹：單叉樹、過度子樹、一般子樹。并且將XML樹的節(jié)點分為兩類：內部節(jié)點和值節(jié)點。在模式匹配的時候，用更新操作、刪除操作、插入操作完成了模式匹配。

關鍵詞：三層子樹；更新操作；刪除操作；插入操作

中圖分類號：TP301.6 文獻標識碼：A 文章編號：1674-7712 （2014） 04-0000-01

一、問題的描述

XML文檔數據的重要特點之一就是具有結構性數據，在結構匹配的研究中，主要是信息檢索中TF*IDF技術的方法。

TF-IDF是一種用于資訊檢索與文本挖掘的方法。如果某個詞或短語在一篇文章中出現的頻率TF高，并且在其他文章中很少出現，則認為此詞或者短語具有很好的類別區(qū)分能力。

TF-IDF實際上是TF * IDF，TF詞頻（Term Frequency），IDF逆向文件頻率（Inverse Document Frequency）。TF表示詞條在文檔d中出現的頻率。它的主要思想是：如果包含詞條t的文檔越少，也就是n越小，IDF越大，則說明詞條t具有很好的類別區(qū)分能力。例如：如果某一類文檔C中包含詞條t的文檔數為m，而其它類包含t的文檔總數為k，顯然所有包含t的文檔數n=m+k，當m大的時候，n也大，按照IDF公式得到的IDF的值會小，就說明該詞條t類別區(qū)分能力不強。但是實際上，如果一個詞條在一個類的文檔中頻繁出現，則說明該詞條能夠很好代表這個類的文本的特征，這樣的詞條應該給它們賦予較高的權重，并選來作為該類文本的特征詞以區(qū)別與其它類文檔。這就是IDF的不足之處.

本文在這樣的背景下提出模式匹配查詢算法，該算法是以如何提高其數據信息的查詢效率為目的，描述的一種既能夠在保證查全率的同時又對其查準率有所提高的結構查詢優(yōu)化算法。

二、算法的設計

（一）三層子樹

定義1（三層子樹）：如果一個XML子樹以一層節(jié)點為根，并且除了根節(jié)點以外，只包含二層節(jié)點和值節(jié)點，則稱此XML子樹成為三層子樹。

在模式匹配查詢過程中，XML樹的節(jié)點分為兩類：內部節(jié)點和值節(jié)點。值節(jié)點指的是XML樹中的葉子節(jié)點。內部節(jié)點包括三類：一層節(jié)點、二層節(jié)點、過度節(jié)點。根據XML樹的DTD定義三類節(jié)點如下：

（1）一層節(jié)點

一層節(jié)點在對應的DTD中是指的根節(jié)點，能夠重復出現在父節(jié)點中，并且可以擁有二層節(jié)點和值節(jié)點。

（2）二層節(jié)點

二層節(jié)點的定義：至少有一個值節(jié)點（葉子節(jié)點）做它的子孫節(jié)點。

（3）過度節(jié)點

既不屬于一層節(jié)點，也不屬于二層節(jié)點的節(jié)點稱之為過度節(jié)點。一個過度節(jié)點僅僅能夠包含一層節(jié)點的子節(jié)點。

在進行結構查詢的過程中，首先應該把XML樹轉換為三層子樹。

（二）結構模式匹配

在XML樹轉換成三層子樹后，就可以進行結構模式匹配。結構模式匹配的核心是計算編輯距離。編輯距離是指兩個字符串通過插入、刪除、改寫字符等編輯操作而變?yōu)橄嗤址枰淖钚〔僮鲾担鳷ai最早使用編輯距離計算了兩棵樹（圖）之間的相似度，其基本思想是將兩棵樹間的距離定義為利用編輯操作將一棵樹轉化為另一棵樹所耗費的最小代價。

在“內容十結構”的算法查詢模式（先進行內容查詢再進行結構模式匹配查詢）中，我們應該以內容信息為主，結構信息為輔。所以，在查詢的過程中，結構信息必須與內容信息緊密相關，并且能夠進一步對內容信息進行結構上的限定。也就是說，在進行內容查詢之后，結構模式匹配查詢的關鍵就是合理地計算編輯操作所需要的最小代價。

充分考慮了編輯節(jié)點時的不同代價，，本文定義了三種編輯操作代價的計算模型：（1）更新操作：就是改變一個節(jié)點的標簽，把相關文檔中的某個關鍵詞節(jié)點的標簽更新為用戶查詢中的某個查詢關鍵詞節(jié)點的標簽。（2）刪除操作：把相關文檔中與用戶查詢不相匹配的節(jié)點q刪除。其中，刪除平衡因子（實驗驗證一般取值0.5為最佳），用來調整具體環(huán)境所決定的權重與刪除代價間變換的差異。（3）插入操作：該操作與刪除操作是相反操作。另外，插入平衡因子（實驗驗證一般取值0.5為最佳），用來調整具體環(huán)境所決定的權重與插入代價變換的相似度。

三、算法實現

在實現該算法時，設計了一個系統，該系統包括四個模塊：輸入輸出模塊、轉換模塊，結構查詢模塊，數據庫存儲模塊。

輸入輸出模塊：主要負責XML文檔的輸入、輸出工作；

轉換模塊：輸入的XML文檔樹轉換成為三層子樹，以便為以后的結構查詢做準備。該模塊是過度模塊，是結構查詢模塊的跳板；

結構查詢模塊：經過轉換模塊后進入的第三個模塊，該模塊計算在模式匹配過程中所花費的代價之和；

數據庫存儲模塊：用來存儲XML數據，采用內聯法來將XML映射到關系數據庫中。數據庫模塊主要是關系表的設計。在關系表的設計過程中，主要利用Dewey碼來表示節(jié)點。

四、結束語

本文提出了結構模式匹配查詢算法， 該算法包括兩部分，第一部分是將XML文檔樹轉換成為三層子樹。第二部分是利用各種操作進行結構模式匹配。

首先，本文中提出了三層子樹的概念，在XML文檔樹轉換成為三層子樹的過程中，涉及到了三種形態(tài)的子樹：單叉樹、過度子樹、一般子樹。并且將XML樹的節(jié)點分為兩類：內部節(jié)點和值節(jié)點。值節(jié)點指的是XML樹中的葉子節(jié)點。內部節(jié)點包括三類：一層節(jié)點、二層節(jié)點、過度節(jié)點。

在結構模式匹配中，涉及到了更新操作、刪除操作和插入操作。在更新操作中引入遷移頻度；在刪除操作中引入刪除平衡因子；在插入操作代價中引入插入平衡因子。遷移頻度主要是體現更新時的等價度；刪除平衡因子主要是用來調整具體環(huán)境所決定的權重與刪除代價間變換的差異；插入平衡因子主要是用來調整具體環(huán)境所決定的權重與插入代價變換間的相似度。

參考文獻：

[1]Stefano Ceri et al.XML-GL：A Graphical Language for Querying and Restructuring XML Documents，SEBD，1999：151-165.

[2]孟小峰.XML數據管理[M].北京：清華大學出版社，2009.