这就是搜索引擎 -- 读书笔记

sowang

（作者：天才白痴梦 来源：http://www.cnblogs.com/BaiYiShaoNian/p/4527388.html）


相信搜索引擎对于每一个爱好算法甚至爱好技术的IT人员都具有强烈的好奇心吧，因为搜索引擎在互联网中的地位实在是不可撼动。想象如果互联网没有了搜索引擎，那么我们平常技术上出现瓶颈了怎么办？甚至连普通的生活都离不开搜索，大学生的你订餐了吗？

搜索引擎已经发展为每个人上网都离不开的重要工具，其技术发展历程是怎样的呢？其基本目标是什么？核心技术问题又是什么呢？在接下来的一系列博文中，我会根据读书和自己的总结用平乏的语言来表达出来，希望对朋友们有所帮助。另外，博友们如果有好的相关资源，也感谢留言。

今天，我给大家讲解一下搜索引擎及其技术架构的基础知识，让我们对搜索引擎有一个大致的了解。

商业搜索引擎公司的发展

在信息量快速增长的情况下，如何能够找到满足用户需求的网页内容就日益成为越来越重要的问题。信息增长速度越快，用户需求越迫切，相应的搜索结果就越要准确。大的搜索引擎公司就是在这个用户需求背景下，从建立到逐步壮大，乃至发展到今天搜索引擎成为最重要的互联网的应用。

早期时候，随着互联网的进一步的快速发展，信息的爆炸性增长，已有的搜索引擎服务
提供商所提供的搜索服务质量并无大的改善。Google于1998年成立，以PageRank链接分析等新技术大幅度提高了搜索质量，之后高速发展并抢占了绝大多数的搜索引擎市场，成为目前最重要的互联网之一。想想为什么搜索引擎公司这么看重搜索技术？就拿大学生订餐这一事情来说，够实际吧，如果你订餐时查询到的前3页搜索结果都是已经售完了的饭菜品，那么此时饥饿的你感受如何？相信你连揍死店家的冲动都有。在另外一家外卖店的首页上，搜索第一条就是很新鲜的菜品，你会选择哪一家外卖店呢？

搜索引擎技术发展史

从搜索引擎所采取的技术来说，可以将搜索引擎技术的发展划分为4个阶段：分类目录、文本检索、链接分析和用户中心。

史前时代：分类目录的一代

这个时代可以称为“导航时代”，Yahoo和国内hao123是这个时代的代表。通过人工收集整理，把属于各个类别的高质量网站或者网页分门别类罗列，用户可以根据分级目录来查找高质量的网站。这种方式是纯人工、最原始的方式，并未采取什么高深的技术手段。

第一代：文本检索的一代

文本检索的一代采用经典的信息检索模型，比如布尔模型、向量空间模型或者概率模型，来计算用户查询关键词和网页文本内容的相关程度。网页之间有丰富的链接关系，而这一代搜索引擎并未使用这些信息。早期的很多搜索引擎比如AltaVista、Excite等大都采取这种模式。

第二代：链接分析的一代

这一代的搜索引擎充分利用了网页之间的链接关系，并深入挖掘和利用了网页链接所代表的含义。通常而言，网页链接代表了一种推荐关系，所以通过链接分析可以在海量内容中找出重要的网页。这种重要性本质上是对网页流行程度的一种衡量，因为被推荐次数多的网页其实代表了其具有流行性。搜索引擎通过结合网页流行性和内容相似性来改善搜索质量。

我们都知道Google率先提出并使用PageRank链接分析技术，并大获成功，这同时引起了学术界和其他商业搜索引擎的关注。后来学术界陆续提出了很多改进的链接分析算法。目前几乎所有的商业搜索引擎都采用了链接分析技术。

采用链接分析能够有效改善搜索结果质量，但是这种搜索引擎并未考虑用户的个性化要求，所以只要输入的查询请求相同，所有用户都会获得相同的搜索结果。另外，很多网站拥有者为了获得更高的搜索排名，针对链接分析算法提出了不少链接作弊方案，这样导致了搜索结果质量变差。

