4

晚安，

我一直在使用模糊字符串匹配一段时间，并且使用带有一些指针的 C，我可以编写一个非常快速的（满足我的需要）两个字符串之间的 Levenshtein 距离的实现。我尝试使用不安全代码和fixed关键字将代码移植到 C#，但性能要慢得多。所以我选择构建一个 C++ dll 并使用[DllImport]来自 C#，自动编组每个字符串。问题是，在分析之后，这一直是我的程序中最耗时的部分，占程序总运行时间的 50-57%。因为我认为我需要对来自大约 300 万条数据库记录的文本字段的大量子字符串做一些繁重的工作，所以我认为 Levenshtein 距离所花费的时间几乎是不可接受的。也就是说，我想知道您是否对下面的代码有任何建议，无论是算法还是编程相关，或者您是否知道任何更好的算法来计算这个距离？

#define Inicio1  (*(BufferVar))
#define Inicio2  (*(BufferVar+1))
#define Fim1  (*(BufferVar+2))
#define Fim2  (*(BufferVar+3))
#define IndLinha (*(BufferVar+4))
#define IndCol  (*(BufferVar+5))
#define CompLinha (*(BufferVar+6))
#define TamTmp  (*(BufferVar+7))

int __DistanciaEdicao (char * Termo1, char * Termo2, int TamTermo1, int TamTermo2, int * BufferTab, int * BufferVar)
{
 *(BufferVar) = *(BufferVar + 1) = 0;
    *(BufferVar + 2) = TamTermo1 - 1;
    *(BufferVar + 3) = TamTermo2 - 1;

 while ((Inicio1 <= *(BufferVar + 2)) && (Inicio2 <= *(BufferVar + 3)) && *(Termo1 + Inicio1) == *(Termo2 + Inicio2))
  Inicio1 = ++Inicio2;

  if (Inicio2 > Fim2) return (Fim1 - Inicio1 + 1);

 while ((Fim1 >= 0) && (Fim2 >= 0) && *(Termo1 + Fim1) == *(Termo2 + Fim2))
  { Fim1--; Fim2--;}

  if (Inicio2 > Fim2) return (Fim1 - Inicio1 + 1);

 TamTermo1 = Fim1 - Inicio1 + 1;
 TamTermo2 = Fim2 - Inicio2 + 1;
 CompLinha = ((TamTermo1 > TamTermo2) ? TamTermo1 : TamTermo2) + 1;

 for (IndLinha = 0; IndLinha <= TamTermo2; *(BufferTab + CompLinha * IndLinha) = IndLinha++);
 for (IndCol = 0; IndCol <= TamTermo1; *(BufferTab + IndCol) = IndCol++);

 for (IndCol = 1; IndCol <= TamTermo1; IndCol++)
  for (IndLinha = 1; IndLinha <= TamTermo2; IndLinha++)
   *(BufferTab + CompLinha * IndLinha + IndCol) = ((*(Termo1 + (IndCol + Inicio1 - 1)) == *(Termo2 + (IndLinha + Inicio2 - 1))) ? *(BufferTab + CompLinha * (IndLinha - 1) + (IndCol - 1)) : ((*(BufferTab + CompLinha * (IndLinha - 1) + IndCol) < *(BufferTab + CompLinha * (IndLinha - 1) + (IndCol - 1))) ? ((*(BufferTab + CompLinha * IndLinha + (IndCol - 1)) < *(BufferTab + CompLinha * (IndLinha - 1) + IndCol)) ? *(BufferTab + CompLinha * IndLinha + (IndCol - 1)) : *(BufferTab + CompLinha * (IndLinha - 1) + IndCol)) : ((*(BufferTab + CompLinha * IndLinha + (IndCol - 1)) < *(BufferTab + CompLinha * (IndLinha - 1) + (IndCol - 1))) ? *(BufferTab + CompLinha * IndLinha + (IndCol - 1)) : *(BufferTab + CompLinha * (IndLinha - 1) + (IndCol - 1)))) + 1);

 return *(BufferTab + CompLinha * TamTermo2 + TamTermo1);
}

请注意，BufferVar 和 BufferTab 是两个外部int *的（在这种情况下，int[]变量是从 C# 编组的），我不会在每个函数调用中实例化它们以加快整个过程。尽管如此，这段代码对于我的需要来说还是很慢的。谁能给我一些建议，或者，如果可能的话，提供一些更好的代码？

编辑：距离不能有界，我需要实际距离。

非常感谢，

4

3 回答 3

5

1.蛮力

这是 Python 中的 Levenshtein 距离的实现。

def levenshtein_matrix(lhs, rhs):
  def move(index): return (index+1)%2

  m = len(lhs)
  n = len(rhs)

  states = [range(n+1), [0,]*(n+1)]

  previous = 0
  current = 1

  for i in range(1, m+1):
    states[current][0] = i

    for j in range(1,n+1):
      add = states[current][j-1] + 1
      sub = states[previous][j] + 1
      repl = states[previous][j-1] + abs(cmp(lhs[i-1], rhs[j-1]))

      states[current][j] = min( repl, min(add,sub) )

    previous = move(previous)
    current = move(current)

  return states[previous][n]

