基于改进Trie 树的歧义消解方法∗

陈 倩 乐红兵

（江南大学物联网工程学院 无锡 214122）

1 引言

分词是中文语言处理的基础性工作。近年来，中文分词经历了很大的发展。将分词看作序列标记问题是比较普遍的方法［1］，序列标记的目标是给序列中所有元素分配标签，包括最大熵和条件随机场等监督学习算法［2］。但是语言搭配是随着时间不断变化的，陈旧的语料训练出的基于统计的分词方法难以驾驭人们日益更新的语言习惯，且人工进行语料库更新是十分巨大繁琐的工作，国内没有能够获取并持续更新的语料库，这是基于统计学习的分词方法所遇到的阻碍［3］。

在现实生活中需要切分的语料是多种多样的，并不是所有待切分语料都具有上下文信息，一些需要处理的语料往往以单个句子的形式出现并要求切分。例如在网络上查询信息时输入的文本、网上聊天和电子邮件中输入的单句、问答系统种用户输入的句子等都没有上下文信息［3］。由此可见基于上下文信息进行分词方法具有局限性。在基于词典的分词方法中，未登录词造成的分词精度降低和容易产生歧义是它的缺陷所在，因此未登陆词识别和歧义处理是衡量基于词典的分词系统优劣的重要标准。

针对分词算法的词典构造方法，目前形成了成熟的词典加载结构。如：整词二分法、Trie 索引树、逐字二分法。根据文献［4］，三种词典机制的空间大小排序，Trie 索引＞整词二分=逐字二分；时间大小排序，Trie索引树＞逐字二分＞整词二分。分词词典是划分出每个词的重要依据，因此分词词典的构造至关重要，它无需通过语料库的训练，计算量小，原理简单且易于实现。

宗中等［5］依据双字词占比重较高，单字和多字不常用的特点，提出了双字Hash 词典机制。仅对词语的前两个字顺次建立Hash 索引，构成了深度只为2 的Trie 子树，词的剩余部分构成词组作为词典正文，从而避免了枝干过长，大大提高了词组查询速度。分词速度得到提升，由于没有歧义方面的处理，分词准确率提高不大。

李江波等［6］提出了双数组Trie 思想。首先把所有GB2312 中的基本汉字的顺序码转化成1-6768 的顺序码，然后将所有的顺序码作为初始状态放入Base 数组；接下来将不同词语的后续汉字顺序放进数组，生成新的状态，并对数组中初始状态的Base 值进行调整，以保证所有后续汉字能够放入数组。双数组Trie 改进了数组指针空置的缺陷，实现在空间占有较少的同时还要保证查询的效率。但是双数组Trie内存消耗大，实现复杂。

交集型分词歧义是自动分词遇到的主要歧义类型。以往所提出的歧义处理方法，常需上下文信息的统计进行辨别歧义，例如使用互信息原理、N元统计模型，t-测试原理、HMM 模型、字标注统计等方法或模型进行上下文信息统计以实现歧义消解，无法在没有上下文信息的情况下进行歧义消解，或者上下文信息量少影响歧义消解的质量。

文中进一步改进Trie树词典加载机制，采用双哈希索引，即首字和次字使用哈希索引，词的剩余字串则按字典顺序组成类似“整词二分”的词典正文，最大限度地提高匹配时间效率。然后运用词频和词性信息进行交集型歧义处理，该方法使用于对上下文信息匮乏的语料。

2 双字Hash词典机制

Trie 树是一种以树的多重链表表示的键树，主要有首字散列表和结点两部分组成，在语句切分过程中只需一次扫描，无需知道待分词的长度，沿着树链逐字匹配进行分词，避免了整词二分的词典机制中不必要的多次试探性查询。Tire 树进行词典加载一般采用哈希算法，把任意长度的输入通过散列算法，变换成固定长度的输入，该输出就是散列值，这种转换就是一种压缩映射。哈希算法的基础是哈希表的建立，散列表（哈希表）是根据关键码值直接进行访问的数据结构。当关键字集合很大时，关键字值不同的元素可能会映射到哈希表的同一地址上，从而产生冲突。

与英文不同，目前汉字已经超过8 万字，常用字就有7000多个，27万个词组，如果一条枝干仅代表一个字，将有27 万个叶子节点，Trie 索引树的广度扩大，浪费了一定的存储空间，并且Trie 树中一个关键字关联多个值导致散列表查找碰撞严重，分词速度相应变慢。

因此，用Trie进行中文词典加载会产生大量空指针，散列查找也需要额外的时间，为了最大限度地提高匹配时间的效率并兼顾空间利用率。本文提出双字哈希词典存储，二字词以下的短语使用Trie 索引树机制实现，三字词以上的长词的剩余部分用线性表组织，逐词匹配三字词以上的长词的剩余字符串，从而避免了深度搜索，一定程度上优化了查询性能，提高了分词的速度。虽然与莫建文［4］等提出的双字哈希结构相似，但是本文对词典正文进行了最大长度、词性、使用频率字段的扩充，提高了分词歧义判断的准确性。

根据权威统计，双字词语所占比例很大，使用频率也很高，多（四字以上）字词语占比例很小，使用频率较低。汉语各字词条的词频统计如表1 所示：两字词的词频占了一半以上，而五字以上的词的出现概率就非常小，使用频率低。

表1 不同字长的频率比

结合中文字的编码体系和中文词的分布以及哈希索引结构的词典查询速度快的优点，本文设计了一个基于双字哈希的三层索引词典结构基本结构如下：

1）首字哈希表（Hashmap 存储）：全部中文字符的区位码的哈希值，哈希值的大小由小到大依次排列，由首字哈希表值可以直接找到对应的首字地址。

汉字在计算机中以内码形式存在，将内码计算后转为区位码，再将区位码转换为一个十进制的数字，这个数字就是该汉字在哈希表中的序号。该序号指示了以该字为首字的词长表的入口地址，根据Hash函数入口地址的计算，如式（1）所示：

其中，Offset 为该字在哈希表中的序号，ch1，ch2分别为该字机内码的高字节和低字节。

2）次字哈希表

采用除留余数法的散列函数处理次字哈希索引。

次字哈希函数为

其中，Offset 为该字在哈希表中的序号，ch1，ch2 分别为该字机内码的高字节和低字节。Length是求模系统，文中对其长度进行统一分配。

3）词典正文

词典正文是由词中除首次字外剩余部分组成的按内码顺序排序的有序表。

4）双哈希索引树中的节点用DictSegment类来表示。其中，DictSegment类的单元结构如下。

（1）keyChar（4bit）：当前节点对应的字符。

（2）nodeState（1bit）：到词节点的前缀部分是否为词，nodestate=1为词，nodestate=0不为词。

（3）point（4bit）：获取下一层存储结构的容器对象，null代表叶子节点，词组组成结束。

（4）nMaxLength（4bit）：该首字开始的最长词条长度，一般用于首字。

（5）nWordType：词条的词性，一般用于词典正文。

（6）nFrequenery：词条使用的频率，一般用于词典正文。核心词典的逻辑结构如表2所示。

表2 部分关键字对应AMCTT结构

双字hash 索引可以使查询速度和存储空间达到最优。如：“啊呀/啊哈/大案要案/大青虫/大坝/大白鼠/大白天说梦话”构成本文提出的AMCTT 词典树如图1所示。

图1 双字哈希索引分词词典机制（正向）

双字Hash 在查找某一个词语时，首先要进行词语首字的查找，获得相对应的以次字为首字的最大词长，并根据具体的词长获得次字的Hash 值，进而得到次字和剩余字串，从而得到所要查找的词语。这样的查找方法可以快速准确地获得所查询的词语在词典中的精确位置，减少了不必要的过程，缩短了查询词语的时间，提高了分词的效率，在分词速度上要优于基于传统词典的中文分词方法。

3 歧义消解

歧义现象指一种形式对应着两种或两种以上的解释，在人类丰富的自然语言中充斥着大量的歧义现象。汉语由于缺乏严格意义的形态变化，语法形式和语法意义之间的对应关系错综复杂，因此歧义现象比形态发达的语言更具有普遍性。

使用双向最大匹配分别对原始语料进行切分。双向最大匹配是从左到右和从右到左将待分词文本中的几个连续字符与词表匹配，如果匹配上，并且保证下一个扫描不是词表中的词或词的前缀则切分出一个词。结合词性和词频信息，有两种方法进行词组歧义消解：

