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

有效

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

技術領域

本發明涉及計算機搜索引擎技術，尤其是一種基于廣義后綴樹的中文搜索引擎模糊自動補全方法。

背景技術

近年來，搜索引擎因其能夠在幾乎無限的資源中為廣大用戶找到所需的信息而越來越受到重視。優秀的搜索引擎也不斷涌現，如：Google，Baidu等。在搜索引擎系統中，自動補全是一項非常有用的技術。當用戶在搜索框輸入字符串的前綴時，自動補全接口能夠立刻返回與該前綴匹配的候選詞集合。比如Google?Suggest能夠為用戶提供查詢補全，Facebook能夠為用戶提供好友查詢補全。但是主流搜索引擎如Google，Baidu所提供的是精確自動補全，當用戶鍵入的字符串沒有錯誤時，這種方法工作良好，如果用戶在鍵入字符串時發生錯誤，精確自動補全便不能為用戶提供候選詞。針對上述不足，微軟已經提出了一種基于字典的后綴樹（Suffix?tree）模糊自動補全方法，能夠處理英文語境下單詞的模糊匹配，當用戶在鍵入字符串時發生了小錯誤，用戶期望的字符串仍能被自動補全。所述后綴樹的概念最早由Weiner?于1973年提出，既而由McCreight?在1976年和Ukkonen在1992年和1995年加以改進完善，其實質是一種數據結構，能用來支持有效的字符串匹配和查詢，快速解決很多關于字符串的問題。

然而，微軟的基于字典的后綴樹模糊自動補全方法，卻不支持中文。英文以詞為單位，一個詞表示一種意思，模糊自動補全就是搜索與前綴匹配的候選字母，依據字典使其湊成數個可選的單詞；中文與英文大不相同，中文以字為單位，單獨的一個字，就至少包含一個確定的含義。

發明內容

本發明的目的在于：提供一種基于廣義后綴樹的中文搜索引擎模糊自動補全方法，能夠增強中文自動補全的功能和適用性。

為實現上述目的，本發明可采取下述技術方案：

本發明一種基于廣義后綴樹的中文搜索引擎模糊自動補全方法，包括以下步驟：

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

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

步驟二：計算字的相似度

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

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

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

步驟四：模糊自動補全

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

權利要求1的步驟二中所述的音形相似度，是根據字的發音混淆程度計算得到的數據，如果兩個字發音完全相同，設定其相似度數值為a1?；如果兩個字發音只有聲調不同，設定其相似度數值為a2?；如果兩個字屬于易混淆詞表中的字，設定其相似度數為a3?；所述a1、a2和a3滿足下列條件：a1小于1，且a1>a2>a3>0。

設定所述a1=0.9；設定所述a2=0.8；設定所述a3=0.7。

權利要求1的步驟二中計算所述字形相似度的步驟包括：

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

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

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

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

權利要求1的步驟二中計算所述字形相似度的步驟包括：

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

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

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

。

權利要求1步驟一中所述廣義后綴樹的實現方法為：對于一個詞庫，通過使用Ukkonen算法來構造廣義后綴樹，假設詞庫中詞的平均長度為m，則構造算法的時間復雜度為。

權利要求1步驟二中，使用Mathematica來計算字形的相似度，把GBK中的中文字全部轉化成數字，定量的計算每個字兩兩之間的矩陣的相似度。