搜索引擎的自然语言分词

1、搜索引擎的自然语言分词前言：计算机就像小孩子一样，虽然什么都不懂，什么都不会，但只要耐心教导，他可以做的很出色，以下由天搜科技内部员工分享整理。上一节我们分享了单词的识别，这一节要分享的就是更加有趣也更加复杂的自然语言分词。顾名思义，分词就是将一句句子分成一个一个的单词。但是各国的语言都不一样，比如在英语中，单词一般是用空格或者其他标点符号隔开，这种语种的分词相对比较简单，只需要用空格来分割字符串。但是像中文，日文等等类似的语种，单词之间是没有任何分割的标记，因此在分词的过程中就有点难度。下面就以中文为例子，其他语言也类似。比如有一句句子：我们都喜欢玩全文搜索引擎。那么分词的模式就有多种了，这

2、里笔者只介绍最常用的两种一.智能模式分词后：我们都喜欢玩全文搜索引擎。二.最细颗粒模式分词后：我我们都喜欢玩全文搜索全文搜索引擎搜索引擎全文搜索引擎。但是分词后我们发现，有很多没有意思的单词，比如上句中的“都”，“玩”等等副词或者动词等等，当然还有标点符号。因此智能模式下我们期望是分成我们喜欢全文搜索引擎这三个词，而不需要那么多无用的单词。经过上面的分词，相信读者很容易就能够发现，智能模式是以最长单词为分割限度，而且不回退的分割模式。而相反最细颗粒模式就是以最小单词为限度，并逐一递增的分割模式。比如“全文搜索引擎”在智能模式下，就是一个单词全文搜索引擎,而在最细颗粒模式下可以分割成全文搜索全文

3、搜索引擎搜索引擎全文搜索引擎这么多个单词。经验告诉笔者，智能模式的使用范围更广，因为搜索的精度可以更加准确。需要说明的是，这两个模式在笔者通过程序实现后，它们的分割时间基本持平，智能模式略快。OK,下面开始介绍整个分词的算法与数据结构。同样的,开发环境还是Linux+C+EcipseCDT首先先介绍算法，由于要兼容智能模式与最细颗粒模式，在算法上，笔者采用的是著名的AC算法，全称叫Aho-CorasicK也称有穷自动机类似上一节分享的Trie算法，AC算法也是在内存中建立单词库，不同的是，它不仅仅可以做到单词的识别，还可以做到字符串的多模式匹配，也就是笔者说的分词。AC算法在Trie算法的基础

4、上，添加了失败转换的特性。下面通过图来了解AC算法的奥妙之处。比如我们有单词：全文，全文搜索，全文搜索引擎，搜索引擎，分词引擎，中文分词，分词。那么通过建立ac树就如下所示通过上一节中的trie介绍，相信一看就可以明白了。打x代表单词，只是与trie不同的是，每个节点增加了“虚线”（由于篇幅，没有全部画）这条虚线就是ac算法的奥妙，叫做失败跳转。即在进行模式匹配的时候，一旦匹配失败，就不继续往下，而是跳转到失败指针所指向的节点，然后继续匹配，所以称他为自动机。但是并不是所有的几点的失败指针都是有效地址，也有可能是NULL一旦出现NULL就条转回root。所以又称他有有穷自动机，而不是无穷自动机

5、。那么这条虚线，也就是失败跳转指针，就有一个比较严格的要求。1 .必须指向其他的路径的节点。（如果指向自身所在的路径，那就死循环了，这里的路径，指从当前节点返回到root的路径）2 .指向的节点，从节点开始到root所形成的字符串必须是当前节点到root所形成的字符串的最大子申，也就是深度最大。举个例子:全文搜索引擎中的“擎”节点，的失败指针指向的是“搜索引擎”中的“擎”，因为“搜索引擎”是“全文搜索引擎”中的最大字用（倒序）0在比如，“中文分词”中的“词”的失败指针索指向的就是“分词引擎”中的“词”。一次类推。如果找不到合适的失败跳转节点，则全部指向root,或者为NULL比如“分词引擎”中

