一种基于组合ash索引的分词机制

一种基于组合ash索引的分词机制

0分词方式的选择中国的自动分词是中文信息处理的前提，在中文信息处理的各个领域得到了广泛应用。由于汉语书面语不像西方文字那样词与词之间有特定的分隔标记,而是连续的汉字串,如何自动识别词边界,将汉字串切分为正确词串的汉语自动分词问题无疑是实现中文信息处理中各项任务的首要问题。因此,汉语分词的任务就是将句子中的词自动切分出来,即通过计算机程序识别出句子中的词,并用分词标志符号分隔开。从计算机处理过程上看,分词系统的输入是连续的字符串(C1C2C3C4……Cn),输出是汉语的词串(W1W2W3……Wm)。这里,Wi可以是单字词也可以是多字词。目前对汉语分词方法的研究主要有三个方面,一是基于词表的分词,这是一种有着广泛应用的机械分词方法,该方法依据一个分词词表和一个基本的切分评估原则,即“长词优先”原则来进行分词。这种切分方法,需要最少的语言资源,程序实现简单,开发周期短,是一个简单实用的方法。二是基于统计语言模型(SLM)的分词,该方法首先切分出与词表匹配的所有可能的词,这种切分方法称为“全切分”,运用统计语言模型和决策算法决定最优的切分结果。这类方法的优点是可以发现所有的切分歧义,但是解决歧义的方法很大程度上取决于统计语言模型的精度和决策算法,需要大量的标注语料,并且分词速度也因搜索空间的增大而有所缓慢。三是基于人工智能技术的分词,分词过程是对人脑思维方式的模拟,试图用数字模型来逼近人们对语言认识的过程,理论上是最理想的分词方法。由于汉语自然语言复杂灵活,知识表示困难,基于人工智能的中文自动分词技术还处于起步阶段。根据具体应用领域的不同需求,分词系统常在分词精度和速度上做出选择,要提高速度,就要适当放弃精度的追求,缩减词典,减少匹配次数。而要提高切分精度,就得舍弃速度,无限扩充词典,匹配次数也会无限增加。本文研究的出发点在于保持基于词典的现有分词精度上,提高分词的速度,在第1节介绍几种基于词典的常用中文自动分词算法,第2节提出了一种新的分词词典机制并设计出相应的分词算法——组合Hash索引分词算法,第3节给出对比实验结果,第4节是结束语。1基于字典的分词算法的总结1.1配合算法dmm最大匹配算法(MaximumMatchingMethod,简称MM法)是一种广泛应用的机械分词方法,按其匹配的方向分为正向最大匹配法(MMB)和逆向最大匹配(RMMB)。该算法的基本思想是:事先给定一个最大可能词的长度MAX,分词时首先取出长度为MAX的待分词的汉字串S,若该字串与词库中的词匹配成功,则该字串是词,否则按正向或逆向取MAX-1的子串继续进行匹配,直到子串为空。最大匹配算法通常采用整词二分的匹配策略,因此有词典构造简单,易于实现等特点,但其MAX值需事先确定,若MAX设置过大,造成大量无用的匹配过程,若MAX过小,则无法覆盖所有可能长度的词。算法依托的词典主要由两部分组成,首字散列表和正文词典。结构如图1所示:1.2根控制至中心基于TRIE索引树的逐字匹配算法可以避免上述算法中最大词长的缺点,通常该算法是建立在树型词典机制上,匹配的过程是从索引树的根结点依次同步匹配待查词中的每个字,可以看成是对树某一分枝的遍历。因此,采用该算法的分词速度优于上一种方法,但树的构造和维护比较复杂。词典结构主要有两部分:根结点和其余结点。根结点是一个首字散列表,同整词二分中的首字散列表类似,唯一的区别是指针域少了一个,只含首项入口指针,用来指明所有次字的入口地址;其余结点由许多有序的TRIE索引树结点组成,如图2所示:1.3最大匹配实验词典逐字二分匹配算法是前两种算法的结合,它吸取最大匹配算法词典结构简单、TRIE索引树算法查询速度快的优点。因此词典结构和最大匹配词典构造机制相似,区别在于词典正文前增加了多级索引。匹配过程类似TRIE索引树进行逐字匹配,在性能上和TRIE索引树相近。另外,在文献中提出的双字哈希算法,结合了整词二分,TRIE索引树的优点,通过二级哈希索引表实现逐字匹配,降低了词典组织的复杂度,提高了分词的速度,但哈希表的构建过程和维护仍然比较复杂。2组合hish索引分词算法,现代分词算法中常用的分词算法分词设计三从上一节的介绍可以看出TRIE索引树的词典机制有较好的查词效率,但数据结构比较复杂,树的构造和维护比较繁琐,为了最大限度提高匹配的时间效率,简化词典构造难度,以下提出一种新的分词词典机制,并设计出相应的分词算法——组合Hash索引分词算法。2.1索引表的构造Hash算法通过散列函数直接确定数据项的位置,在理想状况下,查找操作的运行时间可以达到常数时间的目标。其性能的优劣取决于选择合适的散列函数,常用的散列函数有相除散列法、平方取中散列法、相乘散列法等。然而,这几种散列函数通常是以整数值作为关键字,在本文中,关键字是汉字字符串,因此须要设计以汉字字符串为关键字的散列函数。在索引表的构造过程中,采用了.NET内置的Hashtable类,Hashtable由包含集合元素的存储桶组成。存储桶是Hashtable中各元素的虚拟子组,与大多数集合中进行的搜索和检索相比,它可令搜索和检索更简单、更快速。每一存储桶都与一个哈希代码关联,该哈希代码是使用哈希函数生成的并基于该元素的键。当把某个元素添加到Hashtable时,将根据键的哈希代码将该元素放入存储桶中。该键的后续查找将使用键的哈希代码只在一个特定存储桶中搜索,这将大大减少为查找一个元素所需的键的比较次数。2.2定义及数据结构根据学者的统计,一字词和二字词的出现频率约占总词数的94%,三字以上约占6%。若以字串的前两字为关键字建立Hash索引表,多数词用一次匹配就能切分出来,在前两字确定的情况下,用二分法查找剩余字的平均匹配次数小于2次,根据这样的特点,我们在图2的基础上把词典聚合成两个部分,由图2中的部分合并生成以词前两字为关键字的Hash索引表,由图2中部分合并生成一维结点数组。如图3所示。为了叙述的方便,首先给出定义:定义:给定字串a0a1a2a3a4……an,ai表示第i个字符,称为第i字,a0至ai-1间的字符被称为ai的前缀字符,ai-1是ai的第一前缀,ai-2是ai的第二前缀,依此类推;ai+1至an间的字符被称为ai的后缀字符,ai+1是ai的第一后缀,ai+2是ai的第二后缀,依此类推。主要数据结构:1)Hash索引结点①关键字:由二字以上词的首字和次字组合而成,如“中国”、“中国菜”、“中国画”、“中国人”、“中国人民”的索引结点关键字是“中国”。关键字是唯一的。②词标志:标志关键字是否是词,-1表示非词,0表示是词。③第三字首指针:指明以关键字为前缀的所有第三字在剩余结点数组中的索引起始位置,当值为-1时表示关键字没有后缀。④第三字尾指针:指明以关键字为前缀的所有第三字在剩余结点数组中的索引结束位置。2)剩余字串数组结点:①关键字:去除词前两字的其它字,如“中国菜”,关键字是“菜”。②词标志:当值为-1时表示非词,当值i>=1时表示是词且关键字是词中的第i个字符。③第一后缀首指针:指明以当前关键字为第一前缀的所有字首索引位置,当值等于-1时表示到达词尾。④第一后缀尾指针:指明以当前关键字为第一前缀的所有字尾索引位置。2.3查询strtem的方法输入:连续的字符串Str=c1c2c3……cn,N是字符串长度。输出:是汉语的词串W=(w1w2w3……wk),K是词个数。变量说明:intT:查询指针,指向新词的识别的起始位置,初始值为0;intM:移动指针,指向待匹配字位置,初始值为T;intWordFlag:表示到第几个字成词;intStart:后缀入口指针;intEnd:后缀尾指针;stringSubstr:从待查词中截取的子串。算法描述:(1)若查询指针T小于N,反复执行以下过程;(2)初始化WordFlag为1,移动指针M为T;(3)若入口指针为-1,返回长度为WordFlag的词到W中,增加分词标记,查询指针T向后移动m,跳(2);(4)每次以M为基准起点取长度为1的子串strtem,strtem追加到Substr中;(5)若M=T,判断strtem是否为非汉字编码,识别长度为L的英文词、数字、和标点符号等非汉字字符,查询指针下移L,跳(2);(6)否则若M=T+1,在hash索引表中查询strtem,若匹配成功,返回后缀首尾指针Start、End,WordFlag置为2,跳(8);(7)若M>T+1,在(Start,End)之间进行二分查询,跳(8);(8)二分查询成功,得到下一后缀的入口指针和尾指针,若词标志不为-1,词标志赋予WordFlag,否则二分查询失败,返回长度为WordFlag的词到W中,增加分词标记,查询指针向后移动WordFlag步,跳(2);(9)返回W,查询结束。词匹配示例:如对“中国人民从此站起来了”进行分词。假定查询指针已指向“中”的位置。1)取字串“中国”作为关键词进行Hash匹配,匹配成功,返回第一后缀首尾指针Start,End。2)取字串“人”作为关键字,在剩余字串结点数组的Start到End范围内进行快速二分查找,匹配成功,返回第二后缀首尾指针Start,End。3)取字串“民”作为关键字,在剩余字串结点数组的Start,End索引范围内进行二分快速匹配,匹配成功,首尾指针等于-1,查询结束,返回“中国人民”。4)查询指针指向“从”的位置,取字串“从此”作为关键字进行Hash匹配,匹配成功,返回第一后缀首尾指针Start,End。5)取字串“站”作为关键字,在剩余字串结点数组的Start到End范围内进行快速二分查找,匹配失败。“从此”是词,返回“从此”。6)查询指针指向“站”的位置,取字串“站起”作为关键字进行Hash匹配,匹配成功,返回第一后缀首尾指针Start,End。7)取字串“来”作为关键字,在剩余字串结点数组的Start到End范围内进行快速二分查找,匹配成功,返回第二后缀首尾指针Start,End。8)取字串“了”作为关键字,在剩余字串结点数组的Start,End索引范围内进行二分快速匹配,匹配失败,“站起来”是词,返回“站起来”。9)查询指针指向“了”的位置,未切分子串长度不足2,返回“了“,分词结束。从词典的结构及上面的示例中可以看出,词典的Hash索引表关键字是词的第一字和第二字。匹配过程的第一次比较便截取字串的前两个字符进行hash匹配,匹配不成功说明是单字词或者是非汉字字符,匹配成功说明是多字词,若返回的指针域不为-1,再在剩余字串结点数组的相应索引范围内用快速二分法进行第三字以上的匹配查找。3实验分析3.1et技术构建分词系统是在Windows2000操作系统平台下,基于.Net技术构建,词典词条数21,8252条。我们从2000年《人民日报》中随机选取了2个文本,分别进行了整词二分、TRIE索引树算法、组合Hash索引分词算法的对比实验,实验数据见表1:3.2总结点长度和匹配次数一字词的匹配次数:hash索引表匹配不成功时表示关键字的第一字是一字词,因此匹配次数为1。二字词以上的匹配次数分两种情况:①无后缀:此时hash索引表匹配成功,匹配次数为1。②有后缀:平均匹配次数按公式(1)计算n+1n1b(n+1)−1(1)n+1n1b(n+1)-1(1)Hash表总结点长度为142557个,其中有后缀结点92532个,两字有后缀的平均宽度为0.649,代入(1)式,第三字的平均匹配次数为0.834;第四字总长度为42348,平均宽度0.457,第四字平均匹配次数为0.565;四字以上总长度2170,平均宽度0.051,二分查找四字以上词的平均匹配次数为0.041。理论分析表明,切分2字以上词的平均匹配次数少于文献的1.56、1.66各1.08。从实验的结果可以看出,在时间性能上,基于TRIE索引树和组合Hash索引的分词算法比整词二分算法时间效率上有显著提高,组合Hash索引分词算法的处理速度较整词二分平均提高了13.8倍,较TRIE索引树平均提高了2.7倍,并且词典的数据结构比TRIE索引