一种新的中文分词词典结构

1、一种新的中文分词词典结构 摘要 汉语自动分词是汉语信息处理的前提，词典是 汉语自动分词的基础，分词词典机制的优劣直接影响到中文 分词的速度和效率。本文首先分析了已有的几种典型词典结 构，并在此基础上提出了一种新的分词词典结构一全字哈希 词典，提高了中文分词的速度和效率。 关键词 分词词典中文分词全哈希 一、引言 汉语自动分词是汉语信息处理的前提，广泛应用于中文 全文检索、中文自动全文翻译、中文文语转换等领域。自动 分词的基本算法主要分为两大类：基于词典的分词方法和基 于频度统计的分词方法。具体应用时的不同算法则是二者不 同程度的组合。 针对词典分词方式，前人做了大量工作，并形成了许多 汉语词典

2、的组织结构。这些组织结构大体上分成树形结构和 表格形结构：文献 1 介绍了树形结构的构造方法，文献 2 提出了三数组 Trie 索引树结构，文献 3提出一种更加优化 PATRICIA 树；而典型的表格结构有整词二分的和逐字二分 的两种， 文献4 详细阐述了这两种表格结构， 并与 Trie 树词 表在分词效率和空间消费方面作了对比， 文献 5使用了分层 存储词条的表格结构，使其对于优先切分专有名词效率更 佳。文献 6 综合了树形和表格形结构的优点，提出了双字哈 希机制的词典结构。对于切分二字词表现出色，采用的是传 统 Hash 方法。总结下来树形结构和表格形结构各有优劣， 表格结构词典构造相对简

3、单， 占用空间少， 容易更新和维护， 但是查找词条效率相对较慢；而树形结构构造复杂，占用空 间大，难以更改，但是查找词条效率较高。无论哪种结构， 基本的词条查找过程都使用了二分查找，某些词典甚至需要 多次二分查找，这种方式受数据集范围的影响，当在一个大 数据集上进行二分查找其效率难以令人满意，当需要多次二 分查找时，其效率甚至难以预测。 本文提出一种全哈希机制的词典结构，既有较高的查找 速度（总能以常数级的时间复杂度完成任务）又容易维护。 而且与上述任何一种词典都不同的地方是它具有了同义词 的存储结构。 二、全哈希词典结构 该词典包含三级索引，每级索引都用哈希方法实现，其 结构下图所示： 图

4、1 全哈希词典结构 本结构用三层哈希表嵌套，每层哈希表的键（Key ）域 存储该层级索引值。一级索引 I1 是所有词条的首字哈希值， 存储于外层哈希表的键域，每个单元对应一个首字的哈希 值，外层哈希表的值（Value）域存放以字CO为首的所有词 条。二级索引将以 C0 为首的所有词条按照词长分类，一种 长度的词存储在中层哈希表的一个单元中，该单元键域存放 词长，值域存放所有该长度的词条。每个词条经过特定的哈 希函数计算，得到唯一的哈希值（一般是整数） ，这些哈希 值构成了第三级索引，存储于内层哈希表的键域；而内层哈 希表值域存放的是哈希值相同的词条列表。为了能够将每个 词条的同义词合理的植入词

5、典，本文定义了一种特殊结构用 来承载每个词条（Wi）,该结构包含了词条的文本值，该词 条的同义词指针等内容，有关同义词部分将在下一章详细介 绍。 查找速度快是哈希表固有的优势，根据哈希值直接匹配 的时间复杂度几乎是 O （ 1） ，这是其它任何算法不能比拟的。 而查找词条的主要时间消耗是计算哈希值的过程，哈希算法 的优劣是影响查找最重要的因素。 三、哈希算法设计 哈希算法设计应该兼顾以下几个原则： （ 1）计算速度快，便于实现。查找词条的过程主要时 间消耗在哈希值计算上，哈希算法应尽量减少这一过程的时 间复杂度。 (2) 散列均匀，尽可能少产生冲突。哈希算法一定为 同一个对象产生唯一的哈希值，

6、但不一定为不同的对象产生 不同的哈希值，也就是一个哈希值有可能对应多个对象。哈 希算法设计应该尽量使哈希值均匀分布在哈希表单元中，即 使不能完全避免冲突，也应该使尽量少的对象对应同一个哈 希值。 (3) 提高桶利用率，节省哈希表占用空间。我们将哈 希值相同的对象放在同一个桶中，每个桶对应一个哈希值， 所谓桶利用率是指哈希表中已占用的桶数和已分配的桶数 之比。当这个比值超过装载因子时，应该为哈希表分配若干 新的单元，哈希算法应该尽量使空桶数较小，提高存储空间 利用率。 适用于本词典的分词算法是一种最大正向匹配法，该算 法的匹配过程是从左至右读取句子S=C0C1C2C3中的汉 字，在词典中依次查找