这是典型的动态规划算法，只是利用了由于只需要最后一行，一次只保留两行就足够了。

对于 C++ 实现，您可以查看LLVM 的实现（第 70-130 行），注意使用固定大小的堆栈分配数组，仅在必要时由动态分配的数组替换。

我只是无法跟进您的代码来尝试诊断它......所以让我们改变迎角。我们将完全改变算法，而不是对距离进行微优化。

2. 做得更好：使用字典

您面临的问题之一是您可以做得更好。

第一个评论是距离是对称的，尽管它不会改变整体复杂性，但它会使所需时间减半。

第二个是因为你实际上有一个已知单词的字典，你可以在此基础上构建：“actor”和“actual”共享一个共同的前缀（“act”），因此你不需要重新计算第一阶段。

这可以使用 Trie（或任何其他排序结构）来存储您的单词。接下来，您将取一个单词，并利用前缀计算它与字典中存储的所有单词的相对距离。

举个例子dic = ["actor", "actual", "addict", "atchoum"]，我们要计算距离word = "atchoum"（此时我们将其从字典中删除）

  1. 初始化单词 "atchoum" 的矩阵：matrix = [[0, 1, 2, 3, 4, 5, 6, 7]]
  2. 选择下一个词“演员”
  3. 前缀 = “a”，矩阵 =[[0, 1, 2, 3, 4, 5, 6, 7], [1, 0, 1, 2, 3, 4, 5, 6]]
  4. 前缀 = “ac”，矩阵 =[[0, 1, 2, 3, 4, 5, 6, 7], [1, 0, 1, 2, 3, 4, 5, 6], [2, 1, 1, 2, 3, 4, 5, 6]]
  5. 前缀=“行为”，矩阵=[[..], [..], [..], [..]]
  6. 继续，直到“演员”，你有你的距离
  7. 选择下一个单词“actual”，倒回矩阵直到前缀是我们单词的前缀，这里是“act”
  8. 前缀 = “actu”，矩阵 =[[..], [..], [..], [..], [..]]
  9. 继续直到“实际”
  10. 继续看其他词

这里重要的是倒带步骤，通过保留对前一个单词所做的计算，与您共享一个长长的前缀，您可以有效地节省大量工作。

请注意，这是通过简单的堆栈轻松实现的，不需要任何递归调用。

于 2010-11-24T09:01:19.427 回答
4

首先尝试简单的方法 - 不要使用指针和不安全的代码 - 只需编写普通的 C# 代码......但使用正确的算法。

维基百科上有一个简单而有效的算法，它使用动态编程并运行 O(n*m)，其中 n 和 m 是输入的长度。我建议您首先尝试实现该算法，因为它在那里描述，并且只有在您实现它之后才开始优化它，测量性能并发现它不够。

另请参阅可能的改进部分，其中说：

通过检查对角线而不是行，并使用惰性求值，我们可以在 O(m (1 + d)) 时间内找到 Levenshtein 距离（其中 d 是 Levenshtein 距离），这比常规动态规划算法快得多，如果距离很小

如果我不得不猜测问题出在哪里，我可能会先查看在两个循环中运行的这条线：

*(BufferTab + CompLinha * IndLinha + IndCol) = ((*(Termo1 + (IndCol + Inicio1 - 1)) == *(Termo2 + (IndLinha + Inicio2 - 1))) ? *(BufferTab + CompLinha * (IndLinha - 1) + (IndCol - 1)) : ((*(BufferTab + CompLinha * (IndLinha - 1) + IndCol) < *(BufferTab + CompLinha * (IndLinha - 1) + (IndCol - 1))) ? ((*(BufferTab + CompLinha * IndLinha + (IndCol - 1)) < *(BufferTab + CompLinha * (IndLinha - 1) + IndCol)) ? *(BufferTab + CompLinha * IndLinha + (IndCol - 1)) : *(BufferTab + CompLinha * (IndLinha - 1) + IndCol)) : ((*(BufferTab + CompLinha * IndLinha + (IndCol - 1)) < *(BufferTab + CompLinha * (IndLinha - 1) + (IndCol - 1))) ? *(BufferTab + CompLinha * IndLinha + (IndCol - 1)) : *(BufferTab + CompLinha * (IndLinha - 1) + (IndCol - 1)))) + 1);

尽管我很难确切地发现发生了什么，但那里似乎有很多重复。你能把其中的一些因素考虑进去吗？你肯定需要让它更具可读性。

于 2010-11-23T20:12:04.307 回答
2

您不应该使用 Levenshtein 距离算法尝试所有可能的单词。您应该使用另一个更快的指标来过滤掉可能的候选人，然后才使用 Levenshtein 来消除歧义。第一个筛子可以基于 n-gram（trigram 通常效果很好）频率直方图或散列函数。

于 2010-11-23T20:36:54.177 回答