搜索引擎技术之概要预览

搜索引擎技术之概要预览

前言

    近些天在学校静心复习功课与梳理思路（找工作的事情暂缓），趁闲暇之际，常看有关搜索引擎相关技术类的文章，接触到不少此前未曾触碰到的诸多概念与技术，如爬虫，网页抓取，分词，索引，查询，排序等等，更惊叹于每一幅精彩的架构图，特此，便有记录下来的冲动，以作备忘。

    本文从最主要的搜索引擎的概念谈起，到全文检索的概念，由网络蜘蛛，分词技术，系统架构，排序的解说（结合google搜索引擎的技术原理），而后到图片搜索的原理，终于以几个开源搜索引擎软件的介绍结束全文。

    因为本文初次接触此类有关搜索引擎的技术，參考和借鉴了互联网上诸多牛人的文章与作品，有不妥之处，还望诸君海涵。再者因本人见识浅薄，才疏学浅，有不论什么问题或错误，欢迎不吝指正。同一时候，正式进军搜索引擎领域的学习与研究。谢谢。

1、什么是搜索引擎

    搜索引擎指自己主动从因特网搜集信息，经过一定整理以后，提供给用户进行查询的系统。因特网上的信息浩瀚万千，并且毫无秩序，全部的信息像汪洋上的一个个小岛，网页链接是这些小岛之间纵横交错的桥梁，而搜索引擎，则为用户绘制一幅一目了然的信息地图，供用户随时查阅。

    搜索引擎的工作原理以最简单的语言描写叙述，即是：

1. 搜集信息：首先通过一个称为网络蜘蛛的机器人程序来追踪互联网上每一个网页的超链接，因为互联网上每一个网页都不是单独存在的（必存在到其他网页的链接），然后这个机器人程序便由原始网页链接到其他网页，一链十，十链百，至此，网络蜘蛛便爬满了绝大多数网页。
2. 整理信息：搜索引擎整理信息的过程称为“创建索引”。搜索引擎不仅要保存搜集起来的信息，还要将它们依照一定的规则进行编排。这样，搜索引擎根本不用又一次翻查它全部保存的信息而迅速找到所要的资料。
3. 接受查询：用户向搜索引擎发出查询，搜索引擎接受查询并向用户返回资料。搜索引擎每时每刻都要接到来自大量用户的差点儿是同一时候发出的查询，它依照每一个用户的要求检查自己的索引，在极短时间内找到用户须要的资料，并返回给用户。

    整理信息及接受查询的过程，大量应用了文本信息检索技术，并依据网络超文本的特点，引入了很多其他的信息。接下来，下文便由网络蜘蛛，分词技术，到系统架构，排序一一介绍。

2、网络蜘蛛

    网络蜘蛛即Web Spider，是一个非常形象的名字。把互联网比喻成一个蜘蛛网，那么Spider就是在网上爬来爬去的蜘蛛。网络蜘蛛是通过网页的链接地址来寻找网页，从站点某一个页面（一般是首页）開始，读取网页的内容，找到在网页中的其他链接地址，然后通过这些链接地址寻找下一个网页，这样一直循环下去，直到把这个站点全部的网页都抓取完为止。假设把整个互联网当成一个站点，那么网络蜘蛛就能够用这个原理把互联网上全部的网页都抓取下来。

    在抓取网页的时候，网络蜘蛛一般有两种策略：广度优先和深度优先（例如以下图所看到的）。广度优先是指网络蜘蛛会先抓取起始网页中链接的全部网页，然后再选择当中的一个链接网页，继续抓取在此网页中链接的全部网页。这是最经常使用的方式，因为这种方法能够让网络蜘蛛并行处理，提高其抓取速度。深度优先是指网络蜘蛛会从起始页開始，一个链接一个链接跟踪下去，处理完这条线路之后再转入下一个起始页，继续跟踪链接。这种方法有个长处是网络蜘蛛在设计的时候比較easy。至于两种策略的差别，下图的说明会更加明白。

    因为不可能抓取全部的网页，有些网络蜘蛛对一些不太重要的站点，设置了訪问的层数。比如，在上图中，A为起始网页，属于0层，B、C、D、E、F属于第1层，G、H属于第2层，I属于第3层。假设网络蜘蛛设置的訪问层数为2的话，网页I是不会被訪问到的。这也让有些站点上一部分网页能够在搜索引擎上搜索到，另外一部分不能被搜索到。 对于站点设计者来说，扁平化的站点结构设计有助于搜索引擎抓取其很多其他的网页。

