1、lucene搜索引擎与信息检索第1章 搜索引擎与信息检索Google的巨大成功让整个世界都把眼光投入到搜索引擎这个领域中。仿佛一夜间，各种各样的搜索服务席卷而来，从最初的Google、Yahoo到现今的Baidu、MSN、中搜、Sogou等，搜索引擎的品牌越来越多，服务也越来越丰富。同时，伴随着Web2.0的疯狂普及，网络信息的膨胀速度成指数急速增长，各种各样的网站都需要为其加入检索功能，以满足用户的需要。另外，在企业级应用的市场上，全文信息检索的需求也一直在增加，各种文档处理、内容管理软件都需要加入全文检索的功能。在这样的背景下，搜索引擎的技术迅速发展。各种讨论搜索的文章、杂志、论文铺天盖地
2、，论坛和博客上也有着许多相关贴子。一时间，搜索技术成为最为热门的技术之一。不过，搜索引擎技术并非是一种大众技术，从其出现开始，就一直是一种高门槛的技术，它的后台包括学术领域的众多先进思想和设计，其涉及的学科包括自然语言处理、人工智能、离散数学、排列组合、编译原理等等。因此设计一个性能良好，并且实用性强的搜索引擎并非易事。本书不研究上述多种学科与搜索引擎的关联理论，但是作为读者，了解和掌握搜索引擎技术的方方面面，会对阅读有很大的帮助。因此，作为本书的第1章，将带领读者了解一下搜索引擎和信息检索的基础知识、发展历史、现今状况等内容。1.1 搜索引擎的历史在互联网发展的最初阶段，网站的数量相对较少，
3、信息查找比较容易。随着互联网爆炸性地发展，用户很难找到所需的资料。这时，搜索引擎的需求就出现了，一些为满足大众信息检索需求的专业搜索网站也就应运而生。1.1.1 萌芽：Archie、Gopher1Archie事实上，搜索引擎的的诞生追溯到1990年，在加拿大蒙特利尔（Montreal）的麦吉尔大学，一个学生制作了一个自动索引互联网上匿名FTP网站文件的程序。这个学生叫Alan Emtage。如图1-1所示。图1-1 Alan Emtage这个能够自动索引互联网上匿名FTP网站文件的程序，被他们称为Archie。Archie是Internet上用来查找文档的自动搜索服务工具，这些文档的标题必须满
4、足特定条件通常，为了从匿名FTP服务器上下载一个文件，必须知道这个文件的所在地，同时必须知道这个匿名FTP服务器的地址，及文件所在的目录名。Archie可以帮助用户在遍及全世界的千余个FTP服务器中寻找文件。Archie Server又被称作文档查询服务器。用户只要给出所要查找文件的全名或部分名字，文档查询服务器就会指出在哪些FTP服务器上的哪个路径下存放着这样的文件。使用Archie进行查询前提：输入要查找的文件名或部分文件名，知道某个或几个Archie服务器的地址。如今，提供Archie服务的网站已经很少了，笔者在Google上查找了一下，链接到了一个波兰的网站，仍在提供着Archie服务
5、，如图1-2所示。有兴趣的读者可以上去一看。图1-2 一个Archie网址从概念上讲，Archie的工作十分简单。每隔一段时间，一个特殊的程序连到每一个已知的匿名FTP主机，然后下载所有公共文件的完整目录表。这些表存储于Internet Archives Database（Internet档案数据库）中。当用户要求Archie检索一个文件时，所要进行的工作就是对该数据库进行检索。2Gopher简介受其启发，美国明尼苏达大学的一个学生Mark McCahill，于1991年发明了一种叫“Gopher”的搜索协议。“Gopher”的命名来自于这所学校的吉祥物。这种协议与Archie最大的不同是，A
6、rchie仅能够索引网络上的文件，而Gopher却可以对网页也进行索引。同时，另外两个程序“Veronica”和“Jughead”用来对以Gopher格式进行索引的文件进行检索。“Veronica”的名字来自于“Very Easy Rodent-Oriented Net-wide Index to Computerized Archives”（非常方便的、专门用于收取网络范围内的、可计算机化的文档）的首字母。它能够对整个Gopher列表中的目录主题进行关键字查找。而“Jughead”的名字则来源于（Jonzys Universal Gopher Hierarchy Excavation And
7、 Display）（Jonzy的通用Gopher层次挖掘和显示）的首字母，它是一个能够从很多Gopher服务器上获取目录信息的工具。直到今天，网上仍然有一些Gopher的服务器在运作着。许多Gopher协议的狂热者依然在维护着它们。只不过大多数浏览器已经不支持Gopher协议，因此，很难为读者找到一个可以演示的网站。不过，在SourceForge的开源项目中，有一个叫GoFish的项目，它实现了一个支持Gopher协议的服务器，如图1-3所示。有兴趣的读者可以下载下来，研究一下它的实现。图1-3 GoFish的主页1.1.2 起步：Robot（网络机器人）的出现与Spider（网络爬虫）实际上
8、，Archie的工作原理与现在的搜索引擎已经很接近，它依靠开发者撰写的脚本程序，自动搜索网上的文件，然后对相关信息进行索引，保存入索引库，供用户查询。1Robot在当时，在开发者中，“机器人”（Robot）是个十分流行的词汇。电脑“机器人”（Computer Robot）是指能够以人类无法达到的速度，不间断地执行某项任务的软件程序。由于用于检索信息的“机器人”程序像蜘蛛一样，在网络间爬来爬去，因此搜索引擎的“机器人”程序就被称为“蜘蛛”程序。第一个用于监测互联网发展规模的“机器人”程序诞生于1993年，由美国麻省理工学院的Matthew Gray开发，名字叫做World Wide Web Wa
9、nderer。最初它只是用来统计互联网上的服务器数量，监测网络的规模。从1993年到1995年间，这个“漫步者”每个月都会运行一次，以获取相关信息。后来，它演变成为收集URL的工具。同时，它也成为有史以来第一个网站资源库，被称为“Wandex”。从“The Web Robots FAQ”（http:/www.robotstxt.org/wc/faq.html）上得到这样的定义：一个网络机器人是一段程序，它能够在获取网页的情况下，自动遍历其超文本结构，同时递归遍历所有与其相关的网页。通常，人们所说的Robot是指Web漫步者、Web爬虫或Web蜘蛛。它们的名字可能有一些误导的作用，让人们觉得软件
10、本身有点像病毒一样侵蚀着网页，但实际上，它们只是简单的从网站上获取到网页的内容。2SpiderMatthew Gray所开发的“漫步者”应该是第一个网络爬虫。不过在1993年10月，英国的软件工程师Martijn Koster创建了ALIWEB（），这个名字来自于Archie-Like Indexing of the Web（像Archie一样索引互联网）的首字母。从名字就可以看出，ALIWEB事实上是一个Archie的互联网版本。ALIWEB允许用户提交他们自己的网页，以便能够被索引，也就是说，如果网站主管们希望自己的网页被ALIWEB所收录，则需要自己提交每一个网页的索引信息，有点类似于后
11、来的Yahoo。根据Koster的说法，ALIWEB是基于自动元数据收集的搜索引擎，如图1-4所示。图1-4 自称是互联网上最古老的搜索引擎的ALIWEB1.1.3 发展：Excite、Galaxy、Yahoo等慢慢的，网络机器人理论逐渐成熟。在1993年底，一些基于此原理的搜索引擎开始纷纷涌现。1993年2月，6个Stanford（斯坦福）大学生希望通过分析字词关系，以对互联网上的大量信息做更有效的检索，于是他们开发出了Excite（），后来它曾以概念搜索闻名。仅用了一年时间，Excite就组成了公司，并在1995年12月上线。不过在2002年5月，被Infospace收购的Excite停止
12、了自己的搜索引擎，改用元搜索引擎Dogpile。1994年1月，第一个既可以搜索又可以浏览的分类目录EINet Galaxy (Galaxy)成功上线了。除了网站的搜索外，它还支持了Gopher和Telnet搜索。它最早是作为德克萨斯大学微电子与计算机研究中心的一个产品，不过最终还是被大学卖给了公司。在几经转手后，它成为了一家独立的公司。1994年，斯坦福的两名博士生，美籍华人杨致远Jerry Yang和与David Filo共同创建了雅虎Yahoo。一开始，雅虎只是列出一些用户喜爱的站点。与其他分类搜索引擎的最大不同是，除了简单的URL链接之外，它还提供了对于网页的一些简单描述信息。另外，随
13、着访问量和收录链接数的增长，Yahoo的目录也开始支持简单的数据库搜索。因为最初Yahoo的数据是手工输入的，所以还不能被归为搜索引擎。事实上它只是一个可搜索的目录。不过在一年间，他们就得到了投资，并迅速成长壮大，最终成为今天家喻户晓的搜索引擎。1994年初，美国华盛顿大学计算机工程系的学生Brian Pinkerton开始了他的小项目WebCrawler。1994年4月20日，WebCrawler正式亮相时，仅包含来自6000个服务器的内容。WebCrawler是第一个全文搜索引擎（Full Text Search Engine）。在它之前，用户只能通过URL和摘要进行搜索，摘要一般来自人工
14、评论，或程序自动提取正文的前100个字。（后来Webcrawler陆续被AOL和Excite收购，现在和Excite一样，改用元搜索引擎Dogpile）。如图1-5所示。图1-5 第一个全文搜索引擎WebCrawler1994年7月20日，数据量为54000个文档的Lycos（）搜索引擎正式发布。Lycos的出现是搜索引擎史上又一个重要的进步。美国卡耐基梅隆大学的的Michael Mauldin将John Leavitt开发的网络机器人程序与其创建的索引程序组合在一起，创建了Lycos。Lycos除了引入相关度排序外，还提供了前缀匹配和字符相似度限制。同时，Lycos还是第一个使用了网页自动摘
15、要的搜索引擎。不过，其最大的优势还是它远胜过其他搜索引擎的数据量：1994年8月它收集了394000个文档；到了1995年1月，这个数量达到了150万；而到了1996年11月，Lycos已经有了超过6000万个的文档。如图1-6所示。图1-6 搜索引擎历史上的一个里程碑Lycos1.1.4 繁荣：Infoseek、AltaVista、Google和Baidu1Infoseek1995年初，搜索引擎家族又添加了新的一员：Infoseek。Infoseek是另一个重要的搜索引擎。虽然公司声称1994年1月已经创立，但直到年底其搜索引擎才与公众见面。起初，Infoseek只是一个不起眼的搜索引擎。它
16、沿袭了雅虎和Lycos的概念，并没有什么独特的创新，但是它的发展史和后来受到的众口称赞证明了它的重要性。Infoseek友善的用户界面、大量附加服务使它的声望日益增加。而1995年12月与Netscape的战略性协议，使它成为一个强势搜索引擎。作为当时使用最为广泛的互联网浏览器，每当用户点击Netscape浏览器上的搜索按钮时，总会弹出Infoseek的搜索服务，在此前，该项服务是由Yahoo提供的。到了Infoseek时，搜索引擎的的发展基本已经成型。它已经与现有的搜索引擎在功能上没有太大的区别。所不同的只是受当时的硬件发展束缚，搜索引擎在性能上还有待提高。2AltaVistaAltaVis
17、ta（）是在1995年12月时推出的。虽然晚到些，不过大量的创新功能使它迅速达到了搜索引擎的顶峰。Altavista最突出的优点是搜索速度。同时，它的另一些新功能，则永远改变了搜索引擎的定义。AltaVista是第一个支持自然语言搜索的搜索引擎。同时它也是第一个实现高级搜索语法的搜索引擎。所谓高级搜索语法，就是允许用户在查找关键字时，输入一些逻辑运算符，以表示关键字之间的关系。用户可以用AltaVista搜索新闻组的内容，并从互联网上获得文章，还可以搜索图片名称中的文字、搜索目录、搜索Java applets、搜索ActiveX对象。AltaVista也声称是第一个支持用户自己向网页索引库提交
18、或删除URL的搜索引擎，并能在24小时内上线。除此之外，AltaVista还添加了一个新功能，就是它能搜索有链接指向某个地址的所有网站。在用户的界面上，AltaVista也有了长足的进步。它在搜索框区域下使用一些提示，以帮助用户更好的表达搜索式，从而构建更为准确和有效的搜索关键字。这些搜索提示经常更新，这样，在使用过几次AltaVista的服务后，用户会看到很多他们从来不知道的搜索功能。如图1-7所示。图1-7 AltaVista的搜索界面应该说，AltaVista是功能最为全面的搜索引擎，它在Google声名鹊起之前曾经名噪一时，但现在其地位已被Google取代。即便如此，它仍被认为是功能最
19、完善，搜索精度较高的全文搜索引擎之一。截止2002年6月，AltaVista宣称其数据库已存有11亿个Web文件，并且经过升级，其搜索精度已达业界领先水平。3Google在AltaVista诞生的那几年，业界还出现了一些搜索引擎。但是它们的出现并没有给整个搜索引擎领域带来新鲜感。不过，这种情况很快被打破了。1998年的10月Google正式推出，迅速成为业界的领头羊。Google在网页排序、动态摘要、网页快照、每日更新、多文档格式支持、地图股票词典人物搜索等方面的创举，令全世界为之一惊。它在集成搜索、多语言支持、用户界面等功能上的革新，象Altavista一样，再一次永远改变了搜索引擎的定义。
20、事实上，在1998年10月之前，Google只是斯坦福大学的一个小项目BackRub。1995年博士生Larry Page开始学习搜索引擎设计，并于1997年9月15日注册了的域名。1997年底，在Sergey Brin和Scott Hassan、Alan Steremberg的共同参与下，BachRub开始提供Demo。1999年2月，Google完成了从Alpha版到Beta版的蜕变。Google公司则把1998年9月27日认作自己的生日。在2000年中以前，Google虽然以搜索准确性备受赞誉，但因为数据库不如其他搜索引擎大，并且缺乏高级搜索语法，所以使用价值不是很高，推广并不快。直到2
21、000年中数据库升级后，又借被Yahoo选作搜索引擎的东风，才一飞冲天。4Baidu进入2000年后，互联网高速发展，网上信息量以指数级速率增长着。这再次为搜索引擎的发展提供了良好的背景。搜索引擎成为继门户网站后的又一个重心。但是同时，在中文搜索领域，全世界还没有任何一个搜索引擎有着令人满意的效果，这其中的原因是多方面的：一方面，缘自于中文的复杂性和汉语分词的不确定性；另一方面，也是由于国内搜索引擎技术水平与国外还有着较大的差距。2000年的1月，超链接分析专利发明人、前Infoseek资深工程师李彦宏与好友徐勇（加州伯克利分校博士）携120万美元从美国硅谷回国，在北京中关村创立了XX（Bai
22、du）公司。创立之初，XX就将自己的定位于打造中国人自己的中文搜索引擎。2000年5月，XX首次为门户网站“硅谷动力”提供搜索技术服务，之后它迅速占领了中国搜索引擎的市场，成为国内最主要的搜索技术供应商。2001年8月，XX公司发布了B搜索引擎Beta版，从后台服务转向了独立提供搜索服务，并在中国首创竞价排名的商业模式。2001年10月22日，正式发布Baidu搜索引擎。Baidu虽然只提供中文搜索，但目前收录中文网页超过9000万，是最大的的中文数据库。Baidu搜索引擎的其他特色包括：网页快照、网页预览/预览全部网页、相关搜索词、错别字纠正提示、新闻搜索、Flash搜索、信息快递搜索。20
23、05年8月5日，XX在纳斯达克上市，成为2005年全球资本市场上，最为引人注目的上市公司，中国的搜索引擎市场也由此进入一个崭新的阶段。1.2 信息检索系统的基本知识本节将向读者介绍信息检索系统的一些基本知识。这些知识有助于读者更好的阅读本书，掌握其中要领。由于本书并非一本学术性书籍，因此，对于一些信息获取技术的细节知识只是提纲挈领并不深究，读者在阅读时，也不会感到晦涩。1.2.1 什么是信息检索系统1从Word中看搜索举个最简单的例子，当使用Word的时候，按Ctrl+F键，系统就会弹出一个对话框，如图1-8所示。图1-8 Microsoft Word里的搜索功能它会提示输入需要查找的关键字。
24、待输入完毕后，单击“查找下一处”按钮，系统便会自动找到你所想查找的关键字，然后定格在那一页上，并高亮显示它。可以说，这就是一个最为简单的信息检索系统。2从Windows资源管理器中看搜索再举一个例子，某天你和朋友出去游玩，用数码相机拍了许多照片。回到家中后，就把这些照片从数码相机上拷贝到了自己的电脑上，其中，有一张你和朋友的合影，将它命名为“合影.jpg”。事隔多日，你偶然想起那天的游玩，希望重温昨日情怀，于是便打开电脑，希望能够再次回味那天的照片。可是，你突然发现，已经完全记不起来那天的照片放在电脑的哪个文件夹下了，无论如何回忆，依然无法找到那天的照片。此时，可以打开Windows自带的“搜
25、索”功能，输入那张照片的名字：合影.jpg，然后单击“搜索”按钮，Windows就会自动查找名为“合影.jpg”的文件，然后你会发现，原来那些照片就在某个目录下放着，系统不但给出了照片的路径信息，你还可以通过双击照片直接打开它。Windows的这种搜索功能，同样也是一个信息检索系统。如图1-9所示。图1-9 Windows的搜索功能3总结简而言之，信息检索系统就是帮助用户查找到特定信息的一种工具。为了达到这个目的，信息检索系统需要能够对信息进行正确的表示、存储和组织，同时还要提供对于信息的访问方式。在这里，信息的概念很宽范。信息可以是一篇文章，一段文本，一个网页，一封邮件，一张照片，甚至是一些
26、虚拟信息集合。从一些资料中得知，大约在4000年前，人类就开始有目的地组织信息，以方便对其的获取和使用。最典型的例子可以说是图书的目录，读者可以从目录中获得到正文内容所在的页面，从而直接阅读他们感兴趣的信息。后来，随着人们对于信息访问速度要求的提升，出现了一种从某个词指向相关文档的指针，也就是索引（Index）。目前，索引已经成为所有信息检索系统的核心。利用索引，可以快速的存取数据，并且加速存储的过程。在计算机被发明之前，人们主要通过手工的方式，来对大量的信息进行分类和建立索引。不过，随着计算机技术的普及，信息检索系统与计算机的结合越来越紧，出现了利用计算机来实现大规模自动索引的方法，互联网搜
27、索引擎就是其中的最典型代表。除此之外，信息检索系统也被广泛应用于各种领域，来帮助人们完成他们所需要的查找。1.2.2 信息检索的过程1构建文本库在开发检索功能前，一个信息检索系统需要做些准备工作。首先必须构建一个文本的数据库。这个文本数据库用来保存所有用户可能检索的信息。在这些信息的基础上，确定检索系统中的文本模型。文本模型是被系统所认可的一种信息格式，这种格式应当具有可识别、冗余程度低等特点。当然，在系统的运作过程中，文本数据库的信息可能会不断的发生变化。但是一旦文本模型确定下来后，就不应当对其进行大的变动。2建立索引在有了这种文本模型后，就应该根据数据库内的文本，建立索引。索引可以大大提高
28、信息检索的速度。目前，有许多种索引的建立方式。采用哪种方式取决于信息检索系统的规模。对于大型信息检索系统（如XX、Google这样的搜索引擎）来说，“倒排”是一种常用的建立索引的方式，如图1-10所示。图1-10 信息检索系统的数据处理流程3进行搜索在为文档建立索引之后，就可以开始对其进行搜索。这时，通常都是由用户提交一个检索请求，该请求将被分析，然后利用文本操作进行处理。对于真实的信息检索系统，在真正处理查询请求前，还可以对请求进行一些预处理，然后再将请求送到后台，并返回给用户所需要的信息。4返回结果以前，对结果进行过滤通常，在信息检索系统检索到用户需要的信息后，还要做一步操作。就是将信息以
29、一定的规则进行排序或过滤，再返回给用户。这一步实际上关乎到最终用户的体验，试想一下，如果总是将一些无关信息返回给用户，那么它一定不是一个成功的信息检索系统。用户可能会有疑问，在前面所提到的Microsoft Word中的检索，似乎完全没有这些过程。其实，Word是从内存中直接利用字符串匹配的方式来查找关键字，它忽略了索引建立这个环节。这是因为，此时所有的内容已经全都在内存中了。另外，由于建立索引这种方式更适用于大数据量时的情况，因此，在Word的搜索中并非很适合。1.2.3 传统查找的优点和不足在Word中，查找是通过线性匹配驻留于内存中的文本而实现的。这种方式被称为顺序查找，或是在线查找。它
30、无需对文档集合中的信息进行预处理，或者是只需很少的预处理。这种在线分析方法仅适合于文档较少的情况（例如，目标文档集合大小仅有几M），或是文档集合的内容经常发生变化（如Word中，一个文档的内容可以被任意修改），或是没有足够空间来支持索引的情况下。它的优点是结构简单，易于实现；缺点就是信息检索的速度比较慢。例如，构建一个10M左右的Word文件，并将一个关键字“This is a test”放置于文档的最后，然后使用Word提供的查找功能，来查找这个关键字。如图1-11所示。图1-11 一个10M的Word文档，共有2820页Word大约需要3秒钟才能完成查找，可如果将这个关键字放在文档的头几页
31、（比如第10页），再次进行查找时，我们会发现，在按下“查找下一处”按钮的同时，Word已经找到了关键字，并高亮显示它。这种时间上的差别，是线性查找（或称在线查找）的显著特点。可以想象，如果将这种方法应用于一个大型的信息检索系统，信息的存储容量在T级别时，查找的速度是无法忍受的。1.2.4 使用索引提高检索速度我们需要一种方法，对文档进行预处理，在文档间建立一种便于检索的数据结构，以此来提高信息检索的速度。这种数据结构就是索引。当信息检索系统所要处理的文档数量巨大时，建立索引能够显著提高信息检索的速度。不过，索引系统不支持快速的信息更改，因为这涉及到数据内容的变更，需要对整个数据结构中的关系链进
32、行维护。但大多数信息检索系统中的文档数据都相对稳定，小的变更与整个系统的数据量相比，可以忽略不计。比如Web搜索引擎，它就维护了一个庞大的索引库，由爬虫蜘蛛每天从网上抓取最新网页，并更新索引库。1.2.5 倒排索引事实上，常用的索引方式有3种，分别是倒排、后缀数组和签名文件。倒排索引已经被当前大多数信息系统所广泛使用。它特别适合于人们的思维习惯，同时它对关键字检索非常有效。后缀数组在短语查询时，具有较快速度，只是构造和维护这样的索引库非常复杂。签名文档的方式已经基本被淘汰，更多人转而使用倒排方式。1什么是倒排用一个简单的例子来说明，当我们在阅读一本书时，通常使用页数来查找相关内容。每一页上具有一定数量的文本，这些文本记录了信息。当使用倒排方式后，不再有整页整页的信息了，信息被分割成一个个的关键字，并辅以关键字所在原书中的页数，而构成一个倒排基本单位。例如，一本旅游类书籍的第13
