2021年03月24日阅读 4

分布式搜索引擎ElasticSearch之高级运用（三）

一、倒排索引原理

ES采用的是倒排索引（Inverted Index）, 也称为反向索引。有反向索引，也会有正向索引。

正向索引

正排索引是以文档的ID作为关键字，并且记录文档中每个字段的值信息，通过查询id来把整条文档拿出来。

但是在查询某一个keyword存在于哪些文档的时候，需要对所有文档进行扫描匹配。这样检索效率比较低下。
倒排索引

倒排索引以字或词作为关键字索引，倒排索引建立的是分词（Term）和文档（Document）之间的映射关系。

倒排索引表结构，去除停用词后构造的倒排索引：

单词文档ID列表
elasticsearch 1，3
最流行 1，2
搜索引擎 1
...

倒排索引主要由单词词典（Term Dictionary）和倒排列表（Posting List）及倒排文件(Inverted File)组成。

**单词词典（Term Dictionary）：**搜索引擎的通常索引单位是单词，单词词典是由文档集合中出现过的所有单词构成的字符串集合。 **倒排列表(PostingList)：**倒排列表记载了出现过某个单词的所有文档的文档列表，以及单词在该文档中出现的位置信息及频率，每条记录称为一个倒排项(Posting)。 **倒排文件(Inverted File)：**所有单词的倒排列表按顺序地存储在磁盘的某个文件里，这个文件即被称之为倒排文件，倒排文件是存储倒排索引的物理文件。
如何定位

对于规模很大的文档集合，里面可能包含上百万的关键单词（term）, 找出某个特定的term就会很慢，需要逐个过滤一遍，如何快速定位？

先做好排序，然后用二分查找的方式，这样比全部遍历方式来得更快，这个就是term dictionary。可以采用logN次磁盘查找获取目标，但是磁盘随机读操作仍然非常昂贵（一次随机读random access 大概需10ms），

所以尽量少读磁盘，但缓存到内存中，整个term dictionary又非常大，于是就有了term index字典的索引。

term index 是b-tree结构：

这棵树不会包含所有的term，它只记录term的一些前缀。通过term index可以快速地定位到term dictionary的某个offset，然后从这个位置再往后顺序查找。

所以term index不需要存储所有的term，而仅仅是他们的一些前缀与Term Dictionary的block之间的映射关系，再结合FST(Finite State Transducers)的压缩技术，可以使term index缓存到内存中。从term index查到对应的term dictionary的block位置之后，再去磁盘上找term，大大减少了磁盘随机读的次数。

单词	文档ID列表
elasticsearch	1，3
最流行	1，2
搜索引擎	1
...

二、评分TF/IDF/BM25计算

每条搜索记录ES都会给出一个评分，ES有两个打分计算方式：

TF: Term Frequency，即词频。它表示一个词在内容中出现的次数。定义：

TF = 某个词在文档中出现的次数／文档的总词数

某个词出现越多，表示越重要，如果某篇文章出现了elasticsearch多次，而spring出现了两三次，那很可能就是一篇关于elasticsearch的专业文章。
IDF: Inverse Document Frequency，即逆文档频率，它是一个表达词语重要性的指标。计算公式：

IDF＝log(库中的文档数／(包含该词的文档数+1))

log为对数函数，如果所有文章内容都包涵某一个词，那这个词的IDF＝log(1)=0, 重要性为零。停用词的IDF约等于0。

如果某个词只在很少的文章中出现，则IDF很大，其重要性也越高。为了避免分母为0，所以＋1.
BM25

BM25 实质是对 TF-IDF 算法的改进，对于 TF-IDF 算法，TF(t) 部分的值越大，整个公式返回的值就会越大。

随着TF(t) 的逐步加大，该算法的返回值会趋于一个数值，BM25 就针对这点进行来优化。

例如，某个文章的关键词出现的频率不断增多，得分就会越来越高，有的文章关键词出现40次，和有的文章关键词出现60次或80次，但实际上出现40次的文章，可能就是所期望的结果。

查看ES评分计算：

增加explain标识为true，会列出计算执行计划：

GET /movies/_search
{
  "explain": true, 
  "query":{
    "match":{
      "title":"heart"
    }
  }
}
复制代码

里面会详细记录评分细则：

...
"_explanation" : {
          "value" : 6.0875173,
          "description" : "weight(title:heart in 276) [PerFieldSimilarity], result of:",
          "details" : [
            {
              "value" : 6.0875173,
              "description" : "score(freq=1.0), computed as boost * idf * tf from:",
              "details" : [
                {
                  "value" : 2.2,
                  "description" : "boost"


    
,
                  "details" : [ ]
                },
                {
                  "value" : 5.8863263,
                  "description" : "idf, computed as log(1 + (N - n + 0.5) / (n + 0.5)) from:",
                  "details" : [
                  ...
复制代码

整个评分计算： boost * idf * tf （boost为放大系数，默认为2.2）

BM25的计算在tf的描述中： (freq + k1 * (1 - b + b * dl / avgdl))

本文由mirson创作分享，感谢大家的支持，希望对大家有所收获! 入群申请，请加WX号：woodblock99