3、中文分词

    下图是我无聊之际，在百度，谷歌，有道，搜狗，搜搜，雅虎中搜索：结构之法的搜索结果比較（读者能够永久在百度或谷歌中搜索：结构之法4个字，即可进入本博客）：

    从上图能够看出，百度，谷歌，搜狗，搜搜，雅虎都在第一个选项链接到了本博客–结构之法算法之道，从上面的搜索结果来看，百度给的结果是最令我惬意的（几个月前，谷歌的搜索结果是最好的），其次是雅虎英文搜索，谷歌，而有道的搜索结果则差强人意。是什么影响了这些搜索引擎搜索的质量与相关性的程度呢?答曰：中文分词。以下，咱们来详细了解什么是中文分词技术。

    中文分词技术属于自然语言处理技术范畴，对于一句话，人能够通过自己的知识来明白哪些是词，哪些不是词，但怎样让计算机也能理解？其处理过程就是分词算法。
    现有的分词算法可分为三大类：基于字符串匹配的分词方法、基于理解的分词方法和基于统计的分词方法。

    1、基于字符串匹配的分词方法
    这样的方法又叫做机械分词方法，它是依照一定的策略将待分析的汉字串与一个“充分大的”机器词典中的词条进行配，若在词典中找到某个字符串，则匹配成功（识别出一个词）。依照扫描方向的不同，串匹配分词方法能够分为正向匹配和逆向匹配；依照不同长度优先匹配的情况，能够分为最大（最长）匹配和最小（最短）匹配；依照是否与词性标注过程相结合，又能够分为单纯分词方法和分词与标注相结合的一体化方法。经常使用的几种机械分词方法例如以下：
    1）正向最大匹配法（由左到右的方向）；
    2）逆向最大匹配法（由右到左的方向）；
    3）最少切分（使每一句中切出的词数最小）。

    还能够将上述各种方法相互组合，比如，能够将正向最大匹配方法和逆向最大匹配方法结合起来构成双向匹配法。因为汉语单字成词的特点，正向最小匹配和逆向最小匹配一般非常少使用。一般说来，逆向匹配的切分精度略高于正向匹配，遇到的歧义现象也较少。统计结果表明，单纯使用正向最大匹配的错误率为1/169，单纯使用逆向最大匹配的错误率为1/245。但这样的精度还远远不能满足实际的须要。实际使用的分词系统，都是把机械分词作为一种初分手段，还需通过利用各种其他的语言信息来进一步提高切分的准确率。
    一种方法是改进扫描方式，称为特征扫描或标志切分，优先在待分析字符串中识别和切分出一些带有明显特征的词，以这些词作为断点，可将原字符串分为较小的串再来进机械分词，从而降低匹配的错误率。还有一种方法是将分词和词类标注结合起来，利用丰富的词类信息对分词决策提供帮助，并且在标注过程中又反过来对分词结果进行检验、调整，从而极大地提高切分的准确率。

    2、基于理解的分词方法
    这样的分词方法是通过让计算机模拟人对句子的理解，达到识别词的效果。其基本思想就是在分词的同一时候进行句法、语义分析，利用句法信息和语义信息来处理歧义现象。它通常包含三个部分：分词子系统、句法语义子系统、总控部分。在总控部分的协调下，分词子系统能够获得有关词、句子等的句法和语义信息来对分词歧义进行推断，即它模拟了人对句子的理解过程。这样的分词方法须要使用大量的语言知识和信息。因为汉语语言知识的笼统、复杂性，难以将各种语言信息组织成机器可直接读取的形式，因此眼下基于理解的分词系统还处在试验阶段。

    3、基于统计的分词方法
    从形式上看，词是稳定的字的组合，因此在上下文中，相邻的字同一时候出现的次数越多，就越有可能构成一个词。因此字与字相邻共现的频率或概率能够较好的反映成词的可信度。能够对语料中相邻共现的各个字的组合的频度进行统计，计算它们的互现信息。定义两个字的互现信息，计算两个汉字X、Y的相邻共现概率。互现信息体现了汉字之间结合关系的紧密程度。当紧密程度高于某一个阈值时，便可觉得此字组可能构成了一个词。

    这样的方法仅仅需对语料中的字组频度进行统计，不须要切分词典，因而又叫做无词典分词法或统计取词方法。但这样的方法也有一定的局限性，会经常抽出一些共现频度高、但并非词的经常使用字组，比如“这一”、“之中的一个”、“有的”、“我的”、“很多的”等，并且对经常使用词的识别精度差，时空开销大。实际应用的统计分词系统都要使用一部主要的分词词典（经常使用词词典）进行串匹配分词，同一时候使用统计方法识别一些新的词，即将串频统计和串匹配结合起来，既发挥匹配分词切分速度快、效率高的特点，又利用了无词典分词结合上下文识别生词、自己主动消除歧义的长处。

    究竟哪种分词算法的精确度更高，眼下并无定论。对于不论什么一个成熟的分词系统来说，不可能单独依靠某一种算法来实现，都须要综合不同的算法。个人了解，海量科技的分词算法就採用“复方分词法”，所谓复方，相当于用中药中的复方概念，即用不同的药才综合起来去医治疾病，相同，对于中文词的识别，须要多种算法来处理不同的问题。

