浅析如何构建搜索引擎

最近几天看了些搜索引擎方面的书，主要阅读了《自己动手写搜索引擎》、《自己动手写网络爬虫》、《搜索引擎技术实践》、《搜索模式》、《瞬间之美》等书，都很不错，也学到了不少知识，本文谈一下我对构建搜索引擎的认识。

 

要构建一个搜索引擎，首先要确定搜索源，也即被搜索的对象。被搜索的对象可以是一堆文档，用户需要确定包含某关键字的文档集合；可以是一系列网页，用户需要确定跟关键字内容相关的网页；或是一系列的图片，音视频等，用户需要确定包含特定人物、风景的图片，特定艺术家的音乐等；搜索的对象也可以是某种特定的商品，如数码产品。

 

以网页搜索为例，商业搜索引擎google、baidu拼的一个重要指标就是收录的网页数目，那么这些收录的网页从哪里来呢？答案就是”网络爬虫”，网络爬虫从起点url集合，不断的提取url对应的网页，再提取对应网页上的链接网页，依次不断进行，互联网上网页的链接关系构成一个图（每一个url可以看成是图的节点，网页之间的相互链接关系构成图的边），通常网络爬虫采用广度优先遍历的方法来提取网页，这样做的原因主要包括: （1）离初始抓取集合网页越近的网页越重要。（2）初始集合到互联网中的某个网页的链接路径可能有很多条，应该尽量保证以最近的那条路径访问到这个网页。

 

在不加任何限制的情况下，网络爬虫可能无限的工作下去，而通常我们需要对爬虫的行为作出一些限制，如由于资源的限制，只能抓取一定数目的网页，当达到设定的阈值时，即停止抓取过程，也可以通过设置遍历深度来控制提取过程，或是只抓取某一个网站（如只抓取网易的内容，则需要对url进行过滤，是否包含163等）、抓取某个特定国家/地区的网页（需要知道IP与地理位置的对应关系，可通过查询腾讯纯真IP数据库确定IP对应的地理位置）。另外对于可以为重要的网页设置优先级，网络爬虫则会优先分析这些网页及其包含的链接网页，可通过建立优先级队列实现。

 

网络爬虫的整个过程大致如下：

从某个起点，抓取网页，并将抓取过的网页加入到已抓取集合中，这个集合需要能快速判断一个元素是否存在该集合中，可以通过hash表（集合较小），如果网页规模较大时，可借助Bloom Filter、BerkleyDB（Heritrix中包含bdb的实现）等实现。对每个网页包含的链接网页，不断提取，对于url或网页内容满足某种条件比较高的网页，可将提升其优先级，网络爬虫会优先提取这些网页。开源的软件heritrix实现了网络爬虫的框架，并能很好的扩展，支持各种自定义需求。

 

到这里，我们假设网络爬虫已经为我们收集了足够多的网页，而且它仍然在勤恳的工作着，为我们收集更多的网页，所以说每个成功的搜索引擎背后都有一个贤惠的网络爬虫。以百度为例，爬虫提取到的网页在百度的服务器中都有一份副本，使用百度搜索时，结果后面的“百度快照”的入口即指向百度服务器里网页的副本，以加速访问过程，对于内容基本不更新的网页来说，通过百度快照访问的确能快不少，谁叫人家百度的服务器牛X呢。

 

爬虫收集的网页，我们仅能从其对应的url获取一些信息，如一些新闻网站的页面会将时间信息作为url的一部分，其它的一无所知。大多数用户搜索之前对目的的url一无所知，你总不能要求用户指定url的一部分作为搜索的关键字吧。那么用户的搜索跟对应的网页时如何关联起来的呢，除了网页对应的url外，只能是网页的内容了，而网页在浏览器解析前，它是一堆html标签即内容的集合，最简单的方式是我们根据用户搜索的关键字逐个对比网页，确定网页中是否包含需要的关键字，也就是说如果有1亿个文件，搜索引擎需要对比1亿次才能确定哪些网页跟用户的搜索相关，使用google时，在搜索框下面你会看到类似“获得约 19,400,000 条结果 （用时 0.20 秒）”的信息，如果搜索引擎真是这样做的，即使只有19,400,000个网页，也不能在0.20秒匹配完吧，所以搜索引擎肯定有更高明的招数。搜索引擎的这个杀手锏就是倒排索引，基本上所有的搜索引擎都是建立在倒排索引的基础上的，何为倒排索引，请先google/baidu一下。

 

要为网页文件建立倒排索引，首先需要从html文件中提出有用的信息，网页的标题，摘要，内容都是很重要的内容，通常确定网页跟用户搜索是否相关也就是判断网页的标题中是否包含关键字、内容是否包含关键字。类似于htmlParser的工具能帮助你快速分析html文件，并提取出网页的标题，内容等信息。

 

