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

最大匹配中文分词算法在垂直搜索引擎中的应用 李晓红 (邵阳医学高等专科学校 湖南邵阳 422000) 摘要:中文分词对垂直搜索引擎的意义不容忽视，本文结合顺序 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 和跳跃表，提出一种改进的整词分词词典结构，探讨一种基于最大匹配的分词算法，将哈希法和二分法进行分词匹配，并引入随机数。实验表明，该算法具有较高的分词效率和准确率，性能较好。 关键词:分词词典;分词算法;哈希法;垂直搜索 Application on Vertical search engines of Chinese Word Segmentation Based on the Maximum Match Li Xiao-hong (Shaoyang 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 maximum 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 search 1、引言 21世纪的飞速发展,人们已无法离开互联网这个共享信息的平台。然互联网的共享信息也成爆炸性膨胀。在这种背景下,搜索引擎技术以其界面友好、使用方便成为目前不可或缺的检索工具。传统搜索引擎已不能满足特定用户的需要，垂直搜索引擎的诞生解决了广大用户对某种特定需求的搜索和解决。在专业，精度和深度方面，垂直搜索确实比传统搜索略胜一筹。在用户的体验程度上垂直搜索引擎能更好的贴近用户的使用，用户满意度良好。先来看看垂直搜索引擎的结构。 2、垂直搜索引擎体系结构 垂直搜索引擎基础体系结构及运行原理包括搜索器(Spider/Crawler)、索引器(Indexer)和检索器(Searcher)[1]。搜索引擎利用Spider/Crawler获取网页,用Indexer解析和索引页面,用Searcher利用Web服务器(Web Server)来响应用户的查询请求 【作者简介】李晓红(1980,)，女，大学本科，讲师，主要从事计算机网络教学与研究。 WEB 网络蜘蛛 用户界 面 图1:垂直搜索体系结构 ]。从图1中我们可以看出，搜索引擎通过解析器将网页 内容 财务内部控制制度的内容财务内部控制制度的内容人员招聘与配置的内容项目成本控制的内容消防安全演练内容 读入内进行检索[7 存后，首先对其进行分词虽然分词只是垂直搜索中很小的一个模块，可是它将直接影响用户的体验，有文献资料指出，如果 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 一个垂直搜索引擎，给分词部分安排十个人工作都不算多，可见现今的搜索引擎不仅仅只是满足搜索信息量大，内容多，而是如何让用户使用之后感觉这个搜索就是能更好体现用户的意图。 3、中文分词 近10年来， 众多专家在汉语自动分词与自动标引上进行了许多的研究，也找到了许多方法，如最大匹配法、逐词遍历法、高频优先分词法等。但由于中文语言的复杂性，自动分词技术还一直处于发展阶段。再者由于现在开源的蜘蛛有Nutch和Lucence，目前最新版本的Lucence，对最大匹配中文分词算法能较好的支持，因此本文试将最大匹配算法与概率算法结合起来，并应用到垂直搜索引擎当中，以期找到一种准确、高效的中文自动分词算法，提高搜索引擎的的效率，与用户体验程度。 3.1、词典结构 在分析最大匹配算法之前，先开看看汉语分词的词典机制。现在已有3种汉语分词词典机制:基于整词二分的分词词典机制，基于TRIE 索引树的分词词典机制，基于逐字二分的分词词典机制。本方法采用顺序词表和跳跃词表相结合的一种改进的整词二分的分词词典机制，有效减少词典空间实现快速查询，如图 1 所示。 索引二字词表 三字词表 顺序词表 项 链式词表 多字词表 图1 词典机制 词典结构主要由 2 个部分组成，即词首字索引表和词典正文。 (1)词首字索引表 词首字索引表的结构是:按区位码的Hash 散列存储。 根据汉字系统区位码、 与机内码的换算关系，散列的词首字索引节点可以根据汉字的机内码采用下式获得: Pos(C1C2)=Pos0，((C1-176)×94+(C2-161))×L 其中，Pos0 为词首字索引表起始地址;C1, C2 分别为词首字机内码第 1 个和第 2 个字节的无符号数;L 为词首字索引节点大小。 (2)词典正文 典正文采用顺序存储和链式存储相结合的存储结构。二字词和三字词采用词 有序顺序表来存储。多字词表采用跳跃表来存储，如图 2 所示。跳跃表是在有序链表的部分节点处增设附加指针以提高其搜索性能。 2 L 1 I 多字词多字词2 多字词0 N 1 m 图2 3.2、字典查询过程 若给定待查询的汉字串 Str= S1S2„Sn。根据词首字索引节点地址计算公式求得 S1 在首字索引表中的位置，读取该节点的数据。查询过程如下: (1)若最长词词长 Lmax>1，则词表非空，转(2);否则词表为空，S1 为单字词，查询中止。 k=2，则根据索引项中二字词数 Ntw，以及二、三字词顺序表指针 SPointer，(2)若 用二分法进行查找，若找到，则返回 True，否则返回 False。 (3)若 k=3，则在 SPointer+Ntw~SPoinnter+Ntw+Nth 中用二分法查找;处理方式同(2)。 (4)若 k>3，则根据多字词链表指针 LPointer，在跳跃表中查找。跳跃表的搜索从最高级开始，逐级搜索，搜索过程类似二叉搜索树的查找。若找到，则返回 True，否则返回False。 (5)返回。 4、自动分词算法 4.1、基于最大匹配的概率算法 由于汉语词的长度差异大，有的多字词长度达十几个汉字，而单字成词长度为 1。最大匹配算法的初始切分长度常为词典最长词条的汉字数 M，如此切分和匹配影响了算法效率。另外，二字词和三字词在汉语词中占有相当大的比例，而以词首字开始的二字词、三字词和多字词的数量能够反映出词首字开始的词为二字词、三字词和多字词的可能性。因此， 在最大匹配算法中引进随机数得到最大匹配的概率算法，并以词首字最长词长 Lmax 为最大切分限界值。 设待切分的语料汉字串 Str=S1S2„Sn。基于最大匹配的概率算法描述如下: (1)取 S1，通过 Hash 映射，找到词首字索引项，获取相关数据。 (2)若 Lmax=1，则 S1 为词首字的词表为空，则将 S1 切分出来。令 Str=S2S3„Sn，继续下一次切分;若 Lmax>1，则计算: SNo= Ntw(二字词数量)+Nth(三字词数量)+Nmlt(多字词数量) (3)产生 1~SNo 范围内的随机数:X=Randmon(SNo) (4)Case X?Ntw，取 k=2;Case X?Ntw+Nth，取 k=3;Case X< Ntw+Nth+Nmlt，则取 k=Lmax。 (5)取 Str1=S1S2„Sk，在字典中查找 Str1: 1)若 Str1 不是词，重新产生随机数，获取余下的 k 值，继续在字典中查找，直到查找成功。若所有 k 值查找都不成功，则 S1 在此处可视为 1 个单字词，得到切分 S1/S2S3„Sn。同时可通过人工干预方式，将词首字为 S1 的一个子串作为新词，将其插入到多字词链表。 2)Str1 是词，则增加一个字 Str1=Str1+Sk+1，再查找，若Str1 是词，继续增加一个字，直到 Lmax，并记录词的最后一个字的位置 p。则可暂时获得切分词:Stmp1=S1S2„Sp。 3)取 S2 为首字词，重复以上操作，则可获得另一切分词Stmp2，若 Length(Stmp1)>Length(Stmp2)，则得到切分词:Stmp1，否则，得到切分词:S1/Stemp2。 (6)移动汉字串指针，进行下一次切分，直到整个串切分完成。 例如:切分句子“当中国人民解放军成立的时候” 。首先取词首字为“当” ，得到 Stmp1=“当中” ，然而以“中”为词首字时得到 Stmp2= “中国人民解放军” ， 由于 Length(Stmp1)< Length(Stmp2)，因此得到的切分为: “当/中国人民解放军” ;再取词首字“成” ，则 Stmp1=“成立” ，而词首字为“立”时，Stmp2=“立” ，由于 Length(Stmp1)>Length(Stmp2)，则切分为: “当/中华人民共和国/成立” 。继续后面的切分，最后得到的切分为: “当/中国人民解放军/成立/的/时候” 。 4.2、歧义词的消去 汉语不同于其他的语言，一句话产生歧义的时候经常发生。为了正确切分真实的汉语文本语料，必须对歧义字段进行处理，消去歧义切分词。 定义 1(歧义字段) 一个汉字串存在不同的切分形式，则称该汉字串为歧义切分字段，简称歧义字段。 根据歧义字段的构成形式可分为 2 种基本类型:交集型歧义切分字段和组合型歧义切分字段。其中，交集型歧义切分字段又占全部歧义切分字段的绝大多数。 定义 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%。由于交集型歧义切分字段又占全部歧义切分字段的绝大多数，因此本文采用基于统计模型的方法进行，对交集型歧义字段进行处理。 该算法过程如下: (1)多次运用概率算法，得到每一次的切分结果(且每次可随机选取MM 法或RMM 法); (2)比较每次切分结果，记录无歧义切分结果; (3)找出所有歧义字段，统计切分词出现的频度，选出频度最高的切分词; (4)对歧义字段剩余部分再进行统计，直到整理完毕。 5、实验结果 通过编写一个小型垂直搜索引擎，将该中文分词模块放入分词部分，通过实验，实验数据来源于从新浪网下载的新闻等共 1 000 篇文章。根据文章的大小，从每个类别中各抽出5篇文章，分派到5组中，作为测试集，且每组文档大小大致相同。测试环境为 P4/3.0 GHz/1 GB。实验数据如表 实验结果数据 平均文档 平均分词 平均出错 平均分词 平均词 -1大小/字 数量/词 词/数 速度(词?秒) (准确率/(%) 364 142 24 12680 94.1 507 200 32 12400 94.2 1102 532 60 11800 94.3 1490 649 92 12203 94.4 通过测试，一般出错的词语大多是人名、地名和专用词，这些出错是不可完全避免。实验结果表明，基于最大匹配的概率算法的平均分词速度达到了约 12000 词/秒，平均分词准确率达到 94%以上。分词准确率与文档长度有一定的关系， 当对文档长度增加时，分词的准确率略有提高。 6、结束语 中文自动分词技术在垂直搜索引擎中有着重要的作用。分析表明，本文提出的一种改进的整词分词的字典机制占用内容空间小，算法的平均时间复杂度低，具有较高查询的效率。该方法的引入很好的对中文文本语料实现了自动切分，相对传统的机械分词算法，对歧义词的消去也有较好的性能。 参考文献 [1] Baeza-Yates R, Ribeiro-Neto B. Modern Information Retrieval.China Machine process, 2004 [2] 文庭孝. 汉语自动分词研究进展[J]. 图书与情报, 2005, (5): 54-62. [3] 张海营. 全二分快速自动分词算法构建[J]. 现代图书情报技术, 2007, (4): 52-55. [4] 熊回香, 夏立新. 基于词索引的中文全文检索关键技术及其发展方向[J]. 中国图书馆 学报, 2007, 33(4): 45-49. [5] 何国斌，赵晶璐 基于最大匹配的中文分词概率算法研究 计算机工程 2010， 36(5):173-175. [6] 荣 陆, 王建会, 陈晓云. 使用最大熵模型进行中文文本分类[J].计算机研究与发 展, 2005, 42(1): 94-101. [7] 曹勇刚,曹羽中,金茂忠,刘超.提取、索引和挖掘中文学术论文.南京大学学报(自然科学 版), 2005,41:845~852