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