第三代：用户中心的一代

目前的搜索引擎大都可以归入第三代，即以理解用户需求为核心。不同用户即使输入同一个查询关键词，但其目的也有可能不一样。比如同样输入“苹果”作为查询词，一个追捧IPhone的时尚青年和一个果农的目的会有相当大的差距。而目前搜索引擎大部分致力于解决如下问题：如何能够理解用户发出的某个很短小的查询词背后包含的真正需求，所以这一代搜索引擎称之为以用户为中心的一代。

搜索引擎的技术架构

作为互联网应用中最具技术含量的应用之一，优秀的搜索引擎需要复杂的架构和算法，以此来支撑对海量数据的获取、存储、以及对用户查询的快速而准确的相应。



我们来看看这个搜索引擎的基础架构：

搜索引擎的信息源自于互联网的网页，通过网络爬虫将整个互联网的信息获取到本地，因为互联网页面中有相当大比例的内容是完全相同或者近似重复的，“网页去重”模块会对此做出检测，并去除重复内容。

在此之后，搜索引擎会对网页进行解析，抽取出网页主题内容，以及页面中包含的指向其他页面的链接。为了加快响应用户查询的速度，网页内容通过“倒排索引”这种高效查询数据结构来保存，而网页之间的链接关系也会予以保存。之所以要保存链接关系，是因为这种关系在网页相关性排序阶段是可利用的，通过“链接分析”可以判断页面的相对重要性，对于为用户提供准确的搜索结果帮助很大。

当搜索引擎接收到用户的查询词后，首先需要对查询词进行分析，希望能够结合查询词和用户信息来正确推到用户的真正搜索意图。在此之后，首先在缓存中查找，搜索引擎的缓存系统存储了不同的查询意图对应的搜索结果，如果能够在缓存系统找到满足用户需求的信息，则可以直接将搜索结果返回给用户，这样既省掉了重复计算对资源的消耗，又加快了响应速度；如果保存在缓存的信息无法满足用户需求，搜索引擎需要调用“网页排序”模块功能，根据用户的查询实时计算哪些网页是满足用户信息需求的，并排序输出作为搜索结果。而网页排序最重要的两个参考因素中，一个是内容相似性因素，即哪些网页是和用户查询密切相关的；另外一个是网页重要性因素，即哪些网页是质量较好或相对重要的，这点往往可以从链接分析的结果获得。结合以上两个考虑因素，就可以对网页进行排序，作为用户查询的搜索结果。

后话

如今，除了上述的子功能模块，搜索引擎的“反作弊”模块成为日益重要的功能。搜索引擎作为互联网用户的上网入口，对于网络流量的引导与分流至关重要，甚至可以说起了决定性作用。

因此，作为IT人员或者即将进入IT行业的童鞋们，我们都应该对搜索引擎有一些基本的认识。

sowang

这就是搜索引擎 -- 读书笔记二


网络爬虫基础

前言
通用搜索引擎的处理对象就是互联网网页，目前网页数量以百亿计，所以搜索引擎首先面临的问题就是：如何能够设计出高效的下载系统，以将如此海量的网页数据传送到本地，在本地形成互联网网页的镜像备份。


网络爬虫即起此作用，它是搜索引擎系统中很关键也很基础的构建。本次总结以及接下来的几次总结主要给大家简单介绍一下与网络爬虫相关的技术。说到爬虫，又想到了Python，所以首先了解一下爬虫的简单机制，这样对学习Python爬虫会有很大的帮助。

通用爬虫框架

如图所示



这是一个通用的爬虫框架流程。

