搜索引擎基石倒排索引

       搜索引擎技术，一个是准确，一个是性能，两个因素构成搜索体验核心，要满足这两个因素，需要好数据结构以及算法，倒排索引可以说是搜索引擎基石。

       倒排索引结构中核心是单词词典以及倒排文件。

       单词词典用于存储文章分词，词典设计目标是能快速查找到相关分词，hash是存储这种结构不二选择，实际搜索引擎也是会采用这种数据结构进行存储。

       倒排列表为了快速查找定位词下文件，数据结构有签名文件、后缀树、倒排列表，实际无论是实验或者线上效果都是倒排文件效果最优。

       词典是存储文章分词索引结构，采用hash数据结构，hash冲突则通过链表或红黑树处理，熟悉java hashmap同学会发现这是jdk中标准实现。搜索引擎词典一般采用此数据结构实现，实现词的高效查找。

       倒排列表是存储分词与文档关系，这样根据词能够快速查找到相应文档。

       倒排列表形成实际过程如下：

       比如有下列文档，比如有下边文档关系，5片文档，每篇文档对应相应文档内容。

       首先对每篇文章进行分词、分词要分的准确需要有扩展词表、停用词、新词发现等一系列技术来保证分词准确。

       倒排索引存储分词与文章id倒排关系，存储实际形式如下：

图中关系即是单词与单词所在文档倒排关系，根据单词能快速查找到相应文档，是一种极其高效存储结构，倒排文件一般会很大所以存储在磁盘。

      倒排列表剋扩展存储三元组文章id、词频。词频是单词在文章中是否重要关键指标。如下图：

词频作为标识词在文档中重要性指标与文档id同时存储，能在快速找到搜索词同时获得词频，方便进行TF-IDF进行打分。

        由词典与倒排文件列表共同构成倒排索引结构：

词典部分一般存储在内存，已实现单词快速查找定位，倒排列表因数据很大一般存储在文件系统。

       为了加快倒排列表查询，会采用id存差值技术，存差值是为了进行文章id压缩，压缩之后采取跳跃表技术进行快速查找定位。

       根据用户输入内容分词，基于分词会做相应拓展同义词、近义词、拼音等，可以很快找到词下文章，拉取词下文章id、词频根据TF-IDF算法、BM25算法对文档相关度进行重排序，排序后按高到低返回top10，完成一次搜索查询。

       文章去掉算法架构实现，着重讲述搜索引擎核心过程，以便掌握核心，为后续进行继续深入学习理解搜索引擎打下坚实基础。

        文中图片来自于《这就是搜索引擎》作者张俊林，书对搜索引擎讲的深入浅出，简明扼要，是学习搜索引擎必备书籍，对搜索引擎技术感兴趣读者可以买来看。