ElasticSearch 倒排索引（Inverted Index）| 什么是倒排索引？

末蓝、 2021-10-18 21:58 431阅读 0赞

## 什么是倒排索引？ ##

ElasticSearch中一个重要的概念 ： `倒排索引（Inverted Index）也叫反向索引`，有反向索引必有正向索引。通俗地来讲，正向索引是通过key找value，反向索引则是`通过value找key`。  
![在这里插入图片描述][20190813105401429.png]  
首先弄懂几个概念，如果类比现代汉语词典的话，那么`Term`就相当于`词语`，`Term Dictionary`相当于`汉语词典本身`，`Term Index`相当于词典的`目录索引`，`Posting List`相当于`词语在字典的页数集合`：

*  **Term（单词）**：一段文本经过分析器分析以后就会输出一串单词，这一个一个的就叫做Term（直译为：单词）
 *  **Term Dictionary（单词字典）**：顾名思义，它里面维护的是Term，可以理解为Term的集合
 *  **Term Index（单词索引）**：为了更快的找到某个单词，我们为单词建立索引。B-Tree通过减少磁盘寻道次数来提高查询性能，Elasticsearch也是采用同样的思路，直接通过内存查找term，不读磁盘，但是如果term太多，term dictionary也会很大，放内存不现实，于是有了Term Index，就像字典里的索引页一样，A开头的有哪些term，分别在哪页，可以理解term index是一颗树：![在这里插入图片描述][2019081310525064.png]
 *  **Posting List（倒排列表）**：倒排列表记录了出现过某个单词的所有文档的文档列表及单词在该文档中出现的位置信息，每条记录称为一个倒排项(Posting)。根据倒排列表，即可获知哪些文档包含某个单词。（PS：实际的倒排列表中并不只是存了文档ID这么简单，还有一些其它的信息，比如：词频（Term出现的次数）、偏移量（offset）等，可以想象成是Python中的元组，或者Java中的对象）

## 倒排DEMO ##

{ "doc_id"="1","hospitalName":"北京大学第三附属医院"}
    { "doc_id"="2","hospitalName":"北京协和医院"}
    { "doc_id"="3","hospitalName":"解放军总医院第一附属医院"}
    { "doc_id"="4","hospitalName":"Peking University Third Hospital"}
    { "doc_id"="5","hospitalName":"Peking Union Medical College Hospital"}

\*.`<?>`部分等你一边思考一边补充：

<table> 
 <thead> 
  <tr> 
   <th>Term ID / 单词ID</th> 
   <th>Term / 单词</th> 
   <th>Posting List /倒排列表(出现的id:位置:次数)</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>1</td> 
   <td>医院</td> 
   <td>(1:&lt;8&gt;:1),(2:&lt;4&gt;:1),(3:&lt;4&gt;:2)</td> 
  </tr> 
  <tr> 
   <td>2</td> 
   <td>北京</td> 
   <td>(1:&lt;0&gt;:1),(2:&lt;0&gt;:1)</td> 
  </tr> 
  <tr> 
   <td>3</td> 
   <td>北京大学</td> 
   <td>(1:&lt;0&gt;:1)</td> 
  </tr> 
  <tr> 
   <td>4</td> 
   <td>第三</td> 
   <td>(1:&lt;4&gt;:1)</td> 
  </tr> 
  <tr> 
   <td>5</td> 
   <td>附属</td> 
   <td>(1:&lt;6&gt;:1),(3:&lt;8&gt;:1)</td> 
  </tr> 
  <tr> 
   <td>6</td> 
   <td>协和</td> 
   <td>(2:&lt;?&gt;:1)</td> 
  </tr> 
  <tr> 
   <td>7</td> 
   <td>解放军</td> 
   <td>(3:&lt;?&gt;:1)</td> 
  </tr> 
  <tr> 
   <td>8</td> 
   <td>第一</td> 
   <td>(3:&lt;?&gt;:1)</td> 
  </tr> 
  <tr> 
   <td>9</td> 
   <td>总</td> 
   <td>(3:&lt;?&gt;:1)</td> 
  </tr> 
 </tbody> 
