使用优化的Levenshtein算法寻找最接近的邻居

Question

使用优化的Levenshtein算法寻找最接近的邻居

algorithmoptimizationlevenshtein-distance

3

最近我发布了一个问题，关于优化计算Levenshtein距离的算法，回复中提到了维基百科上的Levenshtein Distance文章。

文章提到，如果对给定查询结果的最大距离有一个界限k，则运行时间可以从O(mn)降低到O(kn)，其中m和n是字符串的长度。我查找了算法，但实际上并不知道如何实现它。我希望在这里能得到一些线索。

这个优化是“可能的改进”中的第四个。

让我困惑的部分是，文章说我们只需要计算以主对角线（主对角线定义为坐标（i，i））为中心，宽度为2k + 1的对角线条纹。

如果有人能提供一些帮助/见解，我会非常感激。如果需要，我可以在这里以答案的形式发布书中算法的完整描述。

- efficiencyIsBliss

你从哪里得到了“以主对角线为中心...定义为坐标(i，i)”？引用的文章并没有这么说。条纹需要居中于尾对角线（其结束于(m，n)）...整个思路是计算d[m][n]... d[i][j]是字符串s中前i个字符和字符串t中前j个字符之间的Lev.距离。 - John Machin

@John：我在维基百科引用的那本书中找到了这个。它明确指出，最后一个元素不一定是d[m][n]，而是[i][i]。虽然这不是两个单词的正确Levenshtein距离，但它会告诉我们这两个单词是否比我们的边界k更接近，这就是为什么它仍然有用的原因。 - efficiencyIsBliss

1个回答

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

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

- Mike Dunlavey · Accepted Answer

我已经做过这个很多次了。我使用递归深度优先树遍历可能变化的游戏树来完成。有一个更改的预算 k ，我用它来修剪树。有了这个程序，我首先将其运行k = 0，然后k = 1，然后k = 2，直到我要么找到一个命中，要么不想再继续了。

char* a = /* string 1 */;
char* b = /* string 2 */;
int na = strlen(a);
int nb = strlen(b);
bool walk(int ia, int ib, int k){
  /* if the budget is exhausted, prune the search */
  if (k < 0) return false;
  /* if at end of both strings we have a match */
  if (ia == na && ib == nb) return true;
  /* if the first characters match, continue walking with no reduction in budget */
  if (ia < na && ib < nb && a[ia] == b[ib] && walk(ia+1, ib+1, k)) return true;
  /* if the first characters don't match, assume there is a 1-character replacement */
  if (ia < na && ib < nb && a[ia] != b[ib] && walk(ia+1, ib+1, k-1)) return true;
  /* try assuming there is an extra character in a */
  if (ia < na && walk(ia+1, ib, k-1)) return true;
  /* try assuming there is an extra character in b */
  if (ib < nb && walk(ia, ib+1, k-1)) return true;
  /* if none of those worked, I give up */
  return false;
}

为了解释Trie搜索而添加：

// definition of trie-node:
struct TNode {
  TNode* pa[128]; // for each possible character, pointer to subnode
};

// simple trie-walk of a node
// key is the input word, answer is the output word,
// i is the character position, and hdis is the hamming distance.
void walk(TNode* p, char key[], char answer[], int i, int hdis){
  // If this is the end of a word in the trie, it is marked as
  // having something non-null under the '\0' entry of the trie.
  if (p->pa[0] != null){
    if (key[i] == '\0') printf("answer = %s, hdis = %d\n", answer, hdis);
  }
  // for every actual subnode of the trie
  for(char c = 1; c < 128; c++){
    // if it is a real subnode
    if (p->pa[c] != null){
      // keep track of the answer word represented by the trie
      answer[i] = c; answer[i+1] = '\0';
      // and walk that subnode
      // If the answer disagrees with the key, increment the hamming distance
      walk(p->pa[c], key, answer, i+1, (answer[i]==key[i] ? hdis : hdis+1));
    }
  }
}
// Note: you have to edit this to handle short keys.
// Simplest is to just append a lot of '\0' bytes to the key.

现在，如果要将其限制在预算内，只需在hdis太大时拒绝下降即可。