小型搜索引擎的设计与实现.docx

小型搜索引擎的设计与实现.docx

《小型搜索引擎的设计与实现.docx》由会员分享，可在线阅读，更多相关《小型搜索引擎的设计与实现.docx（20页珍藏版）》请在冰点文库上搜索。

小型搜索引擎的设计与实现

摘要

互联网上的信息每天都以指数量级的速度爆炸性增长，面对如此浩瀚的资源，搜索引擎为所有网上冲浪的用户提供了一个入口，所有的用户都可以从搜索引擎出发到达自己想去的网上任何一个地方。

因此它也成为除了电子邮件以外最多人使用的网上服务。

但是，随着信息多元化的增长，千篇一律的给所有用户提供同一个入口显然已经不能满足特定用户更深入的查询需求。

本文首先详细介绍了基于英特网的搜索引擎的系统结构，然后从网络机器人、索引引擎、Web服务器三个方面进行详细的说明。

这不仅对政府、企业、院校的发展极为不利，还在宏观上成为制约我国信息化建设健康良性发展的一大障碍。

搜索引擎不是单纯的技术问题。

在互联网时代，哪一个公司掌握了包括搜索引擎、信息传递在内的基础软件，它就能在竞争中傲视群雄；哪一个国家掌握和普及了这些技术，她就能在运用互联网的商业竞争占尽先机。

关键词：

搜索引擎，网络机器人，优化策略，索引

Abstract

InformationontheInternetgrowsexplosivelyeveryday.Searchengineprovidesallthesurfersonitwithanentrance,fromwhichtheycanreacheverycorneroftheweb.Therefore,searchenginebecomesthemostpopularnetworkservicesecondtoemail.Withinformationcontinuingtoexplodeinalldirections,however,somespecifickindsofusersarenotsatisfiedwithonlyoneentrance.Thisarticlefistintroducesthesystemstructureofsearchenginebasedontheinternetindetail,thengivesaminuteexplanationformSpidersearch,engineandwebserver.

Thisnotonlyisextremelydisadvantageoustothedevelopmentofthegovernment,businessenterprise,college,butalsobecometomakeonthemacroviewtheroughlyourcountryinformationturnsabigobstacleofthepositivedevelopmentinhealthindevelopments.

Searchingfortheengineisnotapuretechniqueproblem.LookdownuponthegroupofheroesinInternetages,whichcompaniescontrolincludemanhuntengine,informationdeliverfoundationininsidesoftware,itcaninthecompetition;Whichnationscontroledwithmadewidelyavailablethesetechniqueses,shecanoccupyatthebusinessthatmakeuseoftheInternetcompetitionexhaustedfirsttiming.

Keywords:

SearchEngine，Robot，OptimizeStrategies，Index

第一章概述

1.1引言

随着计算机技术和互联网技术的飞速发展，人们越来越依靠网络来查找他们所需要的信息，但是，由于网上的信息源多不胜数，也就是我们经常所说的"RichData,PoorInformation"。

所以如何有效的去发现我们所需要的信息，就成了一个很关键的问题。

为了解决这个问题，搜索引擎就随之诞生。

搜索引擎是仅次于门户的互联网的第二大核心技术，伴随着互联网的普及和网上信息的爆炸式的增长，它越来越引起人们的重视。

现在在网上的搜索引擎也已经有很多，比较著名的有Google，AltaVista,Yahoo,InfoSeek,Metacrawler,SavvySearch等等。

国内也建立了很多的搜索引擎，比如：

搜狐、新浪、北极星、XX等等,当然由于它们建立的时间不长，在信息搜索的取全率和取准率上都有待于改进和提高。

例如：

AltaVista是一个速度很快的搜索引擎，由于它强大的硬件配置，使它能够做及其复杂的查询。

它主要是基于关键字进行查询，它漫游的领域有Web和Usenet。

支持布尔查询的"AND"，"OR"和"NOT"，同时还加上最相近定位"NEAR"，允许通配符和"向后"搜索（比如：

你可以查找链接到某一页的所有Web站点）。

你可以决定是否对搜索的短语加上权值，在文档的什么部位去查找它们。

