[發明專利]一種用于信息檢索的任意大小n-gram頻率統計方法及其裝置

無效

• 申請號: 200910044547.0
• 申請日: 2009-10-16
• 公開（公告）號: CN102043775A
• 公開（公告）日: 2011-05-04
• 發明（設計）人: 張偉;孫星明;孫德才
• 申請（專利權）人: 湖南大學;張偉;孫星明;孫德才
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術領域

本發明一般地涉及信息檢索中的n-gram頻率統計技術，尤其設計出一種在給定文本和字符串中任意長度n-gram出現頻率的快速統計方法和裝置。

技術背景

N-gram是信息檢索中常用的一種語言模型。它通過對長度為n的連續字串進行計算來完成檢索過程。計算過程中，連續字串在語言現象中的出現頻率至關重要。在n-gram中，1-gram、2-gram、3-gram被應用得最多。究其原因，是因為它們消耗的計算機資源在可被接受的范圍之內。通常，對于n-gram的計算都是基于索引的。就中文而言，GB2312-80字符集中包含了漢語中常用漢字6763個，則為了保證查找效率，1-gram的索引入口數量為6763，2-gram的索引入口數量為6763²＝45738169，3-gram使用的索引入口數量多達6763³≈288giga。依照這種規律以幾何級數遞增下去，更大的n值消耗的計算機資源是驚人的。因此任意大小的n-gram很少被應用。然而，在通過n-gram模型對語言文字進行處理時，n越大，供語言模型參考的上下文就越多，其優勢是越明顯，在某些應用環境下，必須對大n-gram進行統計計算。

現有的解決該問題的方法包括兩類：對索引進行壓縮；對一定范圍內的n值進行處理。

在真實的語言現象中，很多字符之間不存在搭配關系。在構建索引時，如果考慮到所有理論上的可能性，隨著n增大，數據稀疏的情況越來越嚴重，系統資源浪費驚人。對索引進行壓縮就是基于這樣一種思路，即去除掉那些不可能出現的字符搭配情況，盡可能消除數據稀疏的現象。

這種方法的缺點在于：

1、這種方法雖然在一定程度上對n值增大后的索引空間增速有所改善，但這種改善是有限的，不能對任意大小的n值進行處理。同時，壓縮和解壓縮的過程也會降低系統效率。

2、所有語言文字處理的本質都是對文字符號編碼的處理。在構建索引時，編碼的連續性對于檢索效率有非常大的影響，而索引壓縮破壞了這種連續性。因此，檢索效率不高。

對一定范圍內的n值進行處理，具有代表性的方法是Suffix?Array。該方法通過如下步驟對n-gram進行統計：

1、將整個文本視為一個字符串，以每個字符作為起點，以文本結束位置作為終點，提取子串；

2、對所子串進行排序；

3、統計排序后相鄰子串之間的最長相同前綴長度，并記錄下來；

4、通過比較n值和所記錄的最長前綴的長度，若前綴長度大于n，則對應的n-gram頻率加1，如此進行下去，直到得出最終的統計值。

該方法的局限性在于：

1、對文本進行預處理時，需要進行排序操作。若語料庫規模大，則排序時間較長。若對語料庫進行擴充，則需要重新排序；

2、它可以處理比較大的n值，但無法處理任意大小的n值。n值由保存相鄰子串最長相同前綴的單元大小決定，例如當保存共同前綴長度的單元為1字節，則它能統計的n-gram最大為2⁸-1＝255。

發明內容

有鑒于此，本發明實施例提供了一種能對任意大小n-gram進行頻率統計的方法，克服了現有n-gram頻率統計方法的時間復雜度高，不能對任意n值進行統計的缺陷。

本發明實施例是通過以下技術方案實現的：

文本預處理；

構建變長二級變長索引，保存和檢索給定文本和字符串中的2-gram位置值；

基于2-gram的任意n-gram頻率統計。

本發明實施例還提供一種任意大小n-gram頻率統計裝置，包括：文本預處理模塊，索引生成模塊，頻率計算模塊。其中：

文本預處理模塊，切分給定的文本和字符串，得到2-gram，將2-gram中的漢字(GB2312-80)映射到從0開始的連續整數空間；

索引生成模塊，將得到的2-gram位置值信息存儲到變長二級變長索引中；

頻率計算模塊，根據不同的n值，對n-gram進行2-gram切分。從索引中檢索相關2-gram位置值列表，通過并集或交集運算得到其位置值列表，從而得到其使用頻率。

由上述本發明例的具體技術實施方案可以看出，本發明實施例對n-gram的統計都是建立在2-gram索引基礎之上的。在變長二級變長索引中保存給定文本和字符串中所有出現過的2-gram的入口，消除了很大一部分數據稀疏的情況，節省了存儲空間。同時，相鄰索引入口對應的漢字編碼的連續性得到了保證，可以實現對2-gram的高效檢索。