基于词典的中文自动分词系统

基于词典的中文自动分词系统

1基于词典的体系综合优化随着个人计算机和internet网络的普及，中文信息的处理变得一个非常重要的领域。中文字务用户使用的许多软件和硬件都与中文信息处理有关。我们必须建立自己的中文信息处理系统。许多辅助软件是巨大的开发成本。由于许多辅助软件的独立开发导致中文处理的水平不高，因此开发一种统一、共享、高水平的中国信息处理系统非常重要。基于该词典的自动汉语排序技术在中文信息处理中占有基本地位。在公共汉语处理系统中，需要平衡不同方面的性能需求。提高调查操作的空间和时间效率非常重要。近年来提出的许多中文句子算法重视不同方面的性能改善，需要充分考虑性能优化，并在实践中不断提高性能。随着社会的发展，新词和短语的产生，多语混合的词条和包含特定符号的词条也大量使用。新字典无法满足人们的工作量和生活需求。快速正确地在词典中添加新词（短语），对基本无用的旧词进行分类是非常重要的。此外，在之前的分词系统项目中，考虑到大量使用快速减速对计算算法的影响最大的原因。在一些算法测试中，结果是非常可疑的，不同的结论在不同的方面是矛盾的。因此，本文提出了综合优化的原则，从更全面的角度评估了几种典型算法，并提出了一种综合优化的分词系统。2查词为编码查询在文献中,孙茂松等提出了评价分词系统的3种基本查询操作:(1)指定词查找;(2)最长词查找;(3)全部词查找.该体系被许多论文引用,影响较大.本文中为了综合性能,希望词典能够根据指针快速定位每一个词条,比如根据词条属性,反查出某词条后,要能够快速给出该词条的汉字串.即第四种查询方法:(4)词的字符串查询.具体描述如下:查询方式1(指定词查找):在分词词典中查找指定词W0(词在分词词典中的定位);这是一种最基本的查询方式.给定词W0,返回W0在分词词典中的位置,以便得到W0的各类附属信息.此时W0是确定的,所以可以简单地通过二分查找给出结果.查询方式2(最长词查找):根据分词词典,在汉字串S中查找从某一指定位置i开始的最长词Wi,max(对应最大匹配分词法);有别于查询方式1,这里最长词Wi,max无法预知,需要在查询过程中动态地确定.通常的做法是尝试始于位置i的所有可能长度的词,多次运用查询方式1来完成查询.查询方式3(全部词查找):根据分词词典,在汉字串S中查找从某一指定位置i开始的所有的词Wi,1;Wi,2;……;Wi,max(对应全切分分词法)查询方式4(词的字符串查询):根据词典中词条的位置,查找该词的字符串.即词典正文的存储方式要恰当.为了评估词典维护的方便性,增加词、删除词和编辑词条的性能也是重要的评价指标.3般优化原则算法在数学上的优化是第一步,也是最关键的.本质上不同的算法,差别极大,在查询中依次比较查找是最慢的;二分查找改进很大,但要求被查询的集合中的元素是有序的,如果元素本身排序困难,则需要进行编码,然后建立索引,这在空间上花了一定的代价;根据指针查找数组是最快的,但指针的计算不要太复杂,如果数组太稀疏,则空间的开销太大.第二步是算法的运用.比如在最长词查找时,通常的做法是尝试始于某位置的所有可能长度的词,多次运用指定词查询来试探,速度很慢.这就是算法应用不当造成的.实际上以最大长度的试探词进行第一次指定词查询失败的位置离要查找的最长词很近了,第二次的试探完全可以在更小的查询范围和更限定的试探词选择情况下进行,从而大大地提高效率.本文在后面还有详述.第三步是算法在计算机上实现的优化.下面主要讨论现代计算机技术带来的一般优化原则.近年来,计算机技术得到飞速发展,各个部件的性能都大大提高.但是CPU的计算速度提高的幅度远远高于内存数据的读写速度,为了减少CPU等待数据的时间,CPU中设计了芯片内的一级缓存,同时在计算机中还设计了二级缓存(可以与CPU同频也可以不同频),这个趋势将维持相当长的时间,目前使用最多的Intel奔腾系列处理器和PC体系架构就使用了这种设计.这充分说明各种算法的优化必须主要考虑如何减少CPU与内存的数据交换,如何使CPU需要的数据能够预取(Prefetch)到缓存中,然后才是CPU内部计算指令的优化.Intel编写的《IA-32Intel®架构优化参考手册》中提出了许多数据预取的优化原则,一些优化建议如下:—Minimizeuseofglobalvariablesandpointers(尽量少地使用全局变量和全局指针)—Minimizeuseofcomplexcontrolflow(尽量少地使用复杂的控制流)—MinimizememorybankconflictsbyapplyingarraygroupingtogroupcontiguouslyuseddatatogetherorallocatingdataWithin4KBmemorypages.(运用连续的数组或将数据定位在4KB内存页范围内以尽量地减少内存栈的冲突)—Faraheadenoughtoallowinterimcomputationtooverlapmemoryaccesstime.(尽可能地用内部计算代替内存读写的时间)—Nearenoughthattheprefetcheddataisnotreplacedfromthedatacache.(数据尽量靠近以避免预取到缓存的数据被代替)词典的各种查询算法涉及到字串比较、指针计算、寻址、内存读写,以及算术和逻辑运算等.在CISC类型的CPU中(比如Intel奔腾系列处理器),加法和逻辑运算很快;比较操作等同于减法,比加法略慢;片内一级缓存的读写相当于加法;乘法比加法慢许多,但在CISC类型的CPU中专门有乘法的硬件优化设计,比以前通过多次加法来实现乘法的算法快不少;二级缓存的读写与乘法相当;除法和取模运算更慢一些;内存中数据的读写最慢,常常是速度提高得主要瓶颈.4以三部分三用于词典的属性表1分词系统需要尽可能少地占用存储空间,使词典和词条的重要属性可以全部存放在内存中;还要考虑主要查询操作读写词典时,方便数据预取到缓存中,同时,词典的数据结构要方便主要的查询和维护操作的算法实现.实质上,词典由4部分组成:(1)词典正文,存放词条的字符串和指向该词条的属性;(2)词条属性:存放词条对应的主要属性和指向词条正文中该词条的位置的指针;(3)首字散列表:国家标准用于计算机进行汉字处理的汉字和符号的序列,根据汉字的机内码可以方便和唯一地确定汉字在序列中的位置;(4)索引:用于搜索某字符串是否在词典正文中的辅助数据,根据搜索算法的不同,索引部分有较大区别,可以是二分查找的索引表,可以是TRIE索引树,也可以是PATRICIA搜索树,还可以是单字或多字的哈希散列索引表,实际上常常是几种索引的组合.下面介绍两种经典的词典数据结构,并分析如何按照方便缓存预取的方式进行优化.4.1确定使用表1.文献所叙述的基于整词二分的分词词典机制如图1所示,该机制的词典结构分为词典正文,词索引表,首字散列表等3部分.词典正文是以词为单位的有序表,词索引表是指向词典正文中每个词的指针表.通过首字散列表的哈希定位和词索引表很容易确定指定词在词典正文中的可能位置范围,通过词索引表和词典正文的配合,很容易实现指定词在词典正文中的整词二分进行快速查找定位.在图1中,词索引表是1个连续的数组,其实可以按照首字的不同,最多可以分成6763不同的小数组,也可以把一些太小的邻近数组合成1个较大的数组,希望这些分散的数组都小于4KB,而且它们对应的词典正文也连续排列,也小于4KB,好将它们预取到缓存.对于某个首字对应的索引数组或词典正文大于4KB时,可以采用其他种种技术手段将其划分为更小的数组.4.2按文本个数分的方法,有以下简称TRIE索引树是一种以树的多重链表形式表示的键树,面向中文的TRIE索引树的结点应允许指针个数变化.基于TRIE树的分词词典由两部分组成(见图2).第一部分为首字散列表,对应汉字的单元包括TRIE大小(2字节)和指向该汉字的TRIE索引树的根结点指针(4字节).第二部分为TRIE索引树结点,是一个按关键字排序的数组(方便二分查找):每个单元包括:关键字(2字节):单一汉字;子树大小(2字节):以从根结点到当前单元的关键字组成的子串为前缀的词的个数;子树指针(4字节):子树大小非0时,指针指向子树;否则指向叶子.由于TRIE索引树已蕴涵了词条信息,因此词典中可以不必显式地罗列词条,可直接存储词的附属信息(叶子指针直接指向这些信息).但是为了快速进行查询方式4(词的字符串查询)操作,叶子指针指向的存储单元还是需要显式地列出词条内容.TRIE索引树的结构本身就是分成一个个按关键字排序的小数组,非常适合预取到缓存中进行二分查找.5一些搜索算法的介绍5.1最坏时的编码算法二分查找算法是一个相当好的简便算法,其基本思想来将N个元素的有序集合分成个数大致相同的两半,取第[N/2]个元素与待测的元素作比较,决定待测的元素在哪个半区,然后依次递归.整个算法在最坏情况下的计算复杂性为O(㏒n).当查找的索引范围比较小,索引可以一次性放入缓存并且关键字(词)包含在索引中时,该算法比PATRICIA树搜索算法略好,因为PATRICIA树搜索是不平均的二叉树,所以分支节点的深度要大于二分查找;如果关键字(词)要通过索引指针从内存中毒去,但存放相当集中,可以一次放入缓存,则增加一次内存读取就行,那么就比PATRICIA树略差一点.5.2多对待表项的连接基于词典机制的哈希索引的实现过程中,往往用单个汉字做取模的哈西索引,单个汉字的哈希值H=VmodL,其中V是此汉字的内码,L是Hash表的可变表长.对于两个汉字组合的哈希值计算可以是H=V1×V2modL,V1和V2对应两个汉字的机内码.但是当汉字串再长一些,多个机内码相乘会很快溢出,必须设计专门的算法才能进行,所以很少被使用.哈西索引算法常采用链地址法来处理溢出情况,它把哈希表中储存的所有关键码划分为L个子集合(桶),具有同一个哈希值H的表项均被置于第H个桶中;同一个桶中的不同表项通过一个单链表进行连接.理想分布是桶与字一一对应;正常分布有接近2/3的桶对应一个或多个汉字,1/3为空;最差的分布是一个桶对应所有汉字,其他桶为空.这就需要通过选择恰当的表长L使哈希索引接近理想情况.在关键码相互独立的假设下,统计意义上,正常分布出现的概率最大.为了避免最差分布出现,关键码数应该是一个大数,实际工作中20就可以看作为大数,100是比较保险的阈值.哈希索引算法的过程是:(1)通过待查询词S,取出指定的汉字,计算该字的哈希值H;(2)读出H指向的词条T和指向下一个相同哈希值的词条的指针P,如果T为空,停止;(3)比较T和S,如果相同,查询成功,停止;如果不同,读出P指向的新T和新P,重复(3)直到T为空便停止.对于哈希索引算法,需要在CPU内对S做一些比较复杂的取模运算,与内存的存取速度相比就是非常快的,所以理想情况的哈希索引算法最好,只需要根据哈西值H从内存中的桶中读取关键字与S比较,就完成了;对于正常情况,有时需要几次读取关键字和指针,如果同一个桶中的后续关键字在内存中存放得足够近,在读第二个关键字时,其它关键字也会被预取到缓存,则以后再读关键字时,就在缓存中了,所以平均来看仍是非常快的;对于最坏情况,则还不如不用哈希算法,就是直接用最笨的依次比较算法也会更好.5.3根据信息的方向,选择合适的位串和转向抗辩事由PATRICIAtree本质上是一种压缩的二叉查询树,它将关键词作为二进制位串记录在树的结构中,从根结点到叶子结点的每一条路径都代表一个关键词位串.在PATRICIAtree中,关键词的具体信息都保存在叶子结点上,PATRICIAtree的内部结点则用来记录关键词的路径,它有3个基本的数据项:比较位、左指针、右指针,其中,左指针和右指针分别指向该结点的左、右子树,比较位记录的是从根结点到达该结点的所有位串中第一个不相同位的位置.判断查询词是否存在于词典中,只须从PATRICIAtree的根结点出发,根据查询词位串(包括结尾处的‘0’)在PATRICIAtree中寻找路径.当比较位为0时,位串转向左子树,当比较位为1时,位串转向右子树.若比较完所有位后,查询词位串不能到达叶子结点,则可以断定该查询词不在词典中.在查询词位串到达叶子结点时,由于只对查询词中某几位进行了比较,并不能保证查询词与叶子结点中的关键词一定是相同的,在这种情况下,还要对两者进行一次字符串的比较,相同才表明查询成功.对于PATRICIA树搜索算法,首先要从内存读取根节点的比较位和转向指针,作简单的比较运算,再读取子节点的比较位和转向指针,经过多次比较与读取,到达叶节点读取词条.如果整个PATRICIA树比较小,在内存中的安排又符合数据预取的条件,则经过第一次从内存读取根节点数据的操作,就可以把整个整个PATRICIA树的全部内部节点放在缓存中,多次的比较位和转向指针的读取就在缓存中操作,相当于多次的加法运算,可能5次左右的读取与比较相当于一次哈希索引的取模运算,则7次左右相当于相同哈希值的关键码的平均数为2得正常分布的哈希索引计算,叶节点的词条内容一般还需一次内存的读取;如果PATRICIA树很大,不能一次性放入缓存,则多次的内存读操作会将速度降得很慢.所以尽量地切分PATRICIA树,使其足够小时很重要的.PATRICIA树在增加新词和删除旧词方面非常方便.增加新词X时,先建立X的叶结点,搜索一次PATRICIA树找到最接近的词条S,然后从头比较出X和S的第一个不同位t,然后再搜索一次PATRICIA树路径,到达t位时,插入一个新节点n,将父节点指向同路径的指针继承指向原来的子节点,使父节点指向新节点n,新节点n的另一条路经指向新词X.对待删除词Y进行一次查询,找到待删除词存在的叶子结点,将此叶子结点及其父结点从树中删除,将其父结点的另一个子树(或叶子结点)直接连在其祖父结点上.当PATRICIAtree只有一根结点和两个叶子结点时,只删除待删除词所在的叶子结点.针对缓存优化的几种情况的搜索算法的比较见表1.根据以上的分析,理想和正常分布下的哈希索引很好,但是差的分布下它又很差,这在搜索范围很小时出现的概率较大,这时使用PATRICIA树(小)或者二分查找(小)会更好.6哈希拉索tri索引国标GB2312汉字编码表就是一个理想的哈希索引表,共收录了6763个汉字,根据汉字的机内码,汉字在编码表中的位置h=(c1-0xB0)×94+(c2-0xA1),其中,h代表某汉字在编码表中的位置(就是哈希值),c1、c2代表该汉字的机内码.在基于词典的各种具体中文分词软件的实现中都应该利用首字哈希散列表提高效率,同时缩小搜索范围.基于TRIE索引树的分词词典数据结构,是逐字搜索来定位一个词的,每一个字的二分查找都可以用哈希索引代替二分查找来提高效率,对于相同哈希值的关键字还可以用二分查找.对于小于32个搜索项的二分查找就不该用哈希索引了,这时平均来看,哈希索引并不比二分查找更优.6.1查检行为中使用的问题文献给出了一个整词二分法进行查询方式2(最长词查找)的例子:[例1]查询S“水怪大白天现形一个多小时这个令人惊异的消息不径而走.”中从“大”字开始的最长的词.(1)取从“大”字开头最长可能的汉字串:wi,max=“大白天现形一个多小时这个令人惊异的”(词典中最长词为17个汉字);(2)用整词二分法在词典中查找候选词wi,max,失败;(3)去掉wi,max最后一个字,重复步骤(2),失败;(4)..(5)经过14次的错误尝试,wi,max最终消减到“大白天”,查找成功,于是返回wi,max=“大白天”.首先分析这14次的查找失败(图3).在同一位置的14次查找失败,显然这样的查找效率是低下的,这也就是各种分词词典机制比整词二分效率高很多的原因.由二分法的查找过程知道,在一次查找失败中最后区间的两个端点数据与所要查找的数据最为接近.简单的查询优化是,在每次查找失败时,再次查找时遵守新的规则:失败位置的最后区间的low端(索引号靠前面)的词与所要查询的词从首字开始依次比较相同位置的汉字直到不相同为止,记录相同汉字的个数作为下次查询的长度,范围缩小为首字指向的起点到失败的位置,如果长度与low端的词的长度相等,那么low端的词就是要找的最长词.上例采用这种方式来查询,在经过一次查询后,第二次查询的汉字长为3个汉字的长度,这样就只要查询“大白天”,再次查找显然就查找成功了.经过这样的处理,查询效率提高很多.对于最长词大于2个字时,优化后的整词二分优于逐字二分,甚至还优于TRIE索引树;对于最长词为2个字时,优化后的整词二分与逐字二分相当.文献中的逐字二分法有错误,在进行最长词查询时,文中的停止条件有误.修正错误后,在各种查询时,逐字二分法应该都差于TRIE索引树.6.2优化后的整词二分法测试李庆虎等提出了双字哈希机制的中文分词算法,基本思路正确,但是在首字哈希索引的建立中错误地用取模的哈希算法,反而降低了效率.应该直接用国标的汉字编码表.在剩余字串的数据结构中没有词条的索引,只能进行逐条比较,算法很差;这时,完全可以采用优化后的整词二分法.他们的测试中TRIE索引树算法、逐字二分算法和双字Hash索引都采用Java语言在相同的软硬件环境(OS:WindoWs2000Server;JDK:Version11311;CPU:PentiumIII667MHz;Memory:256M)来实现,得出空间占用,TRIE索引树>双字Hash索引>整词二分=逐字二分;速度,双字Hash索引>TRIE索引树>逐字二分>整词二分的结论;这个结论与孙茂松等的结论有矛盾,但李庆虎等没有给出说明.在速度方面,TRIE索引树>逐字二分的结论正确.6.3基于空间占用比整词东南角的空间占用算法杨文峰等提出基于PATRICIAtree的汉语自动分词算法,并与逐字二分算法进行了测试比较,得出查询速度有一定提高(30-50%),添加词条和删除词条的速度有本质提高(4-8倍)的结论;通过计算,得出空间占用比整词二分算法和TRIE索引树算法大的结论.马哲、姚敏采用首字哈希散列表方法改进了基于PATRICIAt