搜索引擎及其开发

ゝ一纸荒年。 2023-10-22 00:52 101阅读 0赞

一、分类

按照目的的不同，搜索引擎分了两种：通用搜索(业内称为大搜索)和垂直搜索。网页搜索是大搜索，新闻搜索、论坛搜索是垂直搜索，酷讯的生活搜索之类的都是垂直搜索。

二、组成

一般说，搜索引擎包括这几部分：下载（爬虫）子系统，数据预处理子系统，搜索服务，控制（及监控）部分。搜索引擎是一个比较新的行业，国内也掌握了核心的技术。所以，和做OA，做工作流，做核心层上的应用有些不同，系统无论是从规模还是性能上讲都有比较高的要求。

下载。互联网通过超链，每一个网页是一个点，然后点和点之间有关联，关联的注释就是链接文本，所有的链接组成了一个巨大的网。大搜索下载的任务就是把这些网的每一个点都保存到本地（当然这是说理论上，现在互联网的规模，恐怕google也无法把所有的东西都保存到本地）。这带来几个问题：1. 网页如何尽量不重复的下载。网络带宽资源是有限的，本地硬盘资源也是有限的，下载的时间也是有限制的，重复的下载系统受不了。2. 互联网是不断更新的，这种更新需要反映到本地硬盘上的数据。如何尽量及时的更新？

一个Url就是一个字符串，而且这个字符串比较长。给保存和比较都带来了麻烦。我们对Url做md5映射，把它映射成一个64位的整形值。现在大多用的是64位。Md5本来算出来时128位，一般是取前64位。Md5的重复率很低。我曾经做过70亿Url的实验，我尽量模拟Url的组成生成了70亿Url，然后取md5值，排重，没有发现一个重的；而且md5的散列非常好，他本身可以认为是一个哈希散列，但是分布的非常随机。我把70亿的结果值分散到多个文件里边，每个文件里边的ID的个数基本上是一样的。我们可以认为，每一个Url取了md5值以后，他的这个ID值是唯一的。它可以用来比较两个字符串是否相同。也称作信息指纹。是判断是否相同的重要的办法。

对ID值取模（mod）是一个非常重要的思想。依赖于md5值的散列性，你可以把大量的数据分成小堆，存到文件，各个小堆的数据是控制到可以放到内存中处理。这是查找、排重、以及后边建索引的基本的方法。它使得我们可以把大任务分解成可以并发解决。这样的并发系统是一个明显的木桶理论模型：决定于处理速度最慢的一个。但是，md5的散列性非常好，各个处理部分处理的数据在规模上相差不大，或者说基本上是一样的。比如上边所说的例子，70亿ID值。70亿\*8=56G，放到内存里边不太现实。可以把他们对200取模，放到文件，每个文件280M，然后对每一个文件进行处理。那就随你的便了。

下载分成Server端和Client端。Server端指定下载的种子，他把这些url发给Client端，client端把server端给的url下载下来以后，分析页面把分析出来的url发给server端。。。。如此循环。有了上边的介绍，判断是否下载就好说了。都是64位值得比较。最简单的办法，你可以利用平衡二叉树，这是一个非常方便的动态查找的办法。不过，数据量一大，64位值也会占用很多的内存。我们可以算一下。1亿\*8约等于800M，而且树节点左右指针也要占8个字节，平衡二叉树还有一个标记变量，这样算下来，放完1亿大约需要1.8G。不过他的查询速度可以忍受，而且是绝对的不重复，没有误差。假设我们可以探测到的Url是100亿网页，按照这种办法，一台机器按照放2亿计算，需要100/2=50台server端。这样的确是要不少的机器，当然还有其他的办法。需要仔细的去想。呵呵。

垂直搜索的下载和大搜索的下载是不一样的。垂直搜索针对一些特定的网站。以新闻为例：新闻下载会针对新闻源，比如新浪，china.com等新闻发布网站定时、定向抓取；寻找他们的新闻发布的规律，把那些网页下载下来。这就没有上边所说的大图的遍历和更新机制的问题了。难度不可同日而语。

