读书笔记之搜索引擎—原理、技术与系统

搜索引擎 — 原理、技术与系统　　Search Engine: Principle, Technology and Systems

　　　 李晓明 闫宏飞 王继民 著　　by Li Xiaoming, Yan Hongfei and Wang Jimin

内容简介

“本书比较系统地介绍了互联网搜索引擎的工作原理、实现技术及其系统构建方案。全书分三篇共13章内容，从基本工作原理概述开始，到一个小型简单搜索引擎实现的具体细节，进而详细讨论了大规模分布式搜索引擎系统的设计要点及其关键技术；最后面向主题和个性化的Web信息服务，阐述了中文网页自动分类等技术及其应用。本书层次分明，由浅入深；既有深入的理论分析，也有大量的实验数据，具有学习和实用双重意义。本书可作为高等院校计算机科学与技术、信息管理与信息系统、电子商务等专业的研究生或高年级本科生的教学参考书和技术资料，对广大从事网络技术、Web站点的管理、数字图书馆、Web挖掘等研究和应用开发的科技人员也有很大的参考价值。”

---笔记---

这是2004年的一本书，比较系统的介绍了搜索引擎。读完后对其工作原理及相关技术术语有了了解，其中还有些代码可供学习。

Ch1　　引论

Ch2　　Web搜索引擎工作原理和体系结构

1. 三个子系统；即网页搜集，预处理和查询服务
2. 增量搜集

Ch3　　WEB信息的搜集　　

1. Microsoft Windows系统和UNIX系统在空行机制上有所区别：在Windows系统下，纯文本显示中的一个空行由一个回车符（carriage return，CR）和一个换行符组成（即C语言中的“\r\n”）；而在UNIX系统中一个空行仅由一个换行符组成。
2. 用标准IO库打开文件时有两种模式：文本（text）模式和二进制（binary）模式。在UNIX下这两种模式并没有区别，但在Windows下如果用文本模式打开，“\r\n”会被当成一个字符，而天网格式中的“length”域表示的是实际字节数，这就可能会引起错误。因此，在用标准IO读取文件时，为了兼容性最好用二进制模式打开，例如FILE *fp=fopen("filename","rb")。
3. 域名与IP的对应关系存在4种情况：一对一，一对多，多对一，多对多。一对一不会造成重复搜集，后三种情况都有可能造成重复搜集。要解决重复收集网页，就要找出那些指向同一物理位置URL的多个域名和IP。这是一个逐渐累积的过程。首先要累积到一定数量的域名和IP，比如100万个，然后把这些域名和IP对应的首页和首页链接出的最开始的几个页面抓取回来。如果比较结果一样，则应该归为一组。以后搜集的时候可以只选择其中的一个进行搜集。
4. 网页重要度的4个特征有：
   1) 网页的入度大，表明被其他网页引用的次数多；
   2) 某网页的父网页入度大；
   3) 网页的镜像度高，说明网页内容比较热门，从而显得重要；
   4) 网页的目录深度小，易于用户浏览到。  

Ch4　　对搜集信息的预处理

1. ISAM(索引顺序访问模式)
2. map容器采用的数据结构是“红黑树”，“红黑树”是一种较常用的查找效率较高的平衡二叉搜索树
3. 索引网页库算法/倒排文件索引

Ch5(上篇完)　　信息查询服务

1. 从接收到用户的请求到得到相关的网页，相应的运算的复杂度为O(NP(q))，即线性复杂度。

中篇　　对质量和性能的追求

1. 一个并行搜集子系统的详细设计方案; 
2. 去噪&识别相似网页; 
3. 查询子系统的性能模型和并行查询子系统; 
4. 查询局部性的发现与利用; 
5. 相关排序与质量评估。

Ch6　　可扩展搜集子系统

1. 天网主要包括搜集子系统、索引子系统、检索子系统三个组成部分 
2. 采用逻辑上二级映射的方法。首先用散列函数映射URL到一张逻辑表上，然后将这张表上的相应部分映射到各个节点。 
3. 天网主要包括搜集子系统、索引子系统、检索子系统三个组成部分。可扩展Web信息搜集子系统是天网核心部分之一，由N个独立自主的集中式系统和协调模块组合而成。本章先介绍天网的总体系统结构，再介绍集中式搜集系统的设计与实现，接着重点介绍可扩展搜集系统。然后通过模拟实验与实际环境的实验，分析说明可扩展分布式系统结构如何达到设计目标。