</table>

## 标准化规则（normalization）&命中率问题 ##

为解决词条检索时词条`命中率`，ES在建立倒排索引时运用`标准化规则`即针对存储的索引词条进行一些相关`预处理`再作为索引进行存储。

例如：通常情况下，在搜索 `Third` 、 `Hospital` 这两个单词时候，文档4两个单词都出现了，计数为2；文档5只有 `Hospital` 这个单词出现了，计数为1，所以Total之后，文档4命中率高，排名靠前。

<table> 
 <thead> 
  <tr> 
   <th>Term</th> 
   <th>doc_id=4</th> 
   <th>doc_id=5</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>Third</td> 
   <td>1</td> 
   <td>0</td> 
  </tr> 
  <tr> 
   <td>Hospital</td> 
   <td>1</td> 
   <td>1</td> 
  </tr> 
  <tr> 
   <td>Peking</td> 
   <td>1</td> 
   <td>1</td> 
  </tr> 
  <tr> 
   <td>Total</td> 
   <td>3</td> 
   <td>2</td> 
  </tr> 
 </tbody> 
</table>

但是这样搜索就会存在下列问题：

1.  `Third` 与 `third` 用户认为是相同单词，但是首字母小写可能搜不到内容。
2.  `hospitals` 与 `hospital` 有相同的词根，如果存储了 `hospitals` ，那么 `hospital` 可能检索不到 。
3.  `piking` 与 `beijing` 为相同意思的词，如果存储了 `piking` ， `beijing` 可能检索不到。

基于以上问题，ES在建立倒排索引时，会对拆分的各个单词进行相应处理，以提升后面搜索的时候能够搜索到相关联的文档的概率，这就是标准化规则转换，主要包括：时态的转换（例如liked转换为like）、单复数的转换（hospitals转换为hospitals）、同义词的转换（small转换为little）、大小写的转换（默认转换为小写）。

## 标准分词器standard analyzer ##

standard analyzer 标准分词器中做的操作，跟标准化规则有一定关联：

*  standard tokenizer：以`单词边界`进行切分
 *  standard token filter：什么都不做
 *  lowercase token filter：`将所有字母转换为小写`（by normalization）
 *  stop token filer（默认被禁用）：`移除停用词`，比如a the it等等

## 相关度分数score的计算 ##

当利用ES进行查询时，查询结果都会返回一个对应词条的`相关度分数（score）`。相关度分数的计算基于TF/IDF算法（Term Frequence&Inverse Doucument Frequency），翻译大意为：词条在文档中出现的频率及在倒排索引中出现的频率。

1.  Term Frequence ，TF(t in f)：`我们查询的词条在文本中出现多少次，出现次数越多，相关度越高`。例如：前面所列医院信息文档中，“医院”，“北京大学”这两个单词，在第1文档中都出现了，但是第2和第3个文档只出现了“医院”，所以第1个相关度分数高。
2.  Inverse Doucument Frequency，IDF(t in all-f)：`查询词条在所有文本中出现的次数，出现次数越高，相关度越低`。例如：“医院”在3个文档中出现4次，而“北京大学”出现1次，所以“医院”这个单词的相关度越低。
3.  Field-length(字段长度规约)：`字段的长度越长，相关度越低`。例如：“北京大学第三附属医院”长度大于“北京协和医院”，那么在检索“医院”这个单词时，第二个文档中分数要大于第一个文档的分数。

So，ES相关度分数计算结果直接影响搜索排名顺序，对用户检索命中率有极大的影响。

[20190813105401429.png]: /images/20211018/a8d38eb3eee840ae96a476d924e90aa0.png
[2019081310525064.png]: /images/20211018/b5276195d24a44bba9a1fac68204f0cc.png