哈希表在計(jì)算語(yǔ)言學(xué)中的運(yùn)用

高文利　朱　麗

摘 要：在漢語(yǔ)詞典查詢算法中，哈希表知道搜索捷徑，然而數(shù)組只知道正式的路線，因而與標(biāo)準(zhǔn)的二分檢索相比，哈希表的搜索速度比數(shù)組快多了。在算法中，如果能恰當(dāng)?shù)厥褂霉１恚蜁?huì)極大地提高效率。

關(guān)鍵詞：哈希表 數(shù)組 二分檢索 語(yǔ)言統(tǒng)計(jì)

一、問(wèn)題的由來(lái)

在漢語(yǔ)信息處理的整個(gè)過(guò)程中需要頻繁地訪問(wèn)詞典以獲得漢語(yǔ)詞語(yǔ)知識(shí)，漢語(yǔ)詞典的快速查詢是整個(gè)處理系統(tǒng)效率的關(guān)鍵所在。針對(duì)詞典查詢方法，前人做了大量工作，并形成了許多漢語(yǔ)詞典組織結(jié)構(gòu)和相應(yīng)的查詢算法，主要有：傳統(tǒng)Hash方法；三種典型的詞典查詢方法：整詞二分法、TRIE索引樹法、逐字二分法；基于雙字哈希機(jī)制的詞典查詢方法；四字哈希機(jī)制查詢方法；基于Patricia Tree的漢語(yǔ)詞典查詢機(jī)制；兩種漢語(yǔ)詞典快速查詢算法：雙數(shù)組Trie、雙編碼。

基于Trie索引樹的詞典查詢機(jī)制，采用了由短詞及長(zhǎng)詞的確定性工作方式，避免了整詞二分查詢機(jī)制中不必要的多次試探性查詢，能極大地提高分詞系統(tǒng)的速度。在上述這些查詢算法中，雙數(shù)組Trie（Double-Array Trie）是性能最好的一種查詢算法。但它的缺點(diǎn)是構(gòu)造過(guò)程復(fù)雜。由于構(gòu)詞狀態(tài)表的每個(gè)狀態(tài)都依賴于其他狀態(tài)，所以，在詞典中每插入或刪除一個(gè)詞語(yǔ)時(shí)，都需要重新構(gòu)建整個(gè)構(gòu)詞狀態(tài)表，因而這種算法更適用于實(shí)時(shí)性要求較高的封閉式詞典。

在語(yǔ)言研究中，經(jīng)常會(huì)碰到這樣的字符或詞語(yǔ)的統(tǒng)計(jì)問(wèn)題，如《集韻》共使用了多少韻字，《現(xiàn)代漢語(yǔ)詞典》共使用了多少詞形以及字頻統(tǒng)計(jì)等。這實(shí)際是處理中實(shí)時(shí)動(dòng)態(tài)詞典的查詢問(wèn)題。因?yàn)槭菍?shí)時(shí)動(dòng)態(tài)詞典，無(wú)法對(duì)其事先建立索引，無(wú)法運(yùn)用效率極高的Trie索引樹的詞典查詢機(jī)制，因而只能另想它策。

在算法設(shè)計(jì)時(shí)，最容易想到的方法就是在內(nèi)存中創(chuàng)建數(shù)據(jù)表，然后反復(fù)遍歷該數(shù)據(jù)表。其主要算法如下：取一個(gè)待比較（或詞語(yǔ)），遍歷整個(gè)數(shù)據(jù)表，看該字符是不是已登錄過(guò)了的字符。若是，則進(jìn)行相應(yīng)的處理（如統(tǒng)計(jì)計(jì)數(shù)等），否則便在數(shù)據(jù)表中添加新記錄。如此循環(huán)執(zhí)行，直到比較完最后一個(gè)待處理字符。

這種算法每比較一個(gè)數(shù)據(jù)，就需要遍歷整個(gè)數(shù)據(jù)集，訪問(wèn)每一條記錄，一一進(jìn)行比較，然后再進(jìn)行相應(yīng)的處理，因而效率低下。并且隨著整個(gè)數(shù)據(jù)集的記錄數(shù)不斷增多，耗時(shí)量也會(huì)成倍增加。筆者曾做過(guò)試驗(yàn)，在我們的試驗(yàn)平臺(tái)上（筆記本：操作系統(tǒng)WindowsXP，CPU賽揚(yáng)3處理器1.20 GHz，Rom 254MB），用該算法在一個(gè)共66105個(gè)記錄的詞典數(shù)據(jù)表中查找相同詞語(yǔ)，竟耗時(shí)十多分鐘，效率十分低下。

哈希表（Hashtable）具有能夠快速查找的特點(diǎn)，最適合處理實(shí)時(shí)動(dòng)態(tài)詞典的查詢問(wèn)題，是語(yǔ)言統(tǒng)計(jì)中最常用的工具。

二、哈希表