6、的“词”节点，就没有合适他的失败节点，所以就跳转到root或者NULL接下来开始讨论如何分词。比如我们有一句句子叫“我们都喜欢玩全文搜索引擎和分词”。搜先要讨论的就是智能模式的分词。智能模式不需要用到失败指针。只需要顺着边往下走，直到走到叶子节点，也就是最长的单词。如果能够顺利走到叶子节点，那么就直接截取单词，并回到root,继续匹配。若无法走到叶子节点，则从当欠节点往回退，直到找到最长的单词。举个例子，比如句子”全文搜索引擎的分享”。可以顺利走到节点“擎”，则分出单词全文搜索引擎,剩下“的分享”，继续从root开始递归匹配。因此匹配的路径就是“全”，“文”->“搜”->“索”-&

7、gt;“引"->“擎"->“root”->”白r.又比如句子”全文搜索引言的讲解”。走到“弓厂节点就无法继续了，因此从引开始往回退，找到最长单词全文搜索,因此分出单词全文搜索,剩下的“引言的讲解”继续回到root继续匹配。若在回退的过程当中，没有找到单词，则认为该字符串是无效字符用，直接废弃！因此匹配的路径就是“全”，“文”->“搜”->“索”->“引”->“索”->“root”->“引”.因此只要循环或者递归，就可以分出句子中的全部单词（这里的单词必须存在于我们建立的ac词库当中）。下面介绍更加有趣的最细颗粒模式最细颗

8、粒模式是建立在智能模式的基础上的。在智能模式中，一旦匹配失败，则往回退直到找到单词，分出单词为止。而最细颗粒模式，一旦匹配失败，并不需要回退找单词，而是直接跳转到失败指针索指向的节点，继续匹配，并搜集在匹配过程中经过的路径的所有单词（指打上x的节点）。举个例子比如句子”全文搜索引擎的分享”当走到“擎”节点，整个匹配的路径就已经搜集的3个单词全文全文搜索全文搜索引擎，但是“的”匹配失败，则立即跳转到失败指针索指向的节点“搜索引擎”中的“擎”，则又搜集到单词搜索引擎。所以整个的匹配路径就是->“索”->从结果看这种匹配算法，看似有回退，其实并没有回退，而且可以把句子中的单词尽可能的分出

9、来。但是这种模式的分词，可能会破坏句子的结构或者本意。比如句子”全文搜索引擎”，如果词库不是很正确的话，通过最细颗粒模式，可能就会分出索引这样的单词，但是通过句子的本意并不是要表达索引的意思，而是要表达搜索和引擎的意思。也因此笔者才说，经验告诉我们，智能模式的使用范围可能相对广一些，因为它对于搜索的精度可能会高一些。下面还是通过程序来验证分词的效果首先是数据结构和方法定义/* ac.h* Createdon:Aug28,2013* Author:sean* /#ifndefac_H_#defineac_H_#include<stdio.h>#include<stdlib.h&

10、gt;#include<wchar.h>#include"datatype.h/#defineDEBUG/*ac树节点*/typedefstructAcNodewchar_tcharacter;boolisword;structAcNode*children;longchildrenCount;structAcNode*failure;structAcNode*parent;AcNode;/字符/是否是单词节点/子节点数组字节点数量/失败转向节点/父节点/* 初始化ac树，建立词库搜索树* paramdic* /AcNode*ac_init(FILE*dic);词库字典文

11、件/*二分查找，返回目标元素的地址，不存在返回NULL*/AcNode*ac_bin_search(AcNode*arr,intlength,wchar_tcharacter);/*获取单词，从指定节点反向到根节点*/voidac_getword(AcNode*node,wchar_t*word);/*获取节点最近的单词，返回节点与单词的距离return成功返回回退距离，没有单词，返回-1*/intac_get_latest_word(AcNode*node,wchar_t*word);/*判断字符串是不是单词*/boolac_is_word(AcNode*root,wchar_t*word)

