哈希表在計算語言學中的運用

摘 要：在漢語詞典查詢算法中，哈希表知道搜索捷徑，然而數組只知道正式的路線，因而與標準的二分檢索相比，哈希表的搜索速度比數組快多了。在算法中，如果能恰當地使用哈希表，就會極大地提高效率。

關鍵詞：哈希表 數組 二分檢索 語言統計

一、問題的由來

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

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

在語言研究中，經常會碰到這樣的字符或詞語的統計問題，如《集韻》共使用了多少韻字，《現代漢語詞典》共使用了多少詞形以及字頻統計等。這實際是處理中實時動態詞典的查詢問題。因為是實時動態詞典，無法對其事先建立索引，無法運用效率極高的Trie索引樹的詞典查詢機制，因而只能另想它策。

在算法設計時，最容易想到的方法就是在內存中創建數據表，然后反復遍歷該數據表。其主要算法如下：取一個待比較（或詞語），遍歷整個數據表，看該字符是不是已登錄過了的字符。若是，則進行相應的處理（如統計計數等），否則便在數據表中添加新記錄。如此循環執行，直到比較完最后一個待處理字符。

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

哈希表（Hashtable）具有能夠快速查找的特點，最適合處理實時動態詞典的查詢問題，是語言統計中最常用的工具。

二、哈希表

哈希表（又稱散列表）是一種數據結構，它可存儲相關聯的一對數據項：一個鍵（key）和它的對應值（value）。它主要用于把一些數據與鍵相關聯的情況，以便能夠快速查找。哈希表通常操作在O（1）上，與標準的二分檢索相比，哈希表的搜索速度比數組快多了。在二分檢索方法中，必須搜索數組中的每個元素，以發現要尋找的數據。加快搜索的唯一的辦法就是把數組分成幾個部分，然后給各個部分排序并快速搜索，把不在搜索范圍內的值排除掉。

然而，哈希表是按另一種方式組織的，當給它傳遞一個鍵來搜索時，它知道到哪一塊中去搜索。也就是說，哈希表只需要通過所有元素的子集，相對于二分檢索而言，它不必先排序，再把數組分開。而是按時間分開，按一定控制順序來搜索元素?？偟膩碚f，哈希表知道搜索捷徑，而數組只知道正式的路線。

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

總之，只要傳給哈希表一個“鍵”，它就能立刻快速地找到對應的“值”。哈希表對于軟件工程師來說就像望遠鏡對于天文學家一樣。非常慶幸的是VB.NET Framework中已經實現了Hashtable類，這樣我們不必從頭開始構造自己的Hash表，而是可以直接重用Hashtable類，從而節約了許多時間。

哈希表的具體運用方法（用VB.NET語言描述）：

（1）實例化一哈希表

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

（2）哈希表的常用方法

MyHash.ContainsKey（key）用來檢驗哈希表是否有該鍵（key）。

MyHash.add（key，value）用來添加一新的“鍵值”對

MyHash（key）則可獲取與該key對應的value。

三、哈希表在語言統計中的具體運用

（一）查找重復項

明確了哈希表在搜索效率上的優勢后，我們可以在算法中運用哈希表直接查找數據，避免一遍又一遍地查詢整個數據表，大大地提高了搜索速度。于是，我們建立了如下的查找重復項（字、詞語等）的新算法：

1.取一個待檢測項。

2.用哈希表的ContainsKey方法看該項是否已在哈希表中登記。如果該項在哈希表中沒登記過，將該項作為“鍵”（key），以該項出現的ID作為“值”（value），將這一“鍵值對”添加到哈希表中；如果該項在哈希表中已經登記過，就以該詞語為“鍵”，用MyHash（key）方法從哈希表中提取“值”，將重復出現的位置添加到“值”中。

3.如果還有待處理項，就返回步驟1，直到處理完所有的待檢測項。

4.遍歷整個哈希表，輸出所有“值”為不止一個出現位置的“鍵”。

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

筆者曾做過對比性試驗，用哈希表在同一個共66105個記錄的詞典數據表中查找相同詞語，原來需要十多分鐘的工作，現在只需8秒多（8417毫秒）就完成了。所以，如果能在搜索中恰當地使用哈希表，就能極大地提高效率。

（二）字（詞）頻統計

把上述查找重復項的算法稍加改動，便可進行字（詞）頻統計。當然，為了記錄保存字（詞）頻統計結果，首先還得進行預處理，建立一個空的字（詞）頻統計表，該表具有“ID”“字（詞）”“出現次數”“出現頻率”這幾個字段。

具體算法如下：

1.取一個字（詞）。

2.總字（詞）數Total累加1。

3.用哈希表的ContainsKey方法看該字（詞）是否已在哈希表登記。如果該字（詞）在哈希表中沒登記過，將該字（詞）作為“鍵”（key），以該字（詞）出現次數 “1”作為“值”（value），將這一“鍵值對”添加到哈希表中；如果該字（詞）在哈希表中已經登記過，就以該字（詞）為“鍵”，用MyHash（key）方法從哈希表中提取“值”，將出現次數累加1。

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

5.將處理結果整理進字頻統計表。遍歷整個哈希表，依次取哈希表的每條記錄中的“鍵”（即字或詞）作為字頻統計表的“字符”的值，取哈希表的每條記錄中的“值”作為字頻統計表的“出現次數”的值，并算出“出現頻率”的值（出現頻率=出現次數/總字[詞]數Total），將處理結果一一添加至字頻統計表。

6.把字頻統計表保存至硬盤。

筆者用該算法對1995年的《人民日報》（文件大小為49，390KB，一共有26，385，940個字符）進行了字頻統計，共耗時82709毫秒（僅一分多鐘），平均每秒處理31.9萬個字符，處理效率相當高。

哈希表知道搜索捷徑，最適合處理實時動態詞典的查詢問題，當數據在不斷地動態添加，同時又要對新的數據項進行比較時，用哈希表可以避免不停地遍歷數據集，從而極大地提高處理效率。

參考文獻：

[1]王秀坤，李政，簡幼良，劉劍基.基于Hash方法的機器翻譯詞典的組織與構造[J].大連理工大學學報，1996，（3）.

[2]孫茂松，左正平，黃昌寧.漢語自動分詞詞典機制的實驗研究[J].中文信息學報，2000，（1）.

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

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

[5]楊文峰，陳光英，李星.基于Patricia Tree的漢語自動分詞詞典機制[J].中文信息學報，2001，（3）.

[6]李江波，周強，陳祖舜.漢語詞典快速查詢算法研究[J].中文信息學報，2006，（5）.

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

[8]Stephen Walther.ASP.NET技術內幕[M].北京：機械工業出版社，2002.

（高文利 長沙 湖南涉外經濟學院文學部 410205；朱麗 益陽 湖南城市學院圖書館 413049）