哈希表（又稱散列表）是一種數(shù)據(jù)結(jié)構(gòu)，它可存儲(chǔ)相關(guān)聯(lián)的一對(duì)數(shù)據(jù)項(xiàng)：一個(gè)鍵（key）和它的對(duì)應(yīng)值（value）。它主要用于把一些數(shù)據(jù)與鍵相關(guān)聯(lián)的情況，以便能夠快速查找。哈希表通常操作在O（1）上，與標(biāo)準(zhǔn)的二分檢索相比，哈希表的搜索速度比數(shù)組快多了。在二分檢索方法中，必須搜索數(shù)組中的每個(gè)元素，以發(fā)現(xiàn)要尋找的數(shù)據(jù)。加快搜索的唯一的辦法就是把數(shù)組分成幾個(gè)部分，然后給各個(gè)部分排序并快速搜索，把不在搜索范圍內(nèi)的值排除掉。

然而，哈希表是按另一種方式組織的，當(dāng)給它傳遞一個(gè)鍵來(lái)搜索時(shí)，它知道到哪一塊中去搜索。也就是說(shuō)，哈希表只需要通過(guò)所有元素的子集，相對(duì)于二分檢索而言，它不必先排序，再把數(shù)組分開。而是按時(shí)間分開，按一定控制順序來(lái)搜索元素。總的來(lái)說(shuō)，哈希表知道搜索捷徑，而數(shù)組只知道正式的路線。

例如我們進(jìn)入超市購(gòu)物，手中還有其它不方便帶入超市的物件，把它存起來(lái)。因此，我們把該物件交給超市寄存處的服務(wù)員，服務(wù)員把它同其它顧客的物件放在一起，并給我們一個(gè)標(biāo)記牌，上面寫著編號(hào)1799。購(gòu)物后，我們回到寄存處，把標(biāo)記牌遞給服務(wù)員，服務(wù)員就直接從編號(hào)為1799的存物格中取出物件遞給我們。這就是哈希表的工作方式。服務(wù)員并不需要一一查看所有存物格中的物件，檢查其特征，才把我們的物件找出來(lái)（二分檢索的工作方式）。

總之，只要傳給哈希表一個(gè)“鍵”，它就能立刻快速地找到對(duì)應(yīng)的“值”。哈希表對(duì)于軟件工程師來(lái)說(shuō)就像望遠(yuǎn)鏡對(duì)于天文學(xué)家一樣。非常慶幸的是VB.NET Framework中已經(jīng)實(shí)現(xiàn)了Hashtable類，這樣我們不必從頭開始構(gòu)造自己的Hash表，而是可以直接重用Hashtable類，從而節(jié)約了許多時(shí)間。

哈希表的具體運(yùn)用方法（用VB.NET語(yǔ)言描述）：

（1）實(shí)例化一哈希表

Dim MyHash as Hashtable=New Hashtable（100, 0.1）

（2）哈希表的常用方法

MyHash.ContainsKey（key）用來(lái)檢驗(yàn)哈希表是否有該鍵（key）。

MyHash.add（key，value）用來(lái)添加一新的“鍵值”對(duì)

MyHash（key）則可獲取與該key對(duì)應(yīng)的value。

三、哈希表在語(yǔ)言統(tǒng)計(jì)中的具體運(yùn)用

（一）查找重復(fù)項(xiàng)

明確了哈希表在搜索效率上的優(yōu)勢(shì)后，我們可以在算法中運(yùn)用哈希表直接查找數(shù)據(jù)，避免一遍又一遍地查詢整個(gè)數(shù)據(jù)表，大大地提高了搜索速度。于是，我們建立了如下的查找重復(fù)項(xiàng)（字、詞語(yǔ)等）的新算法：

1.取一個(gè)待檢測(cè)項(xiàng)。

2.用哈希表的ContainsKey方法看該項(xiàng)是否已在哈希表中登記。如果該項(xiàng)在哈希表中沒(méi)登記過(guò)，將該項(xiàng)作為“鍵”（key），以該項(xiàng)出現(xiàn)的ID作為“值”（value），將這一“鍵值對(duì)”添加到哈希表中；如果該項(xiàng)在哈希表中已經(jīng)登記過(guò)，就以該詞語(yǔ)為“鍵”，用MyHash（key）方法從哈希表中提取“值”，將重復(fù)出現(xiàn)的位置添加到“值”中。

3.如果還有待處理項(xiàng)，就返回步驟1，直到處理完所有的待檢測(cè)項(xiàng)。

4.遍歷整個(gè)哈希表，輸出所有“值”為不止一個(gè)出現(xiàn)位置的“鍵”。

由于該算法運(yùn)用了哈希表，所以僅需遍歷數(shù)據(jù)集一遍，就可以統(tǒng)計(jì)出所有的重復(fù)詞。哈希表只要一“看”該詞語(yǔ)就可得知該詞語(yǔ)是不是一個(gè)未收錄的新詞語(yǔ)。若是新詞語(yǔ)，就給它開個(gè)新“賬號(hào)”；是已有詞語(yǔ)，就從哈希表中以此詞語(yǔ)為“鍵”，提取其“賬號(hào)”（哈希表中對(duì)應(yīng)的“值”），然后在該賬號(hào)上登上一筆。這樣就避免了反復(fù)盲目地從頭到尾地搜索整個(gè)記錄，同時(shí)也避免了在登記重復(fù)項(xiàng)時(shí)的盲目查找，效率會(huì)得到極大的提高。