能够进行短语查询而不是简单的单词查询的优点是很明显的，比如，我们想要查找一个短语"tobeornottobe"，如果只是把它们分解成单词的话，这些单词都是属于StopWord，这样这个查询就不会有任何结果，但是把它当作一个整体来查询，就很容易返回一些结果，比如关于哈姆雷特或者是莎士比亚等等的信息。

系统对查询结果所得到的网页的打分是根据在网页中所包含的你的搜索短语的多少，它们在文档的什么位置以及搜索短语在文档内部之间的距离来决定的。

同时可以把得到的搜索结果翻译成其他的语言。

信息系统中的数据获取主要就是主要查找那些包含用户查询中的关键词文档。

由于用户查询常常不能准确地表达用户的信息需求。

实际上，用户更多的是希望获取于某个主题相关的信息，而非那些仅仅满足查询的数据。

如果不能很好的解决搜索问题，在收集信息、从事内容方面的花费的人力物力越大，其浪费就越大。

这不仅对政府、企业、院校的发展极为不利，还在宏观上成为制约我国信息化建设健康良性发展的一大障碍。

搜索引擎不是单纯的技术问题。

在互联网时代，哪一个公司掌握了包括搜索引擎、信息传递在内的基础软件，它就能在竞争中傲视群雄；哪一个国家掌握和普及了这些技术，她就能在运用互联网的商业竞争占尽先机。

1.2课题的基本内容

本课题的主要是设计和实现一个小型的搜索引擎，通过大量的学习，实现搜索引擎的主要功能和完成全部的设计工作。

搜索引擎的基本原理是通过网络机器人定期在web网页上爬行，然后发现新的网页，把它们取回来放到本地，用户的查询请求可以通过查询本地的数据来得到。

如yahoo每天会找到大约500万个新的网页，google可以达到80亿网页以及10万台服务器共同工作。

搜索引擎的实现机制一般有两种：

一种是通过手工方式对网页进行索引，比如yahoo的网页是通过手工分类的方式实现的，它的缺点是Web的覆盖率比较低，同时不能保证最新的信息。

查询匹配是通过用户写入的关键字和网页的描述和标题来进行匹配，而不是通过全文的匹配进行的。

第二种是对网页进行自动的索引，像AltaVista则是完全通过自动索引实现的。

这种能实现自动的文档分类，实际上采用了信息提取的技术。

但是在分类准确性上可能不如手工分类。

1.2.1搜索引擎三段式工作流程：

1.搜集：

定期搜集，每次搜集替换上一次的内容，我们称之为“批量搜集”。

主要内容包括：

文本内容的分析与提取、超文本连接的提取与解析、网络通信及信息获取。

搜索引擎一般都有一个Robot（或者称为Spider）定期的访问一些站点，来检查这些站点的变化，同时查找新的站点。

一般站点有一个robot.txt文件用来说明服务器不希望Robot访问的区域，Robot都必须遵守这个规定。

如果是自动索引的话，Robot在得到页面以后，需要对该页面根据其内容进行索引，根据它的关键字的情况把它归到某一类中。

页面的信息是通过元数据的形式保存的，典型的元数据包括标题、IP地址、一个该页面的简要的介绍，关键字或者是索引短语、文件的大小和最后的更新的日期。

尽管元数据有一定的标准，但是很多站点都采用自己的模板。

文档提取机制和索引策略对Web搜索引擎的有效性有很大的关系。

2.整理：

我们将对关键词进行提取，也就是把网页中的文本内容提取出来；由于在互联网上，网页的重复率平均大约为4，所以会对内容完全相同的页进行消除（我们将以改进的TWFormat格式存储）。

主要内容是文本信息的存储与索引：

互联网上大部分信息都是以HTML格式存在，对于索引来说，只处理文本信息。

因此需要把网页中文本内容提取出来，过滤掉一些脚本标示符和一些无用的广告信息，同时记录文本的版面格式信息。

存储在我们这里是在网页种文本内容提取和过滤掉脚本语言后，将其存为HTML格式和TXT格式，并且命名为Sitemap.htm和Sitemap.txt。

3.服务：

因为要对最终用户服务，搜索引擎返回给用户的，是一个和用户查询相关的结果列表。

因此要进行：

查询方式和匹配和结果排序。

1.3开发环境

开发平台：

MicrosoftWindowsXPSp2;

开发工具：