不过，不要看了这些就认为下载很简单，这是一个与经验关系非常密切的活。上边说的都好说，但是，下载过程中碰到的问题可就多了。你需要解决大量的意想不到的事情，我在这里也不能多说，不过可以举几个例子：如果你把一个网站访问的太过频繁，重则把这个网站给弄瘫痪了（特别是小网站，大网站的抗打击能力还可以），轻则。。。让管理员注意到了太多的访问就把你的IP给封了。下载需要礼貌。毕竟是访问别人的网站。这是到别人家里做客啊！可不比自己家！还有作弊网页，大量的SEO作弊网页，下载的时候需要去掉一部分；还有，不是所有的网站都是可以在任何时候访问的，新浪首页下载不下来的时候你怎么办？得多想想后边如何处理。

下载完了的数据需要进行处理。抽取标题，正文，父链接，字连接，链接文本。这是后边的数据基础。所有这些以及后边的其他的部分，难度大多集中于数据量。

正文解析。把一个html中的正文解析出来，不是很轻松。这个一般有两种方法:1. 基于模板。这个用在新闻正文的解析上比较多。一个网站的新闻在一个时间段内往往有基本固定的格式，可以基本按照这个格式把不光是正文，各个值域，比如发布时间，作者等的统统解析出来。只是需要在网页结构改变的时候，人工做很多的模板。 2. **VIPS:****基于视觉的****Web****页面分页算法**。呵呵。简单讲来，就是人看一篇网页的时候，人觉得网页正文应该在什么地方，然后让程序去根据位置模拟人的视觉判断，把正文解析出来。说到这里多说两句，微软很有意思，VIPS以及后边要提到的相关性的BM25公式都是微软研究院提出来的，而且这两种办法在搜索引擎上用的都是很广泛，事实证明，这两个办法是非常有效的办法。但是，呵呵，搜索他还是没有干过google。不光这样，msn的livesearch在各个搜索结果质量排名的时候基本都是倒数的。真是奇了怪了。不知道微软工程院是怎么干的。呵呵。

排重。也叫网页指纹,这个针对于网页的正文。网页有大量的转载网页。他们的正文区别就是一个或者是几个字的区别，剩下的不同都是乱七八糟的广告，flash。如何才能判断是否重复？一般有两种：1. 关键字Top10 2. 文本向量的方法。 这些网上都有很多的讨论，也有人做了很多的教程。你在网上多搜一下，以后有时间我也可以总结一下。而且，这些我们认为重复的网页是否做索引？索引怎么放？是个问题。你可以看看各个大搜索引擎的相似网页功能。

PageRank，基于链接分析。最早是google的创始人提出来的。你可以看他们的论文<<The Anatomy of a Large-Scale Hypertextual Web Search Engine>>; 有意思的是，百度的创始人李彦宏在链接分析上也有专利，是否有点巧合？呵呵。不过，可以说对链接的分析开启了第二代搜索。第一代搜索是以雅虎的目录式，第二代以google为代表。第三代？我认为那是概念。还没有看到，还没有看到搜索的革命性变化。PageRank给出了一个静态的表示网页质量的方法，他认为，被链接的次数越多的网站，他的质量越好，重要程度越高。有点类似于越是明星，认识他的人也就越多一样。当然还有其他的办法分析链接。你可以找找看。 很多这样的论文，简直太多了，不过够用就好。挖地三千尺应该是google们干的事情。

互联网构成的这个巨大的图还有这样的特性，如果我们截取的是一块，假设类似一个圆，那么直径越大，理论上边际节点越多。 所谓的边际节点就是他的链接我们有，但是没有这些链接对应的网页。有点类似于谁的名言来着：知道的越多，不知道的也越多。随着互联规模的扩大，这种趋势也越来越明显，特别是我们只下载其中一部分网页的情况下。这种边际节点给理论上的PageRank计算带来了不小的问题：大量的边际节点的存在，让原始的PageRank计算难以发挥用，不过，很快就有人提出了新的PageRank算法。你可以看一下相应的论文。

快照。下载的时候，把网页down到本地来，然后，当一个Url对应的网页打不开的时候，你可以打开搜索引擎做上的快照，看看爬虫当时爬下来的网页的样子，不过一般都是把网页上乱七八糟的东西比如flash广告都去掉了---为了节省硬盘空间。

