爱华网关键词：搜索引擎 中文分词
1. 绪论
1.1分词技术背景介绍
中文自动分词，是对索引库中的网页文件进行预处理的一个重要步骤。它工作在搜索引擎的网页预处理阶段：在它之前，相关程序已经对从网页库中取出的网页文件进行了处理，获取了其中title、anchor、url等信息，并将html语法部分删除，形成了由网页中文本部分组成的字符串。分词器做的工作，就是把这个字符串按照语意进行分解，使他成为一组能标识该网页的词的集合。
对于英文，最小的语法单位和语意单位都是单词。由于英语的书写习惯把单词与单词之间用一个空格分开，所以很容易依靠空格来分解整篇文章，在这个问题上基本不费力气。
但是对于中文，情形就大不相同。中文里面最小语法单位是字但是最小语意单位是词。如果以字为单位来切分整篇文章，处理起来比较容易，但是带来的时间及空间消耗是非常大的。更重要的是一个字根本无法准确表述一个意思，很容易想象出，假设以字为单位来进行切词，用户搜索的结果很可能与用户原本的意图风马牛不相及。
所以，要准确的标识语意，对于中文文章必须将其切分成汉语词的集合。但是要准确的按照文章语意来切分词不是件容易的事情，例如，对于句子："中华人民共和国"，其中"中华"和"华人"都是词，在这句话中我们知道应该按照"中华"来切词；但是对于句子"参与投资的外商中华人占绝大多数"，这时又该按照"华人"来切分。人处理这些问题是比较简单的，但是机器实现起来就难了。
2.2 目前搜索引擎中中文分词状况
有消息说，Google的中文分词技术采用的是美国一家名叫 BasisTechnology（http://www.basistech.com）的公司提供的中文分词技术，百度使用的是自己公司开发的分词技术，中搜使用的是国内海量科技（http://www.hylanda.com）提供的分词技术。在该文（[1]）中,作者对以上所述的三个引擎分别使用关键字"和服"进行了查询，结果差强人意。但是我重新试验了一遍，以上三个引擎在前10个搜索结果中均返回了与和服有关的网页，完全是正确。说明，经过这些时间的发展，中文分词技术已经得到了重视与发展。
2.中文自动分词介绍
2.1概述
目前，对中文文献的索引方法大致可以分为两类(参考[2]) ：
a）基于字符串匹配的分词方法：
这种方法又称为机械分词方法，它是按照一定的策略将待分析的汉字串与一个充分大的词典中的词条进行匹配，若在词典中找到该字符串，则识别出一个词。
按照扫描方向的不同，串匹配分词的方法可以分为正向匹配和逆向匹配；按照不同长度优先匹配的情况，又可以分为最大匹配和最小匹配。按这种分类方法，可以产生正向最大匹配、逆向最大匹配，甚至是将他们结合起来形成双向匹配。由于汉字是单字成词的，所以很少使用最小匹配法。一般来说，逆向匹配的切分精度略高于正向匹配，这可能和汉语习惯将词的重心放在后面的缘故。统计结果表明：单纯使用正向最大匹配的错误率为1/169，单独使用逆向最大匹配的错误率为1/245。但这都不足够准确，所以很少直接使用正向最大或逆向最大匹配法。
b）基于统计的分词方法
从形式上看，词是稳定的字的组合，因此在上下文当中，相邻的字同时出现的次数越多就越可能构成一个词。因此，字与字相邻共现的频率能够较好的反映成词的可信度。可以对语料中相邻共现的各个字的组合的频度进行统计，计算他们的互现信息。当互现信息较高时，可以认为他们是一个词。这种方法的学习性很强，但很难投入实用。
本文主要介绍基于词典的分词方法。在以下的叙述中，假设T标识需要处理的文章，可以理解为一个较长的中文字符串，设stringLength为指定的每次处理的字符串长度，在对T进行切词之前，先将T按照stringLength长度顺序切割为s1、s2 、s3…，每次取一个s对它进行切词操作。设词典中最长的词的长度为maxLength字（这里为了叙述方便，以字为单位来介绍分词的过程，具体实现时可能要对字符串进行以字节为单位的处理，注意单位换算）。
先来介绍一下简单的匹配方法，然后描述我的算法。
2.2 正向减字最大匹配法（MM）
这种方法的基本思想是：
对于每一个s，先从正向取出maxLength个字，拿这几个字到字典中查找，如果字典中有此字，则说明该字串是一个词，放入该T的分词表中，并从s中切除这几个字，然后继续此操作；如果在字典中找不到，说明这个字串不是一个词，将字串最右边的那个字删除，继续与字典比较，直到该字串为一个词或者是单独一个字时结束。
该过程可简单表示为：
2.3 逆向减字最大匹配法（RMM ）
与正向减字最大匹配法相比，这种方法就是从逆向开始遍历。过程与正向减字最大匹配法基本相同，可以对文本和字典先做些处理，把他们都倒过来排列，然后使用正向减字最大匹法。
例如句子："发展中国家兔"，按照正向减字最大匹配法得出的结果是"发展中国家/兔"，而按照逆向减字最大匹配法得出的结果是"发展/中国/家兔"。据统计，逆向匹配比正向匹配的准确率略高。
2.4 正/逆向结合的方法
不论是正向还是逆向，分词的总体准确率都很难达到实际运用的要求，所以单独的正/逆向方法是行不通的。有人提出正/逆向结合的方法，但具体实现各不相同，下面将介绍我的基于这种思想的算法。
3.改善的匹配算法
3.1 实际运用中的问题
由于语言的灵活性，完全精确的分词算法在目前是不太可能的实现的。除了上述三种基本的分词算法，吴栋和滕育平在[3]中介绍了一种正向逐一增长法，郭辉、苏中义、王文、崔俊在[4]中提出了一种长词优先的方法，都比上述3种算法提高了分词的准确率。
就像在操作系统中我们经常遇到时间与空间相矛盾的情况一样，在中文分词时，分词效果好的算法能够较准确的切分文章的关键字，提高搜索结果的准确度，但是会带来较长的时间开销；而分词速度快的算法，虽然能较快速的完成切分工作，但往往会影响切分的准确率，影响到搜索的结果。
如何在这时间和准确率之间平衡呢？我认为，这需要搜索引擎的建设者根据自己的情况来权衡。
对于Google、Baidu 等大规模商用搜索引擎，处在激烈竞争中的它们应该设法提高搜
索结果的准确性。对此，本文2.2节中提到过这些商用搜索引擎近年来在中文词汇识别上有了很大的提高，可以看到中文分词技术对中文搜索引擎的重要性。但他们的技术都是保密的，尤其是对于中文分词技术――整个中文搜索引擎的核心部分――是绝对保密的。这对学习这方面技术增加了难度。可以肯定的是：他们的工作不仅仅是扩展现有的分词算法，对于词典的扩大（尤其是地名、人名等专有名词的识别和处理），以及消除句子的歧异都需要深入的展开研究。在开源领域，鲜有见到这方面的突破。
作为我个人，要完成一个实用的中文搜索引擎，我是这样考虑的：
首先，没有Google那样庞大的集群处理能力，我的重心放在提高分词速度上，于是正向与逆向结合的方法成为我的选择。
其次，重要的一点，我认为："词是字的有序组合，句子是词的有序组合，'意元'与'顺序'构成了意思"。我们对文章进行分词，是想通过提取文章的关键词来获取整篇文章的意思，简而言之，就是拿"词"这个意元来标识整篇文章的意思。于是分词的正确性直接关系到对文章意思的理解。但是，我们在处理时加上对词的顺序的描述，应该是能大大提高准确性的。
这种思想是：
先对要匹配的字串分别进行正向和逆向的减字最大匹配，
如果两次匹配的结果相同，则认为这种分词是正确的，得到结果
如果不相同，则对划分不相同的部分取某种意义上的交集，以获得最小的划分。
例如：发展中国家兔
正向分词的结果是：发展中国家/兔
逆向分词的结果是：发展/中国/ 家兔
进行最小划分的结果是：发展/中国/ 家/兔
这样得到的结果，看起来似乎比逆向切分的准确度还要差，但是，我们是在做搜索引擎，此时已经不是在传统的"文献检索"领域讨论了。搜索引擎有他的特点，那就是用户查询时输入的信息相当少。如果用户想买一台联想的计算机，他很可能查询"联想"，这可就太笼统了，到底是"联想计算机"？还是"有XX事件引发的联想"？或是"汉字联想输入"？我们要做的就是把他们全找出来，在这种情况只能这样。
也许，有个问题是，上面的方法会把一个长词分解为若干个短词，假如我们就把"中华人民共和国"分成了"中华/人民/共和国"，那么所有出现了"中华""人民""共和国"这三个词的网页都被找了出来，从某种意义上说这是扩大了查询的范围。但是，我们在查询时注意到"中华""人民""共和国"这三个字之间的顺序，以及字与字之间的间距的话，这个问题就容易解决了。在S.Brin和L.Page的论文中[5]，在索引器（indexer）建立索引时是要记录下该词在文中的位置的，就是这个道理。换个角度思考问题：我是把长词变成了有序的短词 。
这样也带了一个坏处：用户输入关键词后，需要对用户输入进行处理，切分为有序的短词；在拿这些短词进行检索时，需要对位置进行计算，这将增加一部分用户等待时间。这部分时间主要花在对索引的结果按照相关性排列上。还是那个例子："中华人民共和国"，用户的输入被分解为"中华/人民/共和国",于是分别拿这三个词到倒排索引表中去查询，例如，假设倒排索引表当前状况如下：（索引记录格式设为DocID,Position,其中position标识该词在文章中的位置）
中华－>001，1;002，2;003，3 ； 004，4
人民－>002，4;003，4;004，7 ； 005，6
共和国－>003， 5 ；004，5；005， 8 ； 006， 10
那么，由于只有003和004号文件包含这三个词，那么这两个词的相关度就高于那些只含部分词的；而003和004号文件相比较，三个关键子词在003号文件中出现的顺序是3 4 5连续出现的，符合用户输入的顺序；在004号文件中没有这个特点，所以003号文件的相关度高于004号文件。
我们在使用google或者其他搜索引擎进行查询时，经验告诉我，他们也是这么做的（的确是这样吗？谁能告诉我）
4.算法描述
上面简述了对词的匹配策略，下面开始构造分词器（Project Cat）。
分词器位置：预处理部分－>网页预处理器－> 分词器
输入：由网页预处理器处理后的网页，中英文字符串
输出：词的集合
策略：
1）中英文处理策略：将中英文分开处理，中文匹配依照上面所述的方法，英文按单词分词。这就有两种处理算法，一种是对文章扫描两次，一次处理中文，一次处理英文；另一种方法是扫描一次，网页预处理器把该网页的类型也作为参数传递给分词器，如果是英文网页则只需按照英文分词策略即可，而对于中文网页，只在遇到英文单词的时候调用英文分词处理程序。鉴于整个互联网上，使用单一中文或英文的网页数目远远大于使用混合文字的网页数目，所以我使用后一种策略。（显然，单单是纯英文网页的数目就远大于含有汉字的网页数目）。
2）对文章先按照"，""。"等表示意思断开的标点符进行一次切分，这将很大提高分词的正确率。
描述：
分词器(){
句子拆分器（T）；//把输入字串T按照"，""。"为标志分开为s
for( i=o ;i<s.lenght ; i++){
切词处理器（s）；//按照正/逆向结合的方法对s进行切词
}
输出结果；//将结果，即词的集合，输出给倒排索引器
}
句子拆分器(){
//顺序查找当前字符与"，""。"比对
//找到"，""。"则以起始位置为起点，当前位置为终点，将这段字符copy到 s中
//删掉这一段，置当前位置为起点继续进行比对操作，直至结束
//这一段用perl写只需一句话
}
切词处理器（s）{
//按照前述方法构造
}
5．未来的工作
正如文中所述，这种分词方法是一种较简单的分词策略，没有涉及到专有名次、新词的处理。主要的目标是在准确率允许的情况下，提高分词的效率。在未来，需要进一步提高分词的准确度。