MicrosoftVisualC++Sp6;

使用语言：

C++；

本系统使用VisualC++6.0集成开发环境，它功能强大而且便于设计交互界面。

在设计的使用了由DavidPullman编写的CRobotInternet类体，方便了开发和加快了工程进度；而且微软提供的Winnet类是一个应用层的网络通信组件，它可以使应用程序很容易的实现http、ftp、gopher等协议而不需要你去深入的了解协议本身的规范，方便了开发者。

第二章搜索引擎的技术概要

2.1搜索引擎简述

第一代搜索引擎出现于1994年。

这类搜索引擎一般都索引少于1，000，000个网页，极少重新搜集网页并去刷新索引。

而且其检索速度非常慢，一般都要等待10秒甚至更长的时间。

在实现技术上也基本沿用较为成熟的IR（InformationRetrieval）、网络、数据库等技术，相当于利用一些已有技术实现的一个WWW上的应用。

在1994年3月到4月，网络爬虫WorldWebWorm（WWWW）平均每天承受大约1500次查询。

2000年搜索引擎2000年大会上，按照Google公司总裁LarryPage的演讲，Google正在用3,000台运行Linux系统的个人电脑在搜集Web上的网页，而且以每天30台的速度向这个微机集群里添加电脑，以保持与网络的发展相同步。

每台微机运行多个爬虫程序搜集网页的峰值速度是每秒100个网页，平均速度是每秒48.5个网页，一天可以搜集超过4，000，000网页。

搜索引擎一词在国内外因特网领域被广泛使用，然而他的含义却不尽相同。

在美国搜索引擎通常指的是基于因特网的搜索引擎，他们通过网络机器人程序收集上千万到几亿个网页，并且每一个词都被搜索引擎索引，也就是我们说的全文检索。

著名的因特网搜索引擎包括FirstSearch、Google、HotBot等。

在中国，搜索引擎通常指基于网站目录的搜索服务或是特定网站的搜索服务，这里我们研究的是基于因特网的搜索技术。

国内最早面世的的搜索引擎是“悠游”这是世界上第一个中文智能搜索引擎，于1997年投入使用。

它是以香港中文大学的研究成果为基础、专为中文设计开发的产品。

在本章中，我们将一次讲述搜索引擎的构成、工作原理及搜索引擎的主要指标及其分析。

2.2基于Internet的搜索引擎的构成的

搜索引擎根据用户的查询请求，按照一定的算法从索引数据中查询对应的信息并返回给用户。

为保证搜索引擎必须建立并维护一庞大的索引数据库。

而一般搜索引擎主要由网络蜘蛛，索引与搜索引擎软件组成。

2.2.1网络蜘蛛

又称“爬行者”（Crawler或WebRobot），是一个功能强大的程序。

它会根据预先的设定的地址去查看对应的网页，如果网页发生变化则重新获取该网页，否则继续访问。

网络蜘蛛访问页面的过程是对互联网上信息遍历的过程，为了保证网络蜘蛛遍历信息的广度，一般事先设定一些重要的链接，然后对这些链接进行遍历，在遍历过程中不断记录网页中的链接。

2.2.2索引

网络蜘蛛将遍历到的网页存放在临时数据库中。

为提高检索的效率，需要按照。

如果有时索引不能被及时更新，网络蜘蛛带回的新信息就不能被使用搜索引擎的用户查到了。

因此，可以得到下面的结论：

新信息更新的周期等于网络蜘蛛停止时间加上遍历的时间加上索引的时间。

2.2.3搜索引擎软件

该软件用来筛选索引中无数的网页信息，挑选出符合查询要求的网页并将它们进行分级排序，与查询的关键字关联越大的排得越靠前，然后将分级排序后的结果显示给用户。

但是根据专家的测评，目前的搜索引擎返回的相关结果的比率不足45%，而且由于机制、范围、算法等的不同，导致同样一个检索请求在不同搜索引擎的查询结果的重复率不足34%。

2.3搜索引擎的主要指标及其分析

搜索引擎的主要指标有响应时间、召回率、准确率、受欢迎程度、建立索引的方法和相关度等。

这些指标决定了搜索引擎的技术指标。

搜索引擎的技术指标决定了搜索引擎的评价指标。