说到这里就需要说一下全局ID以及什么时候需要这样的ID值。每一个网页都有一个ID值，这个ID就是他的url的Md5值。如果我们的数据有 10亿，20亿，几十亿。。。。。把所有的数据都放到一台机器上肯定不可能。我们用上边提到的取模的办法，分散到各个机器上。什么时候需要这样的全局唯一ID值那？那就是你在机器间需要唯一标志的时候。这不是废话吗？我们慢慢讲。一般快照是不和索引数据放到一块的。 我们取快照的时候，其实是给定一个ID值，然后从另外的机器上找到这个值对应的东西显示给用户。如果，我说的是如果，我们的数据都是按照取模的办法分散开来，相应的数据放到了一台机器上，那就不需要全局唯一了，只要本台机器上唯一就可以了。不是吗？

倒排索引。所谓的倒排是相对于我们的平时的习惯来的。平时的习惯是看到文章的标题，正文，然后是文章的内容的词。倒排反了过来，他是这样的，关键词，位置，其他属性，文章。有点类似于，我们写信的时候，地址是从大到小，然后到人，美国人是从人开始直到他的国家。呵呵。这样的好处是什么那？文章的集合是一个无穷尽的集合，但是，关键词的集合是相对小的多的集合，是可以枚举的，是基本有上限的词的集合构成了无穷尽的文章集合。而且，同一个关键词可以存在于不很多的文章里边，这么做可以节省内存，也可以方便做针对关键词的文章间的横向分析；同时，用户输入的是关键词，需要的是结果是文章，这样就在用户和文章之间建立一个通道。现在的搜索都是基于关键词的，所谓的推送，还有用户习惯的分析都是基于关键词的，只不过比用户自己输入关键词做了一层包装，方便了一点。这就是我为什么上边说搜索上革命性的变化还没有看到的原因。如果说关键词搜索是搜索2.0,那些概念做的好的话充其量也就是2.01，比第三代还差的远。当然，也许是我知道的太少，如果您看到了这样的东西，不妨告诉我，我也非常想知道。我认为，第三代是基于内容的分析和理解上的。不过，这只是猜想。我还远没有达到大师的级别。

分词。基于关键词的检索有一个前提条件，那就是，把文章分成一个个关键词。分成怎样的关键词集合，标准是人来制定的。人在看完一篇文章以后，读懂了他的意思，然后把各个句子分开成一个个的词。当网页到了如此大规模的时候，用人工的方法断句分词当然是不现实的。用程序分词就需要告诉程序，怎样才算是一个词。有几种办法。我也知道的不是很多，没有对这个深入的研究过。不过都需要词典的支持，这个词典是人工生成的。基于词典的最大匹配办法很常用。还有一个方法是人工对一堆的文章进行断词，然后计算机统计一个词在另外一个词后边存在的概率。然后在处理新的文章的时候，他可以根据这个确定是否是把字符串这样分开。

关键词也是字符串，他们的比较我们一般还是用md5的办法，称之为WordID。整数的比较、存放比长度变化的字符串之间的比较自然是方便了很多。

如果搜索引擎只是返回包含这个关键词的文章集合，那不叫信息检索，那叫查询。就跟在数据库中写一个sql语句查询一样。呵呵。之所以叫做信息检索，就因为有了对结果的排序，也叫做相关性排序。一个关键词在一个文章中的比重是不同的，甚至是出现在不同的位置，标题，正文的各个位置，链接文本。。。。。。带来的效果都是不同的。也可以说这篇文章对因为关键词所得的分数是不一样的，然后根据这些给文章打分，根据分数把文章排序。上边提到的<<现代信息检索>>讲基础部分讲的很好，BM25公式提出的办法是现在用的最广泛的；当然都需要在实际当中针对自己的方法做出相应的改变。一般认为这和大规模数据的检索程序一起视为搜索引擎的核心技术。 任何的数据处理，检索办法都是为了后续的排序做准备的。没有相关性排序不能称之为搜索引擎。当其他的工程部分趋向于定式的时候，唯有分词和相关性排序需要加大后期的投入。

