algorithm - “fuzzy matching”字符串的算法

通过模糊匹配，我不是指Levenshtein距离相似的字符串或类似的字符串，而是它在TextMate / Ido / Icicles中的使用方式:给定一个字符串列表，找到那些包含搜索字符串中所有字符的字符串，但可能与其他字符串相同字符之间，最适合。

最佳答案

我终于了解了您想要的东西。这个问题很有趣，但是查看您发现的2种算法，似乎人们对规范有很多不同的看法;)

我认为更清楚地陈述问题和要求将很有用。

问题:

我们正在寻找一种方法来加快键入速度，方法是允许用户只键入他们实际想要的关键字的几个字母，然后为他们提供一个可供选择的列表。

预期输入的所有字母都在关键字

中

期望输入的字母在关键字

中的顺序相同

返回的关键字列表应以一致的(可重复的)顺序显示

该算法应不区分大小写

分析:

前两个要求可以这样总结:对于输入axg，我们正在寻找与该正则表达式[^a]*a[^x]*x[^g]*g.*匹配的单词

第三个要求是有目的的。单词在列表中出现的顺序需要保持一致……但是很难猜测评分方法是否比字母顺序更好。如果列表太长，那么评分方法可能会更好，但是对于短列表，眼睛更容易在以明显方式排序的列表中查找特定项目。

同样，字母顺序的优势是在键入时保持一致:即添加字母不会完全重新排序列表(对眼睛和大脑来说是痛苦的)，它只会过滤掉不再匹配的项目。

处理Unicode字符没有精度，例如à是否类似于a或其他字符？由于我目前还不知道在其关键字中使用此类字符的语言，因此暂时不要说。

我的解决方案:

对于任何输入，我都会构建前面表示的正则表达式。它适用于Python，因为该语言已经具有不区分大小写的匹配。

然后，我将匹配我的(按字母顺序排序)的关键字列表，并将其过滤后输出。

用伪代码:

WORDS = ['Bar', 'Foo', 'FooBar', 'Other']

def GetList(input, words = WORDS):
  expr = ['[^' + i + ']*' + i for i in input]
  return [w for w in words if re.match(expr, w, re.IGNORECASE)]

我本可以使用单行代码，但是认为它会使代码模糊不清;)

该解决方案在增量情况下(例如，当您与用户类型匹配并因此不断重建时)非常有效，因为当用户添加字符时，您可以简单地重新过滤刚刚计算出的结果。从而:

字符很少，因此匹配很快，列表的长度也没关系

要么有很多字符，这意味着我们正在过滤一个简短列表，因此，如果匹配花费更长的时间逐元素

并没有太大关系

我还要注意，此正则表达式不涉及回溯，因此非常有效。也可以将其建模为简单的状态机。