好的搜索引擎应该是具有较快的反应速度和高召回率、准确率的，当然这些都需要搜索引擎技术指标来保障。

响应时间、召回率、准确率和受欢迎程度为搜索引擎的主要评价指标。

建立索引的方法和相关度是搜索引擎有代表性的技术指标。

搜索引擎的技术指标决定了搜索引擎的评价指标。

好的搜索引擎因具有应具有较快的响应速度和高召回旅和准确率，这些当然都需要搜索引擎技术指标来保障。

第三章网络机器人

3.1什么是网络机器人

网络机器人又称为Spider程序，是一种专业的Bot程序。

用于查找大量的Web页面。

它从一个简单的Web页面上开始执行，然后通过其超链接在访问其他页面，如此反复理论上可以扫描互联网上的所有页面。

基于因特网的搜索引擎是Spider的最早应用。

例如搜索巨头Google公司，就利用网络机器人程序来遍历Web站点，以创建并维护这些大型数据库。

网络机器人还可以通过扫描Web站点的主页来得到这个站点的文件清单和层次机构。

还可以扫描出中断的超链接和拼写错误等。

3.2网络机器人的结构

3.2.1网络机器人（SPIDER）的组成

SPIDER（也称为CRWALER或WebRobot）搜集的过程主要是的工作过程。

SPIDER要获取的对象是存在于网络上数以亿计的网页，这些网页以超链接形式互相联系在一起，每一网页对应一个超链接，也称统一资源定位符。

我们可以把网络看做一个图，网络中的网页构成节点集，他们之间的链接构成边集，SPIDER正是从某一节点开始沿着边遍历图，每访问到图中一个节点，就进行一定的处理。

当SPIDER程序访问到一个网页，必须进行以下几项基本处理：

A，抽取网页中包含的文本；

B，抽取网页中包含的URL并将其区分。

SPIDER工作过程：

Step1:

给SPIDER程序赋予一个初始URL,加入等待队列。

Step2:

启动。

Step3:

查询等待队列中是否有URL,若没有，且无其他活动线程；线程结束，若有Step4。

Step4:

从URL等待对列中取出一个URL并移入运行队列，根据该URL去访问，并进行网页下载，抽取文本，抽取链接等工作，若网页中包含同网站URL则将这些URL加入等待队列；把访问过的URL加入完成队列，转Step3。

SPIDER搜集的过程：

3.3HTML语言

因为Web中的信息都是建立在HTML协议之上的，所以网络机器人在检索网页时的第一个问题就是解析HTML。

HTML是在WWW上建立的超文本的语言，它通过标记和属性对一段文本的语言进行描述。

在解决如何解析之前，首先来介绍下HTML中的几种数据。

文本：

除了脚本和标签之外的所有数据

注释：

程序员留下的说明文字，对用户是不可见的

简单标签：

由单个表示的HTML标签

开始标签和结束标签：

用来控制所包含的HTML代码

我们在进行解析的时候不用关心所有的标签，只需要对其中几种重要的进行解析即可。

超连接标签

超连接定义了WWW通过Internet链接文档的功能。

他们的主要目的是使用户能够任意迁移到新的页面，这正是网络机器人最关心的标签。

图像映射标签

图像映射是另一种非常重要的标签。

它可以让用户通过点击图片来迁移到新的页面中。

表单标签

表单是Web页面中可以输入数据的单元。

许多站点让用户填写数据然后通过点击按钮来提交内容，这就是表单的典型应用。

表格标签

表格是HTML的构成部分，通常用来格式化存放、显示数据。

3.4网络机器人的实现及代码分析

3.4.1程序结构图

Search整体类图：

CRobotCrawl结构示意图：

3.4.2结点的结构体

structURL_Page{

boolVisited_URL;//链接是否访问过0--未访问1--访问过

intSeqNum;//从0开始给链接的自动编号

CStringAbsolutURL;//链接的绝对URL

CStringURLContext;//链接的说明文字

CStringsLinks;//相对链接

intContextValue;//链接说明文字信息的价值

intImmediateReward;//链接包含关键字.PDF,.DOC,.PS的个数

intoutlink[50];//存放本页指出的网页ID

intinlink[30];//存放其他网页包含本页链接，保存该网页的ID

doublehubscore;//本页的HUB值

doubleauthorityscore;//本页的authorityscore值

};

