有意义的Javascript模糊搜索
我正在寻找一个模糊搜索JavaScript库来过滤数组。我尝试过使用fuzzyset.js和fuse.js,但结果很糟糕(您可以在链接的页面上尝试演示)。
在对Levenshtein距离进行了一些阅读之后,它给我的印象是用户在打字时正在寻找什么的近似值很差。对于那些不知道的人,系统会计算需要多少次插入,删除和替换才能使两个字符串匹配。
在Levenshtein-Demerau模型中修复的一个明显缺陷是,blub和boob被认为与灯泡相同(每个都需要两个替换)。然而,很明显,灯泡比胸部更像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,有时表现要好得多。它在性能上也接近本文考虑的几个最佳指标的学习组合。