求解最小子樹根節點的新型算法

摘 要：求解最小子樹根節點的新型算法，利用Dewey碼有重構XML文檔的功能，首先為XML文檔樹設計Dewey碼，然后查找關鍵詞對應的Dewey碼前綴，根據Dewey碼前綴計算對應的先序編碼，再逐層（從MinMax（D1，D2……Dn）開始）進行求交集的運算，最后求得的先序編碼交集即為最小子樹根節點集合，進而根據最小子樹根節點得出對應的最緊致片段。

關鍵詞：Dewey碼；先序編碼；交集；最小子樹根節點

中圖分類號：TP311 文獻標識碼：A 文章編號：1674-7712 （2014） 02-0000-01

一、引言

在求解最小子樹根節點的新型算法中，主要涉及到的算法有三類，第一類是基于索引的搜索算法，第二類是基于堆棧的算法，最后一類是基于掃描的算法。

第一類算法主要是利用dewey碼進行操作，并且在進行操作的過程中是通過修改B+樹結構來實現的。第二類算法在存儲的過程中利用的存儲結構是棧，不再利用B+樹，相對來說這類算法比第一類算法操作簡單。但是，該算法時間的復雜度和空間的復雜度方面相對第一類算法差。第三類算法在時間復雜度和空間復雜度方面都不是很理想。

根據上述這種情況，本文設計了求解最小子樹根節點的新型算法。該算法不僅僅能夠保證查全率，并且在查準率方面也有所提高。

二、算法設計

最小子樹根節點定義：對應XML數據的標簽有向樹G=（V（g），E（g），R，A），其中：V（g）表示樹中節點的集合；E（g）表示樹中所有邊的集合；R為標簽有向樹的根；A表示所有節點標簽的集合。另外，關鍵詞序列設為k，則k={k1，k2，…，ki}。那么，最小子樹根節點問題就是求解G中所有滿足如下條件子樹的根節點：（1）子樹必須包含關鍵詞序列k，即k中的任一關鍵詞必然分布于該子樹的葉節點；（2）子樹中不存在更小的子樹同樣包含k。

最小子樹根節點有如下兩個特點：（1）如果某節點屬于最小子樹根節點，那么它必然唯一地從屬于某一“層”；（2）根據最小子樹根節點定義，如果m個分別包含給定m個關鍵詞的葉節點在第i層有最小子樹根節點，那么它們不可能都成為第（i+1）層的最小子樹根節點所在子樹的葉節點。

根據上述定義和特點，從最大層MinMax（D1，D2……Dn）-1開始，首先應該獲得Di中所對應層次中的Dewey前綴碼，然后把獲得的Dewey前綴碼整數化成Dewey的先序編碼。先序編碼如下：D1’，D2’，……Dn’，根據Dewey先序編碼最終求得Di’集合的交集。交集出現兩種情況，第一種情況，交集是非空集時，非空集合當中的所有元素就是求得的第一批最小子樹根節點；第二種情況，交集為空時，則說明在該層上沒有出現對應于關鍵詞的最小子樹根節點。最后，當到達了第二層或者是D1’，D2’，……Dn’為空時，此時循環結束，計算終止。

三、實驗

查詢效率通常是用查準率（Precision）和查全率（Recall）的高低作為其標準。查準率表示查詢的有關文檔篇數在查出的文檔總數中所占的比例。查全率是查出的有關文檔篇數在信息庫中有關文檔總數中所占的比例。一般情況下，沒有任何一個檢索工具能夠查詢出所有的信息，所以查全率不容易比較。因此，在評價查詢性能時，主要是看查準率，而查準率不可能達到100%。在下表中涉及的是十組數據的查詢內容，如表1：

四、結束語

本文對提出的求解最小子樹根節點的新型算法進行了實驗，通過實驗驗證，該算法無論是從查準率，還是從查全率方面都有一定程度地提高與改進。

參考文獻：

[1]孔令波，唐世渭，楊冬青.XML數據的查詢技術[J].軟件學報，2007（06）：1400-1418.

[2]宗傳霞.基于父節點的XML查詢優化算法[J].電子測試，2012（15）：63-65.

[3]孔令磊等.面向XML文檔的關鍵字查詢的研究[D].北京：北京交通大學，2008（06）.

[4]孫登峰，玉曉峰.XML查詢語言處理[J].計算機工程，2003（13）：4-7.

[5]G.Gou，R.Chirkova.Efciently Querying LargeXml Data Repositories：ASurvey.IEEE Trans.Knowl.Data Eng，2007（10）：1381–1403.

[作者簡介]宗傳霞（1985-），女，山東章丘人，煙臺南山學院，軟件設計師；郝鑫弟（1984-），男，山東龍口人，煙臺南山學院。