哈希表在计算语言学中的运用

高文利　朱　丽

摘 要：在汉语词典查询算法中，哈希表知道搜索捷径，然而数组只知道正式的路线，因而与标准的二分检索相比，哈希表的搜索速度比数组快多了。在算法中，如果能恰当地使用哈希表，就会极大地提高效率。

关键词：哈希表 数组 二分检索 语言统计

一、问题的由来

在汉语信息处理的整个过程中需要频繁地访问词典以获得汉语词语知识，汉语词典的快速查询是整个处理系统效率的关键所在。针对词典查询方法，前人做了大量工作，并形成了许多汉语词典组织结构和相应的查询算法，主要有：传统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）上，与标准的二分检索相比，哈希表的搜索速度比数组快多了。在二分检索方法中，必须搜索数组中的每个元素，以发现要寻找的数据。加快搜索的唯一的办法就是把数组分成几个部分，然后给各个部分排序并快速搜索，把不在搜索范围内的值排除掉。

然而，哈希表是按另一种方式组织的，当给它传递一个键来搜索时，它知道到哪一块中去搜索。也就是说，哈希表只需要通过所有元素的子集，相对于二分检索而言，它不必先排序，再把数组分开。而是按时间分开，按一定控制顺序来搜索元素。总的来说，哈希表知道搜索捷径，而数组只知道正式的路线。

例如我们进入超市购物，手中还有其它不方便带入超市的物件，把它存起来。因此，我们把该物件交给超市寄存处的服务员，服务员把它同其它顾客的物件放在一起，并给我们一个标记牌，上面写着编号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）