[發明專利]一種中文詞庫的構造方法

無效

• 申請號: 200710050516.7
• 申請日: 2007-11-15
• 公開（公告）號: CN101158955A
• 公開（公告）日: 2008-04-09
• 發明（設計）人: 傅彥;尚明生;陳安龍;王全禮;史偉
• 申請（專利權）人: 電子科技大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 成都九鼎天元知識產權代理有限公司
• 代理人: 溫利平

技術領域

本發明涉及中文信息處理領域的中文詞庫存儲和操作處理技術，具體來講，涉及中文信息處理系統中的詞庫構造方法。

背景技術

詞庫處理的效率是影響中文信息處理系統性能的關鍵因素。在國內對詞庫存儲的研究已經有很長一段時間了，傳統的詞庫存儲與操作算法一般都是使用AVL樹或2-3樹等樹型結構來實現的。AVL樹稱為自平衡二叉查找樹，任何節點的兩個子樹的高度差最大為一，查找、插入和刪除可能需要通過一次或多次樹旋轉來重新平衡這個樹，在旋轉成葉子節點期間最多有logn個節點被旋轉，在平均和最壞情況下的時間復雜度為O(logn)。2-3樹即為三階B-樹，B-樹是一種平衡的多路查找樹，所有的數據都存放在葉子節點，而在葉子節點上存放的數據量是有限的，B-樹的插入與刪除必須滿足插入或刪除以后的樹，依然滿足B-樹的特性，并且此過程有時比較復雜；在n個元素的2-3樹中插入或刪除元素需要O(logn)的時間復雜度。在中文分詞系統中使用的二分查找算法，由于二分查找只適合有序的線性數組，其查找時間復雜度為O(log?n)，并且靈活性也受到限制，操作效率較低。

發明內容

本發明的目的在于克服上述現有技術中的不足，提供一種操作效率高的中文詞庫的構造方法。

為實現上述發明目的，本發明的中文詞庫的構造方法，其特征在于，包括以下步驟：

(1)、將首字相同的詞條放到一張哈希表中，相同首字的詞條在哈希表中的位置由哈希函數根據構成詞條的漢字編碼計算出的哈希值確定；

(2)、建立一個數組，該數組的索引值依據詞條首字的漢字編碼確定，數組元素值指向與索引值相對應的詞條首字的哈希表；

(3)、依據詞條首字的漢字編碼，確定數組索引值，在數組中找到相應的數組元素，找到該詞條首字的哈希表，再根據構成詞條的漢字編碼，用哈希函數計算出的哈希值，確定該詞條在哈希表中的位置；

(4)根據詞條的位置來對詞條進行操作。

在上述步驟中，對詞條的操作包括查找、刪除以及更新等。

本發明提出了一種以漢字編碼為基礎的中文詞庫構造技術，由于采用數組和哈希表相結合的中文詞庫的構造方法，可以依據詞條首字編碼直接在數組中找到該詞條首字對應的哈希表，再根據構成詞條的漢字編碼，用哈希函數計算出的哈希值，直接確定該詞條在哈希表中的位置，哈希表查找效率為O(1)，與查找時間復雜度分別近似為O(logn)的AVL樹查找算法、2-3樹查找算法以及二分查找算法相比，操作效率得到了提高。

附圖說明

圖1是本發明的詞庫在內存中的一種數據結構圖；

圖2是圖1所示詞庫中的詞條在內存中的一種數據結構圖；

圖3是圖1所示詞庫中的詞條在內存中的另一種數據結構圖；

圖4是圖1所示詞庫中的詞條在磁盤上的物理存儲結構圖；

具體實施方式

下面結合附圖，對本發明優選具體實施方式進行描述。需要提醒注意的是，在以下的描述中，當采用的已知功能和設計的詳細描述也許會淡化本發明的主題內容時，這些描述在這兒將被忽略。

圖1是本發明一種具體實施方式的詞庫在內存中的數據結構圖。在本實施例中，提取詞條首字的GB碼，將詞條首字GB碼的高位和低位作為二維數組PrefixIndex的索引值，即二維數組的下標，二維數組PrefixIndex存放不同哈希表的首地址。

具體來講，本實施例的詞庫是根據漢字GB碼的特點建立的，GB2312(1980年)一共收錄了7445個字符，包括6763個漢字和682個其它符號。漢字區的內碼范圍高字節從B0-F7，低字節從A1-FE，占用72*94＝6768個碼位，其中有5個空位是D7FA-D7FE。依據此特點，本實施例的二維數組有72*94個數組元素，即PrefixIndex[0][0]、PrefixIndex[0][1]、PrefixIndex[0][2]......、PrefixIndex[72][94]。

將漢字所在的區號與位號組合在一起就構成了該漢字的外碼——“區位碼”，它用高低兩個字節來表示，高字節表示漢字所在的區號，低字節表示漢字所在的位號。漢字的區位碼是唯一的。GB碼與區位碼之間存在如下關系，假設一個漢字的GB碼高位節為HighGB，低位節為LowGB，則此關系可表示為：

HighGB＝區碼+20H

LowGB＝位碼+20H