fuzzy在es中能够了解为含糊查问，搜寻自身很多时候是不准确的，很多时候咱们须要在用户的查问词中有局部谬误的状况下也能召回正确的后果，然而计算机无法了解自然语言，因而咱们只能通过一些算法代替语言理解能力实现相似的事件，前缀查问的实现比较简单但成果很难令人满意，就含糊查问而言es的fuzzy实现了一种复杂度和成果比拟折中的查问能力。

字符的类似度-编辑间隔

编辑间隔是对两个字符串差别长度的量化，及一个字符至多须要解决多少次能力变成另一个字符，比方lucene和lucece只差了一个字符他们的编辑间隔是1。

  • 莱文斯坦间隔(Levenshtein distance)

编辑间隔的一种，指两个字符串之间，由一个转成另一个所需的起码编辑操作次数。
容许的编辑包含：

  1. 将一个字符替换成另一个字符
  2. 插入一个字符
  3. 删除一个字符
  • Damerau–Levenshtein distance

莱文斯坦间隔的一个扩大版 ，将相邻地位的两个字符的调换当做一次编辑，而在经典的莱文斯坦间隔计算中地位调换是2次编辑。

ElasticSearch反对经典的Levenshtein间隔和Damerau-Levenshtein间隔，在es中对含糊查问的反对有两种形式match query和fuzzy query。

match query

应用形式如下所示：

GET index_name/_search{  "query": {    "match": {      "name": {        "query": "elastic search",        "fuzziness": 0,        "prefix_length": 0,        "max_expansions": 50,        "transpositions": true      }    }  }}

上面对他反对的参数进行一些介绍：

  • fuzziness

本次查问容许的最大编辑间隔，默认不开启含糊查问，相当于fuzziness=0。

反对的格局

  • 能够是数字（0、1、2）代表固定的最大编辑间隔

  • 主动模式，AUTO:[low],[high]的格局，含意为：

    • 查问词长度在[0-low)范畴内编辑间隔为0（即强匹配)
    • [low, high)范畴内容许编辑一次

    • \>high容许编辑2次

      也能够只写AUTO代表默认的主动模式，相当于AUTO:3,6

  • prefix_length

管制两个字符串匹配的最小雷同的前缀大小，也即是前n个字符不容许编辑，必须与查问词雷同，默认是0，大于0时能够显著晋升查问性能，须要留神的是这里的 prefix_length作用在分词后的 term 级，也就是作用在每个分词的词根上而不是整个查问词上，对于下面的例子 elastic search 来说就是须要 elastic 和 search 都会严格匹配前两个字符来召回，是不是很意外。

  • max_expansions

这个参数比拟蛊惑，查问了相当的文档都对这个参数模糊不清，通过对Lucene源码的debug跟踪得出以下论断：

  1. Lucene的fuzzy 查问是通过query改写实现的，查问时会将倒排索引词典中的term汇合和查问term做编辑间隔计算，获取topN个间隔最小的term作为query改写的词，这N个词会组成一组或查问，即改写为boolean query (改写词作为term query放在should clause)
  2. max_expansions影响的是这里的或查问的元素数目，实际上这个数目会被两个参数影响，另外一个是indices.query.bool.max_clause_count，最终取indices.query.bool.max_clause_count和max_expansions的最小值
  3. 倒排中的term总数会影响fuzzy查问的性能，term越多性能越差，文档总数不是影响fuzzy查问性能的关键因素。
  4. 值得注意的是分词后的term自身也算一次max_expansions计数，也就是说 max_expansions=1 时相当于不扩大（分词term级准确查问）
  5. max_expansions 是作用在分片级参数，如果分片数比拟多的话，查问后果看起来和max_expansions设置数目不统一也是失常的
  • transpositions

将相邻地位字符调换算作一次编辑间隔，如 ab -> ba，即应用Damerau–Levenshtein间隔算法，默认开启，设置 transpositions=false将应用经典莱文斯坦间隔算法。

  • minimum_should_match 的作用机制
  1. minimum_should_match作用在分词后的term级，即分词后的term无论是通过准确查找或者含糊查找命中算且算一次计数，对于同一个term扩大进去的term1、term2不做反复计数。
  2. 当operator 为 and 时，minimum_should_match >0 时会导致查不到后果，这是因为minimum_should_match的计算方法是should clause命中的个数，operator为and时无should clause命中数永远不会 >0，所以无后果。参见BooleanWeight.java#L390

  3. minimum_should_match为百分比时ES的计算方法

    float calc = (shouldClauseCount * percent) * (1 / 100f); // shouldClauseCount为分词后的词根个数，percent为传参的百分比result = calc < 0 ? shouldClauseCount + (int) calc : (int) calc; //

    Fuzzy query

fuzzy query用法和match基本一致，参数也蕴含fuzziness、prefix_length、max_expansions、transpositions，惟一的不同点是Fuzzy query的查问不分词。应用形式如下：

GET /test-mapping/_search{  "query": {    "fuzzy": {      "name": {        "value": "elastic",        "fuzziness": 0,        "prefix_length": 0,        "max_expansions": 50,        "transpositions": true      }    }  }}

排序

默认为相关性算分倒序，fuzzy查问过程会改写含糊词查问term权重，编辑间隔越大权重越小
query改写过程权重调整细节为：

  1. 强匹配权重为1.0
  2. 非强匹配权重算法为 1.0 - (编辑间隔 / min(倒排term长度, 查问term长度))

权重调整源码见FuzzyTermsEnum.java#L232
相关性算法默认为bm25，内建几种可供选择的算法及自定义，参见similarity和Similarity module

一个调试小技巧
能够通过将字段的mapping设置为similarity= boolean来查看含糊查问的扩大词的权重，这样查问后果中的打分就是命中该词扩大词的权重

PUT my_index{  "mappings": {    "properties": {      "fuzzy_field": {        "type": "text",        "similarity": "boolean"       }    }  }}

参考文档

  1. 编辑间隔算法实现 http://blog.notdot.net/2010/0...
  2. lucene fuzzy查问优化 http://blog.mikemccandless.co...
  3. ES含糊搜寻介绍 fuzzy search
  4. https://elastic-search-in-act...
  5. https://livebook.manning.com/...
  6. 用Lucene实现fuzzy search
    )

本文首发于简书