有意义的Javascript模糊搜索

我正在寻找一个模糊搜索JavaScript库来过滤数组。我尝试过使用fuzzyset.jsfuse.js,但结果很糟糕(您可以在链接的页面上尝试演示)。

在对Levenshtein距离进行了一些阅读之后,它给我的印象是用户在打字时正在寻找什么的近似值很差。对于那些不知道的人,系统会计算需要多少次插入删除替换才能使两个字符串匹配。

在Levenshtein-Demerau模型中修复的一个明显缺陷是,blubboob被认为与灯泡相同(每个都需要两个替换)。然而,很明显,灯泡胸部更像blub,我刚才提到的模型通过允许换位来识别这一点。

我想在文本完成的上下文中使用它,所以如果我有一个数组,并且我的查询是int,我认为国际应该比夹板的排名更高,即使前者的分数(更高=更糟)为10,而后者的得分为3。['international', 'splint', 'tinder']

因此,我正在寻找的(如果它不存在,将创建)是一个执行以下操作的库:

  • 加权不同的文本操作
  • 根据每个操作在单词中出现的位置,对每个操作的权重不同(早期操作比后期操作成本更高)
  • 返回按相关性排序的结果列表

有没有人遇到过这样的事情?我意识到StackOverflow不是要求软件推荐的地方,但上面隐含的(不再是!)是:我是否以正确的方式思考这个问题?


编辑

我找到了一篇关于这个主题的好论文(pdf)。一些注释和摘录:

仿射编辑距离函数为插入或删除序列分配相对较低的成本

Monger-Elkan距离函数(Monge & Elkan 1996),它是Smith-Waterman距离函数(Durban et al. 1998)的仿射变体,具有特定的成本参数

对于史密斯-沃特曼距离(维基百科),“史密斯-沃特曼算法不是查看总序列,而是比较所有可能长度的段并优化相似性度量。这是n-gram方法。

一个大致相似的指标,不是基于编辑距离模型,是Jaro度量(Jaro 1995; 1989;Winkler 1999)。在记录链接文献中,使用这种方法的变体获得了良好的结果,该方法基于两个字符串之间公共字符的数量和顺序。

Winkler(1999)的变体也使用最长的通用前缀的长度P

(似乎主要用于短字符串)

出于文本完成的目的,Monger-Elkan和Jaro-Winkler方法似乎最有意义。Winkler对Jaro度量的添加有效地赋予了单词开头更重的权重。Monger-Elkan的仿射方面意味着完成一个单词(这只是一系列添加)的必要性不会太过分不利。

结论:

TFIDF排名在几个基于令牌的距离指标中表现最好,Monge和Elkan提出的调谐仿射间隙编辑距离指标在几个字符串编辑距离指标中表现最佳。一个令人惊讶的好的距离度量是一种快速启发式方案,由Jaro提出,后来由Winkler扩展。这几乎与Monge-Elkan方案一样有效,但速度快了一个数量级。结合TFIDF方法和Jaro-Winkler的一种简单方法是将TFIDF中使用的精确令牌匹配替换为基于Jaro-Winkler方案的近似令牌匹配。这种组合的平均表现略好于Jaro-Winkler或TFIDF,有时表现要好得多。它在性能上也接近本文考虑的几个最佳指标的学习组合。


答案 1

我尝试使用现有的模糊库,如fuse.js也发现它们很糟糕,所以我写了一个基本上像Sublime的搜索。https://github.com/farzher/fuzzysort

它允许的唯一拼写错误是转置。它非常可靠(1k星,0个问题),非常快,并且可以轻松处理您的情况:

fuzzysort.go('int', ['international', 'splint', 'tinder'])
// [{highlighted: '*int*ernational', score: 10}, {highlighted: 'spl*int*', socre: 3003}]


答案 2

问得好!但我的想法是,与其尝试修改Levenshtein-Demerau,不如尝试不同的算法或组合/加权两种算法的结果。

令我印象深刻的是,与“起始前缀”完全匹配或接近匹配是Levenshtein-Demerau没有特别重视的东西 - 但你明显的用户期望会。

我搜索了“比Levenshtein更好”,除其他外,发现了这个:

http://www.joyofdata.de/blog/comparison-of-string-distance-algorithms/

这提到了许多“字符串距离”度量。与您的要求特别相关的三个是:

  1. 最长公共子字符串距离:在生成的子字符串相同之前,必须在两个字符串中删除的最小符号数。

  2. q-克距离:两个字符串的 N-gram 向量之间的绝对差值之和。

  3. 杰卡德距离:1分钟共享N克和所有观察到的N-克的商。

也许你可以使用这些指标的加权组合(或最小值),与Levenshtein一起使用 - 常见的子字符串,常见的N-gram或Jaccard都会强烈地喜欢类似的字符串 - 或者也许尝试只使用Jaccard?

根据列表/数据库的大小,这些算法的开销可能适中。对于我实现的模糊搜索,我使用可配置的N-gram数作为DB的“检索键”,然后运行昂贵的字符串距离测量以按首选项顺序对它们进行排序。

我在SQL中的模糊字符串搜索上写了一些笔记。看: