中文快速分词方法

《中文快速分词方法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、一种基于自动机的分词方法摘要本文介绍一种简洁有效的快速分词方法，并通过理论分析和实验对比说明几种分词方法的效率差异，以说明我们所提出的方法的有效性。关键词：中文信息处理，分词，顺序查找，二分查找，自动机，二叉树分类号：TP文献标识码1引言西方语言在语句（或从句）内词汇之间存在分割符（空格），而汉语的词汇在语句中是连续排列的。因此，汉语词汇的切分（分词）在中文信息处理的许多应用领域，如机器翻译、文献检索、文献分类、文献过滤、以及词频统计等，是非常重要的第一步。自动分词是基于字符串匹配的原理进行的。迄今为止，已经

2、有许多文献对各种分词方法进行探讨，其着重点或为分词的速度方面，或为分词的精度方面以及分词的规范。本文主要探讨分词的速度问题，通过实验对比和理论分析，说明我们所提出的算法是有效的。目前人们所提出的分词方法，在考虑效率问题时，通常在词典的组织方面进行某种调整，以适应相应的算法，如最大匹配法、最小匹配法、逐词遍历法、以及最佳匹配法等。这些方法中，或将词典按词条长度排序或按词频排序，其目的在于协调算法与数据结构，使之效率最高。客观地说，它们都在一定程度上提高了分词的效率。本文所介绍的是基于词典的最大向前匹配方法。而在

3、数据结构方面，我们则是将词典组织成自动机形式。2数据结构与算法文献[1，2，3]给出了三种基于词典的最大向前匹配方法的分词算法（相应于文献编号，我们以后分别称其对应的算法为算法1、算法2、和算法3）。我们可以把算法1看作是原始算法，把算法2看作是算法1的改进，而算法3则是算法2的进一步优化。在词典的组织方面，算法2和算法3是按照正常的词典排序（即按汉字的机器内码表示排序），并辅以词条的首字索引，以标明以该字起始词条在词典中的首记录。例如，在一般的词典中，词条的形式如下图所示：图1：一般分词词典的形式啊啊哈啊呀

4、啊哟阿阿爸阿斗阿尔巴尼亚阿飞阿富汗…在实际存储时，可以在词尾部分删除首字。这样做不仅节省了存储空间，更重要的是缩短了字符串比较的长度。算法2和算法3对首字的检索都是基于哈希算法；算法2对于词尾部分采用线性搜索，而算法3则采用二分搜索。采用何种搜索算法应根据所用词典中每个首字下的词条数目确定，一般词条数较小时，二者无明显差异。这是由这两种算法本身的特性决定的。实际词典中许多首字下的词条数目很大，因此，采用二分搜索法较优。我们的实验结果也证实了这一点。算法2和算法3在词典的组织方面是一致的，即如同普通词典一样，按

5、照汉字的内码递增排序，并以词条的首字建立哈希索引。我们可以将同一首字下的所有词条组织成一个子表结构，如下图所示。图2：词典的逻辑结构索引子表…饱私囊…华华民国华民族华人民共和国…中…假设：源文本source_text=“中华人民共和国成立于1949年。”分词结果=“中华人民共和国/成立/于/1949/年/。”分词过程为：1.从源文本source_text中取首字head_word=“中”，并设置已切分词汇segmented_word=head_word；2.从索引中查找该首字。若未找到，则暂将该字作为单字词输

6、出；否则，将其后续字符加入临时变量tail_word=“华”；3.在以“中”为首字的子表中查找包含tail_word的词条；若查到，则从source_text中取字，继续加入tail_word中，并继续在子表中查找。在此过程中，如果满足条件的词条等于当前的tail_word，则置segmented_word=head_word+tail_word；4.步骤3中的查找失败时，则以当前segmented_word中的字符串作为输出结果。算法2和算法3的处理思想是一致的，只是在上述第三步的查找中，算法2采用的是顺序

7、查找，而算法3采用的是二分查找。在本例中，tail_word从“华”递增到“华人民共和国”的过程中，即使不计查找过程中的比较次数，tail_word与词典中的子表项“华”字比较了1次，同“华人民共和国”比较了5次。其比较长度分别为2、4、6、8、10、12。“华”（segmented_word=“中华”）“华人”“华人民”“华人民共”“华人民共和”“华人民共和国”（segmented_word=“中华人民共和国”）显然，这种比较过程存在冗余的比较操作。例如，“人”字比较了5次，其中后4次的比较是多余的。因为字

8、符串比较所需的时间同字符串的长度成正比，对于较长的词条，这种现象尤为突出。为了消除这种冗余操作，我们提出将词典的词尾部分以自动机的形式来组织。为此，我们将组成单词的每个字以一种链表节点的形式存储，其抽象数据结构的定义如下：Pnode=^Tnode;Tnode=recordBrother:Pnode;Cchar:String[2];Accepted:Boolean;Child:Pnode;End;这样