搜索引擎的工作原

1.SE工作原理概述

    大家应该都有在自己的电脑的硬盘上查找某个文件的经历吧。比如你在C盘查找“my.txt"这样一个文件，可能需要4分钟时间，
那么我们知道，如果搜索引擎也是用这样慢的响应速度的话，它会被用户淘汰的。搜索引擎，每天要响应几亿次用户的搜索请求，每天=24小时约=于10万秒.换句话说每秒要响应上万次左右用户的搜索请求，如果它不能在1秒之内完成1万次响应，则属于失败。

    根据我们的经验，如果搜索引擎，不能把搜索结果事先储存起来，而是象我们一样，每次都从数据库里查找的话，那么你也太小瞧这些SE发明人了。其实我们很容易知道，也经过GG官方资料证实，对于所有的词，GG都已经建立了索引。所谓的索引，就相当于一本字典，通过索引，我们可以快速定位到用户输入的查询的词。这样，SE可以在非常短的时间内根据相关性的算法，把搜索结果的前1000项结果返回给用户。当然，如果用户输入的不止是一个词，它有可能输入一句话或者一个词组。则GG自然有一套分词方法，将输入的一句话或者一个词组分解成一个一个的词。然后对于每一个词，进行相关性的运算，最后将最符合相关性的前 1000项结果返回。

    刚才我们讲了第1部分：SE工作原理概述 ，下面我们讲一下蜘蛛的爬行过程。

2.蜘蛛的爬行过程

    无论是哪一个搜索引擎，都有自己的“蜘蛛”，当然名字可能不叫蜘蛛，但其作用都是一样的，尽可能多的将网络上的网页建立快照。据保守估计，GG至少收录了 200亿个页面，我估计可能达到近千亿个页面。我们按照每个页面50K字节算，则这200亿个页面=1000T字节。如果用硬盘来装，按硬盘容量是 100G来算的话，则需要1万只硬盘阵列才能装下这些快照。那么对于这样海量的数据，如果假如下载一个网页需要一秒钟，下载这 200 亿个网页则需要 634 年。可是我们知道，SE当然不会这么笨。用单线程来下载。因此，一个商业的网络爬虫需要有成千上万个服务器，并且由快速网络连接起来。如何建立这样复杂的网络系统，如何协调这些服务器的任务，就是网络设计和程序设计的艺术了。

    当蜘蛛在下载页面的时候，并不是简单的将页面拍成快照就完成工作了。期间它还有一系列复杂的算法。比如，分析一下网页源代码中的超级链接，将符合格式的超级链接的关键字的相关性增加。对于它认为是作弊的链接，则可能会减分。如果判断某个超链违反了它的规定，一旦触发条件，刚有可能将其网址列入黑名单。总而言之，蜘蛛的很多工作我们无法猜测，也无法得到证实，我们只需要知道它在爬行过程中，同时进行大量的计算就可以了。

3.SE的索引原理

    刚才我们讲了网络蜘蛛的爬行过程  下面再讲讲索引：

    建立一个搜索引擎大致需要做这样几件事：自动下载尽可能多的网页；建立快速有效的索引；根据相关性对网页进行公平准确的排序。世界上不可能有比二进制更简单的计数方法了，也不可能有比布尔运算更简单的运算了。尽管今天每个搜索引擎都宣称自己如何聪明、多么智能化，其实从根本上讲都没有逃出布尔运算的框框。
    现在我们看看文献检索和布尔运算的关系。对于一个用户输入的关键词，搜索引擎要判断每篇文献是否含有这个关键词，如果一篇文献含有它，我们相应地给这篇文献一个逻辑值 -- 真（TRUE,或 1），否则，给一个逻辑值 -- 假（FALSE, 或0）。比如我们要找有关原子能应用的文献，但并不想知道如何造原子弹。我们可以这样写一个查询语句“原子能 AND 应用 AND (NOT 原子弹)”，表示符合要求的文献必须同时满足三个条件：
- 包含原子能
- 包含应用
- 不包含原子弹

    一篇文献对于上面每一个条件，都有一个 True 或者 False 的答案，根据上述真值表就能算出每篇文献是否是要找的。早期的文献检索查询系统大多基于数据库，严格要求查询语句符合布尔运算。今天的搜索引擎相比之下要聪明的多，它自动把用户的查询语句转换成布尔运算的算式。当然在查询时，不能将每篇文献扫描一遍，来看看它是否满足上面三个条件，因此需要建立一个索引。

    由于时间有限，有些内容我已经事先准备好了。我们知道，GG收录的所有的网页都有一个编号。最简单索引的结构是用一个很长的二进制数表示一个关键字是否出现在每篇文献中。有多少篇文献，就有多少位数，每一位对应一篇文献，1 代表相应的文献有这个关键字，0 代表没有。比如关键字“原子能”对应的二进制数是0100100001100001...，表示第二、第五、第九、第十、第十六篇文献包含着个关键字。注意，这个二进制数非常之长。同样，我们假定“应用”对应的二进制数是 0010100110000001...。那么要找到同时包含“原子能”和“应用”的文献时，只要将这两个二进制数进行布尔运算 AND。根据上面的真值表，我们知道运算结果是0000100000000001...。表示第五篇，第十六篇文献满足要求。

    由于每个网页的编号都是非常大。因为GG收录了几百个页面。所以对于每个关键词所对应的网页编号来说，它只需要记录包含这个关键词的网页编号即可。对于互联网的搜索引擎来讲，每一个网页就是一个文献。互联网的网页数量是巨大的，网络中所用的词也非常非常多。因此这个索引是巨大的，在万亿字节这个量级。现在的搜索引擎对所有的词都有索引，而不是象以前一样，只有重要的词才有索引。为了网页排名方便，索引中还需存有大量附加信息，诸如每个词出现的位置、次数等等。因此，整个索引就变得非常之大，以至于不可能用一台计算机存下。大家普遍的做法就是根据网页的序号将索引分成很多份（Shards)，分别存储在不同的服务器中。每当接受一个查询时，这个查询就被分送到许许多多服务器中，这些服务器同时并行处理用户请求，并把结果送到主服务器进行合并处理，最后将结果返回给用户。我发现我讲的你们都知道了啊。