筆者曾做過(guò)對(duì)比性試驗(yàn)，用哈希表在同一個(gè)共66105個(gè)記錄的詞典數(shù)據(jù)表中查找相同詞語(yǔ)，原來(lái)需要十多分鐘的工作，現(xiàn)在只需8秒多（8417毫秒）就完成了。所以，如果能在搜索中恰當(dāng)?shù)厥褂霉１?，就能極大地提高效率。

（二）字（詞）頻統(tǒng)計(jì)

把上述查找重復(fù)項(xiàng)的算法稍加改動(dòng)，便可進(jìn)行字（詞）頻統(tǒng)計(jì)。當(dāng)然，為了記錄保存字（詞）頻統(tǒng)計(jì)結(jié)果，首先還得進(jìn)行預(yù)處理，建立一個(gè)空的字（詞）頻統(tǒng)計(jì)表，該表具有“ID”“字（詞）”“出現(xiàn)次數(shù)”“出現(xiàn)頻率”這幾個(gè)字段。

具體算法如下：

1.取一個(gè)字（詞）。

2.總字（詞）數(shù)Total累加1。

3.用哈希表的ContainsKey方法看該字（詞）是否已在哈希表登記。如果該字（詞）在哈希表中沒(méi)登記過(guò)，將該字（詞）作為“鍵”（key），以該字（詞）出現(xiàn)次數(shù) “1”作為“值”（value），將這一“鍵值對(duì)”添加到哈希表中；如果該字（詞）在哈希表中已經(jīng)登記過(guò)，就以該字（詞）為“鍵”，用MyHash（key）方法從哈希表中提取“值”，將出現(xiàn)次數(shù)累加1。

4.如果還有待處理字（詞），就返回步驟1，直到處理完文檔所有的字（詞）。

5.將處理結(jié)果整理進(jìn)字頻統(tǒng)計(jì)表。遍歷整個(gè)哈希表，依次取哈希表的每條記錄中的“鍵”（即字或詞）作為字頻統(tǒng)計(jì)表的“字符”的值，取哈希表的每條記錄中的“值”作為字頻統(tǒng)計(jì)表的“出現(xiàn)次數(shù)”的值，并算出“出現(xiàn)頻率”的值（出現(xiàn)頻率=出現(xiàn)次數(shù)/總字[詞]數(shù)Total），將處理結(jié)果一一添加至字頻統(tǒng)計(jì)表。

6.把字頻統(tǒng)計(jì)表保存至硬盤。

筆者用該算法對(duì)1995年的《人民日?qǐng)?bào)》（文件大小為49，390KB，一共有26，385，940個(gè)字符）進(jìn)行了字頻統(tǒng)計(jì)，共耗時(shí)82709毫秒（僅一分多鐘），平均每秒處理31.9萬(wàn)個(gè)字符，處理效率相當(dāng)高。

哈希表知道搜索捷徑，最適合處理實(shí)時(shí)動(dòng)態(tài)詞典的查詢問(wèn)題，當(dāng)數(shù)據(jù)在不斷地動(dòng)態(tài)添加，同時(shí)又要對(duì)新的數(shù)據(jù)項(xiàng)進(jìn)行比較時(shí)，用哈希表可以避免不停地遍歷數(shù)據(jù)集，從而極大地提高處理效率。

參考文獻(xiàn)：

[1]王秀坤，李政，簡(jiǎn)幼良，劉劍基.基于Hash方法的機(jī)器翻譯詞典的組織與構(gòu)造[J].大連理工大學(xué)學(xué)報(bào)，1996，（3）.

[2]孫茂松，左正平，黃昌寧.漢語(yǔ)自動(dòng)分詞詞典機(jī)制的實(shí)驗(yàn)研究[J].中文信息學(xué)報(bào)，2000，（1）.

[3]李慶虎，陳玉健，孫家廣.一種中文分詞詞典新機(jī)制——雙字哈希機(jī)制[J].中文信息學(xué)報(bào)，2003，（4）.

[4]張培穎，李村合. 一種中文分詞詞典新機(jī)制——四字哈希機(jī)制[J].微型電腦應(yīng)用，2006，（10）.

[5]楊文峰，陳光英，李星.基于Patricia Tree的漢語(yǔ)自動(dòng)分詞詞典機(jī)制[J].中文信息學(xué)報(bào)，2001，（3）.

[6]李江波，周強(qiáng)，陳祖舜.漢語(yǔ)詞典快速查詢算法研究[J].中文信息學(xué)報(bào)，2006，（5）.

[7]Jeffrey R.Shapiro. Visual Basic.NET 完全手冊(cè)[M].北京：電子工業(yè)出版社，2003.

[8]Stephen Walther.ASP.NET技術(shù)內(nèi)幕[M].北京：機(jī)械工業(yè)出版社，2002.

（高文利 長(zhǎng)沙 湖南涉外經(jīng)濟(jì)學(xué)院文學(xué)部 410205；朱麗 益陽(yáng) 湖南城市學(xué)院圖書館 413049）