实现自己的搜索引擎（一）

搜索引擎的原理其实很简单，写出来没两页纸，但是实现中的各种细节写成的论文可以堆满两个图书馆。

让我们先从原理说起。

首先需要用输入数据创建索引，对于互联网搜索引擎，输入数据是一个个由爬虫从网上抓回来的网页，经过清洗之后进行内容抽取，然后整理成统一的格式交给索引程序创建索引。
索引由以下几个基本的组成部分：
1. 倒排索引，这一部分存放"关键字"->文档的映射，一般来说会把同一个关键字对应的所有文档按照统一方法整理成一个排好序的线性结构，以便遍历和各种AND/OR之类的操作。
2. 正排索引，这一部分存放每个文档的各种属性
索引程序要干的事就是从源数据中拿出每个关键字和各种属性，整理成索引文件。文本变成关键字的过程叫做关键字提取，对于英语等语言，这个过程相对容易，一般就是进行大小写、全角/半角转换，拼写检查，字根提取等工作，例如源文本中的“goes”，“going”，“went”统一转换为“go”等；对于中文来说这个过程会比较麻烦，需要进行分词，常用的分词方法有单字切分、正/反向最大匹配、n元分词、隐马模型等。没有那一种单一的方法能满足所有需求，所以实际应用中一般会将多种方法结合使用。

索引创建好之后就可以搜索了，一个典型的搜索过程有这几个步骤：
1. 倒排索引的查询，一般称为“全文检索”，根据输入的关键字序列T1,T2..Tn，在倒排索引中找到对应的文档链，根据查询需求进行AND或者OR的组合，得到一个满足条件的结果集，对于典型的全文搜索引擎，这个阶段还需要计算每个文档的文本相关性以便排序，常用的文本相关性算法有TF-IDF、BM25、VSM、LM等。
2. 正排索引过滤，在得到满足全文检索的文档集后，对每个文档检查其属性是否满足过滤条件，如果不满足则丢弃，剩下的就是最终的结果集。
3. 排序，全文搜索引擎一般的做法是：基于倒排索引查询得到的文本相关性，结合正排索引中的各种属性进行加权，例如给较新的文档加分等，最终得到一个分值，然后对结果集进行排序，保留前若干个结果返回给用户。

以上的过程就是全文搜索引擎的大致工作过程，其中复杂之处在于如何评估输入的查询条件和文档之间的匹配程度，文本相关性只能满足一部分需求，还需要其它一些因素来对文档得分进行调整，例如Google的PageRank就是通过进出的链接对文档重要性进行评估的一种方法。

垂直搜索引擎的基本工作原理和上述的一样，但是侧重点不同，一般来说垂直网站更重视文本之外的各种属性，例如电商网站会很关注商品的库存量和售价，如果排序结果将无库存或者过于昂贵的商品放在最前面会严重影响销售量；本地搜索网站会很关注POI和用户之间的距离，如果将一家距离用户很远的商户排在结果的前面同样也会造成很不好的体验。

另外还有一个很重要的问题就是索引的更新，对于互联网搜索引擎来说，一般会采用定期重建的策略，例如google就是每个几个小时将一个索引块整个重建，但是这种策略对于电商网站显然不行，例如在淘宝上可以进行拍卖，用户出价会导致拍卖价格迅速变化，需要在很短时间内迅速将这个价格的变化反映到搜索结果中，这就需要一些专门设计的索引结构来支持。

下一节我们将看看搜索引擎中的一些基本数据结构