共计 3086 个字符,预计需要花费 8 分钟才能阅读完成。
fuzzy 在 es 中能够了解为含糊查问,搜寻自身很多时候是不准确的,很多时候咱们须要在用户的查问词中有局部谬误的状况下也能召回正确的后果,然而计算机无法了解自然语言,因而咱们只能通过一些算法代替语言理解能力实现相似的事件,前缀查问的实现比较简单但成果很难令人满意,就含糊查问而言 es 的 fuzzy 实现了一种复杂度和成果比拟折中的查问能力。
字符的类似度 - 编辑间隔
编辑间隔是对两个字符串差别长度的量化,及一个字符至多须要解决多少次能力变成另一个字符,比方 lucene 和 lucece 只差了一个字符他们的编辑间隔是 1。
- 莱文斯坦间隔(Levenshtein distance)
编辑间隔的一种,指两个字符串之间,由一个转成另一个所需的起码编辑操作次数。
容许的编辑包含:
- 将一个字符替换成另一个字符
- 插入一个字符
- 删除一个字符
- 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 跟踪得出以下论断:
- Lucene 的 fuzzy 查问是通过 query 改写实现的,查问时会将倒排索引词典中的 term 汇合和查问 term 做编辑间隔计算,获取 topN 个间隔最小的 term 作为 query 改写的词,这 N 个词会组成一组或查问,即改写为 boolean query (改写词作为 term query 放在 should clause)
max_expansions
影响的是这里的或查问的元素数目,实际上这个数目会被两个参数影响,另外一个是indices.query.bool.max_clause_count
,最终取indices.query.bool.max_clause_count
和max_expansions
的最小值- 倒排中的 term 总数会影响 fuzzy 查问的性能,term 越多性能越差,文档总数不是影响 fuzzy 查问性能的关键因素。
- 值得注意的是分词后的 term 自身也算一次
max_expansions
计数,也就是说max_expansions=1
时相当于不扩大(分词 term 级准确查问) max_expansions
是作用在分片级参数,如果分片数比拟多的话,查问后果看起来和max_expansions
设置数目不统一也是失常的
-
transpositions
将相邻地位字符调换算作一次编辑间隔,如 ab -> ba,即应用 Damerau–Levenshtein 间隔算法,默认开启,设置 transpositions=false
将应用经典莱文斯坦间隔算法。
-
minimum_should_match 的作用机制
minimum_should_match
作用在分词后的 term 级,即分词后的 term 无论是通过准确查找或者含糊查找命中算且算一次计数,对于同一个 term 扩大进去的 term1、term2 不做反复计数。- 当 operator 为 and 时,
minimum_should_match >0
时会导致查不到后果,这是因为minimum_should_match
的计算方法是 should clause 命中的个数,operator 为 and 时无 should clause 命中数永远不会 >0,所以无后果。参见 BooleanWeight.java#L390 -
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.0
- 非强匹配权重算法为
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"
}
}
}
}
参考文档
- 编辑间隔算法实现 http://blog.notdot.net/2010/0…
- lucene fuzzy 查问优化 http://blog.mikemccandless.co…
- ES 含糊搜寻介绍 fuzzy search
- https://elastic-search-in-act…
- https://livebook.manning.com/…
- 用 Lucene 实现 fuzzy search
)
本文首发于简书