基於擴展查詢似然模型的動態後繼樹索引裁剪方法
2023-05-23 15:19:21 1
專利名稱：基於擴展查詢似然模型的動態後繼樹索引裁剪方法
技術領域：
本發明涉及信息檢索與數據壓縮技術領域，具體涉及ー種基於擴展查詢似然模型的動態後繼樹索弓I裁剪方法。
背景技術：
隨著以社交網絡為代表的Web 2. O時代的到來，每時每刻都有大量文本數據被生產出來，對這些海量文本數據或者大數據建立索引必然導致龐大的索引文件。同時，為支持更加豐富而多樣化的查詢檢索功能，存儲在索引文件中的信息類型和數量也較以前有大量的増加，這無疑進ー步加劇了索引文件的膨脹。龐大索引文件不僅佔用大量的磁碟空間，更 使得查詢時訪問索引文件時間開銷過大，磁碟I/o的過於頻繁與緩慢的磁碟訪問速度，已經成為影響效率提升的重大瓶頸之一。此外，新應用場景的出現，如移動終端檢索(searchin mobile devices)、個人電腦桌面搜索(desktop search)、P2P 檢索(Peer to Peersearch)等，對信息檢索系統的各項性能提出了更嚴格的要求，迫使現代信息檢索系統必須重新考慮下列問題哪一部分索引數據應該被存儲於索引文件之中。目前降低索引文件大小的最常見方法是使用數據壓縮技術，數據壓縮技術一般存在兩種類型無損壓縮和有損壓縮。無損壓縮採用高效的數據編碼方式表示記錄在索引結構中的數據信息，比如Delta編碼、Golomb編碼和可變長字節編碼等，壓縮過程中不刪除任何索引信息。有損壓縮則是通過刪除在查詢時被認為是無用的索引信息的方式達到降低索引文件大小的目的。目前，對倒排索引文件無損壓縮方法的研究已經有許多成熟的解決方案，也有ー些對動態後繼樹索引文件進行無損壓縮的相關研究。無損壓縮的優勢在於其安全性高，不會損失任何索引信息。與無損壓縮研究不同，針對索引文件的有損壓縮研究，即索引裁剪技術研究，卻並不是很多。依據目前公開可查詢的國內外文獻來看，索引裁剪技術研究主要針對倒排索引文件進行，國內的相關研究更少，而且沒有針對動態後繼樹索引文件進行索引裁剪的相關研究。在充分利用動態後繼樹索引結構針對中文信息檢索的優越性的同時，必須注意到動態後繼樹索引結構的不足產生的索引文件比較大，膨脹比高。因此針對動態後繼樹索引的特點進行相應的索引裁剪技術研究，從而彌補其索引文件膨脹比高的不足就具有極大理論價值和實踐意義。
發明內容
本發明的目的在於針對現有技術的不足，提供了一種基於擴展查詢似然模型的動態後繼樹索引裁剪方法。為了實現上述目的，本發明採用了以下技術方案一種基於擴展查詢似然模型的動態後繼樹索弓I裁剪方法，以完整的動態後繼樹索弓I作為處理對象，對索引中的樹葉信息進行重要性評估，然後刪除不重要的樹葉信息，形成裁剪後的動態後繼樹索引；
該方法依次包括以下步驟
(I)針對動態後繼樹索引結構，創建完整的動態後繼樹索引；(2)依次遍歷索引中每ー篇文檔包含的不同ニ元詞項，提取索引統計信息；
(3)利用重要性評分公式
卿)+^,計算索引中的
ニ元詞項在其當前出現文檔中的重要性評分，然後對ニ元詞項進行重要性降序排列；其中tf(bi)是ニ元詞項&在文檔中的出現次數，TFm是ニ元詞項&在文檔集C中的出現
次數，I Cl是文檔集e的長度，丨D|為文檔ゴ的長度，.W為平滑因子；該評分公式由一系列的公式推導而形成首先從傳統的查詢似然模型出發，引入高效的狄尼克雷平滑機制對此查詢似然模型進行擴展；然後在資訊理論K-L距離定義的基礎上採用算木平均數的方式定義了對稱K-L距離，從而更加平衡的度量文檔與文檔集之間的差異；最後評估文檔中的ニ元
詞項對文檔對稱K-L距離的貢獻度即;
(4)輸入裁剪參數1<1€1€太€が)、/^^.￡^1)，讓裁剪參數しP依次分別和索引中與
一篇文檔關聯的所有樹葉信息的個數μ/41進行比較、計算，控制動態後繼樹索引的裁剪規模，刪除ー篇文檔中排序靠後的ニ元詞項所對應的樹葉信息Leaf Information (LI);裁剪參數k、P在取值範圍內的實際取值可以根據裁剪數據的實際情況、實際需求輸入，通過不同的取值，可以得到我們需要的不同裁剪效果；
(5)形成並輸出裁剪後的動態後繼樹索引。上述的ニ元詞項由樹根詞項和與樹根詞項直接關聯的樹葉詞項組成的整體，是不可分割。所述的樹根詞項是指在創建動態後繼樹索引時，位於樹根的分詞詞項；而樹葉詞項則是樹根的後繼，指位於樹葉的分詞詞項。上述的索引統計信息包括ニ元詞項在每ー篇文檔中出現的次數、含有某一個ニ元詞項的文檔數目、ニ元詞項在文檔集中總的出現次數、每ー篇文檔的長度(即包含ニ元詞項的個數)和文檔集的總長度(即所有文檔長度之和)、與一篇文檔關聯的所有樹葉信息的個數丨Z/41等，索引統計信息還可包括有其他信息，不限於上述提及的統計信息。所述的步驟(4)輸入裁剪參數!^^，!^!^、^(^/^^，讓裁剪參數匕P分別
和索引中與一篇文檔關聯的所有樹葉信息的個數丨進行比較、計算，控制動態後繼樹索引的裁剪規模，刪除ー篇文檔中排序靠後的ニ元詞項所對應的樹葉信息步驟為
①輸入裁剪參數匕P；
②若丨LlLiI < k,轉步驟⑤；
③若μ/4Ι>λ且μ/41- PWLA >k,則裁剪掉排序靠後的Ρ| 4Ι個樹葉信息；ρ\π[ I表示的是對ρμ/41進行上取整，即當I為小數吋，則對其上取整，如,I的結果為8. 2時，則取整為9 ；
④若
權利要求
1.一種基於擴展查詢似然模型的動態後繼樹索引裁剪方法，其特徵在於該方法依次包括以下步驟 (1)針對動態後繼樹索引結構，創建完整的動態後繼樹索引； (2)依次遍歷索引中每ー篇文檔包含的不同ニ元詞項，提取索引統計信息； (3)利用重要性評分公式
2.根據權利要求I所述的基於擴展查詢似然模型的動態後繼樹索引裁剪方法，其特徵在於所述的ニ元詞項由樹根詞項和與樹根詞項直接關聯的樹葉詞項組成的整體。
3.根據權利要求I所述的基於擴展查詢似然模型的動態後繼樹索引裁剪方法，其特徵在於所述的索引統計信息包括ニ元詞項在每ー篇文檔中出現的次數、含有某一個ニ元詞項的文檔數目、ニ元詞項在文檔集中總的出現次數、每ー篇文檔的長度和文檔集的總長度、與一篇文檔關聯的所有樹葉信息的個數丨LlLi I。
4.根據權利要求I所述的基於擴展查詢似然模型的動態後繼樹索引裁剪方法，其特徵在於所述的步驟(4)輸入裁剪參數，讓裁剪參數k、P分別和索引中與一篇文檔關聯的所有樹葉信息的個數μ/らI進行比較、計算，控制動態後繼樹索引的裁剪規模，刪除ー篇文檔中排序靠後的ニ元詞項所對應的樹葉信息步驟為 ①輸入裁剪參數P； ②若轉步驟⑤； ③若μ/4Ι>*且μ/4Ι- p\LiLd \ >k,則裁剪掉排序靠後的個樹葉信息； ④若丨￡/41>た且|￡馬|- p\LILd\^k,則裁剪掉排序靠後的-k個樹葉信息； ⑤結束。
全文摘要
本發明公開了一種基於擴展查詢似然模型的動態後繼樹索引裁剪方法，該方法依次包括以下步驟(1)針對動態後繼樹索引結構，首先創建完整的動態後繼樹索引；(2)然後依次遍歷索引中每一篇文檔包含的不同二元詞項，提取索引的統計信息；(3)計算這些二元詞項在其當前出現文檔中的相對重要性評分；(4)輸入裁剪參數，從完整動態後繼樹索引中刪除掉一定比例的不重要二元詞項所對應的索引信息；(5)形成裁剪後的動態後繼樹索引。本方法通過合理的去掉動態後繼樹索引中的不重要信息達到降低索引文件大小的目的。
文檔編號G06F17/30GK102841945SQ20121030700
公開日2012年12月26日 申請日期2012年8月27日 優先權日2012年8月27日
發明者霍林, 鄒先澤 申請人:廣西大學