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/07/Damn-Cool-Algorithms-Levenshtein-Automata
2. lucene fuzzy查询优化 http://blog.mikemccandless.com/2011/03/lucenes-fuzzyquery-is-100-times-faster.html
3. ES模糊搜索介绍 fuzzy search
4. https://elastic-search-in-action.medcl.com/3.site_search/3.3.search_box/fuzzy_query/
5. https://livebook.manning.com/book/taming-text/chapter-4/3
6. 用Lucene实现fuzzy search