《搜索引擎——原理、技术与系统》[李晓明、闫宏飞、王继民著] (pdf document) free file download at fliiby.com

"华夏英才基金学术文库搜索引擎 — 原理、技术与系统 Search Engine: Principle, Technology and Systems 李晓明闫宏飞王继民著 by Li Xiaoming, Yan Hongfei and Wang Jimin 科学出版社 2004 内容简介本书比较系统地介绍了互联网搜索引擎的工作原理、实现技术及其系统构建方案。全书分三篇共 13 章内容，从基本工作原理概述开始，到一个小型简单搜索引擎实现的具体细节，进而详细讨论了大规模分布式搜索引擎系统的设计要点及其关键技术；最后面向主题和个性化的 Web 信息服务，阐述了中文网页自动分类等技术及其应用。本书层次分明，由浅入深；既有深入的理论分析，也有大量的实验数据，具有学习和实用双重意义。本书可作为高等院校计算机科学与技术、信息管理与信息系统、电子商务等专业的研究生或高年级本科生的教学参考书和技术资料，对广大从事网络技术、 Web 站点的管理、数字图书馆、Web 挖掘等研究和应用开发的科技人员也有很大的参考价值。前言随着互联网的不断发展和日益普及，网上的信息量在爆炸性增长，在 2004 年 4 月，全球 Web 页面的数目已经超过 40 亿，中国的网页数估计也超过了 3 亿。目前人们从网上获得信息的主要工具是浏览器，而通过浏览器得到信息通常有三种方式。第一，直接向浏览器输入一个关心的网址（ URL ）例如， http://net.pku.edu.cn，浏览器返回所请求的网页，根据该网页内容及其包含的超链文字（anchor text）的引导，获得自己需要的内容；第二，登录到某个知名门户网站，例如 http://www.yahoo.com，根据该网站提供的分类目录和相关链接， “冲逐步浪”浏览，寻找自己感兴趣的东西；第三，登录到某个搜索引擎网站，例如 http://e.pku.edu.cn，输入代表自己所关心信息的关键词或者短语，依据返回的相关信息列表、摘要和超链接引导，试探寻找自己需要的内容。这三种方式各有特点，各有自己最适合的应用场合。第一种方式的应用是最有针对性的，例如要了解北京大学计算机系网络与分布式系统实验室在做些什么工作，从某个渠道得知该实验室的网址为 http://net.pku.edu.cn，于是直接用它驱动浏览器就是最有效的方式。第二种方式的应用类似于读报，用户不一定有明确的目的，只是想看看网上有什么有意思的消息；当然这其中也可能是关心某种主题，例如体育比赛，家庭生活等等。第三种方式适用于用户大致上知道自己要关心的内容，例如“国有股减持” ，但不清楚哪里能够找到相关信息（即不知道哪些 URL ；搜索引擎能够为用户提供一个相关内容的网址能给出这样的信息）在这种场合，及其摘要的列表，由用户一个个试探看是否为自己需要的。现在的搜索引擎技术已经能做到在多数情况下满足用户的这种需要。CNNIC 的信息统计指出，目前搜索引擎已经成为继电子邮件之后人们用得最多的网上信息服务系统。同时，随着网上信息资源规模的增长，尤其是其内容总体和我们社会的演化发生着越来越密切的联系，研究网上存在的海量信息逐渐成为许多学科关注的一个方向。为此，不少研究人员也有采样搜集特定内容、一定数量网页的需要。本书以我们设计、实现并维护运行北大“天网”搜索引擎的经验，介绍大规模搜索引擎的工作原理和实现技术。我们要向读者揭示，为什么向搜索引擎输入一个关键词或者短语，就能够在秒钟内得到那么多相关的文档及其摘要，而点击其中的链接就能够被引导到文档的全文，且其中相当一部分可能正是用户需要的。我们按照上、中、下三篇展开相关的内容。上篇讲搜索引擎的基本工作原理，要解决的是为什么搜索引擎能提供如此信息查找服务的问题，以及它在功能上有什么本质的局限性。这一篇的内容包括网页的搜集过程，网页信息的提取、组织方式和索引结构，查询提交和响应的过程以及结果产生，等 i 等。这其中，虽然我们假定读者熟悉 URL，HTML，HTTP，CGI，MIME 等基本概念，但在上下文中也给予了必要的介绍，力图保持行文的流畅性。这一部分内容对于需要构建小规模搜索引擎的研究人员会有直接的参考价值。中篇讨论和大规模实用搜索引擎有关的技术问题。所谓大规模在这里指至少维护超过 1 千万的网页信息，提供相关的查询服务。所涉及的内容包括并行分布处理技术的应用，数据局部性的开发，缓存技术的应用，以及搜集的网页在提供服务之前的预处理问题和高效倒排文件的建立技术等等。这一部分的讨论有比较强的计算机系统结构的风格，我们向读者展示计算机系统结构课程中的那些概念是如何生动地体现在一个实际应用系统中的。这一部分的内容对构建大规模数字图书馆的技术人员也应该有帮助。下篇介绍挑战性更强一些的内容。一般地讲，前面所述可以称为是“通用搜索引擎”，为最广泛的人群提供信息查询服务是它的基本宗旨。这意味着它的应用模式必须尽量简单，即关键词或查询短语的提交和匹配响应。尽管这已经可以解决许多问题了，但对有些重要的信息需求依然显得力不从心。例如，一个人可能会关心最近半年来网上出现了哪些关于他（她）的信息，一个企业可能要关心它做了一次大规模促销活动后一个月内网上有什么反响，一个政府机构可能会关心在一项政策法规颁布后的网上舆论。面向主题和个性化的信息查询服务就是我们试图描述的一种基本途径。这一部分内容更多的和网上中文信息处理技术有关。更准确地讲，我们要介绍网络与并行分布处理技术与中文处理技术的结合，从而实现大规模、高性能、高质量、有针对性地网上信息查询服务。这一部分内容反过来可能对从事中文信息处理的研究人员有启发作用。本书的内容是集体智慧的结晶，主要概括了北大计算机系网络与分布式系统实验室自 1996 年以来的研究成果。其中许多段落直接来自同学的博士和硕士论文，他们是雷鸣、赵江华、冯是聪、单松巍、谢正茂、彭波、张志刚、龚笔宏、孟涛、昝红英，等等。署名作者的主要工作是将这些内容系统化，使其表述的风格统一。我们特别感谢陈葆珏教授，是她在北京大学计算机系开创了搜索引擎这一研究方向，从而使我们能在其后发扬光大，还要感谢刘建国和王建勇，是他们分别带领攻关队伍，实现了天网 1.0 和天网 2.0 版本。感谢黄蕊为本书进行的文字校对。最后，我们感谢国家“九五”攻关计划，“973”计划和“985”计划的支持，是它们的不断支持使我们得以将天网不断推上新的台阶， “让天网和中国网上信息资源规模同步成长” 实现的理想。作者 2004 年 5 月于北大燕园 ii 目录前言第一章引论................................................................................................................. 1 第一节搜索引擎的概念 ................................................................................................ 2 第二节搜索引擎的发展历史 ........................................................................................ 3 第三节一些著名的搜索引擎 ........................................................................................ 7 上篇 WEB搜索引擎基本原理和技术 .................................................................... 16 第二章 WEB搜索引擎工作原理和体系结构 .......................................................... 17 第一节基本要求.......................................................................................................... 17 第二节网页搜集.......................................................................................................... 18 第三节预处理.............................................................................................................. 20 第四节查询服务.......................................................................................................... 22 第五节体系结构.......................................................................................................... 25 第三章 WEB信息的搜集.......................................................................................... 29 第一节引言.................................................................................................................. 29 一、超文本传输协议.............................................................................................. 29 二、一个小型搜索引擎系统.................................................................................. 31 第二节网页搜集.......................................................................................................... 33 一、定义URL类和Page类...................................................................................... 34 二、与服务器建立连接.......................................................................................... 39 三、发送请求和接收数据...................................................................................... 41 四、网页信息存储的天网格式.............................................................................. 42 第三节多道搜集程序并行工作 .................................................................................. 45 一、多线程并发工作.............................................................................................. 46 二、控制对一个站点并发搜集线程的数目 .......................................................... 47 第四节如何避免网页的重复搜集 .............................................................................. 47 一、记录未访问、已访问URL和网页内容摘要信息 .......................................... 47 二、域名与IP的对应问题 ...................................................................................... 48 第五节如何首先搜集重要的网页 .............................................................................. 49 第六节搜集信息的类型 .............................................................................................. 52 第七节本章小结.......................................................................................................... 54 iii 第四章对搜集信息的预处理 ................................................................................... 55 第一节信息预处理的系统结构 .................................................................................. 55 第二节索引网页库 ...................................................................................................... 56 第三节中文自动分词 .................................................................................................. 58 第四节分析网页和建立倒排文件 .............................................................................. 64 第五节本章小结.......................................................................................................... 66 第五章信息查询服务 ............................................................................................... 67 第一节查询服务的系统结构 ...................................................................................... 67 第二节检索的定义 ...................................................................................................... 68 第三节查询服务的实现 .............................................................................................. 69 一、结果集合的形成.............................................................................................. 69 二、查询结果显示 ................................................................................................. 70 第四节本章小结.......................................................................................................... 72 中篇对质量和性能的追求 ..................................................................................... 73 第六章可扩展搜集子系统 ....................................................................................... 75 第一节天网系统概述和集中式搜集系统结构........................................................... 75 一、天网系统结构 ................................................................................................. 75 二、集中式搜集系统.............................................................................................. 76 第二节利用并行处理技术高效搜集网页的一种方案............................................... 82 一、节点间URL的划分策略.................................................................................. 83 二、关于性能的讨论.............................................................................................. 86 三、性能测试和评价.............................................................................................. 88 四、系统的动态可配置性设计.............................................................................. 91 第三节本章小结.......................................................................................................... 93 第七章网页净化与消重 ........................................................................................... 95 第一节网页净化与元数据提取 .................................................................................. 95 一、引言 ................................................................................................................. 95 二、 DocView模型 .................................................................................................. 98 三、网页的表示 ..................................................................................................... 99 四、提取DocView模型要素的方法..................................................................... 103 五、模型应用及实验研究.................................................................................... 108 第二节网页消重算法 ................................................................................................ 112 一、消重算法 ....................................................................................................... 112 iv 二、算法评测 ....................................................................................................... 115 第八章高性能检索子系统 ..................................................................................... 120 第一节检索系统基本技术 ........................................................................................ 121 一、系统设计与结构............................................................................................ 121 二、索引创建 ....................................................................................................... 124 三、检索过程 ....................................................................................................... 126 第二节倒排文件性能模型 ........................................................................................ 127 一、引言 ............................................................................................................... 128 二、倒排文件的概念............................................................................................ 129 三、倒排文件的一种性能模型............................................................................ 131 四、结合计算机性能指标的考虑........................................................................ 136 第三节混合索引技术 ................................................................................................ 138 一、引言 ............................................................................................................... 138 二、混合索引原理 ............................................................................................... 139 三、混合索引实现 ............................................................................................... 141 第四节倒排文件缓存机制 ........................................................................................ 144 一、引言 ............................................................................................................... 144 二、倒排文件缓存 ............................................................................................... 145 三、负载特性 ....................................................................................................... 147 四、缓存策略的选择............................................................................................ 149 第五节本章小结........................................................................................................ 149 第九章用户行为的特征及缓存的应用 ................................................................. 151 第一节用户查询与点击日志 .................................................................................... 152 第二节用户行为特征的统计分析 ............................................................................ 154 一、用户查询词的分布情况................................................................................ 154 二、雷同查询词的衰减统计................................................................................ 155 三、相邻N项查询词的偏差分析......................................................................... 156 四、用户在输出结果中的翻页情况统计 ............................................................ 158 五、用户点击URL的分布情况............................................................................ 159 六、考虑与不考虑查询项时点击URL分布的对比分析 .................................... 160 七、查询过程的自相似性.................................................................................... 161 第三节查询缓存的使用 ............................................................................................ 164 一、基于用户行为的启示.................................................................................... 164 二、缓存替换策略研究........................................................................................ 165 v 第四节用户行为与WEB信息的分布特征................................................................. 167 一、基本术语 ....................................................................................................... 167 二、海量Web信息的特征分析............"

You need to upgrade your Flash Player , or try to enable javascript in order see this document properly.