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

Question

我所说的模糊匹配不是指Levenshtein距离或类似的东西，而是指它在TextMate/Ido/Icicles中使用的方式:给定一个字符串列表，查找那些包括搜索字符串中的所有字符，但可能包含其他字符的字符串，优先选择最佳匹配。

Answer 1

我终于明白你在找什么了。然而，这个问题很有趣，看看你发现的两个算法，人们似乎对规范有很大的不同意见;)

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

Problem

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

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

>G211

分析

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

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

此解决方案非常适用于增量情况(例如，当您匹配为用户类型并因此继续重建时)，因为当用户添加字符时，您可以简单地重新过滤刚刚计算的结果。因此：

• 有几个字符，因此匹配很快，列表的长度也不是很重要，
• 也有很多字符，这意味着我们正在筛选一个很短的列表，因此，如果匹配需要更长的时间，也没有太大关系

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

Answer 2

到目前为止，我发现了两个算法：

1. LiquidMetal
2. Better Ido Flex-Matching

Answer 3

实际上，我正在为Emacs构建一些类似于Vim的Command-T和ctrlp插件，只是为了好玩。我刚刚与一些聪明的同事进行了一次富有成效的讨论，讨论了如何最有效地做到这一点。这样做的目的是减少删除不匹配文件所需的操作数量。因此，我们创建了一个嵌套映射，其中在顶层，每个键都是出现在搜索集中某处的一个字符，映射到搜索集中所有字符串的索引。然后，这些索引中的每一个都映射到该特定字符出现在搜索字符串中的字符偏移量列表。

在伪代码中，对于字符串：

• controller
• model
• view

我们会构建一个这样的地图：

{
  "c" => {
           0 => [0]
         },
  "o" => {
           0 => [1, 5],
           1 => [1]
         },
  "n" => {
           0 => [2]
         },
  "t" => {
           0 => [3]
         },
  "r" => {
           0 => [4, 9]
         },
  "l" => {
           0 => [6, 7],
           1 => [4]
         },
  "e" => {
           0 => [9],
           1 => [3],
           2 => [2]
         },
  "m" => {
           1 => [0]
         },
  "d" => {
           1 => [2]
         },
  "v" => {
           2 => [0]
         },
  "i" => {
           2 => [1]
         },
  "w" => {
           2 => [3]
         }
}

所以现在你有了一个这样的映射：

{
  character-1 => {
    word-index-1 => [occurrence-1, occurrence-2, occurrence-n, ...],
    word-index-n => [ ... ],
    ...
  },
  character-n => {
    ...
  },
  ...
}

现在搜索字符串"oe"：

1. 初始化一个新的映射，其中的关键字将是匹配字符串的索引，以及到目前为止通过该字符串读取的偏移量的值。
2. 使用搜索字符串"o“中的第一个字符并在查找表中查找它。
3. 由于索引0和1处的字符串与"o”匹配，因此将它们放入映射中{0 => 1, 1 => 1}.
4. Now search将消耗输入字符串中的下一个字符"e“，并在表中循环它。
5. Here 3个字符串匹配，但是我们知道我们只关心字符串0和1。
6. 检查是否有任何偏移量>当前偏移量。如果不是，则从地图中删除这些项目，否则更新偏移量：{0 => 9, 1 => 3}.

现在，通过查看我们积累的map中的关键字，我们知道哪些字符串与模糊搜索匹配。

理想情况下，如果搜索是在用户输入时执行的，那么您将跟踪结果的累积散列，并将其传递回搜索函数。我认为这将比迭代所有搜索字符串并对每个字符串执行完整的通配符搜索要快得多。

有趣的是，假设您只关心插入，而不关心替换或删除，那么您还可以有效地存储每个匹配的Levenstein距离。不过，也许添加这种逻辑也并不难。