"fuzzy matching"字符串的算法

Question

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

Answer 1

我终于明白你在找什么了。这个问题很有趣，但是看看你发现的 2 种算法，人们似乎对规范有很大不同的看法；)

我认为更清楚地说明问题和要求会很有用。

问题:

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

1. 期望输入的所有字母都在关键字中
2. 期望输入中的字母在关键字中的顺序相同
3. 返回的关键字列表应以一致(可重现)的顺序呈现
4. 算法应该不区分大小写

分析:

前两个要求可以这样总结:对于输入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)]

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

此解决方案非常适用于增量情况(即，当您匹配用户类型并因此不断重建时)，因为当用户添加角色时，您可以简单地重新过滤刚刚计算的结果。因此:

• 要么字符少，匹配快，列表长度无关紧要
• 要么有很多字符，这意味着我们正在过滤一个短列表，因此如果匹配在元素方面花费更长的时间也没关系

我还应该注意到，这个正则表达式不涉及回溯，因此非常有效。它也可以建模为一个简单的状态机。