Ch7　　网页净化与消重

1. 网页净化和消重是大规模搜索引擎系统预处理环节的重要组成部分。所谓网页净化（noise reduction）就是识别和清除网页内的噪音内容（如广告、版权信息等），并提取网页的主题以及和主题相关的内容；消重(replicas or near-replicas detection)是指去除所搜集网页集合中主题内容重复的网页。建索引一般是在消重后的网页集上进行的，这样就可以保证用户在查询时不会出现大量内容重复的网页。 
2. 网页的表示是网页内容分析的基础，在网页内容分析过程中通常需要两个层次的表示，抽象表示和量化表示。
3. 网页消重算法。

Ch8　　高性能检索子系统

1. 搜索引擎检索系统的设计围绕检索效率和检索效果这两个指标展开。 
2. 系统采取了按站点划分网页数据的分布式方案，各个索引节点相互独立，索引创建过程在每个节点上独立进行。采用两趟的内存倒排创建算法，依次为每个小文档集倒排，最后执行多路归并，生成总的倒排文件。 
3. 对一个中文搜索引擎，索引创建不仅仅是一个高效的倒排算法，它还包含许多重要的方面：索引词的选择，中文分词、编码识别与转换、网页净化、强健的页面分析等。 
4. 在天网的分布式检索结构中，系统性能瓶颈最终在索引节点。通过实验发现，索引节点的检索效率瓶颈在于磁盘系统的性能，检索算法中对倒排文件中查询词对应的倒排项数据读取是检索效率优化的重点。首先采用的是系统级优化措施。注意到操作系统中I/O系统的实现特点，采用C函数库提供的带缓冲的文件访问接口效率最差，操作系统提供的底层文件访问接口read/write效率较好，而使用内存文件映射或者直接设备访问可避免多次的内存拷贝问题，从而大大提高I/O访问的效率。其次再通过对倒排文件的组织优化，通过减少每次访问倒排项数据的数量和访问次数来提高检索效率。天网系统中采用了三种基本技术：索引压缩、随机访问的索引组织和重要索引词单独索引。 
5. 吞吐率是指系统在单位时间（秒）里可以服务的最大用户查询数量。 
6. 探讨了倒排文件缓存优化设计中的性能指标选择问题、替换算法、页面大小和倒排文件组织方式等对缓存性能的影响，得到如下结论：1) 通过缓存变长的IO序列对象，采用GD-SIZE1替换算法，可以明显减少磁盘系统I/O访问的次数；2) 通过按页面对齐方式组织倒排文件，选取大的页面作为访问倒排文件的单位，可以使磁盘系统带宽利用率得到优化。

Ch9　　用户行为的特征及缓存的应用

1. 在查询中使用缓存的可行性：用户经常查询的词其实是很少的，把这些查询次数较高的词的查询结果放在缓存中，使用容量很小的缓存就能命中大部分的用户查询，这样就可以用较小的空间取得较大的缓存命中率。 
2. FIFO(First In First Out)、LRU(Least Recently Used)和LFU(Least Frequently Used)三种，其中LFU是带衰减的LFU，即每次发生替换时用某个衰减因子去衰减原来的查询次数并累加新的查询次数。
3. URL的入度、镜像度等参数与用户行为反馈后的相关度的方差分析对搜索引擎结果排序算法（ranking algorithm）的一些启示。

Ch10(中篇完)　　相关排序与系统质量评估

1. 传统上，人们将信息检索系统返回结果的排序称为“相关排序”（relevance ranking），隐含其中各条目的顺序反映结果和查询的相关程度。搜索引擎要给出的不是一个狭义的相关序，而是某种反映多种因素的综合统计优先序。检索质量评估的目标是对不同搜索引擎系统的检索质量评估其相对优劣次序。 
2. 传统IR的相关排序技术：这方面最经典、最有影响的工作是Gerald Salton等在30多年前提出的“向量空间模型”（Vector Space Model，VSM）[Salton and Lesk,1968, Salton,1971]。 
3. 在应用性很强的领域，理论基础粗糙的先天不足可能由精细的实现技术来弥补。 
4. 链接反映的是网页之间形成的“参考”、“引用”和“推荐”关系。可以合理的假设，若一篇网页被较多的其他网页链接，则它相对较被人关注，其内容应该是较重要、或者较有用。因此，可以认为一个网页的“入度”（指向它的网页的个数）是衡量它重要程度的一种有意义的指标。这和科技论文的情况类似，被引用较多的就是较好的文章。同时，人们注意到，网页的“出度”（从它连出的超链个数）对分析网上信息的状况也很有意义的，因此可以考虑同时用两个指标来衡量网页。这些想法即是斯坦福大学Google研究小组和IBM公司的Clever系统开发小组几乎在同一时间分别提出著名的PageRank技术和HITS技术的基础。 
5. 对于一个查询q，还需要考虑链接权值WL(p)和用户评价权值WU(q,p)。有两种方法来处理这三者之间的关系：
   1) 让WB(q,p)作为基准权值，而链接权值和用户评价权值作为比例系数：W(q, p)=WB(q, p)*WL(p)*WU(q, p);
   2) 每一种权值按照一定的比例重新构成新的权值：W(q, p)=Kwb*WB(q, p)+Kwl*WL(p)+Kwu*WU(q, p);
   其中，1=Kwb+Kwl+Kwu
   天网选择了第二种方法。在这种方法里，每种权值都起到了影响结果权值的作用，但是，它们的影响又都被限制到一定的范围内。

