模糊匹配字符串的算法

Question

模糊匹配字符串的算法

26

“模糊匹配”并不是指 Levenshtein 距离或其他类似的字符串相似性，而是 TextMate/Ido/Icicles 中使用的方式：给定一组字符串，找到那些包括搜索字符串中所有字符（可能有其他字符在它们之间），并优先选择最佳匹配的字符串。

- Alexey Romanov

2

你对问题的描述也相当模糊。从我所了解的那些算法来看，Levenshtein距离可能也适用，只是速度太慢了。也许你能更好地描述一下？ - Matthieu M.

6个回答

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 As String，_ ByVal s2 As String，_ Optional Compare As VBA.VbCompareMethod = vbTextCompare，_ Optional iScore As Integer = 0 _ ）作为整数

应用程序。挥发性假

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

'度量字符串1由字符串2中的子字符串组成的程度的功能

'此函数使用修改后的最长公共字符串算法。 '简单的LCS算法对测试单词中间附近的单个字母删除/更改过于敏感 '例如：星期三明显更接近于WedXesday而不是WednesXXX。所以得分更好 ' Wed '以及'esday'并将匹配的总数相加

'注意长度不同的字符串：

' SumOfCommonStrings（“星期三”，“WednesXXXday”）

'这与以下内容得分相同：

'SumOfCommonStrings（“星期三”，“星期三”）

'因此，请确保调用函数在计算从此分数计算的相似度的程度时使用最长字符串的长度。

'这是为清晰起见编写的，而不是为了性能。

Dim arr（）作为整数的'评分矩阵 Dim n作为整数' s1的长度 Dim m作为整数' s2的长度 Dim i作为整数'在s1中的起始位置 Dim j作为整数'在s2中的起始位置 Dim subs1作为字符串' s1的子字符串 Dim len1作为整数' subs1的长度

Dim sBefore1 '在代码中记录 Dim sBefore2 Dim sAfter1 Dim sAfter2

Dim s3作为字符串

SumOfCommonStrings = iScore n = Len（s1） m = Len（s2）

如果s1 = s2那么 SumOfCommonStrings = n 退出函数结尾如果

如果n = 0或m = 0那么退出函数结尾如果

's1应始终是两个字符串中较短的一个：如果n> m那么 s3 = s2 s2 = s1 s1 = s3 n = Len（s1） m = Len（s2）结尾如果

n = Len（s1） m = Len（s2）

'特殊情况：s1是s2的n个精确子字符串如果InStr（1，s2，s1，Compare）然后 SumOfCommonStrings = n 退出函数结尾如果

对于len1 = n To 1 Step -1

对于i = 1到n-len1 + 1

subs1 = Mid（s1，i，len1） j = 0 j = InStr（1，s2，subs1，Compare）

如果j> 0那么

'We've found a matching substring... iScore = iScore + len1

'现在从s1和s2中剪切出此子字符串... '并搜索此切除之前和之后的片段：

如果i> 1且j> 1那么 sBefore1 = left（s1，i-1） sBefore2 = left（s2，j-1） iScore = SumOfCommonStrings（sBefore1，_ sBefore2，_ Compare，_ iScore）结尾如果

如果i + len1

- Nigel Heffernan

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":

初始化一个新的映射，其中键将是匹配的字符串的索引，值将是到目前为止读取该字符串的偏移量。
从搜索字符串"o"中获取第一个字符并在查找表中查找它。
由于索引0和1处的字符串与"o"匹配，因此将它们放入映射中{0 => 1, 1 => 1}。
现在在输入字符串中消耗下一个字符"e"，并在表中查找它。
这里有3个字符串匹配，但我们知道只关心字符串0和1。
检查是否有任何偏移量>当前偏移量。如果没有，则从映射中删除项目，否则更新偏移量：{0 => 9, 1 => 3}。

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

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

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

- d11wtq

3

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

- Alexey Romanov

2

我最近也遇到了同样的问题。我的解决方案是将连续匹配的字母字符串打分，并排除不按顺序包含键入字母的字符串。

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

- Kazade

0

如果您的文本主要是英语，那么您可以尝试各种Soundex算法

1. 经典Soundex 2. Metafone

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

- Sandeep Datta

这是指“我不是指利用Levenshtein距离或类似方法来比较相似的字符串”。 - Alexey Romanov

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Matthieu M. · Accepted Answer

我终于明白你在寻找什么了。这个问题很有意思，但是看到你找到的两种算法，似乎人们对规范有着广泛不同的意见；）

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

问题:

我们正在寻找一种通过允许用户只输入少数字母来加快输入速度的方法，以便为他们提供一个列表供选择他们真正想要键入的关键词。

预期所有输入的字母都包含在关键词中
预期输入的字母顺序与关键词相同
返回的关键词列表应按照一致（可重现）的顺序呈现
算法应该不区分大小写

分析:

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

我本可以用一行代码，但是觉得那样会使代码变得晦涩难懂 ;)

这种解决方案在增量情况下非常有效（即当您按照用户类型匹配并因此不断重建时），因为当用户添加字符时，您只需简单地重新过滤刚刚计算出的结果即可。因此：

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

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