乐趣区

关于java:分布式搜索引擎ElasticSearch之高级运用三

jiezi

一、倒排索引原理

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

  1. 正向索引

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

    然而在查问某一个 keyword 存在于哪些文档的时候，须要对所有文档进行扫描匹配。这样检索效率比拟低下。

  2. 倒排索引

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

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

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

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

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

  3. 如何定位

    对于规模很大的文档汇合，外面可能蕴含上百万的要害单词（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，大大减少了磁盘随机读的次数。

二、评分 TF/IDF/BM25 计算

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

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

    TF = 某个词在文档中呈现的次数 / 文档的总词数

    某个词呈现越多，示意越重要，如果某篇文章呈现了 elasticsearch 屡次，而 spring 呈现了两三次，那很可能就是一篇对于 elasticsearch 的业余文章。

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

    IDF=log(库中的文档数/(蕴含该词的文档数 +1))

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

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

  3. BM25

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

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

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

  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 创作分享，感激大家的反对，心愿对大家有所播种!
入群申请，请加 WX 号：woodblock99

退出移动版