毕业设计（论文）面向丝绸领域的垂直搜索引擎关键算法研究.doc

摘要垂直搜索引擎是搜索引擎的细分和延伸，是对网页库中的某类专门的信息进行一次整合，定向分字段抽取出需要的数据进行处理后以某种形式返回给用户。垂直搜索引擎与传统的网页搜索引擎最大的区别就是将网页中的信息进行结构化的抽取。使得信息在抽取的时候就建立了分类，更好的适应查询需求。近几年来，垂直搜索引擎已经被应用到某些专业的领域(如化学、科技文献)。本文从研究和设计的角度对垂直搜索引擎的相关技术作了详细的分析和讨论，论述了目前搜索引擎的国内外发展现状和趋势。分析了搜索引擎的工作原理及其各部分主要功能，抓住如何评价页面的主题相关性和设计高效的爬行策略这两个关键问题，提出一个基于丝绸信息的定题搜索器，它是垂直搜索引擎的核心。在文章的主体部分，以搜索引擎的设计流程为主线，重点论述垂直搜索引擎设计与实现时一些独特的信息识别方法，包括pagerank和HITS算法。从HTML页面解析的一般概念入手，结合网页之间的超链接分析，按照搜索引擎系统的要求，采用深度优先的搜索策略设计具有垂直搜索引擎功能的丝绸信息网站。并按照软件工程的方法，研究了丝绸信息搜索引擎的总体设计过程和实现过程，设计过程重点论述了需求分析、网站的功能规划和总体结构、数据库设计等内容，并通过编码实现设计阶段的各种算法和具体功能。最后的软件功能测试表明，此搜索引擎算法准确、确定、不会引起本地资源耗尽；它支持按指定站点搜索，按给定URL范围进行搜索的搜索策略。可以完成指定信息的自动搜索和下载。关键词： 垂直搜索引擎 网页信息抽取 抽取规则 索引库作 者：张小莉指导老师：姚建民AbstractThe Vertical Searching Engine is a typical type of searching engine, which can classify information in certain field from those websites, Directional mark of syllable takes out the data needing carrying out treatment and analyze those data, then return them to users. The major difference between Vertical Searching Engine and traditional searching engine is thtat the vertical one select information from website in a structural way classify the information while selecting it to be better satisfy the searching requirements. In this paper it does detailedly some analying and discussing the technology of the Vertical Searching Engine from the studying and designing angle, has discussed home and abroad present situation and trend searching for an engine at present. The operating principle having analysed searching engine and their every main part function, grasp the two key problems about how to appraising pages subject correlativity and designing the high-effect crawlling tactics, Suggest a directional question Searching machine based on Silk Information,it is the core of a Vertical Searching Engine. In the article main body part, we regarded the Serching Engines designing flow as the main clue, and focused on discussing the designing and carrying out some typical informations identification method about Vertical Seraching Engine, Including PageRanks and HITS s algorithm.Starting with the HTML page analysis s average concept,combine the Hypertext analysis among the Webs,According Searching Engine System requirements ,adopt the depth-first searching tactics to design a silk information website which has Vertical Searching Engine function. And according to the software engineering method, we have studied the silk information Searching Engines overall designing and realizing process, during this process we discussed with an emphasis on requirement analys 、web functions design and total structure 、database design etc. and realized designing stages all kinds of algorithms and specific function by code.The results of software function test show that the algorithm of Vertical Searching Engine is accurate and steady without the risk of local information resource exhaustion. It supports the searching strategy of searching on fixed site or in a given URL circle.It can also do automatic searching and downloading according to the given information.Keywords：Vertical Searching Engine; Web Information Extraction;Extraction rules; Index DatabaseWritten by Shally ZhangSupervised by James Yao目录摘要IAbstractII第1章绪论11.1课题的背景及意义11.2垂直搜索引擎现存的问题11.2.1垂直搜索引擎的产生11.2.2存在的问题21.3国内外垂直搜索引擎的发展31.4垂直搜索引擎的发展前景41.5课题的主要研究内容6第2章搜索引擎实现原理72.1通用搜索引擎的工作流程72.2网页信息采集技术和软件82.2.1网页信息采集软件的工作方式92.2.2网页采集软件的组成模块102.3索引器122.3.1实现原理122.3.2索引数据组织132.3.3索引文件导出过程142.4网页存储器与分析索引器142.5查询器和用户接口的设计152.5.1查询器152.5.2用户接口162.6搜索引擎的性能评价指标162.7小结18第3章垂直搜索引擎的关键技术193.1页面分析技术193.2超链接分析算法203.2.1PageRank算法203.2.2HITS算法223.3网页信息的结构化抽取233.3.1网页信息的结构化抽取方式243.3.2结构化信息抽取系统的结构243.3.3中文网页结构化信息抽取的难点253.4暗藏网页的信息抽取263.5小结27第4章面向丝绸领域垂直搜索引擎的总体设计284.1基本功能需求284.2丝绸产品信息搜索引擎系统的体系结构294.3系统开发环境304.4垂直搜索引擎的主要数据库设计304.5 系统功能特点31第5章面向丝绸领域的垂直搜索引擎的具体实现335.1 丝绸信息网页自动搜索算法的具体实现335.1.1元搜索算法335.1.2自动搜索过程的实现355.1.3 网页爬行的控制模块实现375.1.4 HTML标准化与页面解析385.1.5网页爬行的控制模块的性能测试395.2 页面分析与丝绸产品信息的自动抽取415.3 Lucene倒排文件索引结构445.4 用户查询功能的实现455.4.1网页形式的丝绸产品信息查询与返回465.4.2站内数据库中的丝绸产品信息查询与返回485.5 小结49结论50致谢52参考文献53攻读学位期间公开发表的论文55第1章绪论1.1课题的背景及意义随着网络与通信技术的迅速发展，Web信息爆炸性的增长，互联网已经成为一个巨大的海量信息空间。如何迅速、准确、方便的从如此庞大的信息库获取自己需要的信息，是互联网用户面临的一个重要问题。搜索引擎的出现，整合了众多网站信息，极快的查询起到了信息导航的作用，信息的价值得到众多商家的普遍认可，成为互联网中最有价值的领域。大家熟知的搜索引擎Google、百度、雅虎等都是搜索引擎的杰出代表，为互联网的发展做出了重要的贡献。CNNIC第十四次互联网调查表示，搜索以71.9%的绝对优势成为用户从互联网上获取信息的主要方式1，是互联网上使用程序仅次于电子邮箱的服务。互联网的信息量呈爆炸趋势增长，几年前全球式搜索引擎收录的网页量只有几千万页，而现在已经达到几十亿页，数量增加带来的是搜索服务的品质下降，查询的结果集就是海量的，经常是几十万笔的资料，结果里存在大量的重复信息和垃圾信息，用户越来越难迅速找到符合的信息，现在经常使用搜索引擎可以感觉到很难在短时间内准确的筛选出需要的内容。因此，如何对通用搜索引擎技术进行改进，使查询的结果更加贴近用户的要求，成为搜索引擎行业近期的研究热点。1.2垂直搜索引擎现存的问题1.2.1垂直搜索引擎的产生所谓通用搜索引擎，并不能够囊括所有的网页，据google的人说，也就猜测覆盖了40%不到的网页，也就是说，更多的网页是没有被通用搜索引擎收录的，也就谈不上被搜到了。那些没有机会收录的网页，有些是需要身份验证等之后才可以看到，有些是根本未被通用搜索引擎的蜘蛛爬到。这些信息却往往是宝贵的，更有价值的。 每一个行业都是复杂的，从目前计算机技术来讲，还是遵循冯.诺依曼的体系，也即是说还是依靠图灵未实现的人工智能之下的计算机逻辑来处理信息，在搜索收录的分析过程中，如果不加上行业特点和特性 进行分析，很难说会更准确分析到网页的重要性和分析的准确。这个也是垂直的意义所在2。当然，这里面也需要注意到，并非你垂直了，你的搜索收录和搜索结果就一定比通用搜索更准确3。 垂直搜索引擎和普通的网页搜索引擎的最大区别是对网页信息进行了结构化信息抽取，也就是将网页的非结构化数据抽取成特定的结构化信息数据，好比网页搜索是以网页为最小单位，基于视觉的网页块分析是以网页块为最小单位，而垂直搜索是以结构化数据为最小单位。然后将这些数据存储到数据库，进行进一步的加工处理，如：去重、分类等，最后分词、索引再以搜索的方式满足用户的需求。整个过程中，数据由非结构化数据抽取成结构化数据，经过深度加工处理后以非结构化的方式和结构化的方式返回给用户。垂直搜索引擎的应用方向很多，比如企业库搜索、供求信息搜索引擎、购物搜索、房产搜索、人才搜索、地图搜索、mp3搜索、图片搜索几乎各行各业各类信息都可以进一步细化成各类的垂直搜索引擎。搜索由通用到专业目前来看是一趋势，都分了什么图片搜索、mp3搜索之类，这也好理解，用户输入关键字的时候，可能并不需要其他行业的内容，仅仅一个关键字不结合其他补充信息，是无法准确分析用户的搜索要求的，但是通用搜索引擎只能够一股脑给你信息。从这个角度讲，信息多了会造成一部分搜索结果是垃圾，而这垃圾会影响用户的感受，以及继续试用搜索的兴趣。而垂直搜索引擎应该可以更好的做到理解垂直用户的需求，从而给出更好的结果。举个例子来说明会更容易理解，比如购物搜索引擎，整体流程大致如下：抓取网页后，对网页商品信息进行抽取，抽取出商品名称、价格、简介甚至可以进一步将笔记本简介细分成“品牌、型号、CPU、内存、硬盘、显示屏、”然后对信息进行清洗、去重、分类、分析比较、数据挖掘，最后通过分词索引提供用户搜索、通过分析挖掘提供市场行情报告。 从搜索信息的结果来看，除了上面的垃圾会过多外，还会存在信息不符合要求的情况，有时候用户搜索某类事物，并以此作为关键字，他需要的是关于这个事物的数量、价格等 甚至相关比较信息，而通用搜索引擎只能给你线索，给你网页。通用搜索引擎由于自身巨大，他做不到更深入分析后给出更符合行业、用户需求的结果。一个内容提供商所能担当的，应该是知识导航和知识集成的角色。它所提供的内容，说到底是深加工后的而不是粗放的信息。4-6由此我们可能得出垂直搜索引擎的定义：能够满足某一特定领域，某一特定人群或者说是某一特定需求，提供内容集中而深入的信息与服务的网站。1.2.2存在的问题垂直搜索引擎作为提供专业、集中的内容服务网站，必须首先考虑到为用户提供专业的信息及围绕专业展开的服务。由此看来，要保证一个垂直搜索引擎的生命力，还应为信息工作人员考虑如何确保在尽可能短的时间内的找到最需要的信息内容，进行专业处理、深度加工，及时更新内容。然而经过我们的细致研究，发现现有的多数垂直搜索引擎尚不能达到上述的要求。主要存在以下四个问题：（1）没有为用户和信息人员提供一个合适的专业检索服务、专业搜索引擎，查找所需的信息并不方便。常常是用户找了几千甚至上万条记录出来，根本无法从中再细找。或者找到的内容和要找的内容不是一个专业领域内的，信息无效；（2）信息工作不得不花费大量时间在收集、编辑和发布信息上，工作枯燥且大都属于重复性劳动，还有较高的技术要求，而对信息内容的关注反而少了；（3）信息更新不够及时，或者提供一些过时、不适当的信息；（4）虽然已有足够大的信息量，但由于存储或者管理不适当，难以去检索所需信息，更加无法分析、挖掘数据，从中提炼规则或做判断、预测。这些问题的存在有其技术背景和人为因素的。过去比较落后的技术不能跟上用户的要求，对信息管理人员的要求较高。但随着技术的发展和日益成熟，垂直搜索引擎现存的问题也将得以解决与改善。（1）提供合适的专业搜索引擎，查找专业的信息内容。（2）为信息工作人员提供界面友好、适用的信息管理系统。（3）为信息建立关系型数据库，为今后的进一步发展提供基础。1.3国内外垂直搜索引擎的发展 与以前的通用搜索引擎不同，垂直搜索引擎并不求大求全，而是力求做到一个特定领域内容的全面，这个领域之外的信息并不收集，也不提供这个领域外的服务，这种特定的服务可以有效地把对某一特定领域感兴趣的用户与其他网民区分开来，并能长期久地吸引住这些用户，这就为电子商务的发展提供了一个理想的平台。美国垂直搜索引擎的发展已经充分说明了这种经营模式的正确。M公司通过发布有关疾病和治疗的详细内容，每月赢得高达2500万次的点击，有260万患者和100万医生浏览。Yahoo也从一个单纯的互联网目录发展成为一个垂直搜索引擎总汇，它上面即有保健信息及服务的内容，拍卖、购物、开设网上商店也做得很出色。W的网站其对象只是水和废水处理工程师，这个站点上有聊天室、论坛、就业机会等。内容非常具体丰富。今天，它已发展成为水处理行业的网上交易所，水资源领域的厂商非常愿意在这里投放广告。与此同时，以W起家的这个网站，现在已发展成面向50多个特定领域的垂直搜索引擎社区，从机械制造到医务护理。从食品包装到垃圾处理品，应有尽有，可能最说明问题的还是它的销售额，1998年只有310美元，1999年成功实现IPO（Initial Public Offering）以后，骤升到19亿美元，另外还有一个紧随其后的垂直搜索引擎社区也已囊括26个行业广告领域的，等也正在走向互联网经济的前台7-8。可见，专业化，垂直化已成为未来搜索引擎发展的一个潮流和方向。继2007年1月10日对2006年度互联网市场数据进行系统发布之后，2007年7月9日，2007（上半年）中国互联网市场数据发布会暨2007中国互联网大会发布会在京隆重举行。由中国互联网协会作为指导单位，DCCI互联网数据中心与中国互联网协会交流与发展中心作为主办单位共同实施的2007年度互联网调查，在发布会现场和主网站阶段性的发布了总体市场、网络广告、网络视频、搜索引擎等四个方面的部分数据和分析。 DCCI互联网数据中心发布的最新分析表明，2007下半年垂直搜索依然稳步发展，垂直搜索凭借细分领域的定位，在搜索引擎广告市场赢得一定盈利的空间。但是垂直搜索目前仍处于广告主投放尝试的阶段，离广告主形成投放习惯的阶段还有距离。 垂直搜索得到大量广告主的认可尚需时日。一方面，需要积累更多的用户群。另一方面，对广告主的教育需要时间。而垂直搜索盈利的挑战并不来源与综合搜索。搜索门户（综合类搜索引擎）由于其发展重点不在于特定行业、领域的搜索，因此，搜索门户对垂直搜索的威胁不大。但垂直搜索需要建立符合垂直搜索的算法，才能提高进入直接或间接竞争者的进入门槛。 产业的分工、细分领域的发展是不可避免的产业发展规律。同时，用户的需求也是驱动垂直搜索发展的动力，垂直搜索引擎能够有效解决未来信息过载的问题，有利于用户针对某一特定领域搜索相关信息。反过来，垂直搜索的用户群也相对清晰，基于垂直搜索清晰的用户群定位，广告相对定向，有利于相应行业的广告主投放广告。 国内生活资讯类垂直搜索酷讯、旅行类垂直搜索去哪儿、招聘类垂直搜索职友集和搜职网等垂直搜索引擎稳步发展，相应地带动了生活、旅游、招聘等传统行业广告主投放垂直搜索引擎广告。国外healthline垂直搜索获得了1400万美元的融资，强力刺激了广告主对垂直搜索广告的认可和期待。垂直搜索引擎广告将会在未来几年借助垂直搜索引擎的发展迎来更大的发展空间和机遇9。但是，与美国方兴未艾的垂直搜索引擎发展相比，国内明显还处于落后状态，国内众多网站虽然在自己的发展过程中做了许多有益的探索，但在内容垂直化、服务集中化、访问经常化方面还有很长的路要走。1.4垂直搜索引擎的发展前景搜索作为网民面对互联网海量信息的最有效途径，已经成为网民的基础网络应用。不管网民对什么内容产生好奇或者求知欲，“到网上搜一下”已经成了网民下意识的第一反应。而作为网民个体而言，其关注的领域、感兴趣的内容是有限的，也就是说网民在网上搜索的内容在很大程度上是有一定关联的，这种关联可能是娱乐爱好、职业领域、地理区域、行业分类等等。而这些关联造就了一个搜索领域的细分市场，那就是垂直搜索。已经过去的2007年被称之为“搜索年”，进入2008年，搜索引擎依然持续走热。 2008年伊始，华尔街对互联网行业的第一份预测出炉。根据摩根大通的研究团队预测，被公众广泛关注的互联网发布者、门户、商业站点和搜索引擎在2008年仍然会以较高的边际回报率超越整体股票市场的表现。摩根大通的分析师Imran Khan和他的团队认为，尽管其收入增长率可能会稍微降低，但互联网公司的收入增长仍然要比整体股票市场的增长快4倍以上。Khan在1月2日公布的报告中写到：“我们预测2008年收入增长率会减缓至21.2%，2007年这一比例为25.6%。”2008年最大的实惠将来自搜索引擎领域。Khan预计全球搜索引擎收入将从2007年的262亿美元升至2008年的305亿美元。相对全球搜索引擎的逐步成熟，中国搜索引擎市场仍然处于早期阶段，和美国在1997-2002年的发展类似。而今，搜索引擎已经成为中国数字市场中当之无愧的明星，在历经连续18个季度的高速增长后，搜索引擎正在进入一个相对平稳的发展期。搜索引擎在快速增长中充满各种变数，培养用户粘性至关重要，更佳的用户体验是种不错的选择。百度、谷歌等在搜索领域占的比重更大，但这并不意味着搜索市场已经形成垄断，中国市场上并不缺乏搜索领域的“新生儿”，相对百度、谷歌的强大，更多的“新生儿”实行垂直化、细分化来角逐搜索市场，类似的有锣鼓网商业搜索、去哪儿旅游搜索等垂直搜索。 搜索引擎本身的性质不同，使用人群、以及对用户体验的粘性把握上采用的方式也就不同。百度在市场细分方面投入很大，尽力从客户使用的角度去挖掘产品更大的市场空间。因此百度的客户群体数量大，以年轻群体为主，对于偏重时尚娱乐产品的企业可能是一个比较好的选择，而同是搜索引擎的锣鼓网，与百度不同的是，锣鼓网面向的是商业领域，商业型的企业是锣鼓网偏重的市场。中国现有4000万家中小企业，作为商业搜索引擎，面向的用户群体更集中，相对来说培养企业用户的粘性需要提供更广、更深、更细的服务。中国电子商务协会秘书长陈震认为，“随着技术的发展和用户需求的不断提高，对信息的准确性、有效性和公正性越来越被重视，这势必引发服务的变革，从大而全发展为精准和高效，但企业必须要有强大技术研发实力，以及独特的模式才能在竞争中脱颖而出”。锣鼓网商业搜索在服务提供上，推出“贸易直通车”产品，利用搜索+电子商务的形式，逐步教育企业用户，形成企业人群对锣鼓网商业搜索的使用粘性。有业内人士在预测2008年垂直搜索发展情况时，对“锣鼓网商业搜索、去哪儿旅游搜索等”做了重点推荐10。1.5课题的主要研究内容根据我国丝绸行业的发展现状和信息搜索的需求，本文的主要目的，在于利用当前较为先进的垂直搜索引擎技术，建立一个由丝绸信息结构化抽取和检索为主要服务内容的丝绸产品搜索网站，主要的信息来源于当前网页中发布信息的自动识别，并可以根据用户输入的检索项，返回符合条件的丝绸产品信息。这了实现这一目的，课题将按照如下结构开展以下几个方面的具体研究。第一章，绪论。主要论述课题的研究背景，垂直搜索引擎发展现状、存在的问题、发展趋势以及发展前景。第二章，搜索引擎的基本原理。尽管垂直搜索引擎有自己的独特之处，但毕竟也是搜索引擎的一种，本章将重点论述搜索引擎的基本工作过程，各个过程中所采用的关键技术和信息处理方法，为后文丝绸信息搜索引擎的设计建立一个基本框架。第三章，垂直搜索引擎的关键算法，重点论述垂直搜索引擎设计与实现的一些独特的信息识别方法，提出丝绸信息搜索引擎所采用的一些关键算法。第四章，面向丝绸领域的垂直搜索引擎的总体设计，根据前文的理论分析和当前搜索引擎技术的发展现状，按照软件工程的方法，重点论述丝绸信息搜索引擎的总体设计过程，包括需求分析、网站的功能规划和总体结构等内容。第五章，面向丝绸领域的垂直搜索引擎技术的具体实现，在前面总体设计的基础上，选定系统的开发环境和开发工具，通过编码实现设计阶段的各种算法和具体功能。结论。主要对论文的研究工作进行总结，提出系统的创新之处存在的问题。针对以上几点，本课题做了大量的工作，开发的平台具有较好的通用性，可扩展性。第2章搜索引擎实现原理由于垂直搜索引擎是通用搜索引擎的细分和延伸，因此，在基本原理和工作过程方面，与通用搜索引擎基本相同。本章将在重点论述通用搜索引擎的基本原理，作为开发丝绸信息搜索引擎的基础。2.1 通用搜索引擎的工作流程尽管当前对于各种搜索引擎的分类不同，但从原理上看，搜索引擎主要是指那些使用网页爬行软件，按照一定的策略将Web文档采集到本地数据库，然后对这些网页进行自动分析并建立索引数据库，进而对用户提出的检索请求在数据库中进行搜索，找出匹配的文档或者链接，返回给用户的网络软件。搜索引擎系统一般由蜘蛛（也叫网页爬行器）、切词器、索引器、查询器几部分组成。蜘蛛负责网页信息的抓取工作，一般情况下切词器和索引器一起使用，它们负责将抓取的网页内容进行切词处理并自动进行标引，建立索引数据库。查询器根据用户查询条件检索索引数据库并对检索结果进行排序和集合运算，如并集、交集运算，再抽取网页简单摘要信息反馈给查询用户11。搜索引擎从功能上同样分为三大部分：网页爬行、标引入库和用户查询12。网页爬行主要负责网页的抓取，由URL服务器、爬行器、存储器、分析器和URL解析器组成, 爬行器是该部分的核心；标引入库主要负责对网页内容进行分析，对文档进行标引并存储到数据库里，由标引器和分类器组成，该模块涉及许多文件和数据，有关于桶的操作是该部分的核心；用户查询主要负责分析用户输入的检索表达式，匹配相关文档，把检索结果返回给用户，由查询器和网页级别评定器组成，其中网页等级的计算是该部分的核心。其总体系统结构图2-1所示。图2.1搜索引擎的工作流程搜索引擎的主要工作流程是：首先从蜘蛛开始，蜘蛛程序每隔一定的时间（象google一般是28天）自动启动并读取网页URL服务器上的URL列表，按深度优先或广度优先算法，抓取各URL所指定的网站，将抓取的网页分配一个唯一文档ID(DocId)，存入文档数据库。一般在存入文档数据库之前进行一定的压缩处理。并将当前页上的所的超连接存入到URL服务器中。在进行抓取的同时，切词器和索引器将已经抓取的网页文档进行切词处理，并按词在网页中出现的位置和频率计算权值，然后将切词结果存入索引数据库。整个抓取工作和索引工作完成后更新整个索引数据库和文档数据库，这样用户就可以查询最新的网页信息。查询器首先对用户输入的信息进行切词处理，并检索出所有包含检索词的记录，通过计算网页权重和级别对查询记录进行排序并进行集合运算，最后从文档数据库中抽取各网页的摘要信息反馈给查询用户。2.2 网页信息采集技术和软件当前的网页信息采集技术，主要依赖自动采集软件，也称机器人robot，蜘蛛spider或者爬虫crawler，利用Web文档内的超级链接递归访问新网页。其主要功能是自动从internet上的各Web站点抓取Web文档并从Web文档中撮一些信息来描述该Web文档13；为搜索引擎站点的数据库服务器追加和更新数据提供原始数据，这些数据包括HTML、标题、长度、文件建立时间、HTML文件中的各种链接等14。2.2.1网页信息采集软件的工作方式 蜘蛛(即Web Spider)，实际上是一个基于HTTP协议的网络应用程序。网络蜘蛛是通过网页的链接地址来寻找网页，从网站某一个页面（通常是首页）开始，读取网页的内容，并抽取出网页中的其它超链接地址，然后通过这些链接地址寻找下一个网页，这样一直循环下去，直到把这个网站所有的网页都抓取完为止15。在抓取网页的时候，spider通常将Web作为一个有向图来处理，将每一个页面看作图的一个节点，将页面中的超链接看作图中的有向边。因此，可以使用有向图的遍历算法来对Web进行遍历16。当前流行的遍历算法包括以下几种。（1）IP地址搜索策略先赋予spider一个起始地址的IP，然后根据IP递增的方式搜索本IP段后的每一个WWW地址中的文档，它完全不考虑各文档中指向其他Web站点超链接地址。这种算法搜索全面，能够发现没有被其他文档引用的新文档信息源，但效率较低，不适合大规搜索。（2）深度优先算法从起始页面P0出发沿P0上的某一个链接一直搜索到某个不包含任何链接的文件为止，这样形成一条完整的链。再返回P0继续选择其他链接进行相似的访问。访问结束的标志是不再有其他超链接可以搜索。这种算法的优点是在理论上能够遍历一个Web站点下所有深层嵌套的页面，但如果遇到深度很大的搜索树，有陷入一个分支当中或者进入循环状态的危险，因而不具有完备性和最优性。（3）广度优先算法先搜索完一个Web页中所有的链接，再继续下一层的搜索，直到最底层为止。它克服了深度优先算法所不具备的完备性和最优性的缺点，保证一个服务器上至少有一篇文档加入到索引数据库，能降低同一服务器被访问的频度，但时间复杂度和空间复杂度较大。（4）深度广度结合算法17-18这是一种综合深度优先算法和广度优先算法的优点，并克服两者缺点的算法。使用这种算法的spider每到达一个新的页面后能对该页面的后续链接（即引用该页面的链接）进行统计，并对该页面进行检索，将检索结果返回给用户。接着对所获得的一组URL重复上述步骤。这种算法查全率高，但当同一时间检索的用户过多时可能造成服务器负担过重或者信息阻塞现象。垂直搜索引擎spider和网页库的spider相比应该是更加专业，可定制化。可定向性的采集和垂直搜索范围相关的网页忽略不相关的网页和不必要的网页，选择内容相关的以及适合做进一步处理的网页深度优先采集、对页面有选择的调整更新频率，采集可通过人工设定网址和网页分析url方式共同进行。2.2.2网页采集软件的组成模块根据抓取过程蜘蛛主要分为三个功能模块:一个是网页读取模块主要是用来读取远程Web服务器上的网页内容，另一个是超链分析模块，这个模块主要是分析网页中的超链接，将网页上的所有超链接抽取出来，放入到待抓取URL列表中，再一个模块就是内容分析模块，这个模块主要是对网页内容进行分析，将网页中所有超标志去掉只留下网页文字内容。蜘蛛的主要工作流程如图2.2所示：首先蜘蛛读取抓取站点的URL列表，取出一个站点URL，将其放入未访问的URL列表（UVURL列表）中，如果UVURL不为空则从中取出一个URL判断是否已经访问过，若没有访问过则读取此网页，并进行超链分析及内容分析，并将这些页存入文档数据库，而那些URL则放入已访问URL列表（VURL列表），直到UVRL为空为止，此时再抓取其他站点，依次循环直到所有的站点URL列表都抓取完为止。创建蜘蛛读取站点URL列表站点URL列表是否空结束是否将URL放入UVURL列表UVURL为空？读取此URL网页超链分析内容分析存入文档库删除此URL并加入VURL取出一URL是否已访问？否否是是说明UVURL：为当前站点未访问的URLVURL：为当前站点已访问的URL图2.2 spider的工作流程创建蜘蛛读取站点URL列表站点URL列表是否空结束是否将URL放入UVURL列表UVURL为空？读取此URL网页超链分析内容分析存入文档库删除此URL并加入VURL取出一URL是否已访问？否否是是说明UVURL：为当前站点未访问的URLVURL：为当前站点已访问的URL2.3索引器索引操作是所有搜索引擎的核心概念：为了进行快速查找，就需要把数据处理成一种高效的、可交叉引用的查找表格式。为了快速搜索大量的文本文件，首先必须为文件建立索引，就像是为一本书建立目录，然后把文本转换成你能够快速搜索到的格式，而不是使用慢速顺序扫描的处理方法。我们把这个转换过程称为索引操作。因此索引器是搜索引擎系统必须也是很关键的一个环节，它主要完成将切词形成的顺排档文档组织成倒排档索引数据19-21。2.3.1实现原理1.索引文件结构倒排档索引文件分三个文件保存，一个是存放各词条索引文件，另一个是各文档索引文件，再一个就是各词在文档中出现的位置信息文件。1)、顺排档结构顺排档文档是以DocID为主序的，每一文档下存放各自出现的词的ID及各词所出现的次数和具体位置信息，各数据项的存储长度固定。DocIDWordID出现次数hit.hit.WordID出现次数hit.hitHits(位置)占16位DocIDWordID出现次数hit.hit.WordID出现次数hit.hit图2-3顺排档结构2）、倒排档结构hitWordIDnDocs文档开始位置WordIDnDocs文档开始位置WordIDnDocs文档开始位置hithithithithitDocID出现次数首次出现位置DocID出现次数首次出现位置DocID出现次数首次出现位置DocID出现次数首次出现位置DocID出现次数首次出现位置DocID出现次数首次出现位置.hithithithit一级索引二级索引Hits图2-4倒排档结构2.3.2索引数据组织1）、一级索引：一级索引文件属于记录式文件，每一记录大小固定，共有三个数据项构成，WordID、文档数、第一个文档开始位置。其中WordID是词典中词条的ID，文档数是指这个词总共在多少个文档中出现，文档开始位置是一个文件指针指向二级索引中出现当前词的文档集中的第一个文档存储位置，这个指针是一个长整形值相当于指明了是二级索引文件中的第几条记录，因为各记录长度也是固定大小。通过这个指向可以直接定位到二级索引文件读取位置，然后读取nDocs个记录即可，因为它们是存放在连续的地址空间上。2）、二级索引：二级索引也是一种记录式文件，每一记录有三个数据项组成，DocID、出现次数、第一个Hit位置。其中DocID是文档的ID，出现次数指的是当前文档中某一个词出现的次数，第一个Hit位置也是一个指针，指向Hits文件中的某一位置。通过这个指针