浅谈搜索引擎技术原理与架构

搜索引擎是我们非常熟悉的互联网产品，上网都离不开搜索，毫无疑问，在pc端，是多数流量的入口。大家都会说，“有问题，百度一下”，当初百度靠这句广告语，打开了国内很大的市场。

曾经看过一个百度员工写的段子：“今天一个出租出司机载我去上班，一边看着百度大厦一边说，你们百度不就是个框吗，要这么多员工干啥。他说的好有道理，我竟无言以对”。那么搜索引擎背后到底是什么，到底复杂不复杂，这里为大家一一解答。本文只是简要介绍一下总体需要的原理，具体的技术原理，我会在后续的文章中深入介绍。 1.索引 输入一个关键词，就会出现相关的文档。如果这里有三篇文档，给一个关键词，就通过字符串匹配的方法就可以找到包含该关键词的文档，这很简单。那么如果有一百篇呢，同样对这一百篇文章逐个进行搜索即可，现代计算机对于上百篇文章的检索还是可以毫秒级的时间完成的。那么，网络上数以万计乃至上亿的文章，难道也要这样逐个搜索吗。索引就是解决搜索缓慢的方案，也就是说将每篇文章进行处理，对每一个出现的词建索引。每个词对应的列表是包含这个词的文章的列表，这被称为倒排索引。于是输入一个词，只要查找这张表，就能很快把包含这个词的文章给找出来。那如果有多个词呢，比如，在淘宝上搜索“黄色毛衣”，只要把包含“黄色”的商品和包含“毛衣”的商品求个交集。构建倒排索引是搜索引擎的基础。 2.分词 构建倒排索引的单位是词，词代表了语言中最基本的单位。在英文中，可以通过空格对每个词进行分开，而汉语就相对复杂了，不是通过空格分开的了，需要人通过语义进行分开。上面提到了“黄色毛衣”这个query，可以将“黄色”和“毛衣”分成两个基本的语言单位。但是，计算机来进行汉语分词就相对来说比较困难了。好在目前汉语分词技术已经非常成熟了，也有非常成熟的库进行调用，中科院，复旦等科研机构都对汉语分词技术研究得很深入。 3.排序 找出这些文章以后，怎么进行排序，哪篇文章靠前，哪篇文章靠后，也是个问题。我们暂且可以这样来进行排序，按照相关性来，如果搜索的query跟文档的标题一样，这个相关性就相对来说比在正文中出现这些query的文档高。如果词的顺序都一模一样，那相关性就更高了，如果一字不差，不多字也不少字，当然是相关性最高了。 上述几个问题，是搜索的基础。只要解决了这几个问题，稍微花几天功夫，一个计算机系的研究生，就可以把一个简单的搜索引擎构建起来了。笔者画了一下简单的搜索引擎的技术架构图。 那么搜索引擎的难点到底在哪呢，为什么人们都说，Google比百度好呢。 首先，需要明确，搜索引擎的效果如何评价。回归到人们上网的本质意图，是搜索到自己需要的文档。如果搜索引擎能很快地并且很精准地把用户需要的网页找出来，那好评率会不断飙升，业内大家的共识是，每次搜索用户花在搜索引擎上的时间越短，搜索引擎越好。总结起来，笔者认为，搜索引擎的评价指标在于：速度、精准性、覆盖率、时效性。 那么从这三个指标出发 ，就为搜索提出了一些列问题。 首先，从速度来说，毫无疑问，搜索引擎需要快速对用户的搜索进行响应，把最好的结果展现给用户。我们使用不管哪一款搜索引擎，抛开网速不说，如果说不能在一秒内返回搜索结果，那么基本上就和这一款搜索引擎拜拜了。高速的搜索引擎需要依赖以下方面： 1.高并发架构 像百度这样的搜索引擎，每秒钟至少要能扛得住上百万次搜索请求。这是工程方面的问题。如果是用户量级上亿的搜索引擎，需要上百乃至上千的机器来处理请求。针对不同区域的用户，处理用户请求的机器都是不同的。 由最开始的电信、移动、联通的网关到搜索引擎前端机器的流量划分，再到后端query处理、索引查询，一个搜索请求很可能需要经过几十台机器的处理，才将结果展现给用户，而这些流程，在毫秒级时间就完成了。对此，需要有反向代理、负载均衡这样的技术进行压力的分流，哪些片区需要多少台机器，保证这一片的机房不会因为流量过大而奔溃，都是经过工程师的多年运维经验，预估出来的。并且要考虑过节、突发事件、自然灾害对机房的影响等因素，进行多地备份。 这不仅仅是搜索引擎需要解决的问题，淘宝、微信等任何一款用户量较大的产品也需要考虑大量用户访问带来的高并发处理。 2.缓存技术 每秒钟上百万次的搜索请求，都进行query处理、索引查表、求交集、重排序等工作显然也是扛不住的，就算有上百万台机器来处理，这显然是很浪费资源的。这样，缓存技术就有用武之地了。搜索query的热门程度，大致满足长尾分布（http://baike.baidu.com/link?url=JVwZiT_C4WBqFPLPmJRqiuW3m8kmARip_wv4LYCQLWOQoiXfoxfKGaHmjRIlCOBxYzAGD2653qI1uqmmY5t4Na）的，对于一些非常热门的关键词，可能每秒钟会出现好多次请求，这样，如果每次请求都重新处理一次，就是资源的浪费。可以在第一次处理完就把搜索的结果缓存起来，如果再次发生同样的请求，就可以到缓存池里直接把结果拿出来展现了。不在缓存中的结果就需要重新处理，这样每次需要重新处理的请求都是一些冷门的长尾query。 对于缓存的策略，可以采用LRU算法，按照最近最少使用的方法进行记录的淘汰，如果系统庞大一点，可以设计多级缓存。 3.索引端召回策略 虽然建立了倒排索引，但是如果文章的量级很大，每个term所包含的文章都有上亿篇，对于求交和重排都是很耗费时间的。这就需要在索引端就对文章进行粗打分，如果分数都低于某个阈值，就不会将文档参与求交与精排序。那么另一个问题来了，这个分数怎样衡量，怎样的文档才算分数高。这就需要对query进行上下文的处理，结合其他query以及query本身指标进行粗打分。 把网络上的文章全部收录并且构建索引需要用爬虫（spider或者crawler）将网络上的文章进行处理。 1.爬虫策略技术 爬虫是靠几个起点网页出发，通过网页上的链接导向下一个网页，顺藤摸瓜，将尽可能多的网页进行获取，这里就需要设计到底是深度优先搜索还是广度优先搜索方法来把文章获取到，同时需要对链接进行分析，比如计算网页的PageRank值（http://blog.jobbole.com/71431/），计算网页的权威值。同时，考虑到成本，也不是对所有的网页进行爬取，可以选择性挑选一些质量较高的网页优先进行爬取。至于这个网页质量如何评价，也是需要工程师不断在指标查看下进行优化的。 网页内容是不断在变化的，几个月前，屠呦呦这个名字还不是很火，自从获得诺贝尔奖以后，很多相关的新闻就出来了。经常上网的人可能会发现，消息一发布，就很快就能在搜索引擎上检索到相关的新闻。从 时效性出发，就需要爬虫对一些更新较频繁的网页进行频繁地访问，比如说新闻类网站。所以，网站更新频繁度的指标也是工程师们不断关注的。某些爬虫可能侧重于优先搜索更新频繁度较高的网页。 那么同时，爬虫的访问会对目标网站带来压力，很多网站对有反爬虫机制，如果爬取地较频繁，很可能会被目标网站加入黑名单。需要在时效性与可用性之间寻找一个平衡。 如果搜索引擎能非常“懂你 ”，并且将最好的结果放在最前面。那是相当友好，相当人性化的。为了做到这一点，需要程序对用户的query进行语言的理解，同时对用户的行为进行深入挖掘，例如点击以及停留。笔者认为，精准性是搜索引擎占领市场份额最重要的指标。于是也就提出了以下几个问题： 1.query解析 对于两个城市类型的query，比如说“北京上海”，可以解析出来，并且将相关火车票和机票的结果返回给用户。 在地图检索中，对于“中关村肯德基”这样的query，识别出是商圈加上商户的类型，并将所在商圈的商家都返回给用户。 在淘宝中，检索“好看的衣服”，就能识别出“好看”这样的修饰词和“衣服”这样的中心词，至于好看如何定性，那就是另外一回事了。 另外，类似“北京遇上西雅图首映时间”这样的query，就需要实体识别了，因为分词系统将词切分的粒度比较小，像“北京遇上西雅图”这样的实体，就需要一个智能的系统来进行抽取了，同时在离线端，也需要将“北京遇上西雅图”这个实体建立索引。 复杂query的理解，比如说“谢霆锋的是谁的儿子？”这样的query，需要用复杂的自然语言处理技术将query进行分析，转换成相应的格式去知识库中进行检索。 针对这些不同的query模式，就可以对query进行分类，不同的query请求不用的服务器，然后整合自然搜索的结果，融合起来后进行结果的展示。百度率先推出了阿拉丁平台，给予商户一些接口，这样，搜索“北京上海”，不用再转到去哪儿网，就可以把机票火车票结果获取了。 2.关键词改写 用户输入的query可能由于用户个人理解记忆或者输入的手误打错，这会严重影响搜索的质量，如果搜索引擎能判断出用户输入错误，并进行纠正，把正确query的结果返回，那用户体验会得到更大的提升。对于一些明显错误的query，搜索引擎给直接把正确query的结果返回。如果是模棱两可的结果，搜索引擎会给出一些建议的query。 query改写系统比较复杂，在离线阶段，需要对用户的搜索日志挖掘一些常用易出错的query term对，或者人工配置一些可能出错的term对，然后建立一个类似于机器翻译的模型。在在线阶段，按照模型进行候选query的计算。检索时，对 原query检索的结果打分，结合改写后query的检索结果打分进行判断，到底是给改写后的query，还是给出一些建议，还是不做任何指示。这就需要进行多次检索，同时，结果的选择也可以做成一个分类的模型。 不仅仅是错误的纠正，同义词的扩展也是query改写的一个非常重要的方面，比如说搜索iPhone需要同时把苹果手机相关的结果召回，搜索咖啡厅，同时也需要把咖啡馆相关的结果返回。同时，简称（北大与北京大学）、别名等改写也是需要采纳的。除了用扩展的办法以外，还可以将query与离线端都进行归一化，比如说“的哥”全部归一成“出租车司机”。至于采取哪种策略，需要结合线上的情况进行选择，或者各种方法的融合。 3.个性化排序 不同人对文章的要求不一样。喜欢音乐的人搜索李娜，就希望将歌手李娜的结果排前；喜欢运动的人就希望将运动员李娜的结果排前。传统的搜索引擎对于每个人展现的都是一样的结果，而随着人们需求的增大，个性化的搜索就很热门。这就需要搜索引擎对检索结果打分时考虑的不仅仅是相关性的因素，还需要考虑用户维度的特征。通过对用户历史行为的分析，建立用户的画像，每个用户都可以被量化为一个向量，同时每篇文档也被量化为一个向量，还有用户与文档交互维度的也被量化为一个向量，比如说用户曾经点击过此篇文档或者点击过类似的文档。那么这就是一个机器学习问题。 基于机器学习的排序方法在学术界被称为learn to rank，目前比较成熟的方法有：pointwise、pairwise、listwise。 4.知识库的建立 前面提到的类似“谢霆锋的是谁的儿子？”这样的query的后面就不是简单的基于倒排索引的技术了，需要对实体构建知识库了，在这case中，谢霆锋就是一个实体，同时谢贤也是一个实体，同时，这两个实体之间有一个父子关系，为了构建一个强大的知识库，这都是需要添加的信息。 于是，类似的问答机器人就出现了，一些号称能达到几岁儿童智商的机器人也被炒得很火。你会发现，这样的机器人知识渊博，深知天文下知地理，其实是靠强大的语音识别技术、语言理解技术、知识库技术、搜索技术支撑的。 因此，复杂的搜索引擎架构图如下所示： 这些技术可能只是冰山一角，里面任何一个模块，在大公司里都是需要几十人的团队来完成的，同时还有很多部门负责对这些模块进行有机连接。任何算法都没有绝对的好与坏，都是需要认真调研，并对现有的瓶颈进行分析，选择候选的多个方案进行性能的评估，压力测试才可上线的。 本文地址：http://lanlanwork.gawce.com/quote/7796.html    阁恬下 http://lanlanwork.gawce.com/ , 查看更多