首先从互联网页面中精心选择一部分网页，以这些网页的链接地址作为种子URL，将这些种子URL放入待抓取URL队列中，爬虫从待抓取URL队列依次读取，并将URL通过DNS解析，把链接地址转换成为网站服务器对应的IP地址。然后将其和网页相对路径名称交给网页下载器，网页下载器负责页面内容的下载。对于下载到本地的网页，一方面将其存储到页面库中，等待建立索引等后续处理；另一方面将下载网页的URL放入已抓取URL队列中，这个队列记载了爬虫系统已经下载过的网页URL，以避免网页的重复抓取。对于刚下载的网页，从中抽取出所包含的所有链接信息，并在已抓取URL队列中检查，如果发现链接还没有被抓取过，则将这个URL放入待抓取URL队列末尾，在之后的抓取调度中会下载这个URL对应的网页。这样一直进行下去，直到待抓取URL队列为空，这就代表着爬虫系统已将能够抓取的网页尽数抓完，此时完成了一轮完整的抓取过程。

对于爬虫来说，往往还需要进行网页去重以及网页反作弊（我的读书笔记一中的插图有提到反作弊），而且这是非常重要的一个过滤过程，在这里，我先不讲解反作弊，后面我会慢慢讲解给大家（因为此时的我也不懂反作弊的原理，还在进一步的学习中，所以抱歉）。

上述是一个通用爬虫的整体流程，读完想想还是蛮简单的，我们可以想象成为一只蜘蛛在蜘蛛网上爬行。这里我们再总结一下上述的那段话，宏观角度看爬虫抓取过程中与互联网网页之间的关系可以分为以下5种：

已下载网页集合：爬虫已经从互联网下载到本地进行索引的网页集合。

已过期网页集合：由于网页数量巨大，爬虫完整抓取一轮需要较长时间，在抓取过程中，很多已经下载的网页可能过期。之所以如此，是因为互联网网页处于不断的更新状态中，所以容易产生本地网页中内容和真实互联网里网页的内容不一致的情况。

待下载网页集合：即处于待抓取URL队列中的网页，这些网页即将被爬虫下载。

可知网页集合：这些网页还没有被爬虫下载，也没有出现在待抓取URL队列中，不过通过已经抓取的网页或者在待抓取URL队列中的网页，总是能够通过链接关系发现它们，稍晚时候会被爬虫抓取并索引。

不可知网页集合：有些网页对于爬虫来说是无法抓取到的，这部分网页构成了不可知网页集合。事实上，这部分的网页所占的比例还是很高的。

现在，我们已经知道了通用的爬虫框架，绝大多数爬虫系统遵循此流程，但是并非意味着所有爬虫都如此。大体而言，可以将爬虫划分为3中类型：

批量型爬虫：批量性爬虫有比较明确的抓取范围和目标，当爬虫达到这个设定的目标后，即停止抓取过程。至于具体目标可能各异，也许是设定抓取一定数量的网页即可，也许是设定抓取消耗的时间等。

增量型爬虫：这种爬虫系统会不断地抓取，对于抓取到的网页，要定期更新，因为互联网网页处于不断变化中，新增网页、网页被删除或者网页内容更改都很常见，而增量型爬虫需要及时反映这种情况和变化，所以要处于持续不断的抓取过程中。

垂直型爬虫：垂直型爬虫关注特定主题内容或者属于特定行业的网页，比如对于体育网站来说，就只需要从互联网页面里找到和体育相关的页面内容即可，其他行业的内容不在考虑范围里。

优秀爬虫的特性

爬虫系统和算法设计有一样的道理，如果设计的不是很好，那么不能算作一套优秀的爬虫系统，那么，优秀的爬虫系统具有什么样的特性呢？


高能性
互联网的网页数量庞大如海，所以爬虫的性能至关重要，这里的性能主要是指爬虫下载网页的抓取速度，常见的评价方式是以爬虫每秒能够下载的网页数量作为性能指标，单位时间能够下载的网页数量越多，爬虫的性能就越高。

还有一个方面也是凸显出高性能的特点，那就是爬虫系统得具有针对性。刚才我们有说到爬虫系统需要不断抓取，实时更新，那么如果我们用一套爬虫系统来抓取内容更新速度慢的网页和内容更新速度快的网页，是不是没有那么高效。此时，我们可以采用两套爬虫系统，一套爬虫系统针对更新较慢的网页集合，我们可以以天作为更新周期，另一套爬虫系统针对更新较快的网页集合，我们以秒作为更新周期。这样，明显比只用一套爬虫系统的情况下的性能高的多。


