论文部分内容阅读
[摘要]汉语自动分词是汉语信息处理的前提，词典是汉语自动分词的基础，分词词典机制的优劣直接影响到中文分词的速度和效率。本文首先分析了已有的几种典型词典结构，并在此基础上提出了一种新的分词词典结构——全字哈希词典，提高了中文分词的速度和效率。
[关键词]分词词典 中文分词 全哈希
一、引言
汉语自动分词是汉语信息处理的前提，广泛应用于中文全文检索、中文自动全文翻译、中文文语转换等领域。自动分词的基本算法主要分为两大类：基于词典的分词方法和基于频度统计的分词方法。具体应用时的不同算法则是二者不同程度的组合。
针对词典分词方式，前人做了大量工作，并形成了许多汉语词典的组织结构。这些组织结构大体上分成树形结构和表格形结构：文献介绍了树形结构的构造方法，文献提出了三数组Trie索引树结构，文献提出一种更加优化PATRICIA树，而典型的表格结构有整词二分的和逐字二分的两种，文献详细阐述了这两种表格结构，并与Trie树词表在分词效率和空间消费方面作了对比，文献使用了分层存储词条的表格结构，使其对于优先切分专有名词效率更佳。文献综合了树形和表格形结构的优点，提出了双字哈希机制的词典结构。对于切分二字词表现出色，采用的是传统Hash方法。总结下来树形结构和表格形结构各有优劣，表格结构词典构造相对简单，占用空间少，容易更新和维护，但是查找词条效率相对较慢；而树形结构构造复杂，占用空间大，难以更改，但是查找词条效率较高。无论哪种结构，基本的词条查找过程都使用了二分查找，某些词典甚至需要多次二分查找，这种方式受数据集范围的影响，当在一个大数据集上进行二分查找其效率难以令人满意，当需要多次二分查找时，其效率甚至难以预测。
本文提出一种全哈希机制的词典结构，既有较高的查找速度(总能以常数级的时间复杂度完成任务)又容易维护。而且与上述任何一种词典都不同的地方是它具有了同义词的存储结构。
二、全哈希词典结构
该词典包含三级索引，每级索引都用哈希方法实现，其结构下图所示：
图1全哈希词典结构
本结构用三层哈希表嵌套，每层哈希表的键(Key)域存储该层级索引值。一级索引Ⅱ是所有词条的首字哈希值，存储于外层哈希表的键域，每个单元对应一个首字的哈希值，外层哈希表的值(Value)域存放以字CO为首的所有词条。二级索引将以CO为首的所有词条按照词长分类，一种长度的词存储在中层哈希表的一个单元中，该单元键域存放词长，值域存放所有该长度的词条。每个词条经过特定的哈希函数计算，得到唯一的哈希值(一般是整数)，这些哈希值构成了第三级索引，存储于内层哈希表的键域；而内层哈希表值域存放的是哈希值相同的词条列表。为了能够将每个词条的同义词合理的植入词典，本文定义了一种特殊结构用来承载每个词条(Wi)，该结构包含了词条的文本值，该词条的同义词指针等内容，有关同义词部分将在下一章详细介绍。
查找速度快是哈希表固有的优势，根据哈希值直接匹配的时间复杂度几乎是O(1)，这是其它任何算法不能比拟的。而查找词条的主要时间消耗是计算哈希值的过程，哈希算法的优劣是影响查找最重要的因素。
三、哈希算法设计
哈希算法设计应该兼顾以下几个原则：
(1)计算速度快，便于实现。查找词条的过程主要时间消耗在哈希值计算上，哈希算法应尽量减少这一过程的时间复杂度。
(2)散列均匀，尽可能少产生冲突。哈希算法一定为同一个对象产生唯一的哈希值，但不一定为不同的对象产生不同的哈希值，也就是一个哈希值有可能对应多个对象。哈希算法设计应该尽量使哈希值均匀分布在哈希表单元中，即使不能完全避免冲突，也应该使尽量少的对象对应同一个哈希值。
(3)提高桶利用率，节省哈希表占用空间。我们将哈希值相同的对象放在同一个桶中，每个桶对应一个哈希值，所谓桶利用率是指哈希表中已占用的桶数和已分配的桶数之比。当这个比值超过装载因子时，应该为哈希表分配若干新的单元，哈希算法应该尽量使空桶数较小，提高存储空间利用率。
适用于本词典的分词算法是一种最大正向匹配法，该算法的匹配过程是从左至右读取句子S＝COC1C2C3……中的汉字，在词典中依次查找CO，COC1，COC1C2，……直到找到能够匹配的最长词条，每个汉字只需比较一次，先比较CO，接下来比较C1依此类推，而传统的做法是先比较[CO..Ci]，若不成功再比较[CO..Ci-1]依此类推，这个词条中的前缀子串重复比较了多次，影响效率。为了避免重复比较，哈希函数设计还应考虑哈希值可累加，即子串SI=COC1，hash(S1)=V1；子串$2=COC1C2，hash(S2)=V2；字符c2的哈希值是hash(C21=V3；V2=V1“+”V3(不一定是算数累加)。每次计算新串的哈希值，只需计算末尾字符的哈希值，将它累加到已有的前缀旧串哈希值中，不必重新计算整个新串的哈希值。
基于以上考虑，笔者研究了一些经典的字符串哈希算法，它们是Rs算法、Js算法、ELF算法、BKDR算法、SDBM算法、DJB算法、AP算法。根据人们多年的实践经验，ELF用于计算英文字符串(ASCⅡ码)的哈希值表现较好。本文用开放的中文语料库对以上算法做了对比测试，开放语料库是紫光大词库，该词库包含374993个词条，分别用上述算法计算每个词条的哈希值，将它们插入哈希表，比较哈希函数执行总时间，有冲突的桶数目(一个桶中有两个以上的词条，视为冲突)，最大冲突词条数目(一个桶中最多有多少个词条)，桶利用率和哈希表占用的存储空间。为了更精确说明桶的使用情况，桶利用率用实际占用的桶数来代替。将构造好的哈希表对象序列化到二进制文件，文件的大小可以反映出哈希表占用的存储空间，虽然序列化过程的附加信息也会保存到文件中，但是仍然可以用于对比每个哈希表的相对大小。本文使用两种方式来分配哈希表单元，一种是静态分配(固定长度)，预先分配374993个单元，限制哈希值在此范围内分布；另一种动态分配(不限制长度)，使用系统默认的装载因子，当哈希表单元占用率超过装载因子时，系统会分配若干新的单元。实验环境是2.1G双核CUP，2G内存，XP操作系统，NetFramework平台。下面的实验结果反映了各种算法在两种分配方式下的不同表现(静态分配的实验结果／动态分配的实验结果)(见表1)。
由表1的数据可以得到以下结论：
(1)在静态分配方式下，各种算法产生的哈希值冲突较多(都在98000以上)，最多有八九个词条对应同一个哈希值，实际使用的桶较少，哈希表占用存储空间较少；在动态分配方式下，各种算法产生的冲突较少(最多11474)，最大冲突词条较少，实际使用的桶较多，占用存储空间较多。
(2)在同一种分配方式下，每种算法的表现各有差异，处理英文字符串常用的ELF算法实验结果并不理想，时间复杂度较高，产生冲突较多。而SDBM算法的执行时间最短，哈希值冲突较少，桶利用率较高。
每种算法生成的哈希表占用的存储空间差别不大，在选择哈希算法时，该项参数可以忽略。经过综合考量，本文选用了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]杨文峰，陈光英，李星.基于PATRICIAtree的汉语自动分词词典机制[J].中文信息学报，2000，15(3)：44-49.
[4]孙茂松，左正平，黄昌宁.汉语自动分词词典机制的实验研究[J].中文信息学报1999，14(1)：1-6.
[5]梁卓明，陈炬桦.基于专有名词优先的快速中文分词[J].计算机技术与发展，2008，18(3)：24-27.
[6]李庆虎，陈玉健，孙家广.一种中文分词词典新机制一双字哈希机制[J].中文信息学报2002，17(4)：13-18.
[关键词]分词词典 中文分词 全哈希
一、引言
汉语自动分词是汉语信息处理的前提，广泛应用于中文全文检索、中文自动全文翻译、中文文语转换等领域。自动分词的基本算法主要分为两大类：基于词典的分词方法和基于频度统计的分词方法。具体应用时的不同算法则是二者不同程度的组合。
针对词典分词方式，前人做了大量工作，并形成了许多汉语词典的组织结构。这些组织结构大体上分成树形结构和表格形结构：文献介绍了树形结构的构造方法，文献提出了三数组Trie索引树结构，文献提出一种更加优化PATRICIA树，而典型的表格结构有整词二分的和逐字二分的两种，文献详细阐述了这两种表格结构，并与Trie树词表在分词效率和空间消费方面作了对比，文献使用了分层存储词条的表格结构，使其对于优先切分专有名词效率更佳。文献综合了树形和表格形结构的优点，提出了双字哈希机制的词典结构。对于切分二字词表现出色，采用的是传统Hash方法。总结下来树形结构和表格形结构各有优劣，表格结构词典构造相对简单，占用空间少，容易更新和维护，但是查找词条效率相对较慢；而树形结构构造复杂，占用空间大，难以更改，但是查找词条效率较高。无论哪种结构，基本的词条查找过程都使用了二分查找，某些词典甚至需要多次二分查找，这种方式受数据集范围的影响，当在一个大数据集上进行二分查找其效率难以令人满意，当需要多次二分查找时，其效率甚至难以预测。
本文提出一种全哈希机制的词典结构，既有较高的查找速度(总能以常数级的时间复杂度完成任务)又容易维护。而且与上述任何一种词典都不同的地方是它具有了同义词的存储结构。
二、全哈希词典结构
该词典包含三级索引，每级索引都用哈希方法实现，其结构下图所示：
图1全哈希词典结构
本结构用三层哈希表嵌套，每层哈希表的键(Key)域存储该层级索引值。一级索引Ⅱ是所有词条的首字哈希值，存储于外层哈希表的键域，每个单元对应一个首字的哈希值，外层哈希表的值(Value)域存放以字CO为首的所有词条。二级索引将以CO为首的所有词条按照词长分类，一种长度的词存储在中层哈希表的一个单元中，该单元键域存放词长，值域存放所有该长度的词条。每个词条经过特定的哈希函数计算，得到唯一的哈希值(一般是整数)，这些哈希值构成了第三级索引，存储于内层哈希表的键域；而内层哈希表值域存放的是哈希值相同的词条列表。为了能够将每个词条的同义词合理的植入词典，本文定义了一种特殊结构用来承载每个词条(Wi)，该结构包含了词条的文本值，该词条的同义词指针等内容，有关同义词部分将在下一章详细介绍。
查找速度快是哈希表固有的优势，根据哈希值直接匹配的时间复杂度几乎是O(1)，这是其它任何算法不能比拟的。而查找词条的主要时间消耗是计算哈希值的过程，哈希算法的优劣是影响查找最重要的因素。
三、哈希算法设计
哈希算法设计应该兼顾以下几个原则：
(1)计算速度快，便于实现。查找词条的过程主要时间消耗在哈希值计算上，哈希算法应尽量减少这一过程的时间复杂度。
(2)散列均匀，尽可能少产生冲突。哈希算法一定为同一个对象产生唯一的哈希值，但不一定为不同的对象产生不同的哈希值，也就是一个哈希值有可能对应多个对象。哈希算法设计应该尽量使哈希值均匀分布在哈希表单元中，即使不能完全避免冲突，也应该使尽量少的对象对应同一个哈希值。
(3)提高桶利用率，节省哈希表占用空间。我们将哈希值相同的对象放在同一个桶中，每个桶对应一个哈希值，所谓桶利用率是指哈希表中已占用的桶数和已分配的桶数之比。当这个比值超过装载因子时，应该为哈希表分配若干新的单元，哈希算法应该尽量使空桶数较小，提高存储空间利用率。
适用于本词典的分词算法是一种最大正向匹配法，该算法的匹配过程是从左至右读取句子S＝COC1C2C3……中的汉字，在词典中依次查找CO，COC1，COC1C2，……直到找到能够匹配的最长词条，每个汉字只需比较一次，先比较CO，接下来比较C1依此类推，而传统的做法是先比较[CO..Ci]，若不成功再比较[CO..Ci-1]依此类推，这个词条中的前缀子串重复比较了多次，影响效率。为了避免重复比较，哈希函数设计还应考虑哈希值可累加，即子串SI=COC1，hash(S1)=V1；子串$2=COC1C2，hash(S2)=V2；字符c2的哈希值是hash(C21=V3；V2=V1“+”V3(不一定是算数累加)。每次计算新串的哈希值，只需计算末尾字符的哈希值，将它累加到已有的前缀旧串哈希值中，不必重新计算整个新串的哈希值。
基于以上考虑，笔者研究了一些经典的字符串哈希算法，它们是Rs算法、Js算法、ELF算法、BKDR算法、SDBM算法、DJB算法、AP算法。根据人们多年的实践经验，ELF用于计算英文字符串(ASCⅡ码)的哈希值表现较好。本文用开放的中文语料库对以上算法做了对比测试，开放语料库是紫光大词库，该词库包含374993个词条，分别用上述算法计算每个词条的哈希值，将它们插入哈希表，比较哈希函数执行总时间，有冲突的桶数目(一个桶中有两个以上的词条，视为冲突)，最大冲突词条数目(一个桶中最多有多少个词条)，桶利用率和哈希表占用的存储空间。为了更精确说明桶的使用情况，桶利用率用实际占用的桶数来代替。将构造好的哈希表对象序列化到二进制文件，文件的大小可以反映出哈希表占用的存储空间，虽然序列化过程的附加信息也会保存到文件中，但是仍然可以用于对比每个哈希表的相对大小。本文使用两种方式来分配哈希表单元，一种是静态分配(固定长度)，预先分配374993个单元，限制哈希值在此范围内分布；另一种动态分配(不限制长度)，使用系统默认的装载因子，当哈希表单元占用率超过装载因子时，系统会分配若干新的单元。实验环境是2.1G双核CUP，2G内存，XP操作系统，NetFramework平台。下面的实验结果反映了各种算法在两种分配方式下的不同表现(静态分配的实验结果／动态分配的实验结果)(见表1)。
由表1的数据可以得到以下结论：
(1)在静态分配方式下，各种算法产生的哈希值冲突较多(都在98000以上)，最多有八九个词条对应同一个哈希值，实际使用的桶较少，哈希表占用存储空间较少；在动态分配方式下，各种算法产生的冲突较少(最多11474)，最大冲突词条较少，实际使用的桶较多，占用存储空间较多。
(2)在同一种分配方式下，每种算法的表现各有差异，处理英文字符串常用的ELF算法实验结果并不理想，时间复杂度较高，产生冲突较多。而SDBM算法的执行时间最短，哈希值冲突较少，桶利用率较高。
每种算法生成的哈希表占用的存储空间差别不大，在选择哈希算法时，该项参数可以忽略。经过综合考量，本文选用了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]杨文峰，陈光英，李星.基于PATRICIAtree的汉语自动分词词典机制[J].中文信息学报，2000，15(3)：44-49.
[4]孙茂松，左正平，黄昌宁.汉语自动分词词典机制的实验研究[J].中文信息学报1999，14(1)：1-6.
[5]梁卓明，陈炬桦.基于专有名词优先的快速中文分词[J].计算机技术与发展，2008，18(3)：24-27.
[6]李庆虎，陈玉健，孙家广.一种中文分词词典新机制一双字哈希机制[J].中文信息学报2002，17(4)：13-18.