晚安

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

#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# 编码的)，我不会在每个函数中实例化它们调用使整个过程更快。不过，这段代码对我的需要来说还是很慢的。谁能给我一些建议，或者，如果可能的话，提供一些更好的代码？

编辑:距离无法限定，我需要实际距离。

非常感谢，

最佳答案

<强>1。蛮力

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

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's one (第 70-130 行)，请注意固定大小的堆栈分配数组的使用，仅在必要时由动态分配的数组替换。

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

<强>2。做得更好:使用字典

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

首先要注意的是距离是对称的，虽然它不会改变整体复杂性但会使所需时间减半。

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

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

举个例子dic = ["actor", "actual", "addict", "atchoum"] 我们想计算word = "atchoum"<>(此时我们将其从字典中删除)

1. 初始化单词“atchoum”的矩阵:matrix = [[0, 1, 2, 3, 4, 5, 6, 7]]
2. 选择下一个单词“actor”
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. Prefix = "act", matrix = [[..], [..], [..], [..]]
6. 继续，直到“ Actor ”，你有你的距离
7. 选择下一个单词“actual”，倒转矩阵直到前缀是我们单词的前缀，这里是“act”
8. Prefix = "actu", matrix = [[..], [..], [..], [..], [..]]
9. 继续，直到“实际”
10. 继续寻找其他词

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

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

关于c++ - 更快的 C#(或其他 .NET)Levenshtein 距离实现，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/4260406/