25

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

4

6 回答 6

31

我终于明白你在找什么了。这个问题很有趣，但是看看你发现的 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)]

我本可以使用单线，但认为它会掩盖代码；）

这种解决方案非常适合增量情况（即，当您匹配用户类型并因此继续重建时），因为当用户添加一个字符时，您可以简单地重新过滤您刚刚计算的结果。因此：

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

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

于 2010-05-24T12:52:35.660 回答
9

Levenshtein 的“编辑距离”算法肯定会在您尝试做的事情上发挥作用：它们会给您衡量两个单词或地址或电话号码、诗篇、独白和学术文章的匹配程度，让您对结果并选择最佳匹配。

一种更轻量级的方法是计算公共子字符串：它不如 Levenshtein，但它提供了可用的结果并在可以访问快速“InString”函数的慢速语言中快速运行。

几年前，我在 Excellerando 上发布了一个 Excel 的“模糊查找”，使用的是“FuzzyMatchScore”函数，据我所知，这正是你所需要的：

http://excellerando.blogspot.com/2010/03/vlookup-with-fuzzy-matching-to-get.html

当然，它是在 Visual Basic for Applications 中。小心行事，十字架和大蒜：

公共函数 SumOfCommonStrings( _
                            ByVal s1 作为字符串，_
                            ByVal s2 作为字符串，_
                            可选的比较为 VBA.VbCompareMethod = vbTextCompare, _
                            可选 iScore 作为整数 = 0 _
                                ) 作为整数

Application.Volatile False

' N.Heffernan 2006 年 6 月 6 日
'此代码在公共领域


' 测量字符串 1 中有多少是由字符串 2 中的子字符串组成的函数

' 此函数使用修改后的最长公共字符串算法。
' 简单的 LCS 算法对单字母过于敏感
' 测试词中点附近的删除/更改，例如：
' 在编辑距离上，星期三显然更接近星期三
' 比它是 WednesXXX 的基础。所以最好打分
' 'Wed' 和 'esday' 相加总匹配

' 注意不同长度的字符串：
'
' SumOfCommonStrings("Wednesday", "WednesXXXday")
'
' 这与以下得分相同：
'
' SumOfCommonStrings("星期三", "星期三")
'
' 所以请确保调用函数使用最长的长度
' 从这个分数计算相似度时的字符串。


' 这是为了清晰而不是为了性能而编码的。

Dim arr() As Integer ' 评分矩阵
Dim n As Integer ' s1 的长度
Dim m As Integer ' s2 的长度
Dim i As Integer ' 在 s1 中的起始位置
Dim j As Integer ' 在 s2 中的起始位置
Dim subs1 As String ' s1 的子串
Dim len1 As Integer ' subs1 的长度

Dim sBefore1 ' 记录在代码中
暗淡 sBefore2
昏暗 sAfter1
昏暗后2

将 s3 调暗为字符串


SumOfCommonStrings = iScore

n = 长度 (s1)
m = 长度 (s2)

如果 s1 = s2 那么
    SumOfCommonStrings = n
    退出函数
万一

如果 n = 0 或 m = 0 那么
    退出函数
万一

's1 应该始终是两个字符串中较短的一个：
如果 n > m 那么
    s3 = s2
    s2 = s1
    s1 = s3
    n = 长度 (s1)
    m = 长度 (s2)
万一

n = 长度 (s1)
m = 长度 (s2)

' 特殊情况：s1 是 s2 的 n 个精确子串
如果 InStr(1, s2, s1, 比较) 那么
    SumOfCommonStrings = n
    退出函数
万一

对于 len1 = n 到 1 步 -1

    对于 i = 1 到 n - len1 + 1

        subs1 = Mid(s1, i, len1)
        j = 0
        j = InStr(1, s2, subs1, 比较)

        如果 j > 0 那么

            ' 我们找到了匹配的子字符串...
            iScore = iScore + len1            

          ' 现在从 s1 和 s2 中剪掉这个子串...
          ' 并搜索此切除前后的片段：


            如果 i > 1 并且 j > 1 那么
                sBefore1 = 左(s1, i - 1)
                sBefore2 = 左(s2, j - 1)
                iScore = SumOfCommonStrings(sBefore1, _
                                            s之前2，_
                                            比较， _
                                            iScore)
            万一


            如果 i + len1 < n 并且 j + len1 < m 那么
                sAfter1 = right(s1, n + 1 - i - len1)
                sAfter2 = 对(s2, m + 1 - j - len1)
                iScore = SumOfCommonStrings(sAfter1, _
                                            s后2，_
                                            比较， _
                                            iScore)
            万一


            SumOfCommonStrings = iScore
            退出函数

        万一

    下一个


下一个


结束功能


私有函数最小值（ByVal a As Integer, _
                         ByVal b 作为整数，_
                         ByVal c As Integer) As Integer
将最小值作为整数

  最小值 = 一个

  如果 b < 分钟 那么
        最小值 = b
  万一

  如果 c < 分钟 那么
        最小值 = c
  万一

  最小值 = 最小值

结束功能
于 2011-01-11T17:26:45.260 回答
3

到目前为止我发现的两种算法：

  1. 液态金属
  2. 更好的 Ido 弹性匹配
于 2010-05-23T11:53:19.957 回答
3

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

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

  • 控制器
  • 模型
  • 看法

我们会构建这样的地图：

{
  "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”匹配，因此将它们放入 map{0 => 1, 1 => 1}中。
  4. 现在搜索使用输入字符串中的下一个字符“e”并在表中查找它。
  5. 这里有 3 个字符串匹配，但我们知道我们只关心字符串 0 和 1。
  6. 检查是否有任何偏移>当前偏移。如果不是，则从我们的地图中删除项目，否则更新偏移量：{0 => 9, 1 => 3}。

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

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

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

于 2013-05-16T08:44:12.127 回答
2

我最近不得不解决同样的问题。我的解决方案涉及对具有连续匹配字母的字符串进行高度评分，并按顺序排除不包含键入字母的字符串。

我在这里详细记录了算法：http ://blog.kazade.co.uk/2014/10/a-fuzzy-filename-matching-algorithm.html

于 2014-10-31T08:20:20.367 回答
0

如果您的文本主要是英语，那么您可以尝试各种 Soundex 算法 1.经典 soundex 2. Metafone

这些算法将让您选择听起来彼此相似的单词，并且是查找拼写错误单词的好方法。

于 2010-05-23T11:43:03.837 回答