7、 C0, C0C1 , C0C1C2 ,直到找到 能够匹配的最长词条，每个汉字只需比较一次，先比较 C0， 接下来比较 C1 依此类推，而传统的做法是先比较 C0.Ci ， 若不成功再比较 C0.Ci-1 依此类推， 这个词条中的前缀子串 重复比较了多次，影响效率。为了避免重复比较，哈希函数 设计还应考虑哈希值可累加， 即子串 S1=C0C1，hash(S1)=V1 ； 子串S2=C0C1C2 , hash(S2)=V2 ;字符 C2的哈希值是 hash(C2)=V3 ; V2=V1 ” + ” V3 (不一定是算数累加)。每 次计算新串的哈希值，只需计算末尾字符的哈希值，将它累 加到已有的前

8、缀旧串哈希值中，不必重新计算整个新串的哈 希值。 基于以上考虑，笔者研究了一些经典的字符串哈希算 法，它们是 RS算法、JS算法、ELF算法、BKDR算法、SDBM 算法、 DJB 算法、 AP 算法。根据人们多年的实践经验， ELF 用于计算英文字符串（ ASCII 码）的哈希值表现较好。本文 用开放的中文语料库对以上算法做了对比测试，开放语料库 是紫光大词库，该词库包含 374993 个词条，分别用上述算 法计算每个词条的哈希值，将它们插入哈希表，比较哈希函 数执行总时间，有冲突的桶数目（一个桶中有两个以上的词 条，视为冲突） ，最大冲突词条数目（一个桶中最多有多少 个词条），桶利用率和哈

9、希表占用的存储空间。为了更精确 说明桶的使用情况，桶利用率用实际占用的桶数来代替。将 构造好的哈希表对象序列化到二进制文件，文件的大小可以 反映出哈希表占用的存储空间，虽然序列化过程的附加信息 也会保存到文件中，但是仍然可以用于对比每个哈希表的相 对大小。本文使用两种方式来分配哈希表单元，一种是静态 分配（固定长度） ，预先分配 374993 个单元，限制哈希值在 此范围内分布；另一种动态分配（不限制长度） ，使用系统 默认的装载因子，当哈希表单元占用率超过装载因子时，系 统会分配若干新的单元。实验环境是 2.1G 双核 CUP ， 2G 内 存， XP 操作系统， .NetFramework

10、 平台。下面的实验结果反 映了各种算法在两种分配方式下的不同表现（静态分配的实 验结果 /动态分配的实验结果） （见表 1）。 由表 1 的数据可以得到以下结论： （1）在静态分配方式下，各种算法产生的哈希值冲突 较多（都在 98000 以上），最多有八九个词条对应同一个哈 希值，实际使用的桶较少，哈希表占用存储空间较少；在动 态分配方式下，各种算法产生的冲突较少（最多11474），最 大冲突词条较少，实际使用的桶较多，占用存储空间较多。 （2）在同一种分配方式下，每种算法的表现各有差异， 处理英文字符串常用的 ELF 算法实验结果并不理想， 时间复 杂度较高，产生冲突较多。而 SDBM 算法

11、的执行时间最短， 哈希值冲突较少，桶利用率较高。 每种算法生成的哈希表占用的存储空间差别不大，在选 择哈希算法时，该项参数可以忽略。经过综合考量，本文选 用了 SDBM 算法计算词条的哈希值。 SDBM 算法实现如下： SDBM 哈希函数接收新词条字串和其前缀字串的哈希 值作为参数，返回 uint 类型的新哈希值。计算哈希值使用到 汉字的 Unicode 编码， Unicode 其实就是宽字节字符集，它 对每个字符都固定使用两个字节即 16 位表示。 优秀的哈希算法能尽量减少冲突，但是完全避免冲突几 乎不可能。表 1 的数据显示，将所有词条放在同一个哈希表 中，静态分配产生的冲突哈希值有9 万以上， 即使动态分配， 最少也有 22 个值冲突。若将这些哈希值散列到多个哈希表 中，就能在更大程度上减少冲突，本文设计的分层式的词典 也是出于这种考虑。 参考文献： 1 高文利 ,李德华 .分词索引树的构建 J. 语言研 究,2007,27(4):103 105. 2 高文利 ,李德华 .基于三数组 Trie 索引树的词典查询 机制J.现代图书情报技术，2007(7):76 78. 3 杨文峰 ,陈光英 ,李星.基于 PATRICIA tree 的汉语自动 分词词典机制 J .中文信息学报 ,2000,15(3):