我尝试使用现有的模糊库，如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}]

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

令我震惊的是，与“起始前缀”完全匹配或接近匹配的东西 Levenshtein-Demerau 没有给予特别重视——但您明显的用户期望会。

我搜索了“比 Levenshtein 更好”，其中包括：

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

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

1. 最长公共子串距离：必须在两个字符串中删除的最小符号数，直到生成的子串相同。

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

3. Jaccard 距离： 1 减去共享 N-gram 和所有观察到的 N-gram 的商。

也许您可以使用这些指标的加权组合（或最小值），以及 Levenshtein——共同子串、共同 N-gram 或 Jaccard 都会强烈喜欢相似的字符串——或者也许尝试只使用 Jaccard？

根据列表/数据库的大小，这些算法的成本可能适中。对于我实现的模糊搜索，我使用了可配置数量的 N-gram 作为来自数据库的“检索键”，然后运行昂贵的字符串距离度量以按偏好顺序对它们进行排序。

我写了一些关于 SQL 中模糊字符串搜索的笔记。看：

• http://literatejava.com/sql/fuzzy-string-search-sql/

这是我使用过几次的技术……它给出了非常好的结果。虽然不做你要求的一切。此外，如果列表很大，这可能会很昂贵。

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_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

还有....有一个小提琴

确保您的控制台已打开，否则您将看不到任何内容:)

这是我用于模糊匹配的简短而紧凑的函数：

function fuzzyMatch(pattern, str) {
  pattern = '.*' + pattern.split('').join('.*') + '.*';
  const re = new RegExp(pattern);
  return re.test(str);
}

你可以看看 Atom 的https://github.com/atom/fuzzaldrin/lib。

它在 npm 上可用，具有简单的 API，对我来说还可以。

> fuzzaldrin.filter(['international', 'splint', 'tinder'], 'int');
< ["international", "splint"]