搜索引擎的研究与实现方案.docx
《搜索引擎的研究与实现方案.docx》由会员分享，可在线阅读，更多相关《搜索引擎的研究与实现方案.docx（65页珍藏版）》请在冰点文库上搜索。
搜索引擎的研究与实现方案
搜索引擎的研究与实现方案
（WORD版完整可编辑，需更多资料请联系）
摘要
网络中的资源非常丰富，但是如何有效地找到自己需要的信息却是一件困难的事情。
网络搜索引擎应运而生。
本文首先详细介绍了网络搜索引擎的系统结构，然后从网页信息抓取、网页内容分析、网页索引建立、用户检索与结果排序等方面进行详细的说明。
为了更加深刻的理解这种技术，本人还亲自实现了一个自己的搜索引擎，能够实现网页内容的抓取和搜索功能，也能够自己添加内容并显示在搜索结果中。
网络搜索引擎根据初始配置，自动从网络上抓取信息并处理，将提取到的信息结构化，然后建立索引。
然后通过web服务器接收用户请求，在索引库中找到相关结果并排序，最终通过页面的形式呈现给用户。
本人在介绍搜索引擎的章节中除了详细的阐述技术核心外还结合了搜索引擎的实现代码来说明，图文并茂、易于理解。
关键词：
搜索引擎；网络；Lucene
Researchandimplementationofsearchengine
Abstract
Theresourcesintheinternetareabundant,butitisadifficultjobtosearchsomeusefulinformation.Soasearchengineisthebestmethodtosolvethisproblem.Thisarticlefistintroducesthesystemstructureofsearchenginebasedontheinternetindetail,thengivesaminuteexplanationformSpidersearch,engineandwebserver.Inordertounderstandthetechnologymoredeeply,Ihaveprogrammedawebsearchenginebymyself.
Thenewssearchengineisexplainedandsearchedaccordingtohyperlinkfromaappointedwebpage,thenindexeseverysearchedinformationandaddsittotheindexdatabase.Thenafterreceivingthecustomers'requestsfromthewebserver,itsoonsearchestherightpagesformtheindexengine。
Inthechapterofintroducingsearchengine,itisnotonlyelaboratethecoretechnology,butalsocombinewiththemoderncode,picturesincluded,easytounderstand.
Keywords:
searchengine;network;Lucene
1引言
面对浩瀚的网络资源，搜索引擎为所有网上冲浪的用户提供了一个入口，毫不夸张的说，所有的用户都可以从搜索出发到达自己想去的网上任何一个地方。
因此它也成为除了电子邮件以外最多人使用的网上服务。
搜索引擎技术伴随着WWW的发展是引人注目的。
搜索引擎大约经历了三代的更新发展：
第一代搜索引擎出现于1994年。
这类搜索引擎一般都索引少于1，000，000个网页，极少重新搜集网页并去刷新索引。
而且其检索速度非常慢，一般都要等待10秒甚至更长的时间。
在实现技术上也基本沿用较为成熟的IR（InformationRetrieval）、网络、数据库等技术，相当于利用一些已有技术实现的一个WWW上的应用。
在1994年3月到4月，网络爬虫WorldWebWorm（WWWW）平均每天承受大约1500次查询。
大约在1996年出现的第二代搜索引擎系统大多采用分布式方案（多个微型计算机协同工作）来提高数据规模、响应速度和用户数量，它们一般都保持一个大约50，000，000网页的索引数据库，每天能够响应10，000，000次用户检索请求。
1997年11月，当时最先进的几个搜索引擎号称能建立从2，000，000到100，000，000的网页索引。
Altavista搜索引擎声称他们每天大概要承受20，000，000次查询。
2000年搜索引擎2000年大会上，按照Google公司总裁LarryPage的演讲，Google正在用3,000台运行Linux系统的个人电脑在搜集Web上的网页，而且以每天30台的速度向这个微机集群里添加电脑，以保持与网络的发展相同步。
每台微机运行多个爬虫程序搜集网页的峰值速度是每秒100个网页，平均速度是每秒48.5个网页，一天可以搜集超过4，000，000网页
搜索引擎一词在国内外因特网领域被广泛使用，然而他的含义却不尽相同。
在美国搜索引擎通常指的是基于因特网的搜索引擎，他们通过网络机器人程序收集上千万到几亿个网页，并且每一个词都被搜索引擎索引，也就是我们说的全文检索。
著名的因特网搜索引擎包括FirstSearch、Google、HotBot等。
在中国，搜索引擎通常指基于网站目录的搜索服务或是特定网站的搜索服务，本人这里研究的是基于因特网的搜索技术。
2搜索引擎研究
2.1搜索引擎发展历史
2.1.1分类目录时代
分类目录是将网站信息系统地分类整理，提供一个按类别编排的网站目录，在每类中，排列着属于这一类别的网站站名、网址链接、内容提要，以及子分类目录，可以在分类目录中逐级浏览寻找相关的网站，分类目录中往往还提供交叉索引，从而可以方便地在相关的目录之间跳转和浏览。
也可以使用关键词进行检索，检索结果为网站信息，这种检索也称之为网站检索。
分类目录专案效仿一些在20世纪最重要的编辑员/志愿者项目。
就像牛津英文字典通过志愿者的努力成为权威的工具一样，OpenDirectory跟随着它的脚步也成为了权威的互联网分类目录。
2.1.2文本检索时代
文本检索，亦称为自然语言检索，指不对文献进行任何标引，直接通过计算机以自然语言中的语词匹配查找的系统。
文本检索进行匹配的对象，可以是整个出版的文本，包括文章、报告甚整本图书，也可以是它的部分，如文摘、摘录或只是文献的题名。
以整个文献正文为对象进行的匹配查找，称为全文检索。
这种方式无需标引，数据库制作快，可以很快投入运行。
2.1.3整合分析时代
这一代的搜索引擎所使用的方法大概是和我们今天的网站的外部链接形式基本相同，在当时，外部链接代表的是一种推荐的含义，通过每个网站的推荐链接的数量来判断一个网站的流行性和重要性。
然后搜索引擎再结合网页内容的重要性来和相似程度来改善用户搜索的信息质量。
这种模式的首先使用者是google，google不仅为首次使用并且大获成功，这一成就在当时引起了学术界和其他商业搜索引擎的极度关注。
后来，学术界以此成就为基础，提出了更多的改进的链接分析算法。
大多数的主流搜索引擎都在使用分析链接技术算法。
这就是第三代搜索引擎。
2.1.4用户中心时代
这一时代的搜索引擎的特点是以用户为中心。
其与第三代搜索引擎最大的区别是，对于相同的搜索关键词，不同用户得到的搜索结果可能不同。
第四代搜索将把个性化信息及人际推荐关系叠加到链接分析上，大大改善搜索结果排序效果；同时，跨媒体搜索将实现诸如用图片搜索图片等功能，打通文字，图片，视频，声音的界限，颠覆现在全部基于关键字的搜索方法，为用户带来更加直观的搜索体验。
并且，社交关系的引入将使网页排序质量大大提高。
2.2搜索引擎的结构
2.2.1Web搜索引擎体系结构
在搜索引擎的后台，有一些用于搜集网页信息的程序。
所收集的信息一般是能表明网站内容（包括网页本身、网页的URL地址、构成网页的代码以及进出网页的连接）的关键词或者短语。
接着将这些信息的索引存放到数据库中。
一个典型的网络搜索引擎的结构如图2-1所示：
图2-1搜索引擎的结构
2.2.2网络机器人
又称为网络爬虫，网络蜘蛛等。
在搜索引擎系统中扮演搜集器的角色。
它通常是一个计算机程序，在需要时运行。
网络机器人通过统一资源定位符（URL）来访问网络资源。
它会从一个入口URL列表开始，通过一定的算法顺序，下载并通过网页分析器分析网页，从网页中发现新的URL地址，并将新发现的URL添加到待访问的URL列表中。
网络爬虫将得到的网页保存在本地网页库中，以备网页分析器和索引器进行处理和使用。
互联网中的网页数以亿计，一个网络机器人应该尽可能多地覆盖网络，但不可能访问到所有的网页。
如何更加有效地下载网页就成了网络机器人设计过程中最需要解决的问题。
为了有效利用带宽资源和处理能力，抓取过程中需要算法和策略支持。
常用的算法有深度优先搜索策略、IP段扫描搜索策略、广度优先搜索策略等。
通常主要采用广度优先搜索策略，保证对互联网的整体覆盖率。
同时配合探测性的搜索策略，快速发现新的网络资源。
每个搜索策略的具体介绍如下：
1.深度优先搜索策略：
深度优先的基本方法是依次访问下一级的网页链接，直到不能再深入为止。
网络机器人完成一个搜索分支后返回到上一个链接节点进一步搜索其他链接。
当所有链接已经遍历之后，搜索任务结束。
深度优先算法比较适合垂直搜索或站内搜索等应用环境。
对大规模的互联网搜索，由于部分网站内容层次结构很深，会造成巨大的资源浪费。
2.IP段扫描搜索策略：
IP段扫描搜索策略的基本思想是以某种策略找到一批起始IP地址。
从设定的IP地址，按照IP地址递增的方式搜索后续的每一个IP地址中的信息。
这种方法可以解决网络蜘蛛对HTML文件中指向其他Web站点的超链接地址的过度依赖，能够发现新的孤立资源。
但是这种策略计算范围巨大，不适用于大规模的搜索，但可以用于配合其他策略在小范围内全面搜索。
3.广度优先搜索策略：
广度优先搜索策略主要按照目录层次比较浅的网页内容优先的搜索方法。
网络机器人先访问所有同一层次的内容，然后再继续搜索下一层。
这种方法保证了对网页内容的有效控制，避免遇到一个无穷深层分智时无法结束的问题。
广度优先搜索策略实现方便，不需要存储大量的中间节点，目前被广泛采用。
存在的问题是需要话费比较长的时间才能到达深层的网页。
单个网站的访问速度通常不高，为了提高网络利用率，网络机器人通常会采用多线程技术来同时访问多个网页。
网络机器人遇到的另一个问题是如何高效且正确的提取网页中的URL。
对于普通的HTML中你的链接比较容易。
但是随着XHTML技术的普及，大量的网页不再是简单的链接关系。
很多网络入口都包含在Javascript代码中，甚至有些是动态生成的。
如何正确地得到这些URL，如何解决死链，如何处理非文本内容等，都是网络机器人需要解决的问题。
2.2.3网页分析器
网络机器人搜集来的网页信息或下载的文档一般要首先进行分析，用于后续建立索引。
对于通用型网络搜索引擎，网页提取技术主要对下载的数据进行正文提取分析操作；对于垂直搜索，在结构化操作以后，还要对其进行数据挖掘，进行领域信息识别，从而提高信息的质量。
我呢当分析技术一般包括分词、过滤、转换等工作，具体处理与文档类型、搜索引擎的具体结构和算法密切相关。
网页分析中的一项关键技术就是分词。
与英文为代表的拉丁语系语言相比，英文以空格作为天然的分隔符，而中文由于继承自古代汉语的传统，词语之间没有分隔。
古代汉语中除了连绵词和人名地名等，词通常就是单个汉字，所以当时没有分词书写的必要。
而现代汉语中双字或多字词居多，一个字不再等同于一个词。
在中文里，“词”和“词组”边界模糊。
现代汉语的基本表达单元虽然为“词”，且以双字或者多字词居多，但由于人们认识水平的不同，对词和短语的边界很难去区分。
中文分词对于搜索引擎来说，最重要的并不是找到所有结果，因为在上百亿的网页中找到所有结果没有太多的意义，没有人能看得完，最重要的是把最相关的结果排在最前面，这也称为相关度排序。
中文分词的准确与否，常常直接影响到对搜索结果的相关度排序。
从定性分析来说，搜索引擎的分词算法不同，词库的不同都会影响页面的返回结果。
现有的分词算法可分为三大类：
基于字符串匹配的分词方法、基于理解的分词方法和基于统计的分词方法。
按照是否与词性标注过程相结合，又可以分为单纯分词方法和分词与标注相结合的一体化方法。
2.2.4网页索引器
网页需要建立索引才能被后续流程使用。
设计良好的索引可以加快搜索速度，能够更准确地进行网页定位，从而减少设计开销。
索引的功能是对搜索器所搜索的信息进行分析处理，从中抽取索引项，用于表示文档以及生成文档库的索引表。
搜索引擎普遍借鉴了传统信息检索中的索引模型，包括倒排文档、矢量空间模型、概率模型等。
为了快速查找特定的信息，建立索引数据库是一种常用的方法，即将文档表示为一种便于检索的方式，并存储在索引数据库中。
索引数据库的格式是一种特殊的数据存储格式。
索引结构和效率的好坏是Web信息检索系统的关键，要求易于实现和维护、检索速度快、空间需求低。
倒排索引的结构如图2-2所示：
图2-2倒排索引的结构
索引器是用来建立索引的软件程序。
索引器的主要功能是分析处理文档的内容和信息，把文档转化成一系列的索引项。
索引中的最小信息单位是索引项，索引项除了文档内容，还可以包含文档的大小、时间、类型、存放路径等描述信息和附属信息。
索引项可以是短语、词组或单字。
索引项存储的信息包括关键词及其权重，以及来源URL、更新时间、编码格式、链接情况等。
搜索引擎的索引通常使用倒排表，也就是常说的倒排索引。
根据要求的速度和精度等要求，搜索引擎可以采用复合索引和简单索引。
记录索引项在文档中出现的位置，对检索时的匹配度计算也很有好处。
索引表也可能要记录索引项在文档中出现的位置，以便检索器计算索引项之间的相邻或接近关系。
2.2.5网页搜索器
用户输入检索词后，搜索引擎返回的结果需要根据语义相关性和其他权值进行排序。
通常的网页排序除了基本的检索词语素相关外，还要根据网页的连接情况，分析网页自身的重要性，保证用户得到重要的网页信息。
中文搜索引擎中经常由于语义歧义和差别，造成关键字检索将诶过的语义相关性效果较差。
一词多义造成的搜索结果和用户本意差距较大的情况时常发生。
垂直搜索由于只包含某个领域的信息，词义明确，可以提高结果的相关性。
2.3现代搜索引擎的主要技术
2.3.1倒排索引技术
在关系数据库系统里，索引[1]是检索数据最有效率的方式。
但对于搜索引擎，它并不能满足其特殊要求：
1）海量数据：
搜索引擎面对的是海量数据，像Google，XX这样大型的商业搜索引擎索引都是亿级甚至几千亿的网页数量，面对如此海量数据,使得数据库系统很难有效的管理。
2）数据操作简单：
搜索引擎使用的数据操作简单，一般而言，只需要增、删、改、查几个功能，而且数据都有特定的格式，可以针对这些应用设计出简单高效的应用程序。
而一般的数据库系统则支持大而全的功能，同时损失了速度和空间。
最后，搜索引擎面临大量的用户检索需求，这要求搜索引擎在检索程序的设计上要分秒必争，尽可能的将大运算量的工作在索引建立时完成，使检索运算尽量的少。
一般的数据库系统很难承受如此大量的用户请求，而且在检索响应时间和检索并发度上都不及我们专门设计的索引系统。
倒排索引，也常被称为反向索引、置入档案或反向档案，是一种索引方法，被用来存储在全文搜索下某个单词在一个文档或者一组文档中的存储位置的映射。
它是文档检索系统中最常用的数据结构。
通过倒排索引，可以根据单词快速获取包含这个单词的文档列表。
倒排索引主要由两个部分组成：
“单词词典”和“倒排文件”。
倒排索引有两种不同的反向索引形式：
一条记录的水平反向索引（或者反向档案索引）包含每个引用单词的文档的列表。
一个单词的水平反向索引（或者完全反向索引）又包含每个单词在一个文档中的位置。
后者的形式提供了更多的兼容性（比如短语搜索），但是需要更多的时间和空间来创建。
现代搜索引擎的索引都是基于倒排索引。
相比“签名文件”、“后缀树”等索引结构，“倒排索引”是实现单词到文档映射关系的最佳实现方式和最有效的索引结构.
2.3.2分布式技术
分布式搜索引擎是根据地域、主题、IP地址及其它的划分标准将全网分成若干个自治区域，在每个自治区域内设立一个检索服务器，而每个检索服务器由信息搜索机器人、索引搜索软件数据库和代理三部分组成。
信息搜索机器人负责本自治区域内的信息搜索，并建立索引信息存入索引数据库。
代理负责向用户提供查询接口，并与其它代理进行互换，实现检索服务器之间的信息交换，且查询可以重定向，即如果一个索引数据库没有满足查询要求，它可以将查询请求发送到其它检索服务器上。
它与集中式搜索引擎相比有以下优点：
各检索服务器之间相互共享资源，站点只向本自治区域内的信息搜索机器人提供信息，减轻了网络及各站点的负载。
各代理之间的相互协作及查询重定向使得提供的服务更完善。
与Web本身的分布式特性相适应，具有良好的可扩充性，便于维护。
索引信息划分到各自的索引数据库中，使得各索引数据库相对较小，查询的响应时间相对较短。
部分检索服务器发生故障时，其它部分能正常工作。
2.4小结
本章介绍了搜索引擎的发展历程，并讨论了未来搜索引擎的形态。
然后重点阐述了现代网络搜索引擎的主要组成结构。
网络机器人利用搜索策略和算法获取网页。
网页分析器对网页进行正文提取、分词等加工操作，分析和处理，生成可以被索引的标准文档。
网页索引器生成对文档的倒排索引。
网页搜索器分析用户输入的关键词，在索引库中检索，按照一定的算法将检索结果排序后呈现给用户。
最后，介绍了现代搜索引擎的两个主要技术：
倒排索引和分布式技术。
3
开发平台和技术
本章主要介绍了搜索引擎系统的开发平台以及使用的技术。
3.1Java编程语言
Java是一种可以撰写跨平台应用软件的面向对象的程序设计语言，是由SunMicrosystems公司于1995年5月推出的Java程序设计语言和Java平台（即JavaEE,JavaME,JavaSE）的总称。
Java自面世后就非常流行，发展迅速，对C++语言形成了有力冲击。
Java技术具有卓越的通用性、高效性、平台移植性和安全性，广泛应用于个人PC、数据中心、游戏控制台、科学超级计算机、移动电话和互联网，同时拥有全球最大的开发者专业社群。
在全球云计算和移动互联网的产业环境下，Java更具备了显著优势和广阔前景。
Java语言具有如下特点：
1.简单
Java最初是为对家用电器进行集成控制而设计的一种语言，因此它必须简单明了。
Java语言的简单性主要体现在以下三个方面：
1） Java的风格类似于C++，因而C++程序员是非常熟悉的。
从某种意义上讲，Java语言是C及C++语言的一个变种，因此，C++程序员可以很快就掌握Java编程技术。
2） Java摒弃了C++中容易引发程序错误的地方，如指针和内存管理。
3） Java提供了丰富的类库。
2.面向对象
面向对象可以说是Java最重要的特性。
Java语言的设计完全是面向对象的，它不支持类似C语言那样的面向过程的程序设计技术。
Java支持静态和动态风格的代码继承及重用。
单从面向对象的特性来看，Java类似于Small Talk，但其它特性、尤其是适用于分布式计算环境的特性远远超越了Small Talk。
3.分布式
Java包括一个支持HTTP和FTP等基于TCP/IP协议的子库。
因此，Java应用程序可凭借URL打开并访问网络上的对象，其访问方式与访问本地文件系统几乎完全相同。
为分布环境尤其是Internet提供的动态内容无疑是一项非常宏伟的任务，但Java的语法特性却使我们很容易地实现这项目标。
4.健壮
Java致力于检查程序在编译和运行时的错误。
类型检查帮助检查出许多开发早期出现的错误。
Java自已操纵内存减少了内存出错的可能性。
Java还实现了真数组，避免了覆盖数据的可能。
这些功能特征大大缩短了开发Java应用程序的周期。
Java提供Null指针检测数组边界检测异常出口字节代码校验。
5.结构中立
另外，为了建立Java作为网络的一个整体，Java将它的程序编译成一种结构中立的中间文件格式。
只要有Java运行系统的机器都能执行这种中间代码。
现在，Java运行系统有Solaris2.4（SPARC）,Win32系统（Windows95和WindowsNT）等.Java源程序被编译成一种高层次的与机器无关的byte-code格式语言，这种语言被设计在虚拟机上运行，由机器相关的运行调试器实现执行。
6.安全
Java的安全性可从两个方面得到保证。
一方面，在Java语言里，象指针和释放内存等C++功能被删除，避免了非法内存操作。
另一方面，当Java用来创建浏览器时，语言功能和浏览器本身提供的功能结合起来，使它更安全。
Java语言在你的机器上执行前，要经过很多次的测试。
它经过代码校验，检查代码段的格式，检测指针操作，对象操作是否过分以及试图改变一个对象的类型。
7.可移植的
这句话一直是Java程序设计师们的精神指标，也是Java之所以能够受到程序设计师们喜爱的原因之一，最大的功臣就是JVM的技术。
大多数编译器产生的目标代码只能运行在一 种CPU上（如Intel的x86系列），即使那些能支持多种CPU的编译器也不能同时产生适合多 种CPU的目标代码。
如果你需要在三种CPU（ 如x86、SPARC 和MIPS）上运行同一程序, 就必须编译三次。
但JAVA编译器就不同了。
JAVA编译器产生的目标代码（J-Code） 是针对一种并不存在的CPU--JAVA虚拟机（JAVAVirtualMachine），而不是某一实际的CPU。
JAVA虚拟机能掩盖不同CPU之间的差别，使J-Code能运行于任何具有JAVA虚拟机的机器上。
3.2MyEclipse
MyEclipse企业级工作平台（MyEclipseEnterpriseWorkbench，简称MyEclipse）是对EclipseIDE的扩展，利用它我们可以在数据库和JavaEE的开发、发布以及应用程序服务器的整合方面极大的提高工作效率。
它是功能丰富的JavaEE集成开发环境，包括了完备的编码、调试、测试和发布功能，完整支持HTML,Struts,JSP,CSS,Javascript,Spring,SQL,Hibernate。
MyEclipse是一个十分优秀的用于开发Java,J2EE的Eclipse插件集合，MyEclipse的功能非常强大，支持也十分广泛，尤其是对各种开源产品的支持十分不错。
MyEclipse目前支持JavaServlet,AJAX,JSP,JSF,Struts,Spring,Hibernate,EJB3,JDBC数据库链接工具等多项功能。
可以说MyEclipse是几乎囊括了目前所有主流开源产品的专属eclipse开发工具。
3.3Tomcat
Tomcat是由Apache软件基金会下属的Jakarta项目开发的一个Servlet容器，按照SunMicrosystems提供的技术规范，实现了对Servlet和JavaServerPage（JSP）的支持，并提供了作为Web服务器的一些特有功能，如Tomcat管理和控制平台、安全局管理和Tomcat阀等。
由于Tomcat本身也内含了一个
升级会员 