4、系统架构

• 全文检索

    全文检索的方法主要分为按字检索和按词检索两种。按字检索是指对于文章中的每一个字都建立索引，检索时将词分解为字的组合。对于各种不同的语言而言，字有不同的含义，比方英文中字与词实际上是合一的，而中文中字与词有非常大分别。按词检索指对文章中的词，即语义单位建立索引，检索时按词检索，并且能够处理同义项等。英文等西方文字因为依照空白切分词，因此实现上与按字处理类似，加入�同义处理也非常easy。中文等东方文字则须要切分字词，以达到按词索引的目的，关于这方面的问题，是当前全文检索技术尤其是中文全文检索技术中的难点，在此不做详述。

    全文检索系统是依照全文检索理论建立起来的用于提供全文检索服务的软件系统。一般来说，全文检索须要具备建立索引和提供查询的基本功能，此外现代的全文检索系统还须要具有方便的用户接口、面向WWW的开发接口、二次应用开发接口等等。功能上，全文检索系统核心具有建立索引、处理查询返回结果集、添加�索引、优化索引结构等等功能，外围则由各种不同应用具有的功能组成。结构上，全文检索系统核心具有索引引擎、查询引擎、文本分析引擎、对外接口等等，加上各种外围应用系统等等共同构成了全文检索系统。图1.1展示了上述全文检索系统的结构与功能。

    在上图中，我们看到：全文检索系统中最为关键的部分是全文检索引擎，各种应用程序都须要建立在这个引擎之上。一个全文检索应用的优异程度，根本上由全文检索引擎来决定。因此提升全文检索引擎的效率即是我们提升全文检索应用的根本。

• 搜索引擎与全文检索的差别

    搜索引擎的门槛究竟有多高？搜索引擎的门槛主要是技术门槛，包含网页数据的高速採集、海量数据的索引和存储、搜索结果的相关性排序、搜索效率的毫秒级要求、分布式处理和负载均衡、自然语言的理解技术等等，这些都是搜索引擎的门槛。对于一个复杂的系统来说，各方面的技术固然重要，但整个系统的架构设计也相同不可忽视，搜索引擎也不例外。

    搜索引擎的技术基础是全文检索技术，从20世纪60年代，国外对全文检索技术就開始有研究。全文检索通常指文本全文检索，包含信息的存储、组织、表现、查询、存取等各个方面，其核心为文本信息的索引和检索，一般用于企事业单位。随着互联网信息的发展，搜索引擎在全文检索技术上逐渐发展起来，并得到广泛的应用，但搜索引擎还是不同于全文检索。搜索引擎和常规意义上的全文检索主要差别有以下几点：
