最大匹配中文分词算法在垂直搜索引擎中的应用

1、最大匹配中文分词算法在垂直搜索引擎中的应用李晓红（邵阳医学高等专科学校 湖南邵阳 422000）摘要：中文分词对垂直搜索引擎的意义不容忽视，本文结合顺序表和跳跃表，提出一种改进的整词分词词典结构，探讨一种基于最大匹配的分词算法，将哈希法和二分法进行分词匹配，并引入随机数。实验表明，该算法具有较高的分词效率和准确率，性能较好。关键词：分词词典；分词算法；哈希法；垂直搜索application on vertical search engines of chinese word segmentation based on the maximum matchli xiao-hong(shaoyang

2、 medical college hunan shaoyang 422000)abstract：chinese word segmentation is important to vertical search engines, this article combined with the sequence table and leaping, proposed an improvement structure of segmentation dictionary. discussed an arithmetic based on segmentation algorithm for maxi

3、mum matching. hashing and binary search is used to segmentation match for enquiring, and i introducing the random number.experiment indicates that the arithmetic can improve the speed of chinese segmentation and precision.key words: segmentation dictionary; segmentation algorithm; hashing; vertical

4、search1、引言21世纪的飞速发展,人们已无法离开互联网这个共享信息的平台。然互联网的共享信息也成爆炸性膨胀。在这种背景下,搜索引擎技术以其界面友好、使用方便成为目前不可或缺的检索工具。传统搜索引擎已不能满足特定用户的需要，垂直搜索引擎的诞生解决了广大用户对某种特定需求的搜索和解决。在专业，精度和深度方面，垂直搜索确实比传统搜索略胜一筹。在用户的体验程度上垂直搜索引擎能更好的贴近用户的使用，用户满意度良好。先来看看垂直搜索引擎的结构。2、垂直搜索引擎体系结构垂直搜索引擎基础体系结构及运行原理包括搜索器(spider/crawler)、索引器(indexer)和检索器(searcher)1。

5、搜索引擎利用spider/crawler获取网页,用indexer解析和索引页面,用searcher利用web服务器(web server)来响应用户的查询请求【作者简介】李晓红(1980)，女，大学本科，讲师，主要从事计算机网络教学与研究。查询结果用户界面检索 器查询索引索引 器网页信息分析器分 词 器本 地 磁 盘网络蜘蛛web图1：垂直搜索体系结构进行检索7。从图1中我们可以看出，搜索引擎通过解析器将网页内容读入内存后，首先对其进行分词虽然分词只是垂直搜索中很小的一个模块，可是它将直接影响用户的体验，有文献资料指出，如果设计一个垂直搜索引擎，给分词部分安排十个人工作都不算多，可见现今的搜

6、索引擎不仅仅只是满足搜索信息量大，内容多，而是如何让用户使用之后感觉这个搜索就是能更好体现用户的意图。3、中文分词近10年来， 众多专家在汉语自动分词与自动标引上进行了许多的研究，也找到了许多方法，如最大匹配法、逐词遍历法、高频优先分词法等。但由于中文语言的复杂性，自动分词技术还一直处于发展阶段。再者由于现在开源的蜘蛛有nutch和lucence，目前最新版本的lucence，对最大匹配中文分词算法能较好的支持，因此本文试将最大匹配算法与概率算法结合起来，并应用到垂直搜索引擎当中，以期找到一种准确、高效的中文自动分词算法，提高搜索引擎的的效率，与用户体验程度。 3.1、词典结构 在分析最大匹配

7、算法之前，先开看看汉语分词的词典机制。现在已有3种汉语分词词典机制：基于整词二分的分词词典机制，基于trie 索引树的分词词典机制，基于逐字二分的分词词典机制。本方法采用顺序词表和跳跃词表相结合的一种改进的整词二分的分词词典机制，有效减少词典空间实现快速查询，如图 1 所示。 索引项链式词表二字词表三字词表顺序词表多字词表图1 词典机制词典结构主要由 2 个部分组成，即词首字索引表和词典正文。 (1)词首字索引表 词首字索引表的结构是：按区位码的hash 散列存储。 根据汉字系统区位码、 与机内码的换算关系，散列的词首字索引节点可以根据汉字的机内码采用下式获得： pos(c1c2)=pos0(

8、c1-176)94+(c2-161)l 其中，pos0 为词首字索引表起始地址；c1, c2 分别为词首字机内码第 1 个和第 2 个字节的无符号数；l 为词首字索引节点大小。(2)词典正文 词典正文采用顺序存储和链式存储相结合的存储结构。二字词和三字词采用有序顺序表来存储。多字词表采用跳跃表来存储，如图 2 所示。跳跃表是在有序链表的部分节点处增设附加指针以提高其搜索性能。 201多字词1多字词2多字词mlni图2 3.2、字典查询过程 若给定待查询的汉字串 str= s1s2sn。根据词首字索引节点地址计算公式求得 s1 在首字索引表中的位置，读取该节点的数据。查询过程如下： (1)若最长