有了网页的实际内容（这些内容跟你在浏览器上看到的网页内容差不多），接下来应该如何建立倒排索引呢？首先你需要对网页的内容进行分析，提取出内容里的关键字，这就是所谓的分词机构，如果网页是英文文章，分词相对比较简单，因为英文单词都是用空格隔开的（词法分析），但你需要考虑的是，英文的大小写、单复数、过去时、进行时之间的转换，也就是说内容中的Apple、apples、apple都应该认为是apple；wait、waits、waited、waiting都认为是want，对于这样直接加s/es、ed、ing的当然比较简单（语法分析），对于drive/drove/driven这样的转换就比较复杂了，而处理这个问题就需要借助于字典实现，需要事先建立好关键字字典及转换关系等，另外对于诸如a、an、of、at这样的词搜索引擎则不需要为其建立倒排索引，因为用户不太可能使用这样的没有明确表意的词作为搜索的关键字。而如果网页内容是中文或是日文、韩文，处理起来就更复杂了，中文的词之间没有任何分割，对于“中华人民共和国”这个词，从用户的角度看关键字应该是“中华”、“人民”、“共和国”，而搜索引擎并不知道这一点，它需要考虑每一种组合的情况，然后与实现建立好的字典进行比较，中科院的ictclas是比较好的中文分词工具，被广泛的使用。对于含有特殊内容的网页，如程序源代码、表格等的网页，则需要根据内容的特性使用特定的分词工具。

 

网页的内容在经过分词工具处理后，已经是一个个关键词条的集合，得到的信息类似于：

网页1 （url） { 词条1（频率、位置信息...），词条2（频率、位置信息），..... 词条m ...}

网页2 （url） { 词条1（频率、位置信息...），词条2（频率、位置信息），..... 词条m ...}

网页3 （url） { 词条1（频率、位置信息...），词条2（频率、位置信息），..... 词条m ...}

.....

网页n （url） { 词条1（频率、位置信息...），词条2（频率、位置信息），..... 词条m...}

 

有了这些数据之后，就可以为词条建立倒排索引了，即对于每个词条，建立一个倒排链，链的内容为所有出现该词条的文档（可能包含位置、出现次数等信息），倒排索引类似于：

词条1 ：{ [网页数统计信息]，网页1（频率、位置信息） ..... 网页n（频率，位置信息）}

词条2 ：{ [网页数统计信息]，网页1（频率、位置信息） ..... 网页n（频率，位置信息）}

.......

词条m：{ [网页数统计信息]，网页1（频率、位置信息） ..... 网页n（频率，位置信息）}

 

有了以上的倒排索引信息，我们就能方便的确定搜索的关键字出现在那些网页中，并将其快速的呈现给用户，这就是为什么google能在很短的时间内确定多少个网页跟搜索相关了。那么用户看到的结果顺序又是由什么决定的，搜索引擎通过给网页评分来决定那个网页最符合用户的需求，网页的得分主要可以通过关键字在网页中出现的次数（越高得分越高），出现关键字的网页占总网页数的百分比（越低得分越高），网页的激励因子（由搜索引擎控制，通过设置该参数可很容易的实现竞价排名）。开源的软件Lucene能有效的实现分词、索引的建立、各种复杂查询、以及文档评分等。

 

以上的工作都完成了，接下来给用户一个搜索框，就只等着用户的搜索请求，一切都搞定了。其实你错了，离成功还有很远，真的很远。作为开发者，你不能把用户想象得太聪明了，不要认为用户都跟你一样想问题，如果真是这样，计算机开发者的负担会减少很多。如果用户输入“可恶的家伙”，接下来搜索引擎去匹配词条“可恶的家伙”，结果可能是Not found。一个聪明的分词软件不会在分析了网络内容后返回一个类似于“可恶的家伙”这样的词条，而应该是“可恶”、“家伙”。所以在搜索引擎给为用户服务之前应该先做一些处理，把用户的语言翻译翻译，让搜索引擎更懂它，同样要做的时对搜索的内容进行分词，而且要使用跟建立索引时一样的分词工具，在建立索引时“可恶的家伙”被分词为“可恶”、“家伙”两个词，那么查询前它也应该被分词为这两个词，而不是被其他的分词工具分为“可”、“恶”、“家”、“伙”。另外还要注意的是，在匹配倒排索引条目时，应该支持模糊查询，不一定要完全的匹配，在没有完全匹配词条的情况，部分内容相同即可认为匹配，这就是为什么有时我们看到搜索结果摇头的原因，感觉完全没有满足我们的需求。

 

最后要说的一点是用户搜索前的用户体验，虽然你在大多数商业搜索引擎的主页上看到的内容大致相同，一个搜索框框，页面的角落允许用户缩小搜索范围（网页、新闻、音乐、视频、学术、专利等），但不同的地方还是有很多的。如搜索建议（自动补全），当你输入部分关键字时，搜索引擎能给一些搜索建议，能帮助用户更好的完成搜索；在一些学术搜索引擎上提供跨库检索功能，展示最近做热门的关键字，在简单的搜索主页上加入“高级搜索”入口等往往都能提供用户的搜索体验，这些往往也是决定搜索引擎是否成功的重要环节。

 

以上为我对搜索引擎的一点点认识，欢迎拍砖。