用哈希算法和二分法實(shí)現(xiàn)中文詞典的快速查找

摘 要： 分詞詞典是漢語自動(dòng)分詞系統(tǒng)中的一個(gè)基本組成部分，其查詢速度直接影響到分詞系統(tǒng)的處理速度。文章提出并實(shí)現(xiàn)了一種用哈希算法和二分查找算法相結(jié)合的中文單詞查找算法，實(shí)驗(yàn)顯示，該算法可以實(shí)現(xiàn)對(duì)字符串的快速查找。

關(guān)鍵詞： 詞典； 分詞； 哈希算法； 二分查找算法

中圖分類號(hào)：TP391 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：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 引言

中文分詞是中文信息處理的基礎(chǔ)，要對(duì)中文文本進(jìn)行分詞就很有可能要用到分詞詞典，因此，如何構(gòu)建分詞詞典以及如何實(shí)現(xiàn)對(duì)詞典的快速查找是影響中文分詞效率的一個(gè)重要因素。

本文通過分析漢字區(qū)位碼的特點(diǎn)，將哈希算法和二分查找算法相結(jié)合，構(gòu)建和實(shí)現(xiàn)了一個(gè)快速查找中文詞典的方法，實(shí)驗(yàn)表明，該算法的查找效率是普通二分查找算法的兩倍。

1 漢字區(qū)位碼分布特點(diǎn)

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

其中，x為漢字的區(qū)位碼，當(dāng)x小于或等于0時(shí)表示英文字符。由于每個(gè)漢字的區(qū)位碼（除了在每個(gè)區(qū)之間有6個(gè)缺損之外）是連續(xù)且惟一的，所以每個(gè)漢字區(qū)位碼所對(duì)應(yīng)的哈希函數(shù)值也是惟一的，所以該哈希函數(shù)不會(huì)產(chǎn)生任何沖突現(xiàn)象。

2 漢字內(nèi)碼到區(qū)位碼的轉(zhuǎn)換

通常情況下，漢字在計(jì)算機(jī)內(nèi)部是以“內(nèi)碼”的形式存放的，每個(gè)漢字“內(nèi)碼”由兩個(gè)字節(jié)組成，可以通過如下公式實(shí)現(xiàn)漢字“內(nèi)碼”到區(qū)位碼的轉(zhuǎn)換：

qh=c1-160，wh=c2-160

qh為某一個(gè)漢字的區(qū)碼，wh為某一個(gè)漢字的位碼，c1為某一漢字的內(nèi)碼的高字節(jié)，c2為某一漢字的低字節(jié)。

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

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

3 詞典的數(shù)據(jù)結(jié)構(gòu)及其查找算法的實(shí)現(xiàn)

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

詞典在內(nèi)存中的數(shù)據(jù)結(jié)構(gòu)如圖1所示。

3.1 詞典的構(gòu)建過程

詞典構(gòu)建過程示意圖如圖2所示。

3.2 字符串的查找過程

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

4 總結(jié)

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

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

參考文獻(xiàn)：

[1] 黃昌寧等.利用漢字二元語法關(guān)系解決漢語自動(dòng)分詞中的交集型歧

義[J].計(jì)算機(jī)研究與發(fā)展，1997.5.

[2] 劉挺，吳巖等.串頻統(tǒng)計(jì)和詞形匹配相結(jié)合的漢語自動(dòng)分詞系統(tǒng)[J].

中文信息學(xué)報(bào)，1997.1.

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

[4] 孫茂松，左正平.漢語自動(dòng)分詞詞典機(jī)制的實(shí)驗(yàn)研究[J].中文信息學(xué)

報(bào)，2000.1.

[5] 梁南元.書面漢語自動(dòng)分詞系統(tǒng)—CDWS[J].中文信息學(xué)報(bào)，1987.2.