Question

(2007-5-22更新)Lucene(Nutch)距离商业文本搜索引擎还有多远？

Answer 1

注（2007-5-22）：最新一次更新的时候，我再次研究了一下Lucene，读完了Lucene In Action，并且实际的使用Lucene构建了一个小型的搜索系统之后，我感觉到很惭愧，因为我一直对Lucene有不满的心理，认为它做的不好（可能受了国内的某些使用Lucene构建搜索引擎的网站的影响，因为他们构建的都很差，现在想来，可能是他们和我一样没有真正深入理解Lucene）。现在我才发现，Lucene的作者在大方向上考虑问题的全面比我要好很多（虽然有些功能我不知道是否真的有用）。现在我的感受是：1）Lucene对查询的理解十分深入，几乎什么样的查询需求它都考虑到了。而对于普通的商业搜索引擎来说（比如，百度），它们只是考虑到了布尔查询模式，远不及Lucene里面的查询方式多；2）Lucene对过滤和排序的处理已经能够满足90%的要求了。过滤可以把不需要的结果删除，而排序则可以根据某个域的值来进行结果排序。基本的垂直搜索引擎，是必须这些功能的，因为这些功能能够缩小查询的结果集，提高用户体验。而百度等商业搜索引擎显然是不需要（或者没有提供）这些功能的。3）Lucene的分值计算效果不错。抛开基本的IR的那些标准的分值计算算法不说（谁都知道总体上Lucene使用了简化的向量模型，但实际上Lucene在布尔模型查询上面也使用了简化的扩展布尔模型分值计算公式），Lucene支持了大部分额外的基于经验的分值计算。举例来说，查询“中国北京”的时候，以下是几个文档的实际排序（直接解析这个查询短语是得不到这个结果的，见第4点）：中国北京北京中国中国可爱北京 北京属于中国4）Lucene不提供真正的查询串解析。基于文法的查询串解析，一个严重的结果就是容错太差，所以，我们几乎可以认为Lucene并不提供实际有用的查询串解析。所以呢，上面我们说的“中国北京”需要您自己把它解析为： PhraseQuery query = new PhraseQuery(); query.add(new Term("name","中国")); query.add(new Term("name","北京")); query.setSlop(1000);然后才会有上面的那个结果。所以，使用Lucene的第一步是提供您自己的查询串解析器。5）理解Lucene的算法限制。Doug Cutting不是神仙，他也无法解决算法的问题，所以呢，几乎所有算法的限制都会在Lucene里面出现，比如，RangeQuery查询速度极慢，Sort排序需要很大的内存来缓冲Field的值。这些并不是Doug Cutting的错，而是算法的限制，我想应该没有人能够解决这类问题吧？（虽然从IR中我们知道RangeQuery可以使用B+树等结构来加快查询，不过，我们似乎不能够责怪Lucene，因为Lucene使用的是紧凑的文件结构，难以支持B+树结构） 如果您真的需要考虑这些问题的话，您可以自己修改Lucene的代码或者提供额外的扩展。6）理解Lucene的其他限制。在实际应用的过程中，您会发现Lucene有各种各样的限制，在这里，我想提醒您2个问题：a)缓冲同步；b)写/读同步。Lucene的缓冲做的不好，您可以根据实际情况自己扩展，在扩展的时候，请时刻注意缓冲和实际数据同步的问题。写/读同步其实是Lucene自己的问题，在同时读写一个Directory的时候，写的数据并不会马上表现到读上面，所以呢，要么关闭写，要么自己缓冲写结果。Lucene是一个开源的基于java的搜索引擎，它只包含IR(Information Retrieve)部分。它即不是唯一的也不是最好的一个开源搜索引擎，更好的比如egothor，但是它是文档最全面和受到关注最多的一个。Nutch是基于Lucene并加入了分布式和Crawler部分的搜索引擎。在本文中，作者试图从掌握的知识范围谈论一下它们使用的技术和一般商业文本搜索引擎使用的技术之间的距离。因为作者水平有限，仅仅拥有2年不到的搜索研究和实践经验，不足之处请大家多多指教。谢谢。1 网络搜索引擎的构架一个专业的网络搜索引擎至少包含3部分，即抓取、处理和搜索。下面是它们的一般功能：抓取：抓取（蜘蛛、爬虫、crawler、spider等）程序负责爬行特定网络（也可能是整个网络），把网络上的页面和其它需要的文件下载到本地来。目前的难点是web2.0的普及导致的js分析和身份认证等问题。处理：处理（分类、信息抽取、数据挖掘、classify、information extraction、data mining等）程序对抓回来的页面进行分析，比如，对网站的内容进行分类、对新闻页面的新闻信息进行提取、页面模版生成、对各个网站之间的关系进行计算等等。搜索：搜索（information retrieve）程序负责把文档填充到数据库，然后根据查询字符串到数据库中寻找最相关的文档展现给用户。仅仅从搜索引擎的构架来看，Lucene(Nutch)缺失的一环是信息的处理。信息的处理恰恰是整个搜索引擎中最核心的技术。2 信息抓取网络信息抓取包含了网页抓取、文本文件抓取和其它文件抓取。对于使用http(还有https)等协议的网站来说，信息抓取的主要过程是：根据指定uri地址，进入第一个页面；分析页面构成，得到超链接地址，把地址加入到待下载链接中去；当还有未下载的链接时，下载对应页面，保存页面，并返回到第2步；所有链接都下载完毕，退出。普通的信息抓取一般可以被称为Spider，它利用基本的html页面分析器（比如，HtmlParser、NeckoHtml、JTidy等）来解析html页面，得到页面中的超链接。一般的说，一个Spider由以下2部分组成：http下载器。给定一个uri地址，http下载器负责把这个地址的数据下载回来。或许大家会认为这个很容易，其实不然。网络中的页面，除了http协议以外，https安全协议也是十分常用的一种协议。当你要下载的数据需要认证的时候，你还需要让你的下载器支持认证。当你下载的数据需要登录的时候，你还需要让你的下载器支持Cookie。所以，你的下载器仅仅支持http还是远远不够的。在这点上，Nutch还差得远。html页面解析器。html页面解析器并不是支持html页面就万事大吉了的，现在的很多页面其实使用的是xml的构建方法，虽然html和xml很像，但是，它们的tag名字显然有很大差别。除此以外，wap手机类页面也是你可能需要支持的页面。Nutch使用的是NeckoHtml或者JTidy。实际应用表明JTidy比较一般，但是NeckoHtml具有不错的效果。在开源的软件中，它应该算是最好的一个html页面解析器。然而，它和IE或者Mozilla这些浏览器的html parser比较起来，还是有一段距离的。除此以外，这类Spider仅仅只是把页面分析成了DOM树，它并不能够对基于ajax技术的web2.0页面进行有效处理。要想处理那些大量使用ajax技术或者大量运用js代码的页面数据，Spider需要的仍然是js处理能力。当然了，关于js的处理也可以被划分到数据处理部分去。3 信息处理似乎在Lucene(Nutch)面前谈论信息处理显得有点不专业，因为它们压根就不支持。但是，信息处理部分你还是可以自己编写后嵌入到Lucene(Nutch)里面去的。信息处理话题太大，作者没有这个胆量和水平对此妄加谈论，虽然这个是作者一直研究的主要方向。唯一可以肯定的就是，信息处理需要的知识至少有2点：1，机器学习(ML)；2，自然语言理解(NLP)。前者典型的包括SVM、HMM等，后者包括HNC、知网等。笔者自信对ML有一定的理解，但是，对NLP的理解不太深入，还没有形成一个完整的解决方案。4 信息获取对信息获取的研究已经好多好多年了，多到那个时候作者都未出生。这部分主要分为2个步骤，第一个步骤是把文档填入到数据库（也就是所谓的构建索引）；第二个部分就是根据用户输入得到一系列最相关文档（即所谓的搜索）。得到最相关文档无外乎就是比较2个文档的相似度。当用户输入一个字符串（即一个文档）之后，搜索引擎根据这个文档到数据库中寻找和它最相关的文档，然后返回给用户。实际搜索引擎必须考虑速度的问题，不可能像理论上说的那样去做。搜索的时候，一般有如下3步：查询字串解析。查询的组织方式有很多种，比如布尔查询等。一般商业文本搜索引擎支持的查询大约这样：“北京黄河 AND tom cat(OR 美丽-祖国)jerry + mouse”。即支持AND(+)、OR(|)、-、括号和引号的复合表达式。光解析还不行啊，你还得进行额外的优化，比如，对于“北京北京北京北京”这个串来说，它和“北京”的效果是一样的吧？Lucene在这个方面做了不少工作，只是，你仍然需要自己写一个更接近中文和商业搜索引擎的查询字串解析器。你可以根据需要，决定是把表达式优化为适合并行计算还是最小计算量的形式。 我们AND AND AND 他们 作为一个追求完美的人，作者实在无法接受这样无法忍受的“错误”。查询。查询的部分没有什么太多可以说的。有一点是，算法该优化的都没有优化。不过，对于一个处于初级开发中，并且开发人员缺乏的Project来说，这样就足够了。结果排序。Lucene使用的分值计算方法在比较接近于IR理论上使用的一些计算方法。可是，实际中的分值计算却比这个要麻烦很多。一个例子就是Lucene使用的方法没有考虑到查询词语之间的紧密位置。比如，对于“北京商店”和“北京 商店”来说，得到的前几个结果显然应该差别很大，这是因为前者更倾向于“北京”和“商店”这2个词语在一起的情况。要Lucene做到这一点其实也容易，只是，它会严重的降低搜索速度（几倍）。 实际应用中，还常常需要计算某些属性的值的权重。比如，新闻搜索里面，今天的新闻是不是应该比昨天的新闻权重大一点呢？Lucene未能支持这点。5 速度第一对于搜索引擎来说，速度绝对是第一个需要考虑的问题。信息抓取的速度显然不在软件能够解决的范围内，它只能通过增加带宽和多级更新策略来提高了。信息处理的速度不在本文的讨论之列。信息获取的时候，有2个地方需要考虑到速度：索引速度。索引速度包含索引的构建速度、文档的修改速度和文档的删除速度。在粗粒度上说，Nutch采用的基于MapReduce策略的分布式索引构建方法是一个不错的构架。在细粒度上说，Lucene使用的内存缓冲和磁盘小索引合并的方法也是一个很好的构架。它们在构建索引上的表现都是令人称道的。在文档的删除上，Lucene使用的标记后再删除的方法是无可厚非的。在文档的修改和文档的追加上面，Lucene做的还差强人意。文档在修改的时候，唯一的办法就只能是先删除然后再追加。这点显然是不能令人满意的。查询速度。Lucene(Nutch)认为分布式的查询是不可取的，因为速度更慢。其实并不是速度慢，而是分布式查询需要一个快速的构架，这个构架涉及到搜索引擎的所有方面。暂时不是Nutch能够达到的。所以，Lucene(Nutch)的查询都是在一台机器上运行的。另外，Lucene因为它采用的分值计算方法的缘故，它不需要加载词语在文档中的位置信息，所以，它表面上看起来比其它搜索引擎快速了。其实是牺牲精度获得速度，另外，它自己使用的文件结构严重的制约了它的速度。没有引入缓冲是Lucene(Nutch)的另外一个严重失误。在这个构架里面，你可以自己构建一个查询结果缓冲（一级缓冲），但是，你很难构建一个基于词语的索引缓冲（二级缓冲）。这对于一个大搜索量的系统来说，是不可想象的。更何况普通商业搜索引擎还会有第三级缓冲。6 精度第二如果仅仅从Lucene(Nutch)支持的查询方式和分值计算来看，Lucene(Nutch)不存在精度的问题，因为它们都是计算了全部数据的。商业搜索引擎因为数据量过大的缘故，不得不使用一些估计的算法来减少磁盘数据的读取，这会导致精度的略微丢失。反过来说，Lucene无法支持大规模数据。7 效率第三这里说的效率主要是空间效率。比如，程序的内存占用和磁盘占用。Lucene使用了zlib压缩技术来压缩文档内容，还有使用了简单的压缩整数的方法。但是，它使用的压缩方法还是太少了，它少用压缩的结果是：1）文件结构和代码简单；2）查询速度变慢；3）索引segment合并快速；4）磁盘占用增加。同时，它几乎不用压缩也和它放弃缓冲有很大联系，因为压缩过的索引很容易放到内存里面，这点十分满足缓冲的空间需求。后记：因为作者对算法极其狂热，本文更多的是比较了开源搜索引擎Lucene(Nutch)和基本的商业搜索引擎之间在算法上的差别。为了让大家看的更明白，这里几乎没有提到任何算法。写的太多了，有空再增加。07.5.9 后记：根据最近的一些感悟，修改了本文。增加了一些认为重要的语句。