　　1、数据量
　　传统全文检索系统面向的是企业本身的数据或者和企业相关的数据，一般索引库规模多在GB级，数据量大的也仅仅有几百万条；但互联网网页搜索须要处理几十亿的网页，搜索引擎的策略都是採用server群集和分布式计算技术。
　　2、内容相关性
　　信息太多，查准和排序就特别重要，Google等搜索引擎採用网页链接分析技术，依据互联网上网页被链接次数作为重要性评判的依据；但全文检索的数据源中相互链接的程度并不高，不能作为判别重要性的依据，仅仅能基于内容的相关性排序。
　　3、安全性
　　互联网搜索引擎的数据来源都是互联网上公开的信息，并且除了文本正文以外，其他信息都不太重要；但企业全文检索的数据源都是企业内部的信息，有等级、权限等限制，对查询方式也有更严格的要求，因此其数据通常会安全和集中地存放在数据仓库中以保证数据安全和管理的要求。
　　4、个性化和智能化

　　搜索引擎面向的是互联网訪问者，因为其数据量和客户数量的限制，自然语言处理技术、知识检索、知识挖掘等计算密集的智能计算技术非常难应用，这也是眼下搜索引擎技术努力的方向；而全文检索数据量小，检索需求明白，客户量少，在智能化和个性可走得更远。

• 搜索引擎的系统架构

    这里主要针对全文检索搜索引擎的系统架构进行说明，下文中提到的搜索引擎假设没有特殊说明也是指全文检索搜索引擎。搜索引擎的实现原理，能够看作四步：从互联网上抓取网页→建立索引数据库→在索引数据库中搜索→对搜索结果进行处理和排序。　　
　　1、从互联网上抓取网页
　　利用能够从互联网上自己主动收集网页的网络蜘蛛程序，自己主动訪问互联网，并沿着不论什么网页中的全部URL爬到其他网页，重复这过程，并把爬过的全部网页收集到server中。

　　2、建立索引数据库
　　由索引系统程序对收集回来的网页进行分析，提取相关网页信息(包含网页所在URL、编码类型、页面内容包含的关键词、关键词位置、生成时间、大小、与其他网页的链接关系等)，依据一定的相关度算法进行大量复杂计算，得到每一个网页针对页面内容中及超链中每一个关键词的相关度(或重要性)，然后用这些相关信息建立网页索引数据库。

　　3、在索引数据库中搜索
　　当用户输入关键词搜索后，分解搜索请求，由搜索系统程序从网页索引数据库中找到符合该关键词的全部相关网页。

　　4、对搜索结果进行处理排序
　　全部相关网页针对该关键词的相关信息在索引库中都有记录，仅仅需综合相关信息和网页级别形成相关度数值，然后进行排序，相关度越高，排名越靠前。最后由页面生成系统将搜索结果的链接地址和页面内容摘要等内容组织起来返回给用户。

　　下图是一个典型的搜索引擎系统架构图，搜索引擎的各部分都会相互交错相互依赖。其处理流程依照例如以下描写叙述：

　　“网络蜘蛛”从互联网上抓取网页，把网页送入“网页数据库”，从网页中“提取URL”，把URL送入“URL数据库”，“蜘蛛控制”得到网页的URL，控制“网络蜘蛛”抓取其他网页，重复循环直到把全部的网页抓取完毕。

　　系统从“网页数据库”中得到文本信息，送入“文本索引”模块建立索引，形成“索引数据库”。同一时候进行“链接信息提取”，把链接信息(包含锚文本、链接本身等信息)送入“链接数据库”，为“网页评级”提供依据。

　　“用户”通过提交查询请求给“查询server”，server在“索引数据库”中进行相关网页的查找，同一时候“网页评级”把查询请求和链接信息结合起来对搜索结果进行相关度的评价，通过“查询server”依照相关度进行排序，并提取关键词的内容摘要，组织最后的页面返回给“用户”。

• 搜索引擎的索引和搜索

    以下咱们以Google搜索引擎为例主要介绍搜索引擎的数据索引和搜索过程。

　　数据的索引分为三个步骤：网页内容的提取、词的识别、标引库的建立。