9、词词长 lmax1，则词表非空，转(2)；否则词表为空，s1 为单字词，查询中止。 (2)若 k=2，则根据索引项中二字词数 ntw，以及二、三字词顺序表指针 spointer，用二分法进行查找，若找到，则返回 true，否则返回 false。 (3)若 k=3，则在 spointer+ntwspoinnter+ntw+nth 中用二分法查找；处理方式同(2)。 (4)若 k3，则根据多字词链表指针 lpointer，在跳跃表中查找。跳跃表的搜索从最高级开始，逐级搜索，搜索过程类似二叉搜索树的查找。若找到，则返回 true，否则返回false。 (5)返回。 4、自动分词算法 4.1、基于最大

10、匹配的概率算法 由于汉语词的长度差异大，有的多字词长度达十几个汉字，而单字成词长度为 1。最大匹配算法的初始切分长度常为词典最长词条的汉字数 m，如此切分和匹配影响了算法效率。另外，二字词和三字词在汉语词中占有相当大的比例，而以词首字开始的二字词、三字词和多字词的数量能够反映出词首字开始的词为二字词、三字词和多字词的可能性。因此， 在最大匹配算法中引进随机数得到最大匹配的概率算法，并以词首字最长词长 lmax 为最大切分限界值。 设待切分的语料汉字串 str=s1s2sn。基于最大匹配的概率算法描述如下： (1)取 s1，通过 hash 映射，找到词首字索引项，获取相关数据。 (2)若 lma

11、x=1，则 s1 为词首字的词表为空，则将 s1 切分出来。令 str=s2s3sn，继续下一次切分；若 lmax1，则计算： sno= ntw(二字词数量)+nth(三字词数量)+nmlt(多字词数量) (3)产生 1sno 范围内的随机数：x=randmon(sno) (4)case xntw，取 k=2；case xntw+nth，取 k=3；case xlength(stmp2)，则得到切分词：stmp1，否则，得到切分词：s1/stemp2。 (6)移动汉字串指针，进行下一次切分，直到整个串切分完成。 例如：切分句子“当中国人民解放军成立的时候” 。首先取词首字为“当” ，得到 st

12、mp1=“当中” ，然而以“中”为词首字时得到 stmp2= “中国人民解放军” ， 由于 length(stmp1)length(stmp2)，则切分为： “当/中华人民共和国/成立” 。继续后面的切分，最后得到的切分为： “当/中国人民解放军/成立/的/时候” 。 4.2、歧义词的消去 汉语不同于其他的语言，一句话产生歧义的时候经常发生。为了正确切分真实的汉语文本语料，必须对歧义字段进行处理，消去歧义切分词。 定义 1(歧义字段) 一个汉字串存在不同的切分形式，则称该汉字串为歧义切分字段，简称歧义字段。 根据歧义字段的构成形式可分为 2 种基本类型：交集型歧义切分字段和组合型歧义切分字段。

13、其中，交集型歧义切分字段又占全部歧义切分字段的绝大多数。 定义 2 对于歧义字段 s=abc(a, b 和 c 为字串)，若 ab和 bc 都是词，则字段 s 称为交集型歧义切分字段，b 称为交集字段，len(b)称为链长。 定义 3 对于歧义字段 s=ab，若 a, b 和 ab 三者都分别成词，则 ab 为组合型歧义切分字段。其中，a, b 为字串。 另外，还有多义型和混合型等歧义字段。在交集型歧义字段中，链长为 1 和 2 的歧义字段，两者合计占到了歧义字段的 97.61%。由于交集型歧义切分字段又占全部歧义切分字段的绝大多数，因此本文采用基于统计模型的方法进行，对交集型歧义字段进行处理

14、。 该算法过程如下： (1)多次运用概率算法，得到每一次的切分结果(且每次可随机选取mm 法或rmm 法)； (2)比较每次切分结果，记录无歧义切分结果； (3)找出所有歧义字段，统计切分词出现的频度，选出频度最高的切分词； (4)对歧义字段剩余部分再进行统计，直到整理完毕。 5、实验结果 通过编写一个小型垂直搜索引擎，将该中文分词模块放入分词部分，通过实验，实验数据来源于从新浪网下载的新闻等共 1 000 篇文章。根据文章的大小，从每个类别中各抽出5篇文章，分派到5组中，作为测试集，且每组文档大小大致相同。测试环境为 p4/3.0 ghz/1 gb。实验数据如表实验结果数据平均文档大小/字平

15、均分词数量/词平均出错词/数平均分词速度（词秒-1）平均词（准确率/（%）364142241268094.1507200321240094.21102532601180094.31490649921220394.4通过测试，一般出错的词语大多是人名、地名和专用词，这些出错是不可完全避免。实验结果表明，基于最大匹配的概率算法的平均分词速度达到了约 12000 词/秒，平均分词准确率达到 94%以上。分词准确率与文档长度有一定的关系， 当对文档长度增加时，分词的准确率略有提高。6、结束语 中文自动分词技术在垂直搜索引擎中有着重要的作用。分析表明，本文提出的一种改进的整词分词的字典机制占用内容空间小，算法的平均时间复杂度低，具有较高查询的效率。该方法的引入很好的对中文文本语料实现了自动切分，相对传统的机械分词算法，对歧义词的消去也有较好的性能。 参考文献1 baeza-yates r, ribeiro-neto b. modern information retrieval.china machine process, 20042 文庭孝. 汉语自动分词研究进展j. 图书与情报, 2005, (5): 54-62. 3 张海营. 全二分快速自动分词算法构建j. 现代图书情报技术, 2007, (4): 5