倒排索引原理_搜索引擎都在用的倒排索引——原理与实现

倒排索引（Inverted index），个人理解倒排的意思是说，普通的搜索算法，是从文档里搜索一个关键词（文档→关键词），而倒排索引是首先知道了每个关键词都出现在了哪些文档里，从关键词搜文档（关键词→文档），正好目的反过来，和“颠倒搜索”没什么关系。

想象一个场景，你要对一个很大的文件搜索其中是否有一个关键词，常规的做法是遍历整个文档，那么如果关键词在文档最后，就会非常慢

倒排索引先记录了每个关键词出现在了哪些文档里，需要哪个关键词，把含有的文档直接拎出来就可以，这样就快多了

主流的搜索工具，ElasticSearch都是基于倒排索引的方式

举个栗子，假设我们有如下0-4五个文档

分词后可以得到这16个关键词，倒排列表中记录的是那些文档包含这个关键词

自己实现一个倒排，个人感觉需要注意一下模糊搜索的问题和匹配算法的设计，在使用ES时，虽然这些已经做好了，但是感觉有时效果不佳，具体实现机制还需要再研究。

模糊匹配

我们应该希望系统具有这样的能力

匹配缩写：搜索 UK ，会返回包含 United Kindom 的文档
匹配词根：搜索 jump ，会匹配 jumped ， jumps
匹配同义词：搜索 johnny walker 会匹配 Johnnie Walker ，搜索 people ，会返回包含 person 的文档
理解语境：搜索fox news hunting 应该返回福克斯新闻（ Foxs News ）中关于狩猎的故事，而搜素so fox hunting news 应该返回关于猎狐的故事

要使得系统能够坐到这一点，就需要在分词阶段，对词条进行规范，真实场景下，很多时候并不能实现两个token之间的完美匹配，这时基于token的匹配就失去的作用

自己在使用ES的过程中，普通的匹配无法做到对单复数这种简单情况的处理，或许在建立索引是有一些操作，还需要继续研究

匹配算法设计

如何设计一个合理的匹配算法也是值得研究的问题，如何给搜索结果打分。

例如一个文档，我们用大写字母表示词条，大写字母组成的字符串表示一个文档，对于一个关键词CDEF，匹配算法应该能够对于这几种情况给出不同的分数

匹配到不同数量的词条的得分应该是不一样的
比如有的匹配到CDF三个，有的只匹配到CD两个，通常是匹配更多数量的分数应该更高
匹配到相同数量的词条得分应该是不一样的
比如都是匹配到三个词条，一个是CDE，一个是DEF，如果C是一个类似频繁项的词条，F是一个对文档比较重要的词条，那么后者的的风应该更高

匹配到相同的词条列表的得分应该是不一样的
比如都是匹配到CDE三个词条，有的是连续出现的（ABCDEFG），有的是分开出现（ABCGDFE）或者顺序不同(ABCEDFG)，他们的得分应该是不同的。
另外从搜索的意图上看

如果搜索的关键词是一个专有名词
一些专有名词本质上就是不可分割的(New York不能看成New和York)
一些专有名词去掉其中一些token或改变顺序也并不影响词义（University of Pittsburgh和Pittsburgh university）。

2. 如果搜索仅仅是几个关键词的组合，比如平时使用搜索引擎的场景，那么每个token都是独立的可以以任意顺序在文档中出现。