汉语自动分词的词典机制

汉语自动分词的词典机制

0自动分词处理分词依据中文信息处理包括文献探索、机器翻译、文献分类、文献过滤、自动编辑等。与印欧语不同，汉字是“字”的字符串，所以汉语和汉语之间没有区别。利用计算机处理中文信息时,往往涉及到词的问题,即书面汉语中的词的切分问题。所谓汉语自动分词,是把输入计算机的汉语词句自动切分为词的序列的过程。特定情况下分词结果中也包括一些词组和词素。由于现代汉语缺乏明显的形态标志,词素组合成词也没有严格的规律遵循,从而给自动分词带来很大的困难。本文首先简单描述了已有的分词词典机制,接着介绍了我们提出的新的词典机制——一种基于双哈希二叉树的索引结构,最后对新的机制和已有的机制进行了比较和实验分析。1分词算法的研究方法迄今为止人们己经提出了许多计算机自动分词算法,根据研究方法的出发点不同,可以归纳为三大类:基于词典的分词方法、基于统计的分词方法、基于AI的分词方法。1.1基于词典的分词方法这种分词方法是前苏联专家在上个世纪50年代末提出来的,由于该分词方法是使用词典作为分词依据,故称为基于词典的分词方法。其基本思想是:事先建立一词库,其中包含所有可能出现的词。对给定的待分词的汉字串S,按照某种确定的原则切取S的子串,若该子串与词库中的某词条相匹配,则该子串是词,继续分割剩余的部分,直到剩余部分为空;否则,该子串不是词,转上重新切取S的子串进行匹配。1.2相邻之间的频率或概率计算汉语语言文字较之西文的一个显著区别是:词与词之间没有显著的分隔标记。还有一个很难缠的问题是:“什么是词?”“汉语中究竟有多少个词”,这样就产生了基于统计的分词方法,又称为无词典分词方法。这类方法的主要依据和思想是:词是稳定的字的组合,因此在上下文中,相邻的字同时出现的越多,就越有可能构成一个词。因此字与字相邻共现的频率或概率就能够较好地反映成词的可信度。可以对语料中相邻共现的各个字的组合的频度进行统计,计算它们的互现信息。互现信息体现了汉字之间结合关系的紧密程度。当紧密程度高于某一个阈值时,便可以认为此字的组合可能构成了一个词。基于统计的分词方法优点在于,能够有效地自动排除歧义,能够识别新词、怪词,例如人名、地名等,解决了基于字典的分词方法的弊病。但这种方法也有一定的局限性,会经常抽出一些共现频度高,但并不是词的常用字组,例如“这一”、“之一”、“有的”、“我的”、“许多的”等,并且对常用词的识别精度差,时空开销大。一般的应用中,我们一般是将其与基于词典的分词方法结合起来,即发挥匹配分词切分速度快、效率高的特点,又利用了无词典分词结合上下文识别生词、自动消除歧义的优点1.3根据ai的价格分布方法将专家系统和神经网络应用到中文自动分词中来提高分词的智能性,是近年来研究的一个热点。2现有的词典机制传统的分词词典机制有5种。下面我们简单介绍一下。(1)词典信息编码如图1所示,该机制的词典结构分为首字Hash表、词索引表、词典正文三级。词典正文是以词为单位的有序表,词索引表是指向词典正文中每个词的指针表。通过首字散列表的哈希定位和词索引表很容易确定指定词在词典正文中的可能位置范围,进而在词典正文中通过整词二分进行定位。(2)树的分词词典机制TRIE索引树是一种以树的多重链表形式表示的键树。如图2所示,基于TRIE索引树的分词词典机制由首字散列表和TRIE索引树结点两部分组成。TRIE索引树的优点是在对被切分语句的一次扫描过程中,不需预知待查询词的长度,沿着树链逐字匹配即可;缺点是它的构造和维护比较复杂,而且都是单词树枝(一条树枝仅代表一个词),浪费了一定的空间。(3)逐字第二部分分匹配这种词典机制是前两种机制的一种改进方案。逐字二分与整词二分的词典结构完全一样,只是查询过程有所区别:逐字二分吸收了TRIE索引树的查询优势,即采用的是“逐字匹配”,而不是整词二分的“全词匹配”,这就一定程度地提高了匹配的效率。但由于采用的仍是整词二分的词典结构,使效率的提高受到很大的局限。(4)模式1:顺序搜寻、二元追踪如图3所示,在词典中对于特定的首字,前两字相同的词条很少,前三字相同的词条更少。当以这种形式组织词典后,除子表的第一层外,各个节点的兄弟数目都很小,对它们的查找采用顺序查找方法较为适宜。对于子表的第一层,则采用二分查找。由于无法在一个纯粹的链表结构中进行二分查找,为此,可以将子表的首层节点以动态数组形式组织,或装入容器类的可直接存取的线性表结构中。显然,这实际上是将词典以二叉树的形式组织起来,只是于该文算法。同一首字下的所有词条组织成的子表的查找,应各节点中增加了接收状态。分词使用该词典不会出现同一词条的重复比较,在字表首层以下的搜索过程中,每次搜索的范围因词典的组织方式变化而大大缩小,这也在一定程度上提高了分词效率。(5)“双确定”下的哈希索引,“双下垫型”的词典和未收词型,2该机制吸纳了”整词二分”及”TRIE索引树”二者的优点,仅对词语的前两个字顺次建立哈希索引,构成深度仅为2的TRIE子树,词的剩余字串按序组成类似”整词二分”的词典正文,词典结构如图4所示。3改进的词典组织3.1分词词典机制从第2节中对5种典型词典机制的介绍可以看出:整词二分和TRIE索引树是分词词典机制的两个极端。整词二分的数据结构简单、占用空间小,构建及维护也简单易行,但由于采用全词匹配的查询过程,效率低下;TRIE索引树的数据结构复杂、空间浪费较为严重,树的构造和维护也较为繁琐,但它采用的查询过程是“逐字匹配”,所以查询效率较高。第三种分词词典机制(基于逐字二分)虽然采用了较为高效的匹配方法——逐字匹配,但并没有改进“整词二分”的数据结构,使得匹配过程并不是完全意义上的逐字匹配,这就导致查询效率并没有得到最大限度的提高。第四种分词词典机制(基于自动机)实际上是将词典以二叉树的形式组织起来,只是各节点中增加了接收状态。依此算法,显然不会出现同一词条中的重复比较,且每次比较的字符串(一个汉字)长度均为2。与算法1、算法2和算法3相比,在子表首层以下的搜索过程中,每次搜索的范围因词典的组织方式变化而大大缩小,这也在一定程度上提高了分词效率。为了最大限度的提高匹配的时间效率并兼顾空间利用率,我们提出了一种新的分词词典机制———基于双哈希二叉树的分词词典机制。3.2字典结构1计算哈希地址的确定首字Hash索引的每个单元包括三项内容:①关键字:词的第一个汉字A;②p值:存储次字Hash的p值;③次字Hash索引指针:指向以汉字A起始的所有词语的第二个汉字的索引。采用除留余数法计算哈希地址首字哈希表的单元:Typedefstruct{CharFirstKey;Intp;Tnode*FChild;}FHnode;2字串近接口字次字Hash索引的每个单元包括一项内容:剩余字串指针:指向以A为首字且次字Hash地址同为i的字结点组成的单链表;Typedefstruct{Tnode*Head;}SHnode;3叉树结构结点的数据结构如下定义:Typedefstruct{Tnode*LBrother;CharKey;BooleanAccepted;Tnode*RChild;}Tnode,*Pnode;在该结构中,LBrother为兄弟链,指向出现概率较本结点小的字,Accepted为T时表示独立成词,为F时表示不独立成词,RChild为孩子链,指向下一个出现概率最大的字,如图5所示。3.3算法描述1odl的编码在此算法中,单个汉字的哈希值H=VmodL,其中V是此汉字的内码,L是Hashtable的可变表长,L的初始值取常数initCapacity。(1)选取内码中心上的哈希汉字在计算机内采用内码来存储,而汉字的内码具有唯一性和连续性,因此对于首字哈希,V值我们选取汉字内码,L值我们选取合适的质数p,使哈希地址与汉字一一对应。(2)哈希表的编码和重组以某个汉字开头的非单字词,多则几百个少则几个,甚至一个,如果对第二个字进行哈希存储,则表长不能一概而论,如图5所示,此算法采用链地址法来处理溢出情况,它把哈希表中储存的所有关键码划分为L个子集合(桶),具有同一个哈希值H(0≤H≤L-1)的表项均被置于第H个桶中;同一个桶中的不同表项通过指针存储在一个单链表中。当哈希表中储存的所有表项总数C满足C/L>loadFactor时,此算法令L=2×L+1,并对哈希表进行重组,其中loadFactor是满足0<loadFactor<1的常数。在本实验中,我们令初始表长initCapacity和装添因子上限loadFactor均取缺省值,即令initCapacity=11,loadFactor=0.75。(3)c型的rhild指导思想中,a次字哈希表中的一个表项指向一棵二叉树,该二叉树的根结点是以AB为前两个字的词中出现概率最大的第三个字,我们称该结点为C,它的LBrother指针指向的结点的字的出现概率较C结点小,它的RChild指针指向的结点是以ABC为头三个字的词中出现概率最大的第四个字。如果以AB开头的词只有AB本身,则该二叉树为空。2rchild指导思想①取出待分词文章的第一个字A,将A存入一个长度为17的空数组W中,经过哈希运算求出哈希地址i,在首字哈希表中找到相应的位置i,如果该位置的指针域为空,则该字是一个单字词,设标志位F=1,计数位S=1,继续①。否则②。②取下一个字B,计数位S加1,经过哈希运算求出哈希地址,在次字哈希表中找到相应的位置,在相应的单向链表中查找第二个字所对应的结点,如果找到相应的结点,将B字顺次存入数组W中,判断该结点的Accepted域是否为T,F=S,转向③。如果找不到,则A是一个单字词。转向①。③如果该结点的Rchild域为空,则数组W中的前F个字成词,转向①。否则,取下一个字C,计数位S加1,与相应的结点的Rchild指针指向的结点比较,如果相等,判断该结点的Accepted域是否为T,为T,F=S,转向③;如果不等,转向④。④如果待分词文章结束,则转向⑥。否则,如果相应结点的Lchild指针为空,则数组W中的前F个字成词,转向①。否则,指针指向该结点的Lchild域指向的结点,如果相等,判断该结点的Accepted域是否为T,为T,F=S,转向③;如果不等,转向④。⑤如果待分词文章结束,则转向⑥。否则,如果相应结点的左指针为空,则数组W中的前F个字成词,转向①。继续比较。如果相等,转向④。如果不等,转向⑤。⑥结束。例如:源文本“这个谎言将大白于天下。”分词结果=“这个/谎言/将/大白于天下”以“大白于天下”为例介绍一下分词过程:(1)取“大”字,将“大”字存入空数组W,F=1,S=1,在首字Hash表中直接定位,如果该位置的指针域为空,则该字是一个单字词,否则(2)。(2)取“白”字,将“白”字顺次存入空数组W,S=2,在“大”字指向的次字hash表中定位,沿着单向链表找到“白”字,“白”字的Accepted域为T,F=S。(3)取“于”字,将“于”字顺次存入空数组W,S=3,“白”字结点的RChild指针指向的结点等于“于”。(4)取“天”字,将“天”字顺次存入空数组W,S=4,“于”字结点的RChild指针指向的结点等于“天”。(5)取“下”字,将“下”字顺次存入空数组W,S=5,“天”字结点的RChild指针指向的结点等于“下”。“下”字的Accepted域为T,F=S。待分词文章结束。(6)所以数组中从“大”字开始的前F个字成词,即“大白于天下”是一个词。4种词典机制的比较基于逐字二分的词典机制是基于整词二分和基于TRIBE索引树的分词词典机制的一种改进方案。逐字二分与整词二分的词典结构完全一样,只是查询过程有所区别:逐字二分吸收了TRIE索引树的查询优势,即采用的是“逐字匹配”,而不是整词二分的“全词匹配”,这就一定程度地提高了匹配的效率。所以我们在实验时没有考虑基于整词二分和基于TRIBE索引树的分词词典机制。我们分时间和空间两个方面来对基于逐字二分的词典机制、基于自动机的词典机制、基于双字哈希的词典机制、基于双哈希二叉树的分词词典机制的四种词典机制进行分析比较,后面依次称为算法1、算法2、算法3、算法4。从空间复杂度的角度来考虑算法1所占空间最小,算法4最大,由于空间复杂度是一次性消费,而分词的速度取决于平均比较次数,所以下面从时间复杂度的角度考虑:本次实验采用的是windows2003server,奔腾Ⅲ,800M主频,1GB内存,Java语言编程实现。实验采用的语料是3.23MB的文本,对于上述4种词典机制采用正向最大匹配方法,实验结果如表1所示。从该表可以看出算法2至算法4无论从时间上还是从比较次数上都大大优于算法1,而其中算法4为最佳,究其原因是算法4综合了算法2和算法3的优点,因为字典中两个字的词居多,所以我采用首字和次字哈希索引,对于两字词可