更快的 C#（或其他 .NET）Levenshtein 距离实现

Question

晚安，

我已经研究模糊字符串匹配有一段时间了，并且使用 C 和一些指针，我可以编写一个非常快速的（根据我的需要）实现两个字符串之间的 Levenshtein 距离。我尝试使用不安全代码和 fixed 关键字将代码移植到 C#，但性能要慢得多。因此，我选择构建一个 C++ dll 并使用 C# 中的 [DllImport]，自动编组每个字符串。问题是，在分析之后，这仍然是我的程序中最耗时的部分，占用了程序总运行时间的 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# 编组的），我不会在每个函数调用中实例化它们整个过程更快。尽管如此，这段代码对于我的需求来说还是相当慢。谁能给我一些建议，或者如果可能的话，提供一些更好的代码？

编辑：距离没有限制，我需要实际距离。

非常感谢，

Answer 1

1.暴力破解

这是 Levenshtein Distance 在 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 的一个（第 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. Pick下一个单词“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. 前缀 = "act", 矩阵 = [[..], [..], [..], [..]]
6. 继续直到“actor”，你就有了距离
7. 选择下一个单词“actual”，倒回矩阵直到前缀是我们单词的前缀，这里一直到“act” "
8. Prefix = "actu", Matrix = [[..], [..], [..], [..], [..]]
9. 继续直到“actual”
10. 继续换句话说，

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

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

Answer 2

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

Wikipedia 上有一个简单高效的算法，它使用动态规划并运行 O(n* m) 其中 n 和 m 是输入的长度。我建议您首先尝试实现该算法，正如那里所描述的那样，只有在实现它、测量性能并发现它不足之后才开始优化它。

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

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

如果我不得不猜测问题出在哪里，我可能会首先查看在 two 循环内运行的这一行：

*(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);

似乎有一个 那里有很多重复，尽管我很难准确地发现发生了什么。你能把其中一些因素排除掉吗？而且您肯定需要使其更具可读性。

Answer 3

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