我所说的模糊匹配并不是指通过 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)]
我本可以使用单行代码,但我认为它会使代码变得模糊 ;)
此解决方案非常适用于增量情况(即,当您匹配用户类型并因此不断重建时),因为当用户添加角色时,您可以简单地重新过滤刚刚计算的结果。因此:
- 要么字符少,匹配快,列表长度无关紧要
- 要么有很多字符,这意味着我们正在过滤一个短列表,因此如果匹配在元素方面花费更长的时间也没关系
我还应该注意到,这个正则表达式不涉及回溯,因此非常有效。它也可以建模为一个简单的状态机。
关于 "fuzzy matching"字符串的算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/2891514/