雅虎工程师Winter：中文分词和搜索引擎

sowang

中文分词和搜索引擎（一）

作者：Winter 工程师


        搜索引擎，上网的人基本上都不陌生了，CNNIC的第17次《互联网调查报告》显示，使用搜索引擎服务的网民，仅次于电子邮件。中文分词，估计了解的人并不多，毕竟太技术，太底层。但中文分词是中文搜索引擎系统中非常重要的模块，这里之所以强调是中文搜索引擎，是针对英文搜索引擎来讲，因为对于英文来说，空格代表词和词之间的分隔，也就不存在分词问题。和中文搜索引擎类似还有日文、韩文、泰文搜索引擎等，都需要处理分词问题。


        为什么需要中文分词

        目前的搜索引擎，大多是基于一种称为倒排索引的结构[1]。以什么做为索引的Key值，直接影响到整个搜索引擎的准确度、召回率[2]、速度。我们先看看不使用中文分词的情况。


        如果不使用中文分词，可以采用单个汉字索引方式。例如，雅虎，先索引'雅'字，然后再索引'虎'字。同样，对于一篇文章，先把所有的汉字都单独索引一次，并记录他们的位置。搜索过程中，也是先找'雅'字的所有文档，再找'虎'字的所有文档，然后做交叉'与'运算，即包含这两个字，而且位置连续的文档才会做为符合要求的结果。这种方式是最基本的索引方式，现在有些小引擎中还在使用。但这里存在一个很有挑战性的问题：总共的常用汉字是3000多个，我们每次查询过程中，进行'与'操作的计算量会相当大，对于大数据量搜索引擎来说(超过10亿的文档)，每天上亿次查询，这样的索引结构，无疑是对硬件和算法的极大挑战。


        考虑到速度问题，如果不使用分词，还有另外一种选择：n元组合索引方式，2元/3元等。拿2元来说，中国人，先索引'中国', 再索引'国人'。同样，对于一篇文章，以2为单位，把所有相邻的汉字都索引起来，并记录他们的位置。搜索过程中，也是先找包含'中国'的所有文档，再找'国人'的所有文档，然后做交叉'与'运算，即包含这两个单元，而且位置连续的文档才会做为符合要求的结果。这样以两个字做为索引单元，可以大大减少在搜索过程中的计算量。


        以上两种方式，都可以不需要分词，也能实现搜索引擎的索引和搜索。但是这里存在一个不可忽视的问题：准确度。一个很常见的例子：和服，如果按照上面两种方式，都会查到包含'主板 和服 务器'的文档； 北大 也会得到'东 北大 学'。对于大数据量的搜索引擎来说，每个搜索次都会有成千上万个结果，用户已经很挑选他真正想要的文章，如果这里还要增加许多错误，估计用户体验会极差。这时候，我们需要中文分词。


        词，是中文语言中最小的语意单位。以词为单位做为搜索引擎的索引的Key值，会大大提高搜索引擎结果的准确性，同时保证了搜索过程中计算量小。其实还有一个优点，以词为单位的索引，索引库会比上两种方式小很多。很明显：如果以 中国人 做为一个词，那么搜索的时候，不需要任何'与'运算，索引的时候记录也会减少。关于搜索过程描述参看中文搜索引擎技术揭密：系统架构


参考

1. The Anatomy of a Large-Scale Hypertextual Web Search Engine
2. 召回率: recall. 即得到的正确结果占所有应该得到的正确结果的比例。如：包含'雅虎'的正确的网页应该有500个，但搜索得到了600个结果，其中有400个是正确的，还有200个是错误的。那么准确度是:400/600=66.67%, 召回率是：400/500=80%.


发表于：2006年07月20日

sowang

中文分词和搜索引擎（二）

作者：Winter 工程师


中文分词的算法


中文分词技术的研究，已经有几十年的历史了，在20世纪80年代，我国就有人开始研究如何用计算机来自动分词。如何让机器去识别语言中最小的语意单位，不是一件很容易的事情。


如何进行分词？对于程序员来说，最容易想到的办法是，用一个大词典，把所有的词都存入词典中，扫描输入的文本，查找所有可能的词，然后看哪个词可以做为输出。例如：



输入文本: 我是学生
词: 我/是/学生



其实这样做了以后，可以解决60%的问题。总结起来，分词的算法分为：


1. 基于字符串匹配的分词方法
2. 基于理解的分词方法
3. 基于统计的分词方法


关于这3种算法的详细介绍，可以查看中文分词技术（http://www.stlchina.org/twiki/bin/view.pl/Main/SESegment），我这里想介绍的是，如何处理新词。


新词，术语是"未登录词"，就是那些没有收入到词典里面的词。新词主要包括：人名、地名、机构名、热点新名词等。例如：2003年之前，没有人知道"非典"。"非典"刚出现的时候，这就是新词。还有"超女", "三个代表"，"芙蓉姐姐"。识别新词的能力是评估一个分词系统的重要指标。在国际上每年进行的分词大赛中，识别新词的比赛也单独提出。2006年SIGHAN的分词大赛中，就增添了对于机构名识别的比赛。


如何识别新词成为最近几年分词技术研究的重点。总结起来，无非分成两种：

1. 基于规则的方法。
2. 基于统计、机器学习。


