搜索引擎设计.doc

1、搜索引擎设计学号：姓名：专业： 搜索引擎设计1.研究思路当前主流的搜索引擎使用全文检索技术，收集因特网上几千万到几亿个网页，并对网页中的每一个词进行索引。当用户查找某个关键词的时候，所有在页面内容中包含了该关键词的网页都将作为搜索结果被提交出来，在经过复杂的算法排序后展现给用户。这种基于网页的全文检索系统能够适应大信息量查询的需要，具有很强的实用性。模拟百度、Google 等搜索引擎的运行模式，对此类搜索引擎的结构组成、关键算法、技术改进目标进行探讨。2.搜索引擎的构成一个搜索引擎由搜索器(Spider)、索引器（Indexer） 、检索器（Sercher）和用户接口(UI) 等四个部分组成。

2、系统首先由 Spider 即自动的收集程序收集网页的内容；然后由Indexer 将收集回来的内容进行分析，建立一个索引；再由 Sercher 响应用户的检索请示，用户输入关键字后，搜索器要用这个检索词与建立的索引器匹配，匹配后作相关性排序；最后通过 UI 将排序结果送给用户。系统结构如图 1 所示图 1 搜索引擎系统结构互联网数据库文件搜索器FullText文件索引器用户输入用户接口检索器Index文件2.1 搜索器搜索器俗称蜘蛛，其功能是日夜不停地在互联网中漫游， “耙”回信息。它要尽可能多、尽可能快地搜集各种类型的新信息，还要定期更新已经搜集过的旧信息，以避免死链。目前有两种搜集信息的策略

3、：(1)从一个起始 URL 集合开始，顺着这些 URL 中的超链( Hyper link)，以宽度优先、 深度优先或启发式方式循环地在互联网中发现信息。这些起始 URL 可以是任意的 URL，但常常是一些非常流行、包含很多链接的站点(如 Yahoo！)。(2)将 Web 空间按照域名、IP 地址或国家域名划分 ,每个搜索器负责一个子空间的穷尽搜索。搜索器搜集的信息类型多种多样，包括网页文件(如 HTML、XML、JSP、ASP 等格式)，有的搜索器能处理字处理文档(如 Word、Excel、PowerPoint、PDF、RT F 等格式)，甚至数据库文件(如 Oracle、Lotus Note

4、s 的 NSF 文档数据库文件)等。搜索器将“耙”回的每个文档过滤掉格式符，提取文本数据 fulltext。每个文档对应着一个 fulltext 文件，内容包括网页标题、网页 URL、大小、时间、类型、分类等属性及文本内容，所有生成的这些文件交给 Indexer 进行索引处理。搜索器的实现常常用分布式并行计算技术，以提高信息发现和更新的速度。商业搜索引擎的信息发现可以达到每天几百万网页。2.2 索引器索引器的功能是理解搜索器所搜索的信息，从中抽取出索引项，用于表示文档以及生成文档库的索引表。Indexer 读入 Spider 生成的 Fulltext 文件，采用基于位置倒排索引与三级 n 元索

5、引相结合的索引机制。首先进行分词处理生成索引项，并作归并排序，生成 index 和 inv 文件，inv 文件为倒排表(Inversion List)，即由索引项查找相应的文档，index 文件形成分词-倒排表对应关系，内容为分词在倒排表中相应的文档块起始地址，含有该词的文档数量等信息。索引器可以使用集中式索引算法或分布式索引算法。当数据量很大时，必须实现即时索引，否则不能够跟上信息量急剧增加的速度。索引算法对索引器的性能(如大规模峰值查询时的响应速度)有很大的影响。一个搜索引擎的有效性在很大程度上取决于索引的质量。2.3 检索器检索器的功能是根据用户的查询在索引库中快速检出文档 ,进行文档与

6、查询的相关度评价，对将要输出的结果进行排序，并实现某种用户相关性反馈机制。主要过程如下：Searcher 对 UI 提出的查询要求进行递归分析，在 UI 中一般采用基本语法来组织要检索的条件。Searcher 通常支持多种语法规则，如逻辑操作符 AND、OR、NOT，使用“+、- ”连接号和通配符，使用逗号、括号或引号进行词组查找等。对于每个索引项，匹配 index文件 ,查到倒排表(inv 文件)中包含该索引项的文档，并对所有查找出的文档进行集合运算，将结果集按照基于内容和基于链接分析的方法进行相关度评价并排序，最大限度保证检索出的结果与用户查询串有很高的相关性，将最终形成的有序文档结果集合

7、返回给 UI。2.4 用户接口用户接口的作用是输入用户查询，显示查询结果，提供用户相关性反馈机制。主要的目的是方便用户使用搜索引擎，高效率、多方式地从搜索引擎中得到有效、及时的信息。用户接口的设计和实现使用人机交互的理论和方法，以充分适应人类的思维习惯。用户输入接口可以分为简单接口和复杂接口两种。简单接口只提供用户输入查询串的文本框；复杂接口可以让用户对查询进行限制，如逻辑运算(与、或、非；+、 - )、相近关系 (相邻、NEAR)、域名范围(如.edu 、.com)、出现位置(如标题、内容)、信息时间、长度等等。目前一些公司和机构正在考虑制定查询选项的标准。3.搜索引擎设计中采用的关键算法3