其实，仔细想想就可以发现，现在所有的技术都是基于统计的。没有真正意义上的基于内容的分析和理解。计算机还是一如既往的死板，直肠子，不会拐弯，还只会按照人设定的规则去做，还远没有做到像人一般的联想，自己设定智能意义的规则，我认为，对内容的理解是基于对事物之间的关系以及对它们之间的联想上的。现阶段的内存和硬盘简单的数组、矩阵关系显然难以达到这一点。他的发展应该是向着仿生的方向发展的，特别是人的脑袋，不是说人的脑袋全部开发可以存下美国最大的图书馆吗？呵呵。不过，一旦真正意义上的智能出现，他的发展当然是指数级别的。智能计算机的生产自己的下一代，我的天，那是迭代的。呵呵。这是随便说着玩的。您也就姑且当作一乐。

当然，在全面的解决办法临之前，并不是说我们就堵在这里就没有办法前进了。社区和知识库是现在的搜索引擎的非常好的补充。当大搜索，相关性排序大家做的差不多趋于一致的的时候，百度贴吧、百度知道的有利补充让百度搜索凸显了了和其他公司的大搜索的不同。你搜索的时候可以注意一下，你在百度上搜的东西那些是来自于贴吧和知道的。特别是那些与日常生活关系很大的信息，比如，在北京我到哪里买黄金（前两天跟媳妇去买结婚戒指了！），输入这个关键词“北京 买黄金”。。。。他的问题是人提出来的，人回答的，还有内部的答案筛选机制。大家的参与，一旦形成了规模效应，效果立马显现。就好像，百度搜什么搜的都很准，用户体验非常的好，久而久之形成了搜索的习惯。习惯一旦养成，想改变是一个困难的事情。呵呵。而且现在能做到输入一句话全句飘红的也仅此一家而已。大搜索雅虎中国在做，搜狐在做，QQ也在做。如果不能在这个方面把百度比下去的话，想把头把交椅抢过来是一个很困难的事情，其他的方面弄大家做到最后都差不多嘛！Google就跟天涯这样的社区合作，很漂亮的战略和战术，天涯内容发展好了，对google来讲，跟百度贴吧有的一拼。不过还有一个有潜力的，QQ。他的人气，是任何人都不能小觑的，而且本身又有钱。只是发力晚了4、5年。暂且不对现有的秩序造成大的冲击，过两年就不一定了。

建索引，检索，控制（监控），应该是算是一块的。他们的难度都在于数据量。

数据量的规模上去了，所有以前可能忽略的问题都会变成问题。

1. 7\*24小时服务。这包含两部分，一部分是软件的，一部分是硬件的。

软件部分。数据不停的来，不停的处理；搜索请求不停的来，服务程序不停的响应。一旦程序出现了什么问题，这个流水线的处理就出现了中断。我们需要知道，程序为什么出现了问题。任何的程序都不会是第一次运行就会天生可以稳定高效运行的。我需要实时知道的状态，他在干什么；它死了的时候我需要知道为什么玩完了。这些都需要日志的支持。而且还需要不同的日志记录到不同的文件里边，以便于后续的人工统计和分析。比如，查询日志。用户的查询日志是一个非常重要的资源，是可以用来进行后续分析的重要资源。而对于数据处理程序来讲，可以断点重启，就像flashget的断点重下一样，是非常方便和重要的。这些都有赖于不同的日志和断点环境的保存。

一般的c,c++程序容易出现的问题是内存泄露和内存的越界访问。

Linux的内存泄露问题可以通过一个开源工具valgrind来测试；windows下边的程序也有相应的头文件进行内存的判断（调用微软的API函数），你可以在网上查到。一个不断的流血（泄露内存）的程序是不能指望他长期运行的。内存很快就耗光了。内存分配、文件打开的成对编写程序（编写了分配，直接编写释放语句，然后把中间需要处理的内容在这两个语句之间插入）是非常难过管用的技巧。不过，即便这样，也需要非常注意借个非常容易出现内存不释放的地方。1. 循环的continue。2. 函数中间的返回return。本来后边有内存释放的，但是，让你的那两个语句给挡住了。呵呵。我也放过很多这样的错误。这种错误是一旦不注意就会犯的。特别是你的一个函数写的比较长的时候、一屏显示不开的时候（将函数小型化是非常重要的，但需要有一个度，过而不及！）。