12、;#ifdefDEBUG/*打印ac树paramrootac树*/voidac_print(AcNode*root);#endif#endif/*ac_H_*/* analyzer.h* Createdon:Sep3,2013* Author:sean* /#ifndefANALYZER_H_#defineANALYZER_H_#include<stdio.h>#include<stdlib.h>#include<wchar.h>#include"ac.h"#include"trie.h"#include"s

13、ynonym.h"/* 分词结果单词节点* /单词字符串/下一个节点地址typedefstructWordwchar_t*word;structWord*next;Word;/*分词* paramdic* paramstop* paramtxt* paramsmart颗粒分词词库字典同义词字典分析文本是否使用智能分词，true-智能分词，false-最细*/voidanalyze(AcNode*dic,SynonymNode*synonym,wchar_t*txt,boolsmart);#endif/*ANALYZER_H_*/由于篇幅，有兴趣的读者自行实现了下面看看程序的运行结果，

14、整个ac词库采用IKAnalyzer的默认词库，大概30万个单词intmain()(setlocale(LC_ALL,"zh_CN.utf8");char*dic_path="/home/sean/Desktop/word.dic0"FILE*fp=fopen(dic_path,"r");AcNode*ac=ac_init(fp);fclose(fp);/准备大文本FILE*tmp=fopen("/home/sean/Desktop/essay.txt0","r");wchar_tessay10

15、24*1024=L'0'wchar_tline1024*100=L'0'while(fgetws(line,1024*100,tmp)!=NULL)intlen=wcslen(line);if(len>0)wcscat(essay,line);wmemset(line,L'0',1024*100);printf("%lsn",essay);fclose(tmp);printf("分词后>n");printf("startanalyzing.n");structtimevalt

16、ime_start,time_stop;doubletime_pass;gettimeofday(&time_start,NULL);analyze(ac,synonym,映们都喜欢玩全文搜索引擎",1);/analyze(ac,NULL,essay,1);printf("n");analyze(ac,synonym,映们都喜欢玩全文搜索引擎哦",0);/analyze(ac,synonym,essay,0);gettimeofday(&time_stop,NULL);time_pass=(double)time_stop.tv_sec-

17、(double)time_start.tv_sec)*1000000+(double)time_stop.tv_usec-(double)time_start.tv_usec;printf("ncosts%lfn",time_pass);一:ISConsoleS3±Problems<terruinated>searchengineQ/CfApplicationksac电/c_workspac9/s&an±engir/Debjg/search®nq例后二T_一二二二一二一二Astartanalyzing.,【碰们11毛立搜索引

18、SI【1我幻H喜欢11全文1【全文搜索全文慢索引擎搜索田单索引costs64.B66G80可以看到，第一行是智能模式，第二行是最细颗粒模式的分词，整个分词的时间是64微妙，因为在eclipse下开发，c语言的打印速度比较慢，因此如果不打印的话，时间大概在40微秒，可见分词的速度相当快。下面试试相对比较大的文本，文件大小是5K的文本文件曰canssle为（2Prblemcktrrminjled?searchen4inBApplkdlbnl/home/ud/MXkipace/L-WwIu0au/MJfCheHirw/DebLJ/sEJfcheri4n（3/11/119:19PMJ惺文搜索引堂是广疣度用的主丸搜索引攀.国附建电WoqlR国内工储署名的百度、模技寻.它们从工联同星取小T网帖的醋只：以网W文字为主）专用丢件用M的记承.蚊一文的小利质序旭需段赤泞工未弼眄不同.全支投窜引笨力分为防夷.一改翻糖岂已内楼案程序（Iritfaxw）.能称“JMTf