8、.1 按步长建立索引项的分词机制要实现真正的全文索引，必须采用基于按步长建立索引项的方式，而不能用特定的词典进行词对应的方式，因为词典方式受收集词汇的限制，可能造成分词不全、有的词查询不到的现象。按步长建索引项分词机制可以最大限度地避免这种问题。以步长为 8 举例(一个汉字占两个步长)，分词举例为：中华人民共和国；分词结果为：中华人民、华人民共、人民共和、民共和国按步长分词时以逐个字节形式读入，遇到中文字时就跳动两个位，而英文字符则跳动一位。而且，对于英文分词时，当词小于步长的大小时不会再继续做分词，而是跳到下一个中文字符或英文字符。例如，有字符串“我是 Chinese People ”需要进

9、行分词，定义步长为 8 个字节，分词应该不管中英文按这 8 个字节的长度进行。第一次分词为“我是 Chin”，然后因为开头是 “我” 字 ,则跳两位；第二次从“是”字开始分词，而不是“我”字的第二个字节，结果是“是 Chines”；同理第三次分词也跳两个字节,但是 “Chinese”的长度小于 8 ,则只是将“Chines e”作为第三次分词结果，然后整个词跳过分词停顿的空格后面的“People”。如果字符串是 “Chinese 人”时，分词第一次的结果应该按 Step 为 8，分出“Chinese” 再加上“人”字的第一个字节，第二次分词则跳过英文部分从“人”字的第一个字节开始进行。如果英文

10、单词的长度大于步长，则象中文分词一样递增，只是不会对末尾的字符进行分词，例如“pronunciation”分词的结果就是：pronunci、ronuncia、onunciat、nunciati、 unciatio、nciation 之后就跳过该单词。建立索引项后再通过必要的逻辑运算就可以实现大于或小于步长的词的查询，得到的结果也会比词典分词更准确和完整。3.2 集合多路归并技术利用该技术将查询的多个有序结果集进行归并。流程如下：(1)读入每一路的第一组数据，对每一路的第一个数据进行排序。(2)剩余路数 RouteNum 大于 1 时 ,进行插入归并。(3)合并 DOCID 和 WordID 相

11、同项，将最小的一项放到输出数组中去。如果剩余纪录为 0，则若该路未归并完成，读入新记录，否则该路已经归并完成，路数减 1。(4)否则，将该路的下一个记录读出，进行二分法插入排序。(5)如果 RouteNum0 ,写入最后一路。3.3 大文件处理技术对于 32 位操作系统，一般的文件处理只能支持最大达 2G 的文件，而对于 2G 以上的文件便无能为力。搜索引擎所处理的文件有可能要大于 2G，因此必须采用分布文件或者 64位文件的做法。4.技术改进目标建立优秀、实用的搜索引擎并非易事。当前几个优秀的搜索引擎如 Google(www.google . com)、百度()等除完成基本搜索功能外，着重在

12、以下几个方面加强技术研究。4.1 使用智能化的语言处理技术系统应支持多种编码标准(包括 ISO2885921、gbk、gb2312、big5、Shift-JIS、UTF8等)，并且能够在不同的编码之间转换，这样就能够对多种语言(包括英语、简体中文、繁体中文、日文、韩文等)进行处理。另外，支持中英文混合检索词是一个难点。4.2 利用快照技术减少死链由于网页的更新速度较快，搜索数据库的更新频率无法赶上网页的更新，造成当使用搜索引擎的时候，会发现很多结果链接打不开(死链)。解决死链问题的一个较好方法是利用快照技术，即将页面备份保存在服务器中，用户如果打不开结果链接(常见原因是页面已被删除或更改地址)

13、，仍可以通过链接到该页面的快照以获取页面备份，从而提高查询的有效性。4.3 搜索引擎专业化所谓专业化搜索引擎，就是该搜索引擎专注于某种专业的信息检索，比起常规的搜索引擎，它可能在信息的广度上略有不足，但就某一专业而言，它的检索深度和分类细化远远优于常规的搜索引擎。设计时主要从三个方面加以改进：第一，优化后台的信息集合；第二 , 优化用户查询界面；第三，检索结果的科学性。除此之外，对动态网页的支持、采用灵活的客户化策略和采用高可用性的体系结构也都是改进的方向。5.总结搜索引擎系统具有很高的技术含量，是网络开发的一座高峰。搜索引擎的技术在不断改进，而人们对它的要求也越来越苛刻。 “全面、高速、有效、智能”是新一代搜索引擎的追求目标。本设计研究了通用搜索引擎技术，分析了其结构和工作原理，并对搜索引擎的关键算法进行研究。通过本设计，深化了我对搜索引擎的认知，培养了我对搜索引擎的兴趣。