【毕业学位论文】（Word原稿）搜索引擎检索系统的效率优化与效果评估研究(V2.0)-计算机网络与分布式系统博士论文

北京大学博士研究生学位论文 题目：搜索引擎检索系统的效率优化与效果评估研究 姓 名：彭波 学 号： 10108808 院 系：计算机科学技术系 专 业：计算机系统结构 研究方向：计算机网络与分布式系统 导 师：李晓明 教授 2004 年 5 月 in of or y o ( I 2004 版权声明 任何收存和保管本论文各种版本的单位和个人，未经本论文作者同意，不得将本论文转 借他人，亦不得随意复制、抄录、拍照或以任何方式传播。否则，引起有碍作者著作权之问题，将可能承担法律责任。 i 摘 要 本文研究工作是国家重点基础研究发展规划项目“网络环境下海量信息组织与处理的理论与方法研究”的一部分；针对 索引擎应用背景，以构建大规模、高性能搜索引擎的检索系统为目标，系统地研究了检索系统的效率问题和效果评估问题，提出了若干关键技术，在大量实验和真实数据分析的基础上，得到了如下研究成果和结论： 1）提出了一种混合索引技术。该技术针对中文信息检索索引词选择的问题，通过结合中文自动分词与未 登录词识别技术，把基本分词结果与在识别生成的扩展词典上的分词结果都选择作为索引词。通过在实际系统的应用实践，表明该技术能有效提高短语检索效率。 2）提出了一种倒排文件分块组织方法，它兼顾了文档编号序列和文档权值序列在检索系统性能中的不同作用，为综合优化系统性能提供了一个可操作的框架。和已有相关工作相比，这一研究基于搜索引擎应用背景，通过搜索引擎系统的实际数据，建立了一个检索性能模型，在此模型基础上研究分块组织策略对性能的影响和分块参数的优选。研究结果表明，这一分块组织策略可以有效提高检索效率。 3）倒排文件 缓存是检索系统效率优化的重要技术。结合到大规模检索过程中磁盘 I/O 以及操作系统页面调度的特点，本文研究了倒排文件缓存优化设计中的性能指标选择、替换算法、页面大小和倒排文件组织方式对缓存性能影响等问题。研究结果为倒排文件缓存优化设计提供了指导。 4）针对搜索引擎检索系统效果评估中的若干问题，设计并实现了一个搜索引擎检索系统检索效果评估的实验环境。基于搜索引擎的用户查询日志，按查询类别构建了用户查询集合。对不同搜索引擎搜集系统搜集网页集合的差异、评测员结果之间的差异对评估实验的稳定性、连续性的相关度评分分值以及 对应的评估指标、查询集合大小对评估实验的稳定性等问题进行了研究，结果对于进行有效的检索评估实验有重要指导意义。 5）基于对搜索引擎用户点击日志数据的分析，提出了一种自动构建评估实验相关结果集合与进行自动评估实验的方法。实验显示这一自动方法得到的结果和人工评估实验结果保持一致，并且对不同查询集合保持稳定。这一方法为解决大规模数据集上检索系统评估的可扩展性问题提供了一条有效的途径。 关键词 ：万维网，搜索引擎，信息检索，检索效率，性能，评估 is an of In we of of on 1. A is By we of on on of as of is in 2. A of is It of to of A of on by on of 3. is an We in of of of a of 4. at in of in we an We a of eb h of on of 5. An is on of of on of on to is a of on eb v 目录 摘 要 . i . 录 . v 图示 . 格 . 1 章 引言 . 1 究工作的背景和意义 . 1 文研究工作的内容 . 2 文的主要贡献 . 3 合索引技术 . 3 排文件分块组织技术 . 3 排文件索引的缓存优化技术 . 4 索引擎检索效果评估方法 . 4 于用户点击日志的自动评估方法 . 4 文组织 . 4 第 2 章 搜索引擎检索系统基本技术 . 6 言 . 6 统设计与结构 . 6 引创建 . 10 引词选择 . 10 页预处理 . 11 引创建算法 . 12 索过程 . 12 引压缩 . 13 机访问的索引组织 . 13 要索引词单独索引 . 14 章小结 . 14 第 3 章 混合索引技术 . 15 言 . 15 合索引原理 . 15 合索引的实现 . 18 登录词识别 . 18 展词典组织与分词 . 19 章小结 . 20 第 4 章 倒排文件分块组织技术 . 21 言 . 21 排索引的检索性能模型 . 22 档模型 . 22 户查询模型 . 24 算机系统性能参数 . 26 块索引项的组织策略 . 26 排文件基本组织方式与检索算法 . 26 排文件分块组织方式与检索算法 . 28 验设计 . 29 法仿真 . 29 题分析 . 30 真实验和结果 . 31 R|与 k 比较 . 31 (Q)以及分块因子 对 T(Q)的影响 . 33 章小结 . 35 第 5 章 倒排文件索引缓存机制 . 36 言 . 36 排文件缓存 . 37 系结构 . 37 载数据 . 38 载特性 . 39 列中对象的时间间隔分布 . 40 列的重复模式 . 41 验设计 . 41 题分析 . 41 验设计 . 44 真实验结果 . 45 击 时间间隔 . 72 击 过程具有自相似性特征 . 74 击 聚类分析 . 75 动评估实验 . 77 章小结 . 80 第 8 章 总结和未来工作展望 . 81 参考文献 . 85 北京大学学位论文原创性声明和使用授权说明 . 94 致谢 . 95 博士期间录用和提交的论文 . 96 图示 图 2索系统集成框架结构 . 7 图 2网 索分布式系统构架 . 9 图 3展词典树结构示例 . 20 图 3展词典匹配查找算法 . 20 图 4序号 . 24 图 4户查询词个数分布 . 25 图 4引词区间上的查询分布 . 25 图 4排文件基本检索算法 . 27 图 4块组织倒排文件的检索算法 . 28 图 4R| 与 K 比较的仿真结果 . 32 图 4块检 索 I/O 访问比例 . 32 图 4词区间均匀分块下的 T(Q) . 34 图 4几何级数区间分块下的 T(Q) . 34 图 5索引 擎检索系统缓存结构 . 37 图 5档数据访问对象大小分布 . 40 图 5（ 4列替换算法比较 . 46 图 5缓存性能 . 46 图 5面对齐方式下缓存性能与页面大小的关系 . 48 图 6关度评测环境 . 56 图 6测人员每组评测平均花费时间 . 59 图 6测人员评分差异 . 59 图 6同评估人员与评估指标下结果比较 . 60 图 6询集合大小对评估稳定性影响 . 62 图 7同 数量遵从 . 68 x 图 7击 频度频级关系 . 68 图 7点击 序号 . 70 图 7始索引文档库中网页的大小分布 . 70 图 7引库中与点击页面大小的比较 . 71 图 7面大小与点击次数关系 . 71 图 7击 现的时间间隔 . 73 图 7时间间隔在 60 秒内点击 特征 . 73 图 7击 列的自相似性 . 75 图 7同的 数与对应查询词序号关系图 . 78 表格 表 4档模型参数 . 23 表 4户查询模型参数 . 24 表 4算机性能参数 . 26 表 5据集基本统计信息 . 39 表 5面对齐方式和顺序方式的性能比较 . 47 表 6户查询分类类别 . 53 表 6户查询类别分布 . 53 表 6询集说明及示例 . 53 表 6索引擎覆盖率比较 . 58 表 6估人员与指标比较实验结果 . 61 表 6航型查询评估结果 . 63 表 6航型查询评估结果显著性和错误率 . 63 表 6务型查询评估结果 . 64 表 7网用户点击日志记录格式 . 67 表 7网 2003 年 9 月 点击日志基本情况 . 67 表 7击 应页面的类别 . 72 表 7于 较的自动评估结果 . 78 表 7于 较的相关判别结果统计 . 79 表 7于站点判别的自动评估结果 . 79 表 7于站点判别的相关结果统计 . 79 表 7于站点判别的自动评估实验错误率 . 80 第 1 章 引言 1 第 1章 引言 究工作的背景和意义 我们 正处在一个新时代的起点。 活和工作等各个方面，它们的影响力已经开始渗透到社会的各个层面。而这一切才刚刚开始。 1945 年提出的 945代表了人类长久以来的一个梦想：让每个人都可以十分容易的访问人类积累下来的知识并且十分容易的共享自己的见解。 描述成一个存放了无数本书籍的书桌，这些书籍的内容被超链接互相连接起来，同时其它形式的知识载体，如图片、声音录音等也被放进来。人们可以通过链接在 浏览，也可以通过简单的界面，比如口头的命令来搜索和查询。人们还可以共享自己对书籍阅读的注解。 出现使 再仅仅是一个梦想。万维网（ 记为 源于 1989 年欧洲粒子物理研究室 初计 划是由物理学家 1989 年 3 月提出，在 1993 年 2 月，随着第一个图形界面 发布而开始迅速发展 et 1994。据估计每年 量增加 100%001，每天增加大约100 万的新网页 et 1999。到 2004 年 4 月， 称提供对 4,285,199,774 个网页提供 检索服务 但这还只是 已有网页中很小的一部分 999, 核心技术是超文本和超媒体，它通过将文本、图形、图像、音频、视频等信息的有机结合，给人们提供了丰富的信息表示空间。同时 得信息发布 变得前所未有的简单，也让信息浏览十分方便。整个 当于一个巨大的知识库，越来越多的文本、书籍被数字化提供在线服务，越来越多的文字以数字化的形式创建和存储。 模的迅速增长和内容不断丰富，也给人们进行有效访问带来了困难。人们需要 有 那样理想的搜索和查询的功能，以帮助自己快速、准确的在信息的海洋中找到自己需要的内容。搜索引擎正是由这样一种需求推动而得到快速发展的信息服务形式。根据统计，约 85%的用户使用搜索引擎去定位他们需要的信息，并且，几个著名的通用搜索引擎一直都稳定的处于全球访问 量最大的 50 个网站之列。搜索引擎已经成为第 1 章 引言 2 了人们进行信息获取的一个基础设施。 搜索引擎的检索系统建立在信息检索技术之上。广义的信息检索是研究信息的结构、分析、组织、存贮和检索的学科。其中，非结构化的文本信息检索是信息检索领域研究的重点，当前搜索引擎的检索系统就是这一类的信息检索系统。信息检索从 1960 年代开始，一直坚持采用统计的方法处理语言和文本数据，强调评估方法和评估实验，逐步建立了大规模的测试数据集和评估环境，取得了丰硕的研究成果。 索是信息检索研究的多种信息获取类型中的一种， 的用户查询是多 种用户信息需求类型中很重要的一部分，搜索引擎可以从信息检索领域研究成果中选取成熟的技术。同时， 索本身的特点也为信息检索研究带来了新的研究问题，比如 索下的巨大数据规模和用户数量， 据的超文本结构，索下用户短查询的特点等等。 随着 日益重要， 索成为计算机学科多个领域研究的对象和中心，包括信息检索、数据库、自然语言处理、数据挖掘等。众多研究方法、技术的融合、互相促进是这一方向的特点。 文研究工作的内容 本文研究工作集中在搜索引擎检索系统的性能和评估，主要围绕如何更有效 的组织数据，如何高效检索，如何对检索系统的检索效率和效果进行评估等几个方面。具体体现在研究海量 息的高性能检索技术， 容如下： 1. 混合索引技术：中文全文索引技术中索引词选择直接影响检索系统性能。本文提出了一种基于自动识别新词技术上的混合索引技术。与常用的其它几种索引词选择技术相比，这一技术能够有效提高搜索引擎检索效率，同时不会导致检索效果下降。 2. 分块索引组织技术：对倒排文件索引项数据访问的开销是影响检索系统性能的重要因素。本文针对搜索引擎用户查询的统计特性，提出了一种分块组织 倒排文件的方法及其查询匹配操作算法。该方法兼顾了文档编号序列和文档权值序列在检索系统性能中的不同作用，为综合优化系统性能提供了一个可操作的框架。 3. 索引缓存技术：缓存技术是提高系统效率的重要技术。本文通过分析数据访问序列的局部性特性，和基于用户查询日志数据的缓存仿真实第 1 章 引言 3 验，探讨了倒排文件缓存优化设计中的性能指标选择问题、替换算法选择、页面大小和倒排文件组织方式对缓存性能影响等问题。 4. 检索系统效果评估：检索系统效果评估是信息检索研究的重要内容。本文建立了搜索引擎检索系统效果评估的工具和评估实验环境，对索环 境下的检索效果评估中的若干问题进行研究，包括用户查询类别问题、数据规模和数据集不一致问题、连续型相关性分值与评估标准选择问题、评估评估人员差异对实验的稳定性问题、查询集合大小对实验的稳定性问题等。 5. 点击日志分析：本文对搜索引擎用户点击日志进行统计分析，包括用户点击的基本分布特征分析、局部性特征分析和聚类分析。结果用于指导对检索系统设计和对用户搜索行为的研究。 6. 自动评估方法：自动评估是解决传统检索系统评估的可扩展性问题的一种方法。本文基于用户点击日志分析，提出了一种自动构建评估实验相关结果集合的方法。实验结果 表明这一方法的有