　　互联网上大部分信息都是以HTML格式存在，对于索引来说，仅仅处理文本信息。因此须要把网页中文本内容提取出来，过滤掉一些脚本标示符和一些没用的广告信息，同一时候记录文本的版面格式信息。词的识别是搜索引擎中非常关键的一部分，通过字典文件对网页内的词进行识别。对于西文信息来说，须要识别词的不同形式，比如：单复数、过去式、组合词、词根等，对于一些亚洲语言(中文、日文、韩文等)须要进行分词处理。识别出网页中的每一个词，并分配唯一的wordID号，用于为数据索引中的标引模块服务。

　　标引库的建立是数据索引中结构最复杂的一部分。一般须要建立两种标引：文档标引和关键词标引。文档标引分配每一个网页一个唯一的docID号，依据docID标引出在这个网页中出现过多少过wordID，每一个wordID出现的次数、位置、大写和小写格式等，形成docID相应wordID的数据列表；关键词标引事实上是对文档标引的逆标引，依据wordID标引出这个词出如今那些网页(用wordID表示)，出如今每一个网页的次数、位置、大写和小写格式等，形成wordID相应docID的列表。

　　搜索的处理过程是对用户的搜索请求进行满足的过程，通过用户输入搜索keyword，搜索server相应关键词字典，把搜索关键词转化为wordID，然后在标引库中得到docID列表，对docID列表进行扫描和wordID的匹配，提取满足条件的网页，然后计算网页和关键词的相关度，依据相关度的数值返回前K篇结果(不同的搜索引擎每页的搜索结果数不同)返回给用户。假设用户查看的第二页或者第多少页，又一次进行搜索，把排序结果中在第K+1到2*K的网页组织返回给用户。其处理流程例如以下图所看到的：

5、排序技术

• Google成功的秘密

    到2004年为止，Google（ http://www.google.com ）已经连续两年被评为全球第一品牌，Google成立仅五年时间，最初仅仅是两个斯坦福大学学生的研究项目。这不能不说是一个奇迹，就像比尔?盖茨创制奇迹一样。比尔?盖茨能创造奇迹，是因为他看准了个人计算机软件市场的趋势，所以创建的公司叫Microsoft（微软）：Micro（小）Soft（软件）。那么Google呢？在Google出来之前已经有一些非常有成就的搜索引擎公司，事实上力也非常强，看来不仅仅是Google看见了搜索的趋势。Google究竟成功的秘密在哪儿？

    Google的成功有很多因素，最重要的是Google对搜索结果的排序比其他搜索引擎都要好。Google保证让绝大部分用搜索的人，都能在搜索结果的第一页找到他想要的结果。客户得到了满足，下一次还过来，并且会向其他人介绍，这一来一往，使用的人就多了。所以Google在没有做不论什么广告的前提下，让自己成为了全球最大的品牌。Google究竟採用了哪种排序技术？PageRank，即网页级别。

    Google有一个创始人叫Larry Page，据说PageRank的专利是他申请的，于是依据他的名字就有了Page Rank。国内也有一家非常成功的搜索引擎公司，叫百度（ http://www.baidu.com ）。百度的创始人李彦宏说，早在1996年他就申请了名为超链分析的专利，PageRank的原理和超链分析的原理是一样的，并且PageRank眼下还在Paten-pending（专利申请中）。言下之意是这里面存在专利全部权的问题。这里不讨论专利全部权，仅仅是从中可看出，成功搜索引擎的排序技术，就其原理上来说都差点儿相同，那就是链接分析。超链分析和PageRank都属于链接分析。

    链接分析究竟为何物？因为李彦宏的超链分析没有详细的介绍，笔者唯一看过的就是在美国专利局站点上关于李彦宏的专利介绍。PageRank的介绍倒是不少，并且眼下Google毕竟是全球最大的搜索引擎，这里以PageRank为代表，详细介绍链接分析的原理。

