“模糊匹配”字符串的算法

“模糊匹配”字符串的算法

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

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

问题 ：

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

1. 预期输入的所有字母都在关键字中
2. 预期输入中的字母在关键字中的顺序相同
3. 返回的关键字列表应以一致（可重复）的顺序显示
4. 该算法应不区分大小写

分析 ：

前两个要求可以这样总结：对于输入，

axg

我们正在寻找与该正则表达式匹配的单词

[^a]*a[^x]*x[^g]*g.*

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

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

处理Unipre字符没有精度，例如

à

与Unipre字符

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)]

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

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

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

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