简答
我想你正在寻找的是模糊查询,它使用编辑距离匹配相似单词的算法。
nGrams 的长答案
nGram 过滤器根据定义的最小/最大范围将文本分割成许多较小的标记。
例如,过滤器将根据您的“音乐”查询生成:'mu', 'us', 'si', 'ic', 'mus', 'usi', 'sic', 'musi', 'usic', and 'music'
如你看到的musiic
与这些 nGram 标记中的任何一个都不匹配。
为什么选择 nGram
nGrams 的好处之一是它可以进行通配符查询显著地更快,因为所有潜在的子字符串都是在插入时预先生成和索引的(我已经看到使用 nGrams 的查询速度从几秒加速到 15 毫秒)。
如果没有 nGrams,则必须在查询时搜索每个字符串以查找匹配项 [O(n^2)],而不是直接在索引中查找 [O(1)]。作为伪代码:
hits = []
foreach string in index:
if string.substring(query):
hits.add(string)
return hits
vs
return index[query]
请注意,这是以插入速度变慢、需要更多存储空间以及占用更多内存为代价的。