用哈希算法和二分法實現中文詞典的快速查找

摘 要： 分詞詞典是漢語自動分詞系統中的一個基本組成部分，其查詢速度直接影響到分詞系統的處理速度。文章提出并實現了一種用哈希算法和二分查找算法相結合的中文單詞查找算法，實驗顯示，該算法可以實現對字符串的快速查找。

關鍵詞： 詞典； 分詞； 哈希算法； 二分查找算法

中圖分類號：TP391 文獻標志碼：A 文章編號：1006-8228（2014）09-16-02

Fast search in Chinese dictionary by Hash algorithm and binary algorithm

Huo Shandong

（Chongqing Three Gorges University， Wanzhou， Chongqing 404000， China）

Abstract： Dictionary of segmenting words is an essential part of Chinese automatous segmentation system. The speed of word processing systems is directly related to the querying speed. A Chinese word search algorithm based on Hash algorithm and binary search algorithm is proposed. The experiments show that the algorithm can quickly find the character string.

Key words： dictionary； segment； Hash algorithm； binary search algorithm

0 引言

中文分詞是中文信息處理的基礎，要對中文文本進行分詞就很有可能要用到分詞詞典，因此，如何構建分詞詞典以及如何實現對詞典的快速查找是影響中文分詞效率的一個重要因素。

本文通過分析漢字區位碼的特點，將哈希算法和二分查找算法相結合，構建和實現了一個快速查找中文詞典的方法，實驗表明，該算法的查找效率是普通二分查找算法的兩倍。

1 漢字區位碼分布特點

漢字區位碼共收漢字6763個，分成兩級，第一級漢字3755個，置于16區至55區；第二級漢字3008個，置于56區至87區。通過分析可以發現，從位于第16區的第一個漢字啊（1601）到位于第87區最后一個漢字齄（8794），除了在每個區之間缺損6個漢字之外，其他漢字的區位碼都是連續的，這樣，我們就可以設想將每個漢字的區位碼對應于一個數組元素，然后通過數組元素的下標來實現對該漢字的快速查找，這樣其查找時間復雜度就可以縮小到O（1）。第一個漢字的區位碼是1601，與數組的下標不一致，但是我們可以通過構建一個簡單的哈希函數來實現漢字在數組中的定位問題，其哈希函數可以表示為：

其中，x為漢字的區位碼，當x小于或等于0時表示英文字符。由于每個漢字的區位碼（除了在每個區之間有6個缺損之外）是連續且惟一的，所以每個漢字區位碼所對應的哈希函數值也是惟一的，所以該哈希函數不會產生任何沖突現象。

2 漢字內碼到區位碼的轉換

通常情況下，漢字在計算機內部是以“內碼”的形式存放的，每個漢字“內碼”由兩個字節組成，可以通過如下公式實現漢字“內碼”到區位碼的轉換：

qh=c1-160，wh=c2-160

qh為某一個漢字的區碼，wh為某一個漢字的位碼，c1為某一漢字的內碼的高字節，c2為某一漢字的低字節。

例如漢字“啊”內碼的高字節為176，低字節為161，通過計算可以得到該漢字的區位碼為16，位碼為01，為了便于編程實現，可以通過公式c1*100+c2計算得出該漢字的區位碼為1601。由于在進行詞典查找的過程中通常查的是字符串，所以我們可以通過該字符串的第一個字符（漢字）的區位碼得到該字符串在哈希詞典中的位置，其轉換源代碼如下：

其大致方法是：首先判斷該字符串的第一個字符，如果該字符減去160小于0，則可以判斷該字符為英文字符，否則可以判定該字符串的首字符為一個漢字，并返回該漢字的區位碼。

3 詞典的數據結構及其查找算法的實現

由于在進行中文文本分詞的過程中，對字符串的查找是一個非常頻繁的操作，所以在進行中文文本分詞時，通常要將詞典文件一次性調入內存并為其構建相應的數據結構，同時該詞典文件還應常駐內存。為了實現這個目的，本文為詞典文件設置了一個全局容器（vector）數組，該容器數組的每一個元素對應于以某一個漢字開頭的字符串容器，由于詞典中也存在一些以英文字符開頭的外來詞，為了實現上方便，本文將這些詞全部存放在容器數組的第一個元素中。另外，為了實現在每一個容器內部進行二分查找，本文在將詞典文件調入內存以前對詞典文件進行了排序處理。

詞典在內存中的數據結構如圖1所示。

3.1 詞典的構建過程

詞典構建過程示意圖如圖2所示。

3.2 字符串的查找過程

字符串查找過程示意圖如圖3所示。

4 總結

由于只是為了測試詞典的查找效率，本文以簡單的正向最大匹配算法為基礎，以詞典中最長的詞7（漢字）為最長匹配詞條開始進行查找，分別采用常用的二分查找算法和哈希算法與二分查找算法相結合的方法進行了分詞效果比較，本文用到的詞典共收錄了53335個詞條，其結果如表1。

從表1數據可以看出，采用普通的二分查找算法，由于在本文中其詞典采用的是字符串數組的方式進行加載的，而哈希算法和二分法相結合的方法采用的是容器（vector）加動態內存（堆）的方式進行加載的，故其詞典加載時間是普通二分查找算法的兩倍，但其分詞效率卻也是前者的兩倍。由于在進行中文分詞時，詞典都是常駐內存的，故其詞典的加載時間并不影響中文的分詞效率。

參考文獻：

[1] 黃昌寧等.利用漢字二元語法關系解決漢語自動分詞中的交集型歧

義[J].計算機研究與發展，1997.5.

[2] 劉挺，吳巖等.串頻統計和詞形匹配相結合的漢語自動分詞系統[J].

中文信息學報，1997.1.

[3] 孫茂松，鄒嘉彥.漢語自動分詞中的若干理論問題[J].語言文字應用，1995.4.

[4] 孫茂松，左正平.漢語自動分詞詞典機制的實驗研究[J].中文信息學

報，2000.1.

[5] 梁南元.書面漢語自動分詞系統—CDWS[J].中文信息學報，1987.2.