越界访问一般出现在数组、下标的溢出这样的地方。前两天写下载程序的时候就犯了一个致命的错误，让我调了一下午才找到错误的原因。我在定义Url字符串的时候，认为他的长度不会超过2048，超过2048的很变态，也很少，不过让我碰到了一个11K的。呵呵。一个strcpy让我的栈信息都被冲的无影无踪了。这才是最麻烦的，如果是一般的数组溢出，gdb可以直接定位到哪一行。而这样的错误，你是很难找到的错误点的。废了半天力气我才把错误定位到这一行上。当你发现程序错误错的很奇怪的时候，你会嘀咕，不应该有这样的错误的发生，不可能啊！你不妨考虑一下是否内存被冲了，变量的内容变了或者是运行到不该运行的地方（前者居多），然后程序出错了。那样的话，gdb或者VC给出定位是不对的。他应该是发生在其他的地方，而且严重的是这样的错误很难找。所以，在内存拷贝这样的操作的时候，不要想当然认为如何就如何。比如，strcpy，还是用strncpy吧。其他的错误总是好找，内存错误会让你中头彩。

Gdb给出的错误文件是core.\*\*\*\*\*,如果让VC给出调试文件，需要做点设置。你可以看看我以前转载的那篇[VC下发布的Release版程序的异常捕捉][VC_Release]。

硬件部分。机器不停的提供服务，但是，不能指望他们可以忙一辈子。他们是有寿命的。比如说，损耗的最快的东西是什么？硬盘。搜索引擎一般采用1.4万转的硬盘。不停的读写对他们的寿命造成了很大的损害。呵呵。一般搜索引擎公司买硬盘都是上百块的买。当然，硬件7\*24小时的服务需要软件的支持。比如说，搜索程序在写的时候就需要考虑到硬件当机的情况。当这台服务机器不能正常工作，监控程序需要及时报告维护人员，让他们及时维修；还有重要的一点是，或者是常用的做法是，一份数据，两个到三个相同的镜像。平时是几个镜像同时提供服务，紧急时刻，如果一个镜像不能联系，那么把流量导入另外的镜像。一般两台机器同时出现错误的概率是很低的。出现错误也要快修，别忘了我们的木桶理论。

有一个特殊的东西，叫做GFS。就是google的分布式文件系统。为什么把它单独的提出来，因为他这两年实在是太火了。搜索引擎需要的数据实在是太大了，需要大量的硬盘来存储；他对数据处理的要求又很高，需要分布式的并行的处理。Google利用一批刀锋式PC，成功用低成本解决了这个问题。所说的低成本是每存储1G数据需要的花费的资金，以及能处理如此规模的用户请求的基础上每处理一个用户请求花费的资金。呵呵。说的有点绕口。从外边看来，就是人家把一堆普通PC机，一堆硬盘变成了一个巨大的机器。而且各个节点非常非常的便宜。比廉价磁盘阵列都便宜，也好用（当然是软件的支持）。单说一点，这个机器的内存和硬盘是？差不多是各个节点的内存以及相应硬盘的和。诱人吧。不过，没有钱往里边砸，还是不要做这样的系统。他的论文是公开的，看了之后谁都有点。。。那个蠢蠢欲动。。。呵呵。。。因为，看起来，不是很难嘛！ 不过，你是否发现，论文上所说的东西都是原理，一个错误报告都没有。文件系统是一个底层的服务，没有千锤百炼谁敢把自己的系统放到一个不稳定的文件系统上运行？与原理相比，我更感兴趣的是，按照这种思路进行软件编写，他们在运行的过程中碰到的意外问题是什么？怎么解决的。而且，谁又有这么多的财力向redhat公司定制自己的单机文件系统。呵呵。这样想来，这样的一个程序需要多长的时间去完善？一般的真是耗不起。不过，现在有个开源的东西,Nutch。有时间需要好好看看。

2. 多个机器之间的合作

多个机器一块去处理这么一大堆数据，相应服务请求，总得有个指挥，以便可以做到此起彼落，默契配合。这就是控制和监控做的。说起来也是平平无奇，每一个工作的机器都是服务器端，然后总控程序是一个客户端，他告诉服务器端什么时间，应该做什么。这个时候，一组机器都是统一去做的，你就得将就那个最“无能的”。呵呵。典型的木桶理论的诠释。

不过控制需要注意的是，一组机器作为一个控制单元，如果他们没有都做完你指定动作，你就不能要求他们做下一步动作。他们是一个完整的整体，就把他们看作一台机器好了，一荣不能俱荣，但是一废俱废。

