有意义的Javascript模糊搜索

Question

我正在寻找一个模糊搜索JavaScript库来过滤数组.我已经尝试过使用fuzzyset.js和fuse.js,但结果非常糟糕(你可以尝试在链接页面上进行演示).

在对Levenshtein距离进行一些阅读之后,它让我感到很难接近用户在打字时所寻找的内容.对于那些不知道的人,系统会计算需要多少插入,删除和替换才能使两个字符串匹配.

在Levenshtein-Demerau模型中固定的一个明显的缺陷是blub和boob被认为与灯泡同样相似(每个需要两次替换).然而,很明显,灯泡更像blub而不是bob,而我刚才提到的模型通过允许换位来识别它.

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

所以我正在寻找(并且如果它不存在则会创建),是一个执行以下操作的库:

• 权衡不同的文本操作
• 每个操作的权重取决于它们在单词中出现的位置(早期操作比后期操作更昂贵)
• 返回按相关性排序的结果列表

有没有人遇到这样的事情？我意识到StackOverflow不是要求软件推荐的地方,但上面隐含的(不再是!)是:我正在考虑这个正确的方法吗？

---

编辑

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

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

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

对于Smith-Waterman距离(维基百科),"Smith-Waterman算法不是查看总序列,而是比较所有可能长度的片段,并优化相似性度量." 这是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的一种简单方法是使用基于Jaro-Winkler方案的近似令牌匹配替换TFIDF中使用的确切令牌匹配.这种组合平均比Jaro-Winkler或TFIDF略好,并且偶尔表现得更好.对于本文中考虑的几个最佳指标的学习组合,它的性能也很接近.

Answer 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}]

Answer 2

好问题!但我的想法是,不是试图修改Levenshtein-Demerau,你可能最好尝试不同的算法,或者将两个算法的结果组合/加权.

令我感到震惊的是,对于"起始前缀"的精确或接近匹配是Levenshtein-Demerau没有给予特别重视的东西 - 但是你明显的用户期望会.

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

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

这提到了一些"字符串距离"措施.三个看起来与您的要求特别相关的是:

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

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

3. Jaccard距离: 1分钟的共享N-gram和所有观察到的N-gram的商数.

也许你可以使用这些指标的加权组合(或最小值),Levenshtein - 常见的子串,普通的N-gram或Jaccard都会非常喜欢类似的字符串 - 或者可能只是尝试使用Jaccard？

根据列表/数据库的大小,这些算法可能会非常昂贵.对于我实现的模糊搜索,我使用可配置数量的N-gram作为来自DB的"检索关键字"然后运行昂贵的字符串距离度量以按优先顺序对它们进行排序.

我在SQL中写了一些关于模糊字符串搜索的注释.看到:

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

Answer 3

我修复了 InternalFx 的 CoffeeScript 二元组解决方案的问题，并将其设为通用的 n 元组解决方案（您可以自定义克的大小）。

这是 TypeScript，但您可以删除类型注释，它也可以像普通 JavaScript 一样正常工作。

/**
 * Compares the similarity between two strings using an n-gram comparison method. 
 * The grams default to length 2.
 * @param str1 The first string to compare.
 * @param str2 The second string to compare.
 * @param gramSize The size of the grams. Defaults to length 2.
 */
function stringSimilarity(str1: string, str2: string, gramSize: number = 2) {
  function getNGrams(s: string, len: number) {
    s = ' '.repeat(len - 1) + s.toLowerCase() + ' '.repeat(len - 1);
    let v = new Array(s.length - len + 1);
    for (let i = 0; i < v.length; i++) {
      v[i] = s.slice(i, i + len);
    }
    return v;
  }

  if (!str1?.length || !str2?.length) { return 0.0; }

  //Order the strings by length so the order they're passed in doesn't matter 
  //and so the smaller string's ngrams are always the ones in the set
  let s1 = str1.length < str2.length ? str1 : str2;
  let s2 = str1.length < str2.length ? str2 : str1;

  let pairs1 = getNGrams(s1, gramSize);
  let pairs2 = getNGrams(s2, gramSize);
  let set = new Set<string>(pairs1);

  let total = pairs2.length;
  let hits = 0;
  for (let item of pairs2) {
    if (set.delete(item)) {
      hits++;
    }
  }
  return hits / total;
}

例子：

console.log(stringSimilarity("Dog", "Dog"))
console.log(stringSimilarity("WolfmanJackIsDaBomb", "WolfmanJackIsDaBest"))
console.log(stringSimilarity("DateCreated", "CreatedDate"))
console.log(stringSimilarity("a", "b"))
console.log(stringSimilarity("CreateDt", "DateCreted"))
console.log(stringSimilarity("Phyllis", "PyllisX"))
console.log(stringSimilarity("Phyllis", "Pylhlis"))
console.log(stringSimilarity("cat", "cut"))
console.log(stringSimilarity("cat", "Cnut"))
console.log(stringSimilarity("cc", "Cccccccccccccccccccccccccccccccc"))
console.log(stringSimilarity("ab", "ababababababababababababababab"))
console.log(stringSimilarity("a whole long thing", "a"))
console.log(stringSimilarity("a", "a whole long thing"))
console.log(stringSimilarity("", "a non empty string"))
console.log(stringSimilarity(null, "a non empty string"))

在 TypeScript Playground 中尝试一下

Answer 4

这是我用了几次的技术......它给出了相当不错的结果.不会做你要求的一切.此外,如果列表很大,这可能会很昂贵.

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

还....有一个小提琴

确保你的控制台是打开的,否则你什么都看不到:)

Answer 5

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

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

Answer 6

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

它在npm上可用,具有简单的API,并且对我来说工作正常.

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

Answer 7

我多年来一直喜欢模糊匹配，并且刚刚遇到了这个线程。这里的对话比大多数对话更深入，并且看起来涉及到实施者。多年来，我用不同的语言编写了其中几种算法，并希望向编写 JS 版本的任何人传递一些技巧：

蒙日-埃尔坎统治！

这真是太棒了，它将 n 元语法的许多优点与最好的短字符串比较算法（例如 Jaro-Winkler）相结合。（这就是我在 Monge-Elkan 代码中使用的方法。）几年前，我偶然发现了一篇论文，您可以在网上找到 PDF 格式的论文，名为“用于近似文本字符串比较的通用 Mongue-Elkan 方法”。要点是，不要使用算术平均值，而是使用二次平均值。我尝试了一下，它对各种文本的搜索结果有了显着的改进。

N 元语法规则！

在各种源语言和文本类型上都具有非常强大、高质量的性能。如果您正在查看数据库，则可以在 Postgres 中将其实现为高质量、快如闪电的索引 K-NN 搜索。它需要正确排列一些不同的功能，但这还不错。

无论如何，在分割 n 元语法时，有不同的方法来处理前端填充。就像，如果你有一个传统的n ( q或k ) 3，那么你会像这样分割 'ander'

'  a'
' an'
'and'
'nde'
'der'
'er '
'r  '

或者

'  a'
' an'
'and'
'nde'
'der'

或者

'and'
'nde'
'der'

本能地，我一直期望第一个列表效果最好，但实际上，它可能是第二个或第三个。值得尝试一下填充和窗口规则，看看它们在您的上下文中的表现如何。很少有库提供对此行为的控制，这将是一个很好的支持功能。暗示。