下篇　　面向主题和个性化的Web信息服务

1. 针对某一领域的小型主题搜索引擎、个性化智能搜索引擎的研究已成为下一代搜索引擎的两个研究热点: 中文网页分类技术/个性化信息服务/主题信息的搜集与应用。

Ch11　　中文网页自动分类技术

1. 本章首先系统地定量分析影响分类器性能的各种关键因素。根据实际的测试结果，并结合搜索引擎这一特定的应用环境，来寻找一种中文网页分类器的最佳设计方案：在具有较高分类质量的同时，还具有较高的分类效率。然后，根据这个方案实现了一个能够处理海量中文网页信息的分类器。最后，应用该分类器实现了天网搜索引擎中的目录导航服务。
2. 文档自动分类（Automatic Text Categorization，ATC）技术。所谓文档自动分类就是用计算机程序来确定指定文档和预先定义类别之间的隶属关系。主要可以分为三类：词匹配法/基于知识工程的方法/统计学习法。
3. 构建一个分类器的关键因素包括：预处理、训练集、特征选取算法、分类算法和截尾算法等。 
4. kNN算法本身简单有效，它是一种lazy-learning算法，分类器不需要使用训练集进行训练，训练时间复杂度为0。kNN分类的计算复杂度和训练集中的文档数目成正比，也就是说，如果训练集中文档总数为n，那么kNN的分类时间复杂度为O(n)。 
5. 决策树算法通过对训练数据的学习，总结出一般化的规则，然后再利用这些规则解决问题。 
6. 目前提供Web浏览导航的系统主要分为两大类。第一类是目录导航系统。它主要是通过具有专业知识的网页编辑人员人工地对网站进行精选，建立一个内容分类索引目录，向用户提供目录导航服务。用户可以沿着分类目录的层次结构，逐步进入自己感兴趣的主题，进而找到所需的信息。这类系统的优点是提供的相关信息比例很高，而且信息内容的权威性较高，网页信息和用户的相关性较大，但是覆盖的范围小，系统维护的网页数量有限。其典型代表是Yahoo!的目录系统。第二类是基于自动信息搜集和分析的搜索引擎系统（称为“自动式搜索引擎”）。它通过一个程序自动地在网上沿着超文档链递归地访问、搜集Web网页，分析页面的内容，生成索引和摘要，并向用户提供Web查询界面，根据用户的查询关键词在索引库中查找相关信息在网上的位置，最后将查询结果按照相似度排序后返回，帮助用户尽快地找到所需的信息。这类系统的优点是涵盖的网页数量巨大，但搜索的准确率相对比较低，其典型代表是Google。
7. 系统整体上可以分为两个部分：在线部分和离线部分。在线部分首先接受用户的查询条件，然后根据用户所处的网页目录自动地进行查询扩展，接着在预先分好类的网页库中检索，最后实时地返回查询结果。离线部分的核心部件为中文网页分类器，负责中文网页的自动分类。本文使用的中文网页分类器的工作原理如图11-3所示。分类器的整个工作周期可以分成训练过程和分类过程。在训练过程中，训练集实例经过中文分词和特征选取处理后被表示成向量形式。该特征向量用来描述类别模式，在分类过程中使用。校验集是训练集的一部分，通过应用相应的阈值策略来预先确定每个类别的截尾阈值。在分类过程中，一个待分类的中文网页经过中文分词并表示成向量后，应用分类算法同训练过程得到的类别模式逐一比较，得到候选类别列表，然后同训练过程中得到的每个类别的阈值相比较，保留大于阈值的类别，并作为该网页的分类结果。

