有意义的Javascript模糊search
我正在寻找一个模糊searchJavaScript库来过滤一个数组。 我试过使用fuzzyset.js和fuse.js ，但结果是可怕的（有演示你可以尝试在链接的页面）。
在对Levenshtein距离进行了一些阅读之后，我觉得这是对用户input内容的一种不好的估计。 对于那些不知道的人，系统会计算出两个string匹配需要多less个插入 ， 删除和replace 。
在Levenshtein-Demerau模型中固定的一个明显的缺陷是blub和boob被认为与bulb相似（每个都需要两个replace）。 然而，很清楚的是， 灯泡比胸部更接近巴巴 ，我刚才提到的模型认识到，允许换位 。
我想在文本完成的情况下使用它，所以如果我有一个数组['international', 'splint', 'tinder'] ，我的查询是int ，我认为国际应该比夹板更高，甚至尽pipe前者的得分（较高=较差）为10，而后者为3。
所以我正在寻找（如果不存在，将会创build）是一个库，它执行以下操作：
- 权衡不同的文本操作
- 每个操作的权重取决于它们在单词中出现的位置（早期操作比后期操作更昂贵）
- 返回按相关性sorting的结果列表
有没有人遇到过这样的事情？ 我意识到，StackOverflow不是要求软件推荐的地方，而是隐含的（不再是！）在上面是：我想这是正确的方式吗？
编辑
我find了关于这个问题的好文章（pdf） 。 一些笔记和摘录：
仿射编辑距离函数为插入或删除序列分配相对较低的成本
Monger-Elkan距离函数（Monge＆Elkan 1996）是Smith-Waterman距离函数的仿射变体（Durban et al。1998），具有特定的成本参数
对于Smith-Waterman距离（维基百科） ，“Smith-Watermanalgorithm不是查看总序列，而是比较所有可能长度的片段，并优化相似性度量。 这是n-gram方法。
一个非基于编辑距离模型的广泛相似的度量是Jaro度量（Jaro 1995; 1989; Winkler 1999）。 在logging连接文献中，使用这种方法的变体已经获得了良好的结果，该变体基于两个string之间的共同字符的数量和顺序。
由于Winkler（1999）的这种变化也使用了最长公共前缀的长度P.
（似乎主要用于短string）
为了完成文本，Monger-Elkan和Jaro-Winkler方法似乎是最有意义的。 温克勒对Jaro度量的join有效地加重了单词的开始。 而Monger-Elkan的亲切的方面意味着完成一个单词（这只是一系列加法）的必要性不会太过分。
结论：
在几个基于令牌的距离度量中TFIDF排名performance最好，Monge和Elkan提出的调整后的仿射间距编辑距离度量在几个string编辑距离度量中performance最好。 一个令人惊讶的好距离度量是一个快速启发式scheme，由Jaro提出，后来由Winkler进行了扩展。 这种方法几乎和Monge-Elkanscheme一样，但速度要快一个数量级。 结合TFIDF方法和Jaro-Winkler的一个简单方法是用基于Jar-Winklerscheme的近似令牌匹配replaceTFIDF中使用的确切的令牌匹配。 平均来说，这个组合的performance稍好于Jaro-Winkler或TFIDF，偶尔performance会好得多。 在本文中考虑的几个最好的度量的学习组合也是接近的。
好问题！ 但我的想法是，而不是试图修改Levenshtein-Demerau，你可能会更好地尝试一种不同的algorithm或组合/加权两个algorithm的结果。
我觉得与Levenshtein-Demerau没有特别的分量的“起始前缀”的确切或近似匹配 – 但是你明显的用户期望会。
我search“比Levenshtein更好”，除其他外，发现这一点：
http://www.joyofdata.de/blog/comparison-of-string-distance-algorithms/
这提到了一些“string距离”措施。 三个看起来与你的要求特别相关的将是：
-
最长公共子string距离：两个string中必须删除的符号的最小数量，直到得到的子string完全相同。
-
q-gram距离：两个string的N-gram向量之间绝对差值的总和。
-
雅克卡尔距离： 1分钟共享N-grams和所有观测N-grams的商。
也许你可以使用这些度量的加权组合（或最小），与Levenshtein-普通的子string，普通的N-gram或Jaccard都强烈喜欢相似的string – 或者也许尝试只使用Jaccard？
根据你的列表/数据库的大小，这些algorithm可能是相当昂贵的。 对于我实现的模糊search，我使用了可configuration数量的N-gram作为数据库中的“检索关键字”，然后运行昂贵的string距离度量来按优先顺序对它们进行sorting。
我在SQL中的模糊stringsearch上写了一些注释。 看到：
这是一个我已经使用过几次的技术…它给出了相当不错的结果。 虽然没有做你所要求的一切。 另外，如果名单很大，这可能是昂贵的。
get_bigrams = (string) -> s = string.toLowerCase() v = new Array(s.length - 1) for i in [0..v.length] by 1 v[i] = s.slice(i, i + 2) return v string_similarity = (str1, str2) -> if str1.length > 0 and str2.length > 0 pairs1 = get_bigrams(str1) pairs2 = get_bigrams(str2) union = pairs1.length + pairs2.length hit_count = 0 for x in pairs1 for y in pairs2 if x is y hit_count++ if hit_count > 0 return ((2.0 * hit_count) / union) return 0.0
将两个string传递给string_similarity ，这将返回一个介于0和1.0之间的数字，具体取决于它们的相似程度。 这个例子使用Lo-Dash
用法示例….
query = 'jenny Jackson' names = ['John Jackson', 'Jack Johnson', 'Jerry Smith', 'Jenny Smith'] results = [] for name in names relevance = string_similarity(query, name) obj = {name: name, relevance: relevance} results.push(obj) results = _.first(_.sortBy(results, 'relevance').reverse(), 10) console.log results
另外….有小提琴
确保你的控制台是开放的或你不会看到任何东西:)
你可以看看Atom的https://github.com/atom/fuzzaldrin/ lib。
它在npm上可用，具有简单的API，并为我工作得很好。
> fuzzaldrin.filter(['international', 'splint', 'tinder'], 'int'); < ["international", "splint"]
(function (int) { $("input[id=input]") .on("input", { sort: int }, function (e) { $.each(e.data.sort, function (index, value) { if ( value.indexOf($(e.target).val()) != -1 && value.charAt(0) === $(e.target).val().charAt(0) && $(e.target).val().length === 3 ) { $("output[for=input]").val(value); }; return false }); return false }); }(["international", "splint", "tinder"]))
jsfiddle.net/guest271314/QP7z5/
我尝试使用像fuse.js这样的现有模糊库，并且发现它们很糟糕，所以我写了一个基本类似于sublime的search的东西。 https://github.com/farzher/fuzzysort
唯一的错字是转置。 它非常稳定（1k星，0期） ， 速度非常快 ，可以轻松处理您的情况：
fuzzysort.go('int', ['international', 'splint', 'tinder']) // [{highlighted: '*int*ernational', score: 10}, {highlighted: 'spl*int*', socre: 3003}]