可扩展性
爬虫需要抓取的网页数量巨大，即使单个爬虫的性能很高，要将所有网页都下载到本地，仍然需要相当长的时间周期，为了能够尽可能的缩短抓取周期，爬虫系统应该有很好的可扩展性，即很容易通过增加抓取服务器和爬虫数量来达到目的。


健壮性
不光只有算法设计出现错误时会死循环，爬虫在访问各种类型的网站服务器时，也有可能会遇到很多种非正常状况，比如网页HTML编写不规范，被抓取服务器突然死机，甚至是爬虫陷阱等等。那么在这些情况下，健壮的爬虫系统应该是怎么样的呢？当爬虫程序死掉时，我们再次启动爬虫，能够恢复之前抓取的内容和数据结构，而不是每次都需要把所有工作完全从头做起。


友好性
爬虫的友好性包含两个方面的含义：一是保护网站的部分隐私性，另一方面就是尽量减少被抓取网站的网络负荷。

爬虫抓取的对象是各种类型的网站，对于网站拥有者来说，有些内容并不希望被所有人搜索到，所以需要设定协议来告知爬虫哪些内容是不允许抓取的。目前有两种流行的方法：爬虫禁抓协议和网页禁抓协议。

后话

爬虫技术是一种非常考验实战的技术，如果想要熟悉或了解搜索引擎，那么爬虫应该是必须要学会的。在不久的日子里，我会结合所学的Python基础知识来和大家一起学习Python爬虫。

零搜索引擎经验，零爬虫经验，初手有谦逊的态度和一颗热爱技术的心。

加油！

sowang

这就是搜索引擎 -- 读书笔记三


前言

考虑到上次的网络爬虫总结一文对基础的知识还没有介绍完整，所以今天花一点时间来补充上次的网络爬虫基础知识。这次给大家总结了两个方面的内容：暗网抓取和分布式爬虫。希望对阅读本文的博友们有所收获。

暗网抓取

物理学研究表明，在目前宇宙所有物质的总体质量中，星系等可见物质占其中的20%，不可探测的暗物质占据了总质量的80%。互联网中暗网可以与宇宙的暗物质相类比，而其所占网页的比例，更是远大于暗物质占宇宙质量的比例，大约百倍于目前的明网网页。

什么是暗网

所谓暗网，是指目前搜索引擎爬虫按照常规方式很难抓取到的互联网页面。如前所述，搜索引擎爬虫依赖页面中的链接关系发现新的页面，但是很多网站的内容是以数据库方式存储的，典型的例子是一些垂直领域网站，比如携程旅行网的机票数据，很难有显式链接指向数据库内的记录。所以，常规的爬虫无法索引这些数据内容，这是暗网的命名由来。


为了能够对暗网数据进行索引，需要研发与常规爬虫机制不同的系统，这类爬虫被称为暗网爬虫。暗网爬虫的目的是将暗网数据从数据库中挖掘出来，并将其加入搜索引擎的索引，这样用户在搜索时便可利用这些数据，增加信息覆盖程度。

目前大型搜索引擎服务提供商都将暗网挖掘作为重要研究方向，因为这直接关系到索引量的大小。在此领域的技术差异，将直接体现在搜索结果的全面性上，自然是竞争对手之间的必争之地。Google目前将其作为重点研发方向，而百度的“阿拉丁计划”目的也在于此。

垂直网站提供的搜索界面，往往需要人工选择或者填写内容，比如机票搜索需要选择出发地、到达地和日期，图书搜索需要支出书名或者作者。而暗网爬虫为了能够挖掘数据库的记录，必须模拟人的行为，填写内容并提交表单。对于暗网爬虫来说，其技术挑战有两点：一是查询组合太多，如果一一组合遍历，那么会给被访问网站造成太大压力，所以如何精心组合查询选项是个难点；第二点就是有的查询是文本框，比如图书搜索中需要输入书名，爬虫怎么样才能够填入合适的内容呢？