拿人名识别为例。你不可能把所有的人名都放入词典中，这决定了人名注定会是新词。从人名构造来说，很有规律：姓＋名。张王刘李陈、天下一半人。也就是说可能有一半的人，是这五个姓。名也有一定规律：建华/建国/志强.....等有许多经常用于名字中的汉字；对于地名识别也可以找出很多规则，省/县/村/镇/湾/河等，都是很常用的后缀，如果他们出现，之前出现地名的可能性比较大。如果把这些规律转化成计算机能识别的算法，就是基于规则的算法。这种基于规则的算法简单有效，而且发现规则可很方便加入。


规则总会有例外，规则过多以后，如何去权衡这些规则，会是十分头疼的问题。人们试着告诉计算机目标，让计算机自己去尝试各种方法组合这些规则并得到最优参数，这就机器学习。随着Machine Learning(机器学习)技术的不断进步，其应用范围也越来越广，中文分词算法也从中受益。ANN(人工神经网络), 最大熵模型, HMM(隐马尔可夫模型)等算法都在新词识别中有应用。通过机器学习识别新词的原理并不复杂。一般都是先定义一些特征，然后利用训练语料进行学习，建立模型。还是以人名识别为例，可以定义姓名前面的字、姓、名、姓名后面的字做为特征，通过利用标注好姓名的语料库进行学习训练。


机器学习识别新词的好处在于自动寻找一些识别新词的特征，其准确度和召回率都能达到比较高的水平。但机器学习算法需要有足够多的训练语料，人工准备准确的大规模的训练语料也会十分困难。另外，机器学习算法一般速度会比较慢，优化速度，使之用于海量数据处理，也是使用机器学习的一个关键点。



发表于：2006年07月21日
出    自：雅虎搜索日志

sowang

中文分词和搜索引擎（三）
作者：Winter 工程师

中文分词和搜索引擎
中文分词除了在索引结构上影响搜索引擎以外，还会如何影响搜索引擎？

除了搜索引擎的索引过程需要用到分词以外，所有的搜索之前也需要用到分词。有些人误认为"短语搜索"（即两端加上引号的搜索方式，搜索引擎基本都支持这种方式，查看搜索引擎帮助）是直接拿字符串去匹配不用分词，因为结果看上去好像是字符串匹配的结果。其实不然，短语搜索同样需要用分词，只不过在结果中需要位置连续等严格限制。当位置连续时，在显示摘要的时候，会让你感觉只是用字符串匹配。

除了在搜索前端后端都需要用到分词以外，搜索引擎还有一个原则：前端后端分词结果应该一致。这意思是说，如果你在索引时没有识别出"文德"的人名，你在搜索时最好也别识别出来，这样可以按照两个单字的方式查找，或许有正确结果，否则会查不到结果。反之也一样。由于索引过程中，分词输入的一篇文章，有大量的上下文信息，但在搜索时，用户输入的可能只有几个字，很多上下文信息不在存在。如果过多使用统计或机器学习，很容易导致搜索引擎的前端后端分词不一致的问题。这也是搜索引擎使用分词和其他系统，如机器翻译，使用分词不一样的地方。

如果你看过搜索引擎的query log（即所有搜索词的记录），你会发现新词很多，会占30%，或者更多。对这些新词的识别会直接影响搜索结果的准确性，或者说相关性。搜索结果的相关性决定于排序算法，排序算法一部分依赖于网页的质量和权威性，另一方面依赖于分词结果的准确性。分词结果准确，我们会方便的计算词在文章中的重要程度。"超女"做为一个词在文章中的权重，和"超"、"女"两个字在文章中的权重计算方法会很不一样，这样就会直接影响相关性的计算。

中文分词对于搜索引擎的影响，还表现在对于用户输入词意图的识别。识别用户的输入词是否是人名、网站名、软件名还是其他通用词汇，能够判断用户的意图，从而提供用户想要的结果。

其实中文分词是所有中文处理的基础，因此如果有一个好的分词系统，会对改进搜索引擎的相关性有很大的帮助。但最终展现给用户的是网页结果而不是分词结果，提高网页的相关性，有100%准确的分词也是不够。如何在准确的中文分词基础上，做更多的分析和挖掘，理解用户的意图，满足用户的需要，是每个搜索引擎公司都在努力做的事情。

雅虎的中文分词
YST 是Yahoo Search Technology的缩写。Yahoo收购inktomi公司后，又收购了几家做搜索的公司，综合打造出自己的搜索引擎技术。最开始，雅虎没有分词技术(segmentation), 中文、日文、韩文....等都是使用的第三方的产品。后来，随着雅虎正式进入中文搜索市场，雅虎开始加强对中文分词的研究，现在YST中使用的中文分词系统已经是雅虎中国和雅虎美国工程师共同开发的版本－－YWS(Yahoo Word Segmenter)，而且现在还在持续不断的改进。YWS 在对于人名、地名、机构名等新词识别方面有很不错的准确度，对于query的分析提供了很大帮助。

然而，对于搜索引擎厂商来说，没有最好的分词，只有最合适的分词。如何改进分词系统，配合以合适的索引结构，最终不断提高用户的满意度，这是一个长期的课题。

发表于：2006年07月24日 9:32