一種中文詞庫的構造方法
2023-09-17 06:48:15
專利名稱：一種中文詞庫的構造方法
技術領域：
本發明涉及中文信息處理領域的中文詞庫存儲和操作處理技術，具體來講，涉及中文信息處理系統中的詞庫構造方法。
背景技術：
詞庫處理的效率是影響中文信息處理系統性能的關鍵因素。在國內對詞庫存儲的研究已經有很長一段時間了，傳統的詞庫存儲與操作算法一般都是使用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
、PrefixIndex
[1]、PrefixIndex
[2]......、PrefixIndex[72][94]。
將漢字所在的區號與位號組合在一起就構成了該漢字的外碼——「區位碼」，它用高低兩個字節來表示，高字節表示漢字所在的區號，低字節表示漢字所在的位號。漢字的區位碼是唯一的。GB碼與區位碼之間存在如下關係，假設一個漢字的GB碼高位節為HighGB，低位節為LowGB，則此關係可表示為 HighGB＝區碼+20H LowGB＝位碼+20H 將漢字的GB碼高位節HighGB、低位節LowGB分別作為二維數組PrefixIndex的行列索引值，第一行的索引值為HighGB＝B0，LowGB＝A1-FE。按照這種方式建立一個數組，該數組的索引值依據漢字編碼確定。
二維數組PrefixIndex數組元素值指向以高位節為HighGB、低位節為LowGB的漢字為首字的哈希表。在本實施例中，二維數組PrefixIndex數組元素值為哈希表的存放地址。這樣依據高位節HighGB、低位節LowGB作為索引值，在二維數組PrefixIndex的指向下，直接找到要查找詞條首字開始的一行詞條，相同首字的詞條構成一個哈希詞表，記為SufHashWords表。
每張SufHashWords表中包含著相同首字開始的一行詞條，在本實施例中，將所有以該字為首字的詞條去掉首字後的後綴作為對象存儲到SufHashWords表中。
圖2是圖1所示詞庫中的詞條在內存中的一種數據結構圖。SufHashWords表中的詞條，即哈希詞表中的一條記錄，記為WordItem，包括除去首字的詞條後綴名稱SuffixName、哈希地址HashAddress、詞條屬性Att。詞條屬性Att是指其詞性，即名詞、動詞等，當然可以根據不同的應用需要，對詞條屬性Att進行定義。
圖3是圖1所示詞庫中的詞條在內存中的另一種數據結構圖。SufHashWords表中的詞條WordItem結構，除包括詞條後綴名稱SuffixName、哈希地址HashAddress、詞條屬性Att外，還包括用於解決哈希衝突的序列號Seq。
在本實施例中，設計了一個極小衝突的哈希函數，使用該函數定位一個詞條在哈希詞表中的位置，以滿足對該詞條的各種操作。
在具體哈希函數設計時，將詞庫中的一個詞條去掉首字後的n個字，使用gb[i]
和gb[i][1]來表示第i個字的GB碼的高位和低位，該詞條的哈希函數為 依據該函數計算出函數Hash的值即為圖2以及圖3的詞條WordItem在SufHashWords表中的哈希地址HashAddress。這樣依據詞條首字的高位節HighGB、低位節LowGB對應數組PrefixIndex的索引值，通過索引值在數組PrefixIndex中找到詞條首字相應的哈希表的首地址，然後通過該哈希表的首地址，找到該詞條首字對應的哈希詞表SufHashWords；再依據上述函數Hash確定該詞條在SufHashWords表中的位置。
此外，在另一具體實施方式
中，為解決衝突，將上述函數Hash計算得到的值加上一個序列號，即當發生衝突時，就將序列號加1，此時哈希函數為 Seq是在發生衝突時，解決衝突時的序列號。
圖4是圖1所示詞庫中的詞條在磁碟上的物理存儲結構圖。在本實施例中，詞庫在磁碟上的存儲使用漢字GB碼，將首字相同的詞條放到文本的同一行中，其數據結構包括首字FirstWord、詞條數量Number、是否能單獨成詞標記Flag以及各個詞條WordItem1～WordItemm，各個詞條WordItem1～WordItemm之間用特殊符號「#」隔離。
根據哈希函數的不同，存儲詞條的結構有所不同，一種是根據哈希函數存儲的，其中一個例子為 傲3F#慢194253 ADJ#氣198248 ADJ#骨185199 N 其中「傲」為首字，「3」表示有三個詞條，「F」表示不能單獨成詞，「194253」表示根據「慢」字的GB碼，由函數計算出的值，「ADJ」表示詞性，每個詞條之間以「#」號相隔。
另一種是根據哈希函數存儲的，其中一個例子為 傲3F#慢194253 0 ADJ#氣198248 0 ADJ#骨185199 0 N 其中，「0」表示序列號為0，表示該詞條計算出的哈希值沒有出現衝突。
儘管上面對本發明說明性的具體實施方式
進行了描述，。以便於本技術領域的技術人員理解本發明，但應當清楚，本發明不限於具體實施方式
的範圍，對本技術領域的普通技術人員來講，只要各種變化在所附的權利要求限定和確定的本發明的精神和範圍內，這些變化是顯而易見的，一切利用本發明構思的發明創造均在保護之列。
權利要求
1.一種中文詞庫的構造方法，其特徵在於，包括以下步驟
(1)、將首字相同的詞條放到一張哈希表中，相同首字的詞條在哈希表中的位置由哈希函數根據構成詞條的漢字編碼計算出的哈希值確定；
(2)、建立一個數組，該數組的索引值依據詞條首字的漢字編碼確定，數組元素值指向與索引值相對應的詞條首字的哈希表；
(3)、依據詞條首字的漢字編碼，確定數組索引值，在數組中找到相應的數組元素，找到該詞條首字的哈希表，再根據構成詞條的漢字編碼，用哈希函數計算出的哈希值，確定該詞條在哈希表中的位置；
(4)根據詞條的位置來對詞條進行操作。
2.根據權利要求1所述的中文詞庫的構造方法，其特徵在於，所述的相同首字的詞條在哈希表中的位置由哈希函數根據去掉首字後的構成詞條的漢字編碼計算出的哈希值確定。
3.根據權利要求2所述的中文詞庫的構造方法，其特徵在於，所述的哈希函數為
其中，n表示詞條去掉首字後的字數，gb[i]
和gb[i][1]分別表示第i個漢字的GB碼的高位值和低位值。
4.根據權利要求2所述的中文詞庫的構造方法，其特徵在於，所述的哈希函數為
其中，n表示詞條去掉首字後的字數，gb[i]
和gb[i][1]來表示第i個字的GB碼的高位和低位，Seq為解決衝突時的序列號。
5.根據權利要求1所述的中文詞庫的構造方法，其特徵在於，所述的數組為二維數組，詞條首字GB碼的高位和低位作為該二維數組的索引值。
6.根據權利要求1所述的中文詞庫的構造方法，其特徵在於，所述的中文詞庫在磁碟上的存儲使用漢字GB碼，將首字相同的詞條放到文本的同一行中，其數據結構包括首字、詞條數量、是否能單獨成詞標記以及各個詞條，各個詞條之間用特殊符號隔離。
7.根據權利要求1所述的中文詞庫的構造方法，其特徵在於，所述的數組元素值為存儲哈希表的首地址。
全文摘要
本發明公開了一種中文詞庫的構造方法，包括根據詞條首字構造二維數組，數組索引值是根據詞條首字的漢字編碼確定，數組元素值指向與索引值相對應的漢字為首字的哈希表；該哈希表用於存儲首字相同的詞條除去首字後的後綴信息，根據詞條後綴漢字編碼，由哈希函數計算的哈希值確定詞條在哈希表中的位置。查找詞條的主要過程為根據詞條首字的漢字編碼，確定數組索引值，在數組中找到相應的數組元素，確定該詞條首字對應的哈希表，再根據詞條後綴的漢字編碼用哈希函數計算哈希值，確定該詞條在哈希表中的位置。由於數組和哈希表相結合的詞庫構造方法，哈希表和詞條都可以根據構成詞條的漢字編碼直接找到，因此操作的效率大大提高。
文檔編號G06F17/30GK101158955SQ20071005051
公開日2008年4月9日 申請日期2007年11月15日 優先權日2007年11月15日
發明者彥 傅, 尚明生, 陳安龍, 王全禮, 偉 史 申請人:電子科技大學