Ch12　　搜索引擎个性化查询服务

1. 一般的搜索引擎是基于关键词匹配的方式进行检索的，由于这种方法缺乏对关键词语义的理解，检索结果对用户而言不够理想。主要表现在两个方面：① 检索结果中无关的网页过多。② 没有考虑不同用户的个性差异。 
2. 创建Web个性化服务系统的一般步骤为：（1）收集用户的各种信息，如注册信息，访问历史等；（2）分析用户数据，创建符合用户特性的访问模式；（3）结合用户特性，向用户提供符合其特殊需求的个性化服务。 
3. Web使用挖掘的基本方法包括：聚类、关联规则、序列模式、分类、依赖性建模、统计分析等。 
4. 目前已经出现了多个应用Web挖掘技术创建的个性化Web服务系统。这些系统应用的Web挖掘类型包括使用挖掘、内容挖掘和结构挖掘；收集数据的方式有三种：从客户端、代理或服务器方得到原始数据；最后提供的服务有两类：过滤服务和导航服务。

Ch13　　面向主题的信息搜集与应用

1. 消重工作分为两步：第一步是对每个时间片上搜集的网页进行消重（空间上消重），统计出每个时间片上的独立信息量；第二步再将所有时间片上消重后的网页合并在一起再进行一次消重（时间上消重），统计出整个时间区间内的独立信息量。 
2. 从进一步的工作看，可以有两个方面。一是在模型中引入优化指标，例如考虑为得到特定的统计数据最少需要花费的计算资源和时间。二是更深层次地考察这次得到的数据，以及选择其它主题进行类似实验，看能否得出有一定规律的结论，例如“一个预定事件网上舆论的高峰在该事件发生后X天左右出现”之类；这需要在样板空间的选择和搜集策略上做进一步的研究。

附录　　术语

1. 局部性原则（locality principle），是程序行为的一种性质。它包括：时间局部性和空间局部性。前者指的是，如果某数据刚才被访问，则它很可能在近期内还要被访问；后者指的是，如果某数据刚才被访问，则和它在位置上相邻的数据很可能将被访问。 
2. 链接分析（link analysis）: Web上的网页及其相互之间的链接可以看成一个巨大的有向图，链接分析指的是利用网页之间的链接信息来评判其重要性（或者相关性）的技术。常用的链接信息包含网页的出度、入度，锚文本内容等；常用的链接分析算法有：PageRank，HITS，SALSA，PHITS，Bayesian等。 
3. MD5（message digest 5）, 报文摘要，用于报文编码的一种算法。MD5算法在RFC1321中定义，其基本功能是将一个任意长的报文变换为一个128位的摘要，两个不同的报文对应的摘要相同的概率极小，两个摘要之间的相近程度和对应两个报文的相近程度没有任何关系。 
4. 缓存（cache），在计算机科学领域经常出现的一个概念，其基本含义是利用局部性原理实现的一种匹配两种不同速度的中间机制。它可以出现在CPU和RAM中间，也可以出现在应用系统的I/O操作与磁盘之间。在搜索引擎中，为缓解查询要求的高速度和磁盘访问低速的矛盾，常会在内存中设计各种缓存，包括查询缓存、点击缓存，以及倒排表缓存等。 
5. 向量空间模型（vector space model，VSM），按照共有词汇假设，一组文档有一个总词语集合Σ，一篇文档可以用一个向量表示，其元素是对应词语在该文档中出现情况的一种定量描述，一组文档就可以看成是一个向量空间中的若干元素，于是可以应用向量空间中距离的概念来考察两篇文档之间的相似程度等。 
6. 主题搜集（topic-specific/focused crawling），即面向主题的信息搜集系统，其主要任务是利用有限的网络带宽、存储容量和较少的时间，抓取尽可能多的与主题内容密切相关的网页。 
7. 最低频使用（least frequently used，LFU），缓存内容维护的一种数据替换策略，当缓存满，且有新的数据要进来时，它总是淘汰现有数据中在过去使用频率最低的数据。数据替换的粒度可以根据应用场合确定。 
8. 最近最少使用（least recently used，LRU)，缓存内容维护的一种数据替换策略，当缓存满，且有新的数据要进来时，它总是淘汰现有数据中在过去最长时间未被使用过的数据。

后记(全书完)

1. http://www.infomall.cn/