查询组合问题

对于暗网爬虫来说，刚才就说到不能简单暴力的查询，那么Google对此就提出了一种方案，称之为富含信息查询模板。那么我们首先解释查询模板。比如如我之类的大学生去智联招聘、前程无忧之类的找工作的网站寻找实习职位时，由于不愿意查看和自己不匹配的职位，这时我们需要用到职位搜索这一栏，完整的查询一般由3个不同的属性组成：职位类别、行业类别和工作地点。如果在向搜索引擎提交查询的时候，部分属性被赋予了值，而其他属性不赋值，则这几个赋值的属性一起构成了一个查询模板。

那么什么又是富含信息查询模板呢？对于某个固定的查询模板来说，如果给模板内每个属性都赋值，形成不同的查询组合，提交给垂直搜索引擎，观察所有返回页面的内容，如果相互之间内容差异较大，说明这个查询模板就是富含信息查询模板。

文本框填写问题

在爬虫运转起来之前，因为对目标网站一无所知，所以必须人工提供一些提示。通过人工观察网站进行定位，提供一个与网站内容相关的初始种子查询关键词表。爬虫根据初始种子词表，向垂直搜索引擎提交查询，并下载返回的结果页面。之后从返回结果页面里自动挖掘出相关的关键词，并形成一个新的查询列表，依次将新挖掘出的查询提交给搜索引擎。如此往复，直到无法下载到新的内容为止。

分布式爬虫

对于商业搜索引擎来说，面对海量待抓取网页，分布式爬虫架构是必须采用的技术。只有采取分布式架构，才有可能在较短时间内完成一轮抓取工作。常见的分布式架构有两种：主从式分布爬虫和对等式分布爬虫。

主从式分布爬虫：

不同的服务器承担不同的角色分工，其中有一台专门负责对其他服务器提供URL分发服务，其他机器则进行实际的网页下载。URL服务器维护待抓取URL队列，并从中获得待抓取网页的URL，分配给不同的抓取服务器，另外还要对抓取服务器之间的功过进行负载均衡，使得各个服务器承担的工作量大致相等，不至于出现忙的过忙、闲的过闲的情形。抓取服务器之间没有通信联系，每个抓取服务器只和URL服务器进行消息传递。

对等式分布爬虫：

服务器之间不存在分工差异，每台服务器承担相同的功能，各自负担一部分URL的抓取工作。

这种架构由于没有URL服务器存在，所以每台抓取服务器自己来判断某个URL是否应该由自己抓取，或者将这个URL传递给相应的服务器。至于判断方法，可以对网址的主域名进行哈希计算，之后去模，如果计算所得的值和抓取服务器编号匹配，则自己下载该网页，否则将该网址转发给对应编号的抓取服务器。

后话

网络爬虫确实有非常多的基础知识和实战技术，目前的我掌握的技能是非常的少，接下来肯定会努力学习爬虫实战技术的，往后也会向大家分享我学习的东西。不过，在搜索引擎这一part，索引对搜索是非常重要的，面对海量的网页内容，如何快速的找到包含用户查询关键词的网页，是一直都需要解决并优化的技术。所以接下来，我会在搜索引擎一系列总结中给大家讲解倒排索引这一方法。

sowang

这就是搜索引擎--读书笔记四--索引基础

搜索引擎索引基础

前几天我阅读了搜索引擎索引这一章，发现倒排索引这一方法确实很巧妙和迷人，它包含的原理和设计方法很独到。所以接下来，我想把我学习到的索引方面的知识给大家讲解一下，总共分为三篇：索引基础、索引建立和更新、索引查询。

我们首先认识倒排索引基本概念

文档：一般搜索引擎的处理对象是互联网网页，而文档这个概念要更宽泛些，代表以文本形式存在的存储对象，相比网页来说，涵盖了更多形式，比如Word、PDF、HTML、XML等不同格式的文件都可以称为文档。