1）词频消解：由m 个汉字组成的歧义切分字段C=c1c2...cm有两种切分结果W=w1w2...wn和V=v1v2...vk。

则选择切分结果W，若

则选择切分结果V；其中，frq(w)表示词w的频率。

单纯使用词频信息，没有考虑到词性及词义信息，更没有考虑到不同词性和词义之间的概率转移关系，错误率高。对于低频字不能正确切分。

例：他的确切菜了

错误切分结果：他/的/确切/菜/了。所以需要结合词性信息共同切分。

2）动词消解：对于交集型歧义，即对于字段C=c1c2c3，c1c2∈C，C 为词表，则称C 为交集型歧义。对于这样的歧义，根据中文的规则，如果交集词的前面的词在动词词典中，则直接将该词切分为c1c2/c3，如果后面的词在动词词典中，则将该词切分为c1/c2c3。

显然，切为动词，例句正确切分为他/的确/切/菜/了。

4 实验分析比较

系统环境是core2 i7、双核8G 内存、win7 64位、jdk 1.7 普通pc 坏境。通用词典来自搜狐研发中心发布的搜狗实验室数据（http：//www.sogou.com/labs/resource/w.php），其中词频和词性是Sogou 搜索引擎索引到的中文互联网语料统计出的15 万条高频词，统计时间是2006 年10 月。数据格式示例如表3所示。

表3 词典中数据格式示例

4.1 评价指标说明

本文采用准确率、召回率及F 值作为评价指标。

准确率：

其中tp为分析结果中正确的数目，fp为分析结果中错误的数据量。

召回率：

其中tp为分析结果中正确的数目，fn为正确的但是没有被识别出的数目。使用调和平均值表现出准确率和召回率的共同效果。

调和平均值：

4.2 词典分词比较

从文件中读取词典信息、词频和词性信息及原始语料，放入内存中。

测试1：为使测评结果尽量公平，我们从互联网上下载5 篇不同领域的测试语料作为样本，平均大小为60KB。

1）本文将所构建的词典机制（图中样本中右面第一个）与常用的3 种词典机制（图中样本从左往右依次为：基于整词二分法的词典构造机制，基于Trie 索引树的词典构造机制和基于逐字二分的词典构造机制）进行比较，采用相同的测试样本进行中文分词，具体数据如图2所示。

图2 不同词典分词时间对比

通过不同分词方法的比较和分词效率的分析，本文方法的分词速度相比于其他分词词典的速度有了一定的提高。

2）得出的测试结果如表4所示。

表4 词典加载方法数据对比

根据测试1、测试2，使用传统的基于词典的正向最大匹配法和反向最大匹配法的测评结果与本文方法进行比较：使用改进的正向最大匹配分词算法［9］及中国科学院计算研究所研制的汉语词法分词系统ICTCLAS（http：//ictclas.nlpir.org）的分词结果进行对比，结果如表5所示。

表5 匹配方法数据对比

本文大体上解决了由于机械匹配产生的歧义字段的识别不足问题，可以得出：使用双字哈希词典加载，结合词频和词性进行分词消歧的方法得出的调和平均数明显高于其他方法。

该方法在搜索引擎、自动问答系统、电子邮件过滤、信息检索与信息摘录、文本分类和自动摘要、自然语言理解等需要对无上下文信息预料进行切分的实际运用领域中具有较强的实用性。既能够不使用上下文信息，又能准确提取出需要的词语信息，也不需要各领域的语料作为训练对象，是一种通用高效的中文分词方法。

5 结语

在没有上下文信息或许上下文信息匮乏的情况下，显然不能使用统计学知识进行分词。本文提出用改进Trie 树的双字Hash 词典提高分词速度，再用词典中记载的词频词性信息进行分词的歧义消解，提高了分词的准确率。也存在以下需要改进的方面：

1）本文提出的根据词频和词性的歧义消解只能消解一部分歧义，一些非正式场合没有严格根据构词法使用语句，可能需要运用调节语序，更换词语等方法再进行歧义消解。

2）缺少上下文，组合型歧义和真歧义没有办法解决。

3）分词词典的覆盖面以及测试语料的选取对分词的结果有很大影响，所以下一步的研究重点是如何把专业词典和未登录词典附加到通用词典中，以此为基础，在不同领域以及不同大小的语料中进行分词，更加全面地证明本文方法在分词中的优势。