[發明專利]基于廣義后綴樹的中文搜索引擎模糊自動補全方法

有效

• 申請號: 201110003711.0
• 申請日: 2011-01-10
• 公開（公告）號: CN102063508A
• 公開（公告）日: 2011-05-18
• 發明（設計）人: 吳朝暉;馮葉磊;姜曉紅
• 申請（專利權）人: 浙江大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 杭州裕陽專利事務所(普通合伙) 33221
• 代理人: 冉國政

1.一種基于廣義后綴樹的中文搜索引擎模糊自動補全方法，其特征在于包括以下步驟：

步驟一：建立詞的廣義后綴樹索引

利用現有的建立后綴樹的方法，對中文詞庫中的所有詞建立廣義后綴樹索引；

步驟二：計算字的相似度

對于GBK編碼中的每個中文字進行預處理，計算每個字兩兩之間的音形相似度????????????????????????????????????????????????，將計算結果以數組的形式存儲于音形相似度數據庫中；計算每個字兩兩之間的字形相似度，將計算結果以數組的形式存儲于字形相似度數據庫中；

步驟三：計算相似度接近的詞的權重值

依據用戶輸入的中文字符串，在步驟二所述的音形相似度數據庫和/或字形相似度數據庫中查找相似度接近的詞，計算這些相似度接近的詞的權重值；

步驟四：模糊自動補全

依據步驟三計算出的權重值，得到最終排序過的多個自動補全候選詞。

2.根據權利要求1所述的基于廣義后綴樹的中文搜索引擎模糊自動補全方法，其特征在于：權利要求1的步驟二中所述的音形相似度，是根據字的發音混淆程度計算得到的數據，如果兩個字發音完全相同，設定其相似度數值為a1?；如果兩個字發音只有聲調不同，設定其相似度數值為a2?；如果兩個字屬于易混淆詞表中的字，設定其相似度數為a3?；所述a1、a2和a3滿足下列條件：a1小于1，且a1>a2>a3>0。

3.根據權利要求2所述的基于廣義后綴樹的中文搜索引擎模糊自動補全方法，其特征在于：設定所述a1=0.9；設定所述a2=0.8；設定所述a3=0.7。

4.根據權利要求1所述的基于廣義后綴樹的中文搜索引擎模糊自動補全方法，其特征在于：權利要求1的步驟二中計算所述字形相似度的步驟包括：

步驟一：把每個字分別轉化成圖形；

步驟二：把每個字的所述圖形轉化成像素的矩陣；

步驟三：計算每個字兩兩之間的字形相似度

其中，代表字，代表字的相似度，n為字轉化為圖形的像素矩陣維數，為字像素矩陣第p行第q列的取值。

5.根據權利要求3所述的基于廣義后綴樹的中文搜索引擎模糊自動補全方法，其特征在于：權利要求1的步驟二中計算所述字形相似度的步驟包括：

步驟一：把每個字分別轉化成圖形；

步驟二：把每個字的所述圖形轉化成像素的矩陣；

步驟三：計算每個字兩兩之間的字形相似度

。

6.根據權利要求1至5所述的任一種基于廣義后綴樹的中文搜索引擎模糊自動補全方法，其特征在于：權利要求1步驟一中所述廣義后綴樹的實現方法為：對于一個詞庫，通過使用Ukkonen算法來構造廣義后綴樹，假設詞庫中詞的平均長度為m，則構造算法的時間復雜度為。

7.根據權利要求1至5所述的任一種基于廣義后綴樹的中文搜索引擎模糊自動補全方法，其特征在于：權利要求1步驟二中，使用Mathematica來計算字形的相似度，把GBK中的中文字全部轉化成數字，定量的計算每個字兩兩之間的矩陣的相似度。

8.根據權利要求1至5所述的任一種基于廣義后綴樹的中文搜索引擎模糊自動補全方法，其特征在于：權利要求1步驟三采用基于有權重的編輯距離來計算所述廣義后綴樹中候選詞與用戶輸入的中文字符串之間的相似度，保留傳統編輯距離計算方法中插入和刪除操作權值為1，改變替換操作的權值為1-?。

9.根據權利要求1至5所述的任一種基于廣義后綴樹的中文搜索引擎模糊自動補全方法，其特征在于：權利要求1步驟四中查找自動補全候選詞采用動態規劃算法，其步驟為：

步驟一：維護一個包含節點和權重編輯距離的優先隊列，加入所述廣義后綴樹根節點；

步驟二：按序讀取用戶輸入的中文字符串的單個字符c；

步驟三：從優先隊列中讀取一個節點，等于節點的編輯距離，對于節點的所有兒子節點，如果中的字符和c不同，把()加入優先隊列；如果中的字符和c相同，把（）加入優先隊列，然后對于與相距的每個后代節點，其中為容錯閾值，把（）加入優先隊列；

步驟四：重復步上述驟三，直到舊優先隊列中元素讀取完；

步驟五：重復上述步驟二，直到讀取完輸入的字符串。

10.根據權利要求9所述的基于廣義后綴樹的中文搜索引擎模糊自動補全方法，其特征在于：權利要求1步驟四中，綜合考慮依據用戶輸入的中文字符串與候選詞的相似度和基于候選詞本身熱度而形成的權值，采用的排序函數為，，其中代表字符串q與候選詞w的關聯打分函數，和為權值調節因子，為q和w的編輯距離，為候選詞w的熱度權值。