中文自动分词机制研究

中文自动分词机制研究

1中朝文本分词词典机制的研究汉语词典的研究是语文信息处理的基础工作。它在许多领域的中文自动分词、文本检索、机器翻译和中文机器理解等应用价值非常高。国内自80年代中后期就开展了中文分词词典机制的研究,目前已有的分词词典机制主要有:基于整词二分的分词词典机制、基于TRIE索引树的分词词典机制和基于逐词二分的分词词典机制。第2部分详细介绍这三种分词词典机制,并对其进行了比较;第3部分通过对汉字编码体系、汉语词特点的分析,充分发挥了现代计算机内存大空间的优势,提出了四字哈希机制,给出了分词词典的结构和分词词典的查找算法,提高了分词的速度和效率。2现有的词典机制2.1典中表文本设计该机制的词典结构分为词典正文、词索引表、首字散列表等三级。词典正文是以词为单位的有序表,词索引表是指向词典正文中每个词的指针表。通过首字散列表的哈希定位和词索引表很容易确定指定词在词典正文中的可能位置范围,进而在词典正文中通过整词二分进行定位。2.2tre索引树机制TRIE索引树是一种以树的多重链表形式表示的键树。基于TRIE索引树的分词词典机制由首字散列表和TRIE索引树结点两部分组成。TRIE索引树的优点是在对被切分语句的一次扫描过程中,不需预知待查询词的长度,沿着树链逐字匹配即可;缺点是它的构造和维护比较复杂,而且都是单词树枝(一条树枝仅代表一个词),浪费了一定的空间。2.3逐字第二部分分匹配这种词典机制是前两种机制的一种改进方案。逐字二分与整词二分的词典结构完全一样,只是查询过程有所区别:逐字二分吸收了TRIE索引树的查询优势,即采用的是“逐字匹配”,而不是整词二分的“全词匹配”,这就一定程度地提高了匹配的效率。但由于采用的仍是整词二分的词典结构,使效率的提高受到很大的局限。2.4查询效率较高通过对3种分词词典的介绍可以看出,整词二分和TRIE索引树是分词词典机制的两种极端。前者的数据结构简单、占用空间小,构建及维护也简单易行,但由于采用全词匹配的查询过程,效率低下,后者的数据结构复杂、空间浪费较为严重,树的构造和维护也较为繁琐,但它采用的查询过程是“逐字匹配”,所以查询效率较高。第三种分词词典机制(基于逐字二分)虽然采用了较为高效的匹配方法――逐字匹配,但并没有改进“整词二分”的数据结构,使得匹配过程并不是完全意义上的逐字匹配,这就导致查询效率并没有得到最大限度的提高。3字哈希机制文献对汉语中的词条分布进行了统计,具体情况见表1:由上表可以看出,中文词语中双字词语最多,三字词语和四字词语也较多,随着现代计算机硬件技术的提高,计算机内存大、空间大,笔者觉得有必要对文献双字哈希机制扩展到四字哈希机制,这样可以发挥计算机内存大空间的优势,最大限度的提高匹配的时间效率。3.1汉字在编码表中的偏移量实现Hash算法的关键是有效地分配空间和实现Hash映射。实现Hash映射时,词与词之间存在地址冲突问题,所以除分配当前空间供Hash映射用,还要分配有备用空间,用来存放地址有冲突的词。备用空间有两种设置方案:一是为每个地址设置备用空间,紧随当前空间放置,这样可确保有冲突时,搜索的空间小、次数少,缺点是整个备用空间占用量大;二是同一首字下所有相同的词分配一个备用池,这种分配法空间占用量小,但当词之间存在冲突时,要在备用池中查找,搜索匹配次数多。汉字在计算机内部是以内码的形式进行存储的,汉字内码是汉字在汉字信息处理系统中最基本的表达形式,它与汉字交换码、汉字区位码有一定的对应关系。由于自定义编码顺序的特殊性,因此可以通过计算偏移量的方法来定义该汉字在编码表中任意的位置。国标GB2312汉字编码表共收录了6763个汉字,汉字在编码表中的偏移量计算公式如下:offset=(c1-0xB0)*94+(c2-0xA1)①其中,offset代表某汉字在汉字编码表中的位置,c1、c2分别代表汉字的内部码(c1代表内部码的高字节,c2代表内部码的低字节)。本文中的地址分配空间采用的是为每个地址设置备用空间,首字Hash索引是采用汉字内码来计算的。3.2单词分类词典的结构四字让字数的个数首字Hash索引中的每个单元包括下面几项内容:(1)关键字:词的第一个汉字;(2)是否为词:标志单个首字是否为词;(3)2-Pre-F:是否为2字词的前缀;(4)3-Pre-F:是否为3字词的前缀;(5)4-Pre-F:是否为4字词的前缀;(6)m-Pre-F:是否为多字词的前缀;(7)次字Hash表指针;(8)以该首字为前缀的双字词的个数;(9)三字Hash表指针;(10)以前两字为前缀的三字词的个数;(11)四字Hash表指针;(12)以前三字为前缀的四字词的个数;(13)多字Hash表指针。两个汉字的类型次字Hash索引中的每个单元包括下面几项内容:(1)关键字:词的前两个汉字;(2)是否为词:标志前两个汉字是否为词;(3)3-Pre-F:是否为3字词的前缀;(4)4-Pre-F:是否为4字词的前缀;(5)m-Pre-F:是否为多字词的前缀;(6)三字Hash表指针;(7)以前两字为前缀的三字词的个数;(8)四字Hash表指针;(9)以前三字为前缀的四字词的个数;(10)多字Hash表指针。前三个汉字的数和表的数字化三字Hash索引中的每个单元包括下面几项内容:(1)关键字:词的前三个汉字;(2)是否为词:标志前三个汉字是否为词;(3)4-Pre-F:是否为4字词的前缀;(4)m-Pre-F:是否为多字词的前缀;(5)四字Hash表指针;(6)以前三字为前缀的四字词的个数;(7)多字Hash表指针。近充字2字四字Hash索引中的每个单元包括下面几项内容:(1)关键字:词的前四个汉字;(2)是否为词:标志前四个汉字是否为词;(3)m-Pre-F:是否为多字词的前缀;(4)多字Hash表指针。有序两组学习剩余字串组是以前四个汉字起始的所有词语的剩余字串有序数组,每个单元包括两项内容:(1)剩余字串:除去词的前四个汉字的剩余部分;(2)是否为词:标示从第一个汉字A至对应位置的子串是否也构成一个词。3.3词典中的搜索算法由“前前字”至“前字”的产生,网“就”首先计算字串的首字在编码表中的偏移量(即为相应的Hash地址),如果首字前缀关系都为0,则表明此字不为任何词的前缀,可以独立成词,将其切分出来。否则,增字,进入2字词的查找;前2字作词切出根据首字Hash索引单元中的次字Hash表指针定位次字Hash索引单元,如果是否为词标志为0并且也不是其他词的前缀(如果所有的前缀关系标志都为0,则表明该2字词不是其他词的前缀),将首字切出;否则,查看相应的成词标志,如果能独立成词,且与3字词、4字词和多字词不存在前缀关系,则将字串中的前2字作为词切出。否则,增字进行跳跃查询。例如:与3字词和4字词不构成前缀关系,但与多字词构成前缀关系,则可以1次增3字进入多字表进行查询。若同时与不同长度的词构成前缀关系,则按3字词、4字词和多字词表的顺序进行查找;单元有关为0且不与其他词的前置关系根据次字Hash索引单元中的三字Hash表指针定位四字Hash索引单元,如果是否为词标志为0并且也不是其他词的前缀,则将前2字切出;否则,若前3字独立成词并且不与其他词构成前缀关系,则将前3字切出;否则,根据前缀关系标志判断是独立成词,还是进入4字词、多字词的查找;4个单词的搜索与3字词的查找类似;由独立成词标志的前5字如果在剩余字串数组中查不到,则将前4字切出;否则,如果独立成词标志为0,则将前5字切出;否则,增字再次进入多字词的查找,直到所有的词都被切分为止。4分词词典结构设计本文首先对现有的中文分词词典机制进行了简单的介绍,然后在对中文编码体系和中文词语特点分析的基础上,充分发挥现代计算机内存大空