监控端，关于他的有个名词叫做心跳。你在看其他的资料的时候会看到这个。每一个间隔都向服务器端报告自己的状态（通过socket）。一般是间隔一秒。呵呵。其他的也没有什么可以说的，本来是一个简单的东西。

3. cache

很多地方都用到了cache技术。依据数据访问的时间局部性和内容局部性原理，cache的出现极大的提高了数据访问的效率。特别是互联网上的搜索。扎堆的现象更为严重。这就是为什么会有搜索排行榜的原因了。前两天弄得沸沸扬扬的白领裸照事件。。。很多人搜的都是相同的关键词。在搜索引擎里边，cache作为独立的一部分出现，它能挡住75%以上的访问？也就是说，能进入到后台需要检索的访问占很小的一部分。大部分都在cache里边命中了。

Cache的应用当然不止这一点。在所有你认为有数据需要缓冲访问的地方都可以用。用点内存换来访问的高效率有的时候还是很值得的。不过需要注意cache里边的数据的及时更新的问题，不能访问过时的数据。也就是数据何时更新的问题。

排序，归并，排重。在这里，计算机恢复到了本来的面目，排序。你还记得数据结构和算法里边关于排序的介绍吗？我曾经问过一个面试的兄弟。他已经什么都记不起来了。只记住一个冒泡和快排。我以前听过小乔（中搜架构师）讲解数据结构和算法，让我大开眼界，终于知道什么时候，为什么用这些玩意了。前两天公司面试的时候，一个兄弟做排序，写了一个冒泡。我问他，能不能快点，他说快排。我说还能不能在快点，他说没有了。呵呵，把常数时间的排序都扔了（不过，也可能真的没有学）。下边这个程序是前段时间我在看基数排序的时候写的。工作的变更，一直都没有把它派上用场（以后说不定）。现在，这不会涉及到任何公司的机密，可以给大家看。他用了两倍于快排的内存，但是，我的测试是，可以有将近一倍的排序速度。

平衡二叉树和快排有什么区别吗？从cpu的利用率上说。前者对cpu的使用基本上是平的；后者，在一个段时间把cpu用到100%，如果同一台机器上还有别人的程序在跑，那么他们都得等你，也就是你的资源利用不合理，造成了这段时间，cpu是程序的瓶颈；从动静方面来说，一个是动态的，可以边建，边检索，另外一个是静态的；从内存利用上说，前者耗费的远大于后者，大约一倍多点。

哈希表，基本上算是最快的查找办法。每一个单元下边挂指针，解决冲突。而且，还有很多变体，你可以用内存中的一位表示一个桶。呵呵。这是一个非常好的利用内存的办法。数据量的增大，让我们每省一个字节都是非常有意义。我们称他为内存位图。其实，数组就是一个用下标做的不会有冲突的哈希。

没有一个方法可以包打天下，但是，你要知道他们在什么样的环境下使用才是更合适的，什么样的环境下是无所谓的。让我现在默写一个快排，我会出错，也得调试一段时间。总是不能完全的记住每一个语句。呵呵。不过，我认为这不重要。这样的函数库我都已经写好了，或者是有现成的了，我只需要记住何时选用他们就好了。直接调用不就得了。单纯的记住，没有作用。但是，你要知道他的思想。

Strlen. Strlen函数是用的很多的函数，你可测试过他的时间耗费？每调用一次，程序都需要遍历一次你的字符串，直到碰到0为止。字符串短，次数少的时候还看不出来，相反的情况下尽量少用，为什么不能一次调用，保存结果，到处使用那？

你可以注意一下你的那些函数。关注的不只是功能，而是他们耗费的时间本身（很多时候我们对时间的要求大于对内存的要求）。能不能让你的程序更快点（当然是在程序稳定运行的基础上），而这种快仅限于对算法的选择，不包括语言的换用。你能把所有的C程序都改成汇编？没有必要。投入产出比太低了。不过这种追求也要看环境和用途。不可太过。过犹不及！什么东西都是这样，选择最合适，达到要求就好。过犹不及。还有很多需要做的东西，不是仅仅这一个玩意。

[VC_Release]: http://blog.csdn.net/xwjbs/archive/2006/12/01/1423992.aspx