HITS算法：

Kleinberg’soriginalworkincludingtheCLEVERProjectatIBM该算法认为每个WEB页面都有被指向作为“Authority”（权威goodsourceofcontents）和指向其他页面作为“Hub”（中心goodsourceoflinks）的两方面的属性。

HITS（Hyperlink－InducedTopicSearch）算法是利用Hub/Authority方法的搜索方法，算法如下：

将查询q提交给传统的基于关键字匹配的搜索引擎．搜索引擎返回很多网页，从中取前n个网页作为根集rootset），用S表示。

S满足如下3个条件：

1．S中网页数量相对较小

2．S中网页大多数是与查询q相关的网页

3．S中网页包含较多的权威网页

一个受尊敬的权威网页就是许多可靠的中心网页所提到的网页；而一个有用的中心则是指向许多有价值的权威网页。

他们的计算公式如下：

HITS算法的求解过程如下：

1、将所有页面（根集页面）的A和H赋予初值。

2、根据上面的公式计算新一轮的H和A的值。

3、规范化结果

4、重复2、3、直到结果收敛。

权威网页（Authority）和中心网页（Hub）：

权威网页（Authority），顾名思义，是给定主题底下的一系列重要的权威的网页。

其重要性和权威性主要体现在以下两点：

第一点，从单个网页来看，它的网页内容本身对于这个给定主题来说是重要的；

第二点，从这个网页在整个互联网重的地位来看，这个网页是被其他网页承认为权威的，这主要体现在跟这个主题相关的很多网页都有链接指向这个网页。

由此可见，权威网页对于主题搜索引擎的实现有很重大的意义。

主题搜索引擎一个很关键的任务就是从互联网上无数的网页之中最快最准的找出这些可数的权威网页，并为他们建立索引。

这也是有效区别主题搜索引擎和前三代传统通用搜索引擎的重要特征。

中心网页（Hub），是包含很多指向权威网页的超链接的网页。

最典型中心网页的一个例子是Yahoo！

，它的目录结构指向了很多主题的权威网页，使得它兼任了很多主题的中心网页。

由中心网页出发，轻而易举的就会到达大量的权威网页。

因此，它对于主题搜索引擎的实现也起了很大的意义。

权威网页和中心网页之间是一种互相促进的关系：

一个好的中心网页必然要有超链接指向多个权威网页；一个好的权威网页反过来也必然被多个中心网页所链接；。

他们的关系如图3.1所示。

计算网页的authorityscore值：

for（i=0;i

j=0;sum1=0;sum2=0;if（m_URL[i].inlink[j]==-1）m_URL[i].authorityscore=1;

else{while（m_URL[i].inlink[j]!

=-1&&j

//计算第i个页面的hubscore

{q=m_URL[i].inlink[j];sum1=m_URL[q].hubscore+sum1;j++;}

m_URL[i].authorityscore=sum1;}

归化网页的authorityscore（代码片断）：

for（i=0;i

爬取站点CrawlSite的代码实现片断：

BOOLCRobotCrawl:

:

CrawlSite（constCString&sURL）

{n_URL=0;//表示初试的种子页为0号页面

m_nURLs=1;//表示要统计的子页数，记数从1开始记数

m_sURL=sURL;//这里放入种子页的sURL

KeyWordCount=0;

if（!

m_pInternet）

{m_pInternet=newCRobotInternet;

m_bAllocatedInternet=true;}//Endif

if（m_sUserAgent!

=""）m_pInternet->m_sUserAgent=m_sUserAgent;

if（m_sURL.Left（5）!

="http:

"）

{if（m_sURL.Left

（2）!

="//"）m_sURL="//"+m_sURL;m_sURL="http:

"+m_sURL;}//Endif

AfxParseURL（m_sURL,dwService,m_sServer,sObject,nPort）;

m_sDomain=m_sServer;nPos=m_sDomain.Find（"."）;

if（nPos!

=-1）m_sDomain=m_sDomain.Mid（nPos+1）;

if（m_bRobotExclusion）

{if（m_pInternet->httpGet（m_sServer+"/robots.txt",m_sRobotPolicy,nResult,sErrMsg））m_bRobotPolicyExists=true;

elsem_bR