搜索引擎研究毕业论文.docx

成都理工大学毕业设计(论文)搜索引擎研究摘 要搜索引擎 (search engine)，作为现在万维网中仅次于电子邮件的网络应用，它已成为广大网络用户获取信息的首要途径。目前国内外知名的搜索引起公司包括：Google、百度、雅虎、MSN、InfoSpace等等。其中，像Google、百度这样的全文搜索引擎是完整意义上的搜索引擎；雅虎、MSN则是目录式搜索引擎；InfoSpace则是元搜索引擎。本文简单介绍了搜索引起的发展历史、分类、世界知名搜索引擎和全文搜索引擎的工作流程、原理，各部分（搜索器、分析器、索引器、检索器）的工作方式。搜索引擎优化则是在2004年以后兴起的一门新型的技术，主要目的是增加特定关键字的曝光率以增加网站的能见度，以提高其在搜索引擎中的排名，提升网站的访问量，达到宣传或销售的目的。目前已经有许多的公司开始参与搜索引起优化方向的工作。关键词：搜索引擎分类,全文搜索引擎,搜索引擎优化Search EngineAbstract: Search engine, is now second only to e-mail as network applications in the World Wide Web, it is to become the primary way for internet user to get information channels。 At home and abroad, the well-known search company including: Google, Baidu, Yahoo, MSN, InfoSpace and so on。 Which, like Google, Baidu, full-text search engine is a complete sense of the search engine; Yahoo, MSN is a directory-style search engine; InfoSpace is a meta search engine。 This caused a brief history of search, classification, world-renowned search engine and full-text search engine processes, principles, and each part (search engine, parser, indexer, crawler) work。 Search engine optimization is the rise in 2004 after a new technology, the main purpose is to increase the exposure of a specific keyword to increase the visibility of the site to improve its ranking in search engines, improve site traffic, reach advertising or marketing purposes。 There have been many companies are involvedin the work of searing。Keyword: search engine category, full-text search engine, search engine optimization目 录第1章 前言1第2章 概述22.1发展历史22.2搜索引擎分类32.2.1全文搜索引擎(Full Text Search Engine)32.2.2目录式搜索引擎(Search Index)42.2.3元搜索引擎(Meta Search Engine)42.2.4垂直搜索引擎42.2.5其他非主流搜索引擎52.3著名搜索引擎简介52.3.1谷歌()52.3.2百度（）62.3.3雅虎（）72.4中文搜索引擎的趋势8第3章 全文搜索引擎93.1搜索引擎的体系结构93.2搜索引擎的工作流程103.3搜索器113.3.1搜索器流程123.3.2搜索器爬行策略133.3.3 Robots协议173.3.4常见搜索引擎爬虫183.4分析器193.4.1信息抽取193.4.2网页查重213.4.3中文分词223.4.4 PageRank233.5索引器233.5.1全文检索243.5.2文本信息索引技术243.5.3信息库253.6检索器263.6.1信息检索模型263.6.2搜索引擎采用的检索模型273.6.3多文档求交计算283。6。4检索结果排序283.6.5自动文本摘要293.6.6用户查询意图推测30第4章 搜索引擎优化314.1网站内容314.2关键字密度314.3内外部链接324.4竞价排名324.4.1竞价排名分类334.5编程语言与SEO334.5.1 JavaScript334.5.2 Flash334.5.3动态ASP334.5.4 PHP344.6常见的SEO作弊方法34致谢36参考文献37IV第1章 前言随着互联网的蓬勃发展,建立在互联网上的各种应用也层出不穷,其中最为成功的摸过于万维网(WWW)。万维网的发展也彻底改变了人们的思维、习惯与生活。一方面，它使网络用户更容易获取各种各样的信息，而另一方面，要想在数十亿网页的网络信息中精确地找到自己需要的信息简直就如“大海捞针”一般。在互联网彷徨无计之时,搜索引擎的出现就像是引领互联网走出迷雾的灯塔。网民不在需要记住复杂的网址和路径(URL)，只需要知道搜索引擎的入口，就可以畅游互联网的世界，从海量的互联网信息中找到和分享全人类的经验与智慧。WordNet中对搜索引擎的解释是一种用来在计算机网络特别是在万维网上检索各种文件的计算机程序。而在袁津生等所著的一书中,将搜索引擎定义为根据一定的策略、运用特定的计算机程序搜集互联网上的信息，在对信息进行组织和处理后，为用户提供检索服务的系统。可见搜索引擎在用户面前呈现的动态网页，是由用户定义的一个信息聚合系统。搜索引擎通过用户输入的查询关键词，推测用户的搜索意图，然后快速的返回相关的查询结果。随着搜索引擎技术和商业模式的成熟，更衍生出搜索引擎优化（SEO）的概念，它是近几年非常流行的一种网络营销方式。已有非常多的公司开始从事这方面的工作或者开展相关的业务。搜索引擎优化主要工作是通过了解各类搜索引擎如何抓取互联网页面、如何进行索引以及如何确定其对某一特定关键词的搜索结果排名等技术，来对网页进行相关的优化，使其提高搜索引擎排名，从而提高网站访问量，最终提升网站的销售能力或宣传能力。第2章 概述2.1发展历史现代意义上的搜索引擎的祖先，是1990年由蒙特利尔大学学生Alan Emtage发明的Archie。虽然当时World Wide Web还未出现，但网络中文件传输还是相当频繁的，而且由于大量的文件散布在各个分散的FTP主机中，查询起来非常不便，因此Alan Emtage想到了开发一个可以以文件名查找文件的系统，于是便有了Archie。Archie工作原理与现在的搜索引擎已经很接近，它依靠脚本程序自动搜索网上的文件，然后对有关信息进行索引，供使用者以一定的表达式查询。由于Archie深受用户欢迎，受其启发，美国内华达System Computing Services大学于1993年开发了另一个与之非常相似的搜索工具，不过此时的搜索工具除了索引文件外，已能检索网页。当时，“机器人”一词在编程者中十分流行。电脑“机器人”（Computer Robot）是指某个能以人类无法达到的速度不间断地执行某项任务的软件程序。由于专门用于检索信息的“机器人”程序像蜘蛛一样在网络间爬来爬去，因此，搜索引擎的“机器人”程序就被称为“蜘蛛”程序。世界上第一个用于监测互联网发展规模的“机器人”程序是Matthew Gray开发的World wide Web Wanderer。刚开始它只用来统计互联网上的服务器数量，后来则发展为能够检索网站域名。与Wanderer相对应，Martin Koster于1993年10月创建了ALIWEB，它是Archie的HTTP版本。ALIWEB不使用“机器人”程序，而是靠网站主动提交信息来建立自己的链接索引，类似于现在人们熟知的Yahoo。随着互联网的迅速发展，使得检索所有新出现的网页变得越来越困难，因此，在Matthew Gray的Wanderer基础上，一些编程者将传统的“蜘蛛”程序工作原理作了些改进。其设想是，既然所有网页都可能有连向其他网站的链接，那么从跟踪一个网站的链接开始，就有可能检索整个互联网。到1993年底，一些基于此原理的搜索引擎开始纷纷涌现，其中以JumpStation、The World Wide Web Worm（Goto的前身，也就是今天Overture），和Repository-Based Software Engineering (RBSE) spider最负盛名。然而JumpStation和WWW Worm只是以搜索工具在数据库中找到匹配信息的先后次序排列搜索结果，因此毫无信息关联度可言。而RBSE是第一个在搜索结果排列中引入关键字串匹配程度概念的引擎。最早现代意义上的搜索引擎出现于1994年7月。当时Michael Mauldin将John Leavitt的蜘蛛程序接入到其索引程序中，创建了大家现在熟知的Lycos。同年4月，斯坦福（Stanford）大学的两名博士生，David Filo和美籍华人杨致远（Gerry Yang）共同创办了超级目录索引Yahoo，并成功地使搜索引擎的概念深入人心。从此搜索引擎进入了高速发展时期。目前，互联网上有名有姓的搜索引擎已达数百家，其检索的信息量也与从前不可同日而语。比如最近风头正劲的Google，其数据库中存放的网页已达30亿之巨！随着互联网规模的急剧膨胀，一家搜索引擎光靠自己单打独斗已无法适应目前的市场状况，因此现在搜索引擎之间开始出现了分工协作，并有了专业的搜索引擎技术和搜索数据库服务提供商。像国外的Inktomi（已被Yahoo收购），它本身并不是直接面向用户的搜索引擎，但向包括Overture（原GoTo，已被Yahoo收购）、LookSmart、MSN、HotBot等在内的其他搜索引擎提供全文网页搜索服务。国内的百度也属于这一类，搜狐和新浪用的就是它的技术。因此从这个意义上说，它们是搜索引擎的搜索引擎。2.2搜索引擎分类人们对于搜索引擎的理解经历一个非常漫长的过程,从早前的目录式搜索,到现在的全文搜索,搜索引擎神秘的面纱逐步展现在人们面前。至今主流搜索引擎基本上有以下四种:2.2.1全文搜索引擎(Full Text Search Engine)全文搜索引擎是真正意义上的搜索引擎,它通过从互联网上提取的各个网站的信息而建立的数据库中,检索与用户查询条件匹配的相关记录,然后按一定的排列顺序将结果返回给用户。现在比较有名的搜索引擎包括:Google、AllTheWeb、AltaVista、WiseNut等,国内的有百度、中文搜索、北大天网等。全文搜索引擎具有全文搜索、检索功能强、更新及时,且无须人工干扰等优点,但是却由于提供过多的返回信息而降低了命中率,用户需要从中筛选获得自己想要的信息。2.2.2目录式搜索引擎(Search Index)目录式搜索引擎是最早出现的搜索引擎,它仅仅是按目录分类的的网站链接而已,用户无须进行关键词查询,仅靠分类列表就能找到需要的信息。这种搜索引擎最有名的是早期的雅虎,以及国内的搜狐。其他还包括Open Directory Project(DMOZ) 、LookSmart、新浪、网易等。目录式搜索引擎最大的特点是由人工建立,目标结果是网站,通过仍的方式将各个站点进行了分类,只记录一些摘要信息,及该网站的简要介绍。它的主要优点有:层次、结构清晰,易于查找,其缺点是搜索范围小,数据量有限,更新速度慢,维护成本较高。2.2.3元搜索引擎(Meta Search Engine)元搜索引擎并没有自己的数据,在接受用户查询请求时,同时在其他多个搜索引擎上进行搜索,然后将结果返回给用户。 著名的元搜索引擎有InfoSpace、Dogpile、Vivisimo等，中文元搜索引擎中具代表性的是北斗搜索。在搜索结果排列方面，有的直接按来源排列搜索结果，如Dogpile；有的则按自定的规则将结果重新排列组合，如Vivisimo。元搜索引擎的主要优点是返回结果的信息量大;缺点则是不能充分利用原搜索引擎的功能,用户需要做更多的筛选。2.2.4垂直搜索引擎垂直搜索引擎是针对某一个行业的专业搜索引擎，是搜索引擎的细分和延伸，是对网页库中的某类专门的信息进行一次整合，定向分字段抽取出需要的数据进行处理后再以某种形式返回给用户。垂直搜索是相对通用搜索引擎的信息量大、查询不准确、深度不够等提出来的新的搜索引擎服务模式，通过针对某一特定领域、某一特定人群或某一特定需求提供的有一定价值的信息和相关服务。其特点就是“专、精、深”，且具有行业色彩，相比较通用搜索引擎的海量信息无序化，垂直搜索引擎则显得更加专注、具体和深入。2.2.5其他非主流搜索引擎1集合式搜索引擎 该搜索引擎类似于远搜索引擎,但区别在与不是同时调用多个搜索引擎进行搜索,而是根据用户提供的4个搜索引擎之中选择。2门户搜索引擎 虽然提供搜索服务,但自身即没有分类目录也没有网页数据库,结果完全来自其他搜索引擎。3免费链接列表 这类网站一般只简单地滚动链接条目，少部分有简单的分类目录，不过规模要比Yahoo！等目录索引小很多。2.3著名搜索引擎简介2.3.1谷歌()Google是由单词googol变化而来,而googol表示的是1后带100个零的数字,Google用这个词代表公司向征服网上无穷无尽资料的雄心。 Google 创始人之一 Larry Page 指出：“完美的搜索引擎需要做到确解用户之意，切返用户之需”。 就搜索技术的现状而言，需要通过研究、开发和革新来实现长远的发展。Google 致力于成为这一技术领域的开拓者。目前Google已经成为全球最大的全文搜索引擎,并在2000年已经开始提供中文搜索服务。Google每天提供超过2亿次查询服务,搜索时间不到半秒,成为网上最快捷的信息查询方法。1.Google的特点资源丰富、内容广泛Google是全球最大的互联网文档收集者,在全球范围内已经收集了20多亿网页资料,7亿多新闻组的帖子和3亿多图片。还有网页快照服务,非常适合使用者众多的门户网站。相关性高Google可以根据网页间彼此的连接关系,把一篇网页被连接数目的多寡作为其相关性的一项指标。对于用户输入的关键词,Google最大限度的寻求语义上的匹配。技术先进、搜索结果精确、排序公正有别于其他搜索引擎，没有人能花钱买到Google的一个更高级别的PageRank，保证了排名的工作性，也正是以这样诚信的服务，Google让用户非常容易的找到高质量的网站。搜索快速搜索速度是Google的另一大优势,用户输入的任何关键字或信息,都能得到快速的响应,且其超链分析的算法还会将搜索结果排列出优先序列,节省了互用的查询时间。Google在全世界拥有超过10000台Linux服务器,200多条T3宽带,在超过20亿的网页中搜索问题并回复的时间不到1.5s。 2.Google的检索方式简单查询普通上网用户使用最多的查询方式。Google有自己的语法,它不支持“AND”、“OR”和“”等符号的使用，只要用户输入的关键词完整，准确，都可以获得用户想要的信息。高级查询Google的高级查询可以提供非常专业的关键词查询,可以选择想要查询的地区、语言、时间甚至是网站。3.Google的不足(1)数据搜索速度无法进一步提升。由于数据量的庞大,使Google搜索引擎的数据更新无法超过30天,在一定程度上影响了用户对信息的实效需求,而Google目前还无法突破这一瓶颈。(2)无法搜索动态生成的网页。大多数负责网页抓取的蜘蛛程序都不敢去查找动态网页,怕被变化无穷的动态系统“黑洞”吸进去，但Google似乎已经取得了一些突破。(3)不支持“OR”和“”等符号的使用2.3.2百度（）百度是世界上最大规模的中文搜索引擎,致力于向人们提供最便捷的信息获取方式。百度拥有全球最大的中文网页库,每天向全球100多个国家的网络用户提供超过1亿次以上的搜索服务。由于百度在技术上的领先,奠定了其在中国互联网高科技公司的优势地位,成为中国互联网信息服务的旗帜之一。技术核心:超链分析超链分析技术,是新一代搜索引擎的关键技术,已为世界各大搜索引擎普遍采用,百度总裁李彦宏就是超链分析专利的唯一持有人。超链分析是通过分析连接网站的多少来评价被连接的网站质量,这保证了用户在百度搜索时,越受用户欢迎的内容排名越靠前。搜索资源更大、更新更快百度在中文互联网中，支持搜索8亿个中文网页，是世界上最大的中文搜索引擎，其在中国各地分布的服务器，能直接从最近的服务器上把所搜索信息返回给当地用户，使用户享受极快的搜索传输速度。为中文用户量身定做百度作为中国本地的搜索引擎，深刻理解中文用户的搜索习惯，开发出关键词自动提示、自动纠错等功能百度特色：百度快照百度快照解决了用户上网访问经常遇到的死链接的问题：百度搜索已先预览各网站，拍下网页的快照，为用户存储大量应急网页。2.3.3雅虎（）Yahoo！在全球共有24个网站，12中语言版本，其过人之处，在于其分类目录查询做的相当出色，无论从网站的数量还是分类的合理性方面都是可圈可点。站点目录分为14个大类，每个大类下面分为若干个小类，搜索十分方便。雅虎的特点1.界面简洁。 Yahoo！的网站简介相当简练、严格，一般用很少的文字做客观描述，没有主管评论和类似于广告的夸张语言。2.分类目录准确、合理。 Yahoo！提供了一份规范、科学、层次丰富的网站分类目录，丙炔是通过一大片工程师手工编制的。3.数据量大，内容丰富。 Yahoo！通过14个一级类目将关于政治、经济、文化、房产、科技、教育、娱乐、体育等各方面的信息收集到数据库当中，有资料称，Yahoo！已经收集了超过20亿个中文网页4.速度快、准确率高Yahoo！的分类是由专业计算机人士手工完成的，因此收录的网页经过筛选和系统组织，质量较高，条理性较强，也更接近用户的信息需求雅虎的不足1由于数据量大,许多网站并没有简介,也没有注册信息2人为分类,难免某些网站分类有误3检索结果多有重复,且复杂条件查询较弱4中文版本功能和服务比英文版少许多2.4中文搜索引擎的趋势中文搜索引擎的发展时间并不长,但是发展迅速,技术也日趋成熟,提供的服务业越来越全面。互联网所示引擎将会向着智能化、个性化、精确化、专业化等方向发展。中文搜索引擎的发展趋势应为如下几个方面：1智能化搜索引擎2提高查询结果的精确性、检索的有效性3实现交叉语言检索和自然语言检索4研究汉字内码转换技术，实现汉字各内码之间的无缝切换5桌面型搜索引擎第3章 全文搜索引擎搜索引擎是一种依靠技术取胜的产品，搜索引擎的各个组成部分，包括页面搜集器、索引器、检索器等，都是搜索引擎产品提供商进行比拼的着力点。大型互联网搜索引擎的数据中心一般运行数千台甚至数十万台计算机，而且每天向计算机集群里添加数十台机器，以保持与网络发展的同步。搜集机器自动搜集网页信息，平均速度每秒数十个网页，检索机器则提供容错的可缩放的体系架构以应对每天数千万甚至数亿的用户查询请求。3.1搜索引擎的体系结构搜索引擎是一种依靠技术取胜的产品，搜索引擎的各个组成部分，包括页面搜集器、分析器、索引器、检索器等，都是搜索引擎产品提供商进行比拼的着力点。1搜索器搜索器负责从互联网上下载各种类型的网页,并保持对互联网的同步。2分析器分析器负责网页的初步处理,相对于英文搜索引擎每个字中间有空格隔开，中文搜索引擎则更需要分词技术的支持才能提供更好的服务。3索引器索引器负责理解搜索器搜索的信息,对搜索到的信息进行索引排序，形成完整的数据库文件。在搜索引擎发展的初期，能索引多少数据是行业发展的标志。4检索器检索器的功能是根据用户的查询在索引库中快速检出文档,进行文档与查询的相关度计算,将要输出的结果进行排序,并实现某种用户相关性反馈机制。5用户接口用户接口负责输入用户查询,并显示查询结果。一般搜索引擎的结构如图2-1：万维网控制器搜索器原始数据库索引器日志分析器索引数据库用户行为日志数据库检索器用户用户接口图2-1搜索引擎结构图3.2搜索引擎的工作流程搜索引擎一般的工作过程是: 首先对互联网上的网页进行搜集，然后对搜集来的网页进行预处理，建立网页索引库，实时响应用户的查询请求，并对查找到的结果按某种规则进行排序后返回给用户。大型互联网搜索引擎的数据中心一般运行数千台甚至数十万台计算机，而且每天向计算机集群里添加数十台机器，以保持与网络发展的同步。企业搜索引擎可根据不同的应用规模，从单台计算机到计算机集群都可以进行部署。开始N用户输入关键词关键词分析关键词wordID查找索引库得到wordID列表遍历文档列表docIDN未找到相关网页找到一篇?Y返回给用户结果按相关度排序文档处于列表末尾?N计算文档等级Y 图2-2搜索引擎工作流程3.3搜索器搜索器即是网络爬虫,也被称为漫步者“Wanderers”或者机器人“Robots”，它首先是一组运行在计算机中的程序，在搜索引擎系统中负责抓取时刻更新且公共可访问的Web的网页、图片和文档等资源。这种抓取的过程为通过下载一个网页、分析其中的链接。继而漫游到其他链接指向的网页，循环往复。爬虫的作用是搜索引擎抓取大量的数据,抓取的对象是整个互联网上的网页。爬虫程序不可能抓取到所有的网页,因为在爬虫抓取的同时,Web的规模也在增大,所以一个好的爬虫程序一般能够在短时间内抓取更多的网页。一般爬虫程序的起始点都选择在一个大型综合性的网站,这样的网站已经涵盖了大部分高质量的站点,爬虫程序就沿着这些链接爬行。3.3.1搜索器流程在爬虫开始的时候,需要给爬虫输送一个URL列表，整个列表中的URL地址便是爬虫的起始地址，爬虫从这些URL出发，开始了爬行，一直不断的发现新的URL，然后再根据策略爬行这些新的URL，如此永远反复下去。一般的爬虫都自己建立DNS缓冲，其目的是加快URL解析成IP地址的速度。新URL列表已抓取的网页抓取DNS服务器IP地址缓存URL解析URL列表开始爬虫运行流程如图2-3:图2-3爬虫运行流程 3.3.2搜索器爬行策略1深度优先策略 深度优先的遍历策略类似于中华民族家族继承的策略，典型的如封建帝王的继承。通常为长子继承，如果长子过世，长孙的优先继承，如果长孙过世切长孙无子，那么次子继承，这种继承上的优先关系被称为深度优先。图2-4所示为一个无互相指向对方的网页连接模型： ADBCEGFIH 图2-4简易网页链接模型假设搜索引擎爬虫从A出发,根据深度优先策略,所走的路径为:ABEH:ABEI:AC:ADF:ADG深度优先策略是尽量往最远的地方走,直到不能走为止。此算法的缺点在于,爬虫爬行了许多重复的节点,因此在实际过程中,爬虫需要判断“是否要继续向深层爬行”，抓取数据前需要询问总链接库，询问“这个链接是否已经爬行过了？”然后记录爬行的分支节点。2广度优先策略广度优先搜索策略是指在抓取过程中，在完成当前层次的搜索后，才进行下一层次的搜索。该算法的设计和实现相对简单。在目前为覆盖尽可能多的网页，一般使用广度优先搜索方法。假设图2-4是广度优先策略，则所走路径为：:A:BCD:EFG:HI广度优先策略也称为“层次优先”，第一次层的优先级最高，以此类推，每一层中，内部优先级从左到右排列。采用广度优先的好处有三点：首先由于广度优先的算法相对简单，且距离种子站点越近的网页应该也越重要；其次互联网的深度也没有人们想象的那么深，许多站点有很多通道可以到达；再次广度优先的策略非常适合多个爬虫合作抓取。但是广度优先的策略可能遇到死链，会导致爬虫重复抓取网页，浪费资源。3不重复抓取策略不重复抓取的关键在于记住历史，爬虫记录历史的方式是哈希表，每一条记录是否被抓取的信息存放在哈希表的某一个槽位上。若某网页在过去的某个时刻已经被抓取，则将其对应的槽位的值置1；反之置0。有调查显示，中文万维网的数量超过100亿，若将数量如此庞大的信息存入哈希表中，是非常庞大的。如果哈希表每一个单元为一个字节（8位），则至少需要10GB的容量，然而32位的操作系统的最大寻址空间为4GB（包括Linux系统内核占用的1GB空间），因此内存无法分配如此巨大的一个哈希表。则需借助MD5签名函数。为了将整个哈希表装入内存，通常采用Bitmap的数据结构压缩内存用量，Bitmap需要接触按位于（&）和按位或（|）以及左移（）这4种基本运算。如图2-5:040000000000010034(34/32)%8=134%32=2MD5签名函数URLInt Hash8Hash1图2-5 Bitmap结构的哈希表定义一个哈希表，即Int Hash8。对URL执行MD5签名，假定得到的值为34。用34除32，得到商1，用其对8取模得到1，表示槽位在Hash1中。用34除32得到余数为2，表示34映射到Hash1整个32位整数的第3个比特位上，将这个比特位置1，则Hash1为4。图2-6为34按比特位展开：前3位决定哈希数组下标后5为决定整型的哪一位00100010图2-6 34位比特位展开前面计算的C代码如下：（1）：int MD5 = 34;（2）：int index_int = MD5&31;/相当于34%32（3）：int index_Hash = (MD55)&7; /相当于（34/32）%8,32是2的5次幂（4）：if ( Hash index_Hash & (1 index_int ); /表示探测该槽位是否已经被置位（5）：else Hash index_Hash = Hash index_Hash | (1 index_int );/表示该槽位没有被置位，用或运算置位。不重复抓取的好处在于基本处理了死循环的问题，即抓取过的不会再继续抓取。然而实际操作中有这样一个问题，如果任意2个网页存在链接，则它们的最短路径为万维网直径长度17。这样就不能保证爬虫一定会按照最佳路径抓取每一个网页，因为任何一个网页都可能从多个种子站点开始广度优先被遍历到。所以应在深度为17的时候停止抓取，对于那些未抓到的网页，期待从其他种子站点更加经济的达到。不重复抓取非常合适多个爬虫合作抓取，可以进一步降低记录历史抓取情况的散列表的大小。若有N个爬虫。则散列表的大小可以被压缩到1/N。4网页抓取优先策略网页抓取优先策略也称为“页面选择问题”（Page Selection），通常是尽可能的首先抓取重要性高的网页，这样可以保证在有限的资源内尽可能的照顾某些网页。重要性度由链接受欢迎度、链接重要度和平均链接深度这3个方面决定。链接受欢迎度链接受欢迎度IB(P)主要由反向链接的数目和质量决定。一个网页有越多的链接指向它，那么表示其他网页对于它的认可度就越高，这个网页被访问的概率就越高。一个网页被多个重要性高的网页所指向，那么其重要性也就越高。链接重要度链接重要度IL(P) 是一个关于URL字符串的函数，考察的是字符串本身。如认为包含“。com”或者“。cn”的URL重要度高。平均链接深度平均链接深度ID(P)表示在一个种子站点集合中，每个种子站点都存在一条链路到达某一个网页，这个数值就是平均链接深度。网页重要性的度量为I（P），它由以上两个量化值线性决定，即： I(P)=*IB(P)+*IL(P)平均链接深度由广度优先的遍历规则保证，因此不作为重要性评价的指标。5网页重访策略互联网不仅仅非常庞大，更处于不断的变化中。因此，网络爬虫不得不周期性的重新访问那些已经被抓去过的网页，来保持与互联网的变化一致。网页重访基本分为以下2类：统一的重访策略:爬虫以相同的频率重访那些已经抓去过的全部网页个体的重访策略:爬虫根据其更新频率来决定重访该个体网页的频率。研究表明，网页的更新过程符合泊松过程、网页更新时间间隔符合指数分布，因此可以对不同类型的网页采取不同的更新策略。泊松分布： PX=k=exkk! k=0,1,2,。3.3.3 Robots协议Robots协议是Web站点和搜索引擎爬虫交互的一种方式，robots。txt是存放在站点根目录下的一个纯文本文件，该文件可以指定搜索引擎爬虫只抓去指定的内容，或者是禁止搜索引擎爬虫抓取网站的部分或全部内容。爬虫访问某个站点时，会先查询有没有此文件。若有则按照这个文件访问，若没有则搜索引擎就沿着链接抓取。Robots。txt必须放置在站点的根目录下，并且文件名必须全部为小写。robots。txt文件包含一条或更多的记录，这些记录通过空行分开（以CR,CR/NL, or NL作为结束符），每一条记录的格式如下所示：:。该文件中的记录通常以一行或多行User-agent开始，后面加上若干Disallow行,详细情况如下：User-agent:该项的值用于描述搜索引擎robot的名字，在robots。txt文件中，如果有多条User-agent记录说明有多个robot会受到该协议的限制。Disallow:该项的值用于描述不希望被访问到的一个URL，这个URL可以是一条完整的路径，也可以是部分的，任何以Disallow开头的URL均不会被robot访问到。语法实例：1.允许所有SE收录本站：robots。txt为空就可以，什么都不要写。2.禁止所有SE收录网站的某些目录：User-agent: *Disallow: /目录名1/Disallow: /目录名2/Disallow: /目录名3/3.禁止某个SE收录本站，例如禁止谷歌：User-agent: googlebotDisallow: /4.禁止所有SE收录本站：User-agent: *Disallow: /3.3.4常见搜索引擎爬虫google蜘蛛： googlebot百度蜘蛛：baiduspideryahoo蜘蛛：slurpalexa 蜘蛛：ia_archivermsn 蜘蛛：msnbotaltavista 蜘蛛：scooterlycos蜘蛛：lycos_spideralltheweb蜘蛛：fast-webcrawler/nktomi蜘蛛:slurp3.4分析器分析器的功能就是对搜集器搜集来的网页信息或者下载的文档进行分析，提取相关的网页信息，根据一定的相关度计算，得到每一个网页针对页面内容中级超链接中每一个关键词的相关度。其完成的工作主要包括信息抽取、网页消重、中文分词和PageRank计算等。3.4.1信息抽取 信息抽取的目的，是从半结构化网页中抽取出有价值的能够代表网页的属性，例如锚文本、标题和正文等。把这些属性结合起来组成一个网页对象，这种处理亦叫做“网页结构化”网页结构化的目标:网页结构化的目标是抽取网页的基本属性，其能够描述这个网页，并打包成为一个网页对象:锚文本：就是链接文本，一般来说，页面添加的链接一般来说都应该跟页面有直接相关的联系，搜索引擎可以根据指向某一个网页的链接的锚文本描述来判断该网页的内容属性。标题：特指HTML标识语言中中间的文字部分，这些文字由网页制作者本人编写，表达了网页的基本含义。正文标题：抽取正文中适当的文字作为正文标题。正文：网页的主题内容，它完整的表达了网页的基本信息，一般出现在、等HTML标签中。正向链接：正向链接是网页编写者编写的引导用户继续在网上浏览的链接，也是其他网页的锚文本。图2-7为一个网页一般包含的5个属性：属 性含 义title页面标题content title正文标题concent正文link正向链接集合anchor指向自身的锚文本图2-7网页对象的5个属性及含义HTML标签树、由于互联网上大多数静态网页都是以HTML网页形式存在，它把其描述的全部内容都按照HTML语法存放标签中，为了更清楚地描述网页的组织结构，将网页中的标签按照出现顺序依次整理出来并用适当的结构记录。由于标签的嵌套关系，因此整理结果会成为一个树形结构。HTML HEADBODYTITLETABLETRTRTR TDTDTD 图2-8 HTML标签树通过投票得到正文在HTML语言编写的网页中，由于没有标注出正文，且正文可能分布在多个HTML标签中，因此判定一个完整的正文是一个难点。为此引入文本块的概念，对那些如标签标签间的文字认为是一个文本块。定义一组规则，使他们对文本块进行打分。得分越高的文本块往往重要度也就越高。规则可以诸如：文本长度，位置，反向链接位置等。图2-9为简单投票算法的一般模型：文本块2得分文本块1得分.规则n规则1文本块2文本块1 图2-9简单投票算法3.4.2网页查重重复或者的网页会对搜索引擎产生非常大负载，导致搜索引擎的效率下降，网页查重的第一步就是判断那些网页是重复或者相似的。网页相似有4中类型：（1）内容和格式完全相同（2）内容相同，格式不同（3）部分重要的内容相同，格式相同（4）部分重要的内容相同，格式不同要实现网页查重一般需要3步：1.特征抽取特征抽取有两种算法一种是“I-Match”算法，尽可能只抽取一个特征，这样只要比较一次即可；另一个算法是“Shingle”，抽取多个特征词汇，通过比较亮哥特征集合的相似度实现文档重查。2.相似度计算“I-Match”算法抽取的特征只有一个，因此只需要为文档计算一个签名值，如果2个文档的签名值完全相同，则文档相似。 Shingle”算法的特征有多个，其计算方法为记录完全一致的Shingle个数，然后除以两个文档的Shingle总数个数减去一致的Shingle个数，数学表示为：J=ABAB ,这个数值称为“Jacccard系数”3.消重消重主要考虑得问题是留下哪个网页，现在搜索引擎主要采用的方法是保留爬虫首先抓取的网页，丢弃其他相同的，这种方法实现简单，且很大程度上保证了优先保留原创的原则。3.4.3中文分词在网页分析的过程中，中文与英文的处理方式是不同的，这是因为中文信息与英文信息有一个明显的差别: 英文单词之间有空格，而中文文本中词与词之间没有分割符。这就要求在对中文网页进行分析之前，先要将网页中的句子切割成一个个的词的序列，这就是中文分词。目前，中文自动分词比较成熟的技术是基于分词词典的机械分词方法。这种方法是按照一定的策略将要分析的汉字串与词典中的词条进行匹配。根据匹配策略的不同，机械分词方法又有如下几种算法: 正向最大匹配算法、逆向最大匹配算法、最少分词算法等。这种方法的优点是分词的速度快，准确度有一定的保证，但对未登录词的处理效果较差。中文自动分词的难点在于分词歧义的处理和未登录词的识别，如何处理这两个问题一直是该领域研究的热点。1.歧义处理歧义主要包括交叉歧义（如化妆和服装，可分解为“化妆+和+服装”或者“化妆+和服+装”）、组合歧义（在句子“将军任命了一名中将”中，“中将”是个词，但在句子“产量三年中将增长两倍”中，“中将”就不再是词。）和真歧义（例如: “乒乓球拍卖完了”，可以切分成“乒乓+球拍+卖+完+了”、也可切分成“乒乓球+拍卖+完+了”）。这些交与计算机识别都是有难度的，现在对歧义现象的处理方法一般采用类似于动态规划的算法将歧义问题的求解转化为一个优化问题的求解。在求解过程中，一般使用词频或概率等辅助信息求得一个最大可能的分词结果，这个结果在某种意义下是最佳的。2.未登录词处理未登录词就是分词词典中没有的词，也称为新词。最典型的是人名、地名、专业术语等。未登录词中除了人名以外，还有机构名、地名、产品名、商标名、简称、省略语等都是很难处理的问题，而且这些又正好是人们经常使用的词，因此对于搜索引擎来说，分词系统中的新词识别十分重要。目前，对未登录词的处理一般采用统计的方法，首先从语料中统计出出现频率较高的字组，然后按照某种规则把它们作为新词添加到辅助词典中。目前，中文自动分词技术在搜索引擎中已经得到广泛应用，分词准确度已经达到96%以上，网络上的中文信息越来越多，对网络上的中文信息的处理必将成为一个巨大的产业和广阔的市场，存在无限的商机。但是，中文自动分词技术要想更好地服务于网络中文信息的处理并形成产品，还要在基础研究方面和系统的集成方面做许多工作。3.4.4 PageRankPageRank(网页级别)，是Google用于用来标识网页的等级/重要性的一种方法，是Google用来衡量一个网站的好坏的唯一标准。PageRank模型的分析过程也被称为链接分析（link analyze）, PageRank的排名就是对网页重要性的排名。简单的理解PageRank基本想法是：网页A链接到网页B，则表示网页A的编写者对网页B的认可，且网页A越重要，网页B往往也越重要。影响PageRank值的3个方面：反向链接的数目与质量Google爬虫在你网页抓取的页面数网站被世界3大知名站点DMOZ、Yahoo和Looksmart收录3.5索引器索引器的功能是对搜索器所搜索的信息进行分析处理，从中抽取出索引项，用于表示文档以及生成文档库的索引表。索引项有元数据索引项和内容索引项两种: 元数据索引项与文档的语意内容无关，如作者名、URL、更新时间、编码、长度、链接流行度等等; 内容索引项是用来反映文档内容的，如关键词及其权重、短语、单字等等。在搜索引擎发展得初期，能够索引的网页数量，代表了整个行业的技术发展水平。索引器的输出是索引表，它一般使用倒排形式，即由索引项查找相应的文档。索引表也可能记录索引项在文档中出现的位置，以便检索器计算索引项之间的相邻或接近关系。索引器可以使用集中式索引算法或分布式索引算法。当数据量很大时，必须实现实时索引，否则就无法跟上信息量急剧增加的速度。索引算法对索引器的性能（如大规模峰值查询时的响应速度）有很大的影响。一个搜索引擎的有效性在很大程度上取决于索引的质量。3.5.1全文检索全文检索是计算机程序通过扫描文章中的每一个词，对每一个词建立一个索引，指明该词在文章中出现的次数和位置。当用户查询时根据建立的索引查找，类似于通过字典的检索字表查字的过程。全文检索系统是按照全文检索理论建立起来的用于提供全文检索服务的软件系统。全文检索技术的出现是信息检索领域的一场革命，它细化了信息检索的粒度，提供了时间多角度，多侧面且全新的信息检索体验，因此全文检索已经成为现代搜索引擎的主流检索方法。3.5.2文本信息索引技术1.顺排文档检索顺序文档检索是有日本人菊池敏典提出的，其主要思想是将文档中的每一条记录依次去匹配用户的检索提问集合，文档处理完毕后，将各提问的命中结果归并分发给有关用户。顺序文档检索的关键技术是采用列表处理方法将提问逻辑式变换成等价的提问展开式，按提问展开表的内容对顺排文档的每篇文献进行检索，其优点是能够缩短每个提问式的查找时