全文搜索引擎的设计与实现本科毕业论文(编辑修改稿)

全文搜索引擎的设计与实现本科毕业论文(编辑修改稿)内容摘要：

返回给用户。 无论 搜索 引擎 的规模大小，其主要结构都是由这几部分构成的，并没有大的差别，搜索 引擎 的好坏主要是决定于各部分的内部实现。 江 汉大学本科毕业论文（设计） 5 有了上述的对与 搜索 引擎 的整体了解， 下面对 搜索 引 擎的各个模块进行说明。 网页 收集 全文检索 是工作在某个数据集合上的程序，他需要事先由页面抓取程序，在全网中抓取海量网页，这个抓取程序也叫网络爬虫或 Spider。 只有事先抓取了足够多的网页数据，并处理之，才能对大量的用户查询提供及时的响应。 爬虫的工作流程 网页收集的过程如同图的遍历，其中网页就作为图中的节点，而网页中的超链接则作为图中的边，通过某网页的超链接 得到其他网页的地址，从而可以进一步的进行网页收集；图的遍历分为广度优先和深度优先两 种方法，网页的收集过程也是如此。 综上，Spider 收集网页的过程如下：从初始 URL 集合获得目标网页地址，通过网络连接接收网页数据，将获得的网页数据添加到网页库中并且分析该网页中的其他 URL 链接，放入未访问 URL 集合 中 用于网页收集。 下图表示了这个过程： 图 23 Spider 工作流程 爬虫的抓取策略 爬虫的工作策略一般分为累积式抓取（ cumulative crawling）和增量式抓取（ incremental crawing）两种。 累积式抓取是指从某一个时间点开始，通过遍历的方 式抓取系统所能允许存储和处理的所有网页。 在理想的软硬件环境下，经过足够的运行时间，积累是抓取策略可以保 江 汉大学本科毕业论文（设计） 6 证抓取到相当规模的网页集合。 但由于 Web 数据的动态特性，集合中的网页的抓取时间点是不同的，页面被更新的情况也不同，因此累积式抓取到的网页集合事实上并无法与真实环境中的网络数据保持一致。 与累积式抓取不同，增量式抓取是指在具有一定量规模的网页集合的基础上，采用更新数据的方式选取已有集合中的过时页面进行抓取，以保证所抓取的数据与真实网络数据足够接近。 进行增量式抓取的前提是，系统已经抓取了足够数量的网络页面，并具有这项页面被抓取的时间信息。 面对实际应用环境的网络蜘蛛设计中，通常既包含累积式抓取，也包括增量式抓取的策略。 累积式抓取一般用户数据集合的整体建立或大规模更新阶段；而增量式抓取则主要针对数据集合的日常维护和及时更新。 链接数据库的建立 初始 URL 的建立有两种方式：超链接和站长提交。 超链接：爬虫会根据种子地址（可能是最先提交给爬虫的 URL 集合）抓取页面。 站长提交：在实际运行中，爬虫不可能抓取所有的站点，为此，网站站长可以向搜索引擎进行提交，要求收录， 搜索 引擎 经过核查后，便将该网站加入到 URL 集 合中，进行抓取。 链接数据库的更新 链接的注入：抓取程序会根据预先提供的 URL 集合进行标准化，根据设定的正则检验来过滤 URL，将这些符合标准的 URL 放入到 map 中，并在构造 map 过程中给 URL 初始化得分，分数可以影响 URL 对应主机的搜索排序和采集优先级。 接着会判断 URL 在抓取数据库中是否存在，如果存在，删除旧的，更新新的。 如果不存在，将该 URL 的状态标记为未采集过。 URL 生成器：从抓取回来的网页中，将符合条件的 URL 提出出来，检测 URL 是否在有效更新时间里面，并将 URL 载入相应的任务组，计算 URL 的 hash 值，搜集 URL，直至达到规定的广度。 网页预处理 网页预 处理 的主要目标是 将 原始网页通过一步步的数据 处 理变成可方便搜索的数 江 汉大学本科毕业论文（设计） 7 据形式。 预处理模块的整体结构如下： 图 24 预 处理模块的整体结构 通过 爬虫 的收集，保存下来的网页信息具有较好的信息存储格式，但是还是有一个缺点 ，就是不能按照网页 URL 直接定 位到所指向的网页。 所以，需要先建立网页的索引，如此通过索引， 这样 可以很方便的从原始网页库中获得某个 URL 对应的页面信息。 之后，处理网页数据，对于一个网页，首先需要提取其网页正文信息，其次对正文信息进行分词，之后再根据分词的情况建立索引和倒排索引，这样，网页的预处理也全部完成。 建立索引页面库 索引的主要过程： 江 汉大学本科毕业论文（设计） 8 图 25 索引的主要过程 索引过程可分为三个主要的操作阶段： 将数据转换成文本 分析文本 将分析过的文本保存到数据库中 转换成文本。 在索引 数据之前，首先必须将数据转换成纯文本字符流。 但是，在现实世界中，信息多以富媒体文档格式呈现： PDF,WORD,EXCEL,HTML,XML 等。 为此需要使用文档解析器，将富媒体转换成纯文字字符流。 分析文本。 在对数据进行索引钱，还必须进行预处理，对数据进行分析是之更加适合被索引。 分析数据时，现将文本数据切分成一些大块或者词汇单元，然后对它们执行一些可选的操作，例如：在索引之前将这些词汇单元转换成小写，使得搜索对大小写不敏感；具有代表性的是要从输入中去掉一些使用很频繁但却没有实际意义的词，比如英文文本中的一些停 用词（ a、 an、 the、 in、 on 等）。 同样的，也需要分析输入的词汇单元，一遍从词语中去掉一些不必要的字母以找到他们的词干。 这一处理过程称为分析。 将分析后的数据写入索引。 对输入数据分析处理完成后，就可以将结果写入索引文件中。 结果一般包括网页标题，正文，所属住地址，主机，内容摘要，时间戳，当前 URL 地址等，并更具具体需要建立索引和存储。 江 汉大学本科毕业论文（设计） 9 分词 中文分词是指将一个汉字序列切分成一个一个单独的词，从而达到计算机可以自动识别的效果。 中文分词主要有三种方法：第一种基于字符串匹配，第二种基于语义理解，第三种 基于统计。 由于第二和第三种的实现需要大量的数据来支持， 一般 采用的是基于字符串匹配的方法。 基于字符串匹配的方法又叫做机械分词方法，它是按照一定的策略将待分析的汉字串与一个 “ 充分大的 ” 机器词典中的词条进行配，若在词典中找到某个字符串，则匹配成功（识别出一个词）。 按照扫描方向的不同，串匹配分词方法可以分为正向匹配和逆向匹配；按照不同长度优先匹配的情况，可以分为最大（最长）匹配和最小（最短）匹配。 常用的几种机械分词方法如下： 正向减字最大匹配法（由左到右的方向）； 逆向减字最大匹配法（由右到左的方向）； 最少切分 （使每一句中切出的词数最小）； 双向最大减字匹配法（进行由左到右、由右到左两次扫描）； 采用其中的正向最大匹配法。 算法描述如下：输入值为一个中文语句 S，以及最大匹配词 n 取 S 中前 n 个字，根据词典对其进行匹配，若匹配成功，转 3，否则转 2； n = n – 1：如果 n 为 1，转 3；否则转 1； 将 S 中的前 n 个字作为分词结果的一部分， S 除去前 n 个字，若 S 为空，转 4；否则，转 1； 算法结束。 需要说明的是，在第三步的起始， n 如果不为 1，则意味着有匹配到的词；而如果 n 为 1， 默认 1 个字是应该进入分词结果的，所以第三步可以将前 n 个字作为一个词而分割开来。 还有需要注意的是对于停用词的过滤，停用词即汉语中 “ 的，了，和，么 ”等字词，在 搜索 引擎 中是忽略的，所以对于分词后的结果， 需要在用停用词列表进行一下停用词过滤。 您也许有疑问，如何获得分词字典或者是停用词字典。 停用词字典比较好办，由于中文停用词数量有限，可以从网上获得停用词列表，从而自己建一个停用词字典；然而对于分词字典，虽然网上有许多知名的汉字分词软件，但是很少有分词的字典提供。 在程序使用过程中，分词字典可以放入一 个集合中，这样就可以比较方便的进行比对工作。 分词的结果对于搜索的精准性有着至关重要的影响，好的分词策略经常是由若干个 江 汉大学本科毕业论文（设计） 10 简单算法拼接而成的，所以您也可以试着实现双向最大减字匹配法来提高分词的准确率。 而如果遇到歧义词组，可以通过字典中附带的词频来决定哪种分词的结果更好。 倒排索引 倒排索引（英语： Inverted index），也常被称为反向索引、置入档案或反向档案，是一种 索引 方法，被用来 存储在全文搜索 下某个单词在一个文档或者一组文档中的 存储位置的映射。 它是 文档索引系统 中最常用的 数据结构。 有两 种不同的反向索引形式： 一条记录的水平反向索引（或者反向档案索引）包含每个引用单词的文档的 列表。 一个单词的水平反向索引（或者完全反向索引）又包含每个单词在一个文档中的位置。 后者的形式提供了更多的 兼容性 （ 比如短语搜索 ），但是需要更多的时间和空间来创建。 下面将以图示和实例的方式分别说明正向索引和倒排索引。 图 26 正向索引 江 汉大学本科毕业论文（设计） 11 图 27 倒排索引 以 英文 为例，下面是要被索引的文本： it is what it is what is it it is a banana 这样 就能得到下面的反向文件索引： a: {2} banana: {2} is: {0, 1, 2} it: {0, 1, 2} what: {0, 1} 检索的条件 what, is 和 it 将对应这个 集合 ：。 对相同的文字， 得到后面这些完全反向索引，有 文档 数量和当前查询的单词结果组成的的成对 数据。 同样，文档数量和当前查询的单词结果都从零开始。 所以， banana: {(2, 3)} 就是说 banana在第三个文档里 ( )，而且在第三个文档的位置是第四个单词 (地址为 3)。 a: {(2, 2)} banana: {(2, 3)} is: {(0, 1), (0, 4), (1, 1), (2, 1)} 江 汉大学本科毕业论文（设计） 12 it: {(0, 0), (0, 3), (1, 2), (2, 0)} what: {(0, 2), (1, 0)} 如果 执行短语搜索 what is it 将 得到这个短语的全部单词各自的结果所在文档为文档 0 和文档 1。 但是这个短语检索的连续的条件仅仅在文档 1得到。 查询服务 查询服务的整体结构如下： 图 28 查询服务的整体结构 在网页预处理后，每个元素至少包含如下几个方面： 原始网页文档 URL 和标题 编号 所含的重要关键词的集合（以及他们在文档中出现的位置信息） 其他一些指标（例如重要程度，分类代码等） 而系统关键词总体的集合和文档的编号一起构成了 一个倒排文件结构，使得一旦得到一个关键词输入，系统能迅速给出相关文档编号的集合输出。 查询方式和匹配 查询方式指的是系统允许用户提交查询的形式。 考虑到各种用户的不同背景和不同 江 汉大学本科毕业论文（设计） 13 的信息需求不可能有一种普适的方式。 一般认为，对于普通网络用户来说，最自然的方式就是 “ 要什么就输入什么 ”。 但这是一种相当模糊的说法。 例如用户输入“江汉大学”，可能是他想了解江汉大学目前的招生状况，可能需要找到江汉大学教务系统的网址，可能需要了解大家对江汉大学的评价。 这是三种相当不同的需求。 在其他一些情况下，用户可能关心 的是间接的信息，例如“江汉大学录取分数线”， 450 分应该是他需要的，但不可能包含在这个短语中。 尽管如此，用一个次或短语来间接表达信息需求，希望网页中含有该词或该短语中的词，依然是主流的搜索引擎查询模式。 这不仅是因为他的确代表了大多数的情况，还因为它比较容易实现。 这样，一般来讲，系统面对的是查询短语。 一般地，用 q0 表示用户提交的原始查询，例如，q0 =“ 网络与分布式系统实验室 ”。 它首先需要被 “ 切词 ” （ segment）或称 “ 分词 ” ，即把它分成一个词的序列。 如上例，则为 “ 网络 与 分布式 系统 实验室 ” （注意，不同的分词软件可能得出不同的结果）。 然后需要删除那些没有查询意义或者几乎在每篇文档中都会出现的词（例如 “ 的 ” ），在本例中即为 “ 与 ”。 最后形成一个用于参加匹配的查询词表， q = {t1, t2, „, tm} ，在本例中就是 q = {网络，分布式，系统，实验室 }。 倒排文件就是用词来作为索引的一个数据结构，显然， q 中的词必须是包含在倒排文件词表中才有意义。 有了这样的 q，它的每一个元素都对应倒排文件中的一个倒排表（文档编号的集合），记作 L(ti)，它们的交集即为对。