一、倒排索引原理

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

  1. 正向索引

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

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

    分布式搜索引擎ElasticSearch之高级运用(三)-LMLPHP

  2. 倒排索引

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

    分布式搜索引擎ElasticSearch之高级运用(三)-LMLPHP

    倒排索引表结构, 去除停用词后构造的倒排索引:

    elasticsearch 1,3
    最流行 1,2
    搜索引擎 1
    ...

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

    分布式搜索引擎ElasticSearch之高级运用(三)-LMLPHP

  3. 如何定位

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

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

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

    term index 是b-tree结构:

    分布式搜索引擎ElasticSearch之高级运用(三)-LMLPHP

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

    分布式搜索引擎ElasticSearch之高级运用(三)-LMLPHP

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

二、评分TF/IDF/BM25计算

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

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

    某个词出现越多,表示越重要,如果某篇文章出现了elasticsearch多次, 而spring出现了两三次, 那很可能就是一篇关于elasticsearch的专业文章。

  2. IDF: Inverse Document Frequency,即逆文档频率,它是一个表达词语重要性的指标。计算公式:

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

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

  3. BM25

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

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

    分布式搜索引擎ElasticSearch之高级运用(三)-LMLPHP

  4. 查看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创作分享,如需进一步交流,请加QQ群:19310171或访问www.softart.cn

04-08 12:59