• PageRank揭秘

    PageRank的原理类似于科技论文中的引用机制：谁的论文被引用次数多，谁就是权威。说的更白话一点：张三在谈话中提到了张曼玉，李四在谈话中也提到张曼玉，王五在谈话中还提到张曼玉，这就说明张曼玉一定是非常有名的人。在互联网上，链接就相当于“引用”，在B网页中链接了A，相当于B在谈话时提到了A，假设在C、D、E、F中都链接了A，那么说明A网页是最重要的，A网页的PageRank值也就最高。

    怎样计算PageRank值有一个简单的公式 ：

    当中：系数为一个大于0，小于1的数。一般设置为0.85。网页1、网页2至网页N表示全部链接指向A的网页。

由以上公式能够看出三点 ：

1. 链接指向A的网页越多，A的级别越高。即A的级别和指向A的网页个数成正比，在公式中表示，N越大， A的级别越高；
2. 链接指向A的网页，其网页级别越高， A的级别也越高。即A的级别和指向A的网页自己的网页级别成正比，在公式中表示，网页N级别越高， A的级别也越高；
3. 链接指向A的网页，其链出的个数越多，A的级别越低。即A的级别和指向A的网页自己的网页链出个数成反比，在公式中现实，网页N链出个数越多，A的级别越低。

    每一个网页有一个PageRank值，这样形成一个巨大的方程组，对这个方程组求解，就能得到每一个网页的PageRank值。互联网上有上百亿个网页，那么这个方程组就有上百亿个未知数，这个方程虽然是有解，但计算毕竟太复杂了，不可能把这全部的页面放在一起去求解的。对详细的计算方法有兴趣的朋友能够去參考一些数值计算方面的书。

    总之，PageRank有效地利用了互联网所拥有的庞大链接构造的特性。 从网页A导向网页B的链接，用Google创始人的话讲，是页面A对页面B的支持投票，Google依据这个投票数来推断页面的重要性，但Google除了看投票数（链接数）以外，对投票者（链接的页面）也进行分析。「重要性」高的页面所投的票的评价会更高，因为接受这个投票页面会被理解为「重要的物品」。

6、图片搜索原理

    早有网友阮一峰介绍了一个简单的图片搜索原理，可分为以下几步：

1. 缩小尺寸。将图片缩小到8×8的尺寸，总共64个像素。这一步的作用是去除图片的细节，仅仅保留结构、明暗等基本信息，摒弃不同尺寸、比例带来的图片差异。
2. 简化色彩。将缩小后的图片，转为64级灰度。也就是说，全部像素点总共仅仅有64种颜色。
3. 计算平均值。计算全部64个像素的灰度平均值。
4. 比較像素的灰度。将每一个像素的灰度，与平均值进行比較。大于或等于平均值，记为1；小于平均值，记为0。
5. 计算哈希值。将上一步的比較结果，组合在一起，就构成了一个64位的整数，这就是这张图片的指纹。组合的次序并不重要，仅仅要保证全部图片都採用相同次序即可了。

    这样的方法对于寻找一模一样的图片是有效的，但并不能够去搜索“类似”的照片，也不能局部搜索，比方从一个人的单人照找到这个人与别人的合影。这些Google Images都能做到。

    事实上早在2008年，Google发布了一篇图片搜索的论文（PDF版），和文本搜索的思路是一样的：

1. 对于每张图片，抽取其特征。这和文本搜索对于网页进行分词类似。
2. 对于两张图片，其相关性定义为其特征的类似度。这和文本搜索里的文本相关性也是差点儿相同的。
3. 图片一样有image rank。文本搜索中的page rank依靠文本之间的超链接。图片之间并不存在这样的超链接，image rank主要依靠图片之间的类似性（两张图片类似，便觉得它们之间存在超链接）。具有很多其他类似图片的图片，其image rank更高一些。

7、开源搜索引擎

全文检索引擎 Sphinx

    关注本博客的读者不知是否还记得以前出如今这篇文章从几幅架构图中偷得半点海量数据处理经验中的两幅图，例如以下所看到的：

    上图出自俄罗斯的开源全文搜索引擎软件Sphinx，单一索引最大可包含1亿条记录，在1千万条记录情况下的查询速度为0.x秒（毫秒级）。Sphinx创建索引的速度为：创建100万条记录的索引仅仅需3～4分钟，创建1000万条记录的索引能够在50分钟内完毕，而仅仅包含最新10万条记录的增量索引，重建一次仅仅需几十秒。

Java搜索引擎 Lucene