文档集合：由若干文档构成的集合称为文档集合。

文档编号：在搜索引擎内部，会为文档集合中每一个文档赋予一个唯一的内部编号，以此编号来作为文档的唯一标识，这样方便内部处理。每个文档的内部编号称为文档编号。

单词编号：和文档编号类似，单词编号可以作为某个单词的唯一表征。

倒排索引：倒排索引是实现单词—文档矩阵的一种具体存储形式。通过倒排索引，可以通过单词快速获取包含这个单词的文档列表。倒排索引由两个部分组成：单词词典和倒排文件。

单词词典：搜索引起通常的索引单位是单词，单词词典是由文档集合中出现过的所有单词构成的字符串集合，单词词典内每条索引项记载单词本身的一些信息及指向倒排列表的指针（还记得链表吗？亲）。

倒排文件：所有单词的倒排列表往往顺序的存储在磁盘的某个文件里，这个文件即被称为倒排文件，倒排文件是存储倒排索引的物理文件。

倒排列表：倒排列表记载了出现过某个单词的所有文档的文档列表及单词在该文档中出现的位置信息，每条记录称为一个倒排项。根据倒排列表，就可以获知哪些文档包含某个单词。

倒排索引示意图如下所示



单词词典

单词词典是倒排索引中非常重要的组成部分，它是用来维护文档集合中所有单词的相关信息，同时用来记载某个单词对应的倒排列表在倒排文件中的位置信息。在支持搜索时，根据用户的查询词，去单词词典里查询，就能够获得相应的倒排列表。

对于一个规模很大的文档集合来说，可能包含了几十万甚至上百万的不同单词，快速定位某个单词直接决定搜索的响应速度，所以我们需要很高效的数据结构对单词词典进行构建和查找。常用的数据结构包含哈希加链表和树形词典结构。

哈希加链表

这种词典结构主要由两个部分组成，主体部分是哈希表，每个哈希表项保存一个指针，指针指向冲突链表，在冲突链表中，相同哈希值的单词形成链表结构。

在建立索引的过程中，词典结构也会相应地被构建出来。比如在解析一个新文档的时候，对于某个在文档中出现的单词W，首先利用哈希函数获取其哈希值，之后根据哈希值对应的哈希表项读取其中保存的指针，就找到了对应的冲突链表。如果冲突链表里已经存在这个单词，说明单词在之前解析的文档里已经就出现过，此时就不用加进去了。如果没有发现这个单词，说明该单词是首次碰到，则将其加入冲突链表中。通过这种方式，当文档集合内所有文档解析完成时，相应的词典结构也就建立起来了。



树形结构

B树是另一种高效查找结构，它是一颗多叉树。和哈希方式查找不同，需要字典项能够按照大小排序，而哈希方式无需数据满足此要求。B树形成了层级查找结构，中间节点用于指出一定顺序范围的词典项目存储在哪个子树中，起到根据词典项比较大小进行导航的作用，最底层的叶子节点存储单词的地址信息，根据这个地址就可以提取出单词字符串。

倒排列表

倒排列表用来记录有哪些文档包含了某个单词。一般在文档集合里会有很多文档包含了某个单词，每个文档会记录文档编号，单词在这个文档中出现的次数以及单词在文档中有哪些位置出现过等信息，这样与一个文档相关的信息称作倒排索引项，包含这个单词的一系列倒排索引项形成了列表结构，这就是某个单词对应的倒排列表。在文档集合中出现过的所有单词以及对应的倒排列表就组成了所谓的倒排索引。

然而在实际的搜索引擎系统中，并不存储倒排索引项中的实际文档编号，而是以文档编号差值（想想为什么要这样做呢？原因很简单，互联网中文档集合中的文档很多，对应的文档编号数字到最后也会很大，在倒排列表中不方便存储）。如下图所示，文档编号差值是倒排列表中相邻的两个倒排索引项文档编号的差值，一般在索引构建过程中，可以保证倒排列表中后面出现的文档编号大于之前出现的文档编号，所以文档编号差值总是大于0的整数。