4.分词的计算方法

    刚才讲了 3.如何编制索引 下面讲讲 4.分词的计算方法  对于用户输入的查询。对于中日韩等语言，首先需要进行分词。例如把句子 “中国航天官员应邀到美国与太空总署官员开会。” 分成一串词：
中国 / 航天 / 官员 / 应邀 / 到 / 美国 / 与 / 太空 / 总署 / 官员 / 开会。

    如果是你来设计，你会怎么分？你会怎么设计分词算法？搜标吧你来说说。是不是根据主谓宾啊最容易想到的，也是最简单的分词办法就是查字典。这种方法最早是由北京航天航空大学的梁南元教授提出的。据说Google使用统计方法分词，而百度有自己的巨大词库。

    用 “查字典” 法，其实就是我们把一个句子从左向右扫描一遍，遇到字典里有的词就标识出来，遇到复合词（比如 “上海大学”）就找最长的词匹配，遇到不认识的字串就分割成单字词，于是简单的分词就完成了。这种简单的分词方法完全能处理上面例子中的句子。

    八十年代，哈工大的王晓龙博士把它理论化，发展成最少词数的分词理论，即一句话应该分成数量最少的词串。这种方法一个明显的不足是当遇到有二义性（有双重理解意思）的分割时就无能为力了。比如，对短语 “发展中国家” 正确的分割是“发展-中-国家”，而从左向右查字典的办法会将它分割成“发展-中国-家”，显然是错了。

    我们要保证分出来的词最符合用户的需求，并且最后算法的结果只能存在一种分词方法。另外，并非所有的最长匹配都一定是正确的。比如“上海大学城书店”的正确分词应该是 “上海-大学城-书店，” 而不是 “上海大学-城-书店”。

    九十年代以前，海内外不少学者试图用一些文法规则来解决分词的二义性问题，都不是很成功。90年前后，清华大学的郭进博士用统计语言模型成功解决分词二义性问题，将汉语分词的错误率降低了一个数量级。

    利用统计语言模型分词的方法，可以用几个数学公式简单概括如下：
    我们假定一个句子S可以有几种分词方法，为了简单起见我们假定有以下三种：
A1, A2, A3, ..., Ak,
B1, B2, B3, ..., Bm
C1, C2, C3, ..., Cn

    当然不能保证100%的正确。但只要保证绝大多数正确即可。中文词不能用公式去做,这个是肯定的。呵呵。。错误是允许的，但是要能修正错误。即使是让人来分，也不能保证100%的正确呢。

    其中，A1, A2, B1, B2, C1, C2 等等都是汉语的词。那么最好的一种分词方法应该保证分完词后这个句子出现的概率最大。也就是说如果 A1,A2,..., Ak 是最好的分法，那么 （P 表示概率）：
P (A1, A2, A3, ..., Ak） 〉 P (B1, B2, B3, ..., Bm), 并且
P (A1, A2, A3, ..., Ak） 〉 P(C1, C2, C3, ..., Cn)

    因此，只要我们利用上回提到的统计语言模型计算出每种分词后句子出现的概率，并找出其中概率最大的，我们就能够找到最好的分词方法。上面就是搜索引擎采用的方法。它是基于大量的统计数据来进行分词的。不错，大家没必要搞的太细，只要理解思路即可。

5.一个完整的搜索引擎响应过程范例

    当用户输入一个查询时，搜索引擎将输入的分成一个一个的词，然后用Bool运算，将最符合相关性的网页编号返回给用户。那么对于最简单的情况，比如用户只输入一个词，搜索引擎是根据什么决定排名的呢？大家考虑一下。

    对于给定一个查询，有关网页综合排名大致由相关性和网页排名乘积决定。这是GG官方的说法。但是，很明显，GG不可能把所有的细节都透露给你的。现在的搜索引擎对 TF/IDF 进行了不少细微的优化，使得相关性的度量更加准确了。当然，对有兴趣写一个搜索引擎的爱好者来讲，使用 TF/IDF 就足够了。 如果我们结合上网页排名(Page Rank)，那么给定一个查询，有关网页综合排名大致由相关性和网页排名乘积决定。我认为相关性=网页内部优化+网页外部高质量外接，其中内部优化只占了 10%的权重不到。如果是竞争激烈的词。

6.关于百度

    百度和GG，以及所有的搜索引擎的算法都雷同。经过这么多年的淘汰，能生存下来的搜索引擎，在算法上都大同小异。这些没有官方根据，只是我的猜测。今天的交流内容主要是这些。下面大家可以随便讨论。