有效计算两个字符串之间的编辑距离

Question

我有一个长度为 1000 的字符串 S 和一个长度为 100 的查询字符串 Q。我想计算查询字符串 Q 与长度为 100 的字符串 S 的每个子字符串的编辑距离。一种简单的方法是动态计算编辑距离每个子串独立，即edDist(q,s[0:100]), edDist(q,s[1:101]), edDist(q,s[2:102])....... edDist(q,s[900:1000])。

def edDist(x, y):
""" Calculate edit distance between sequences x and y using
    matrix dynamic programming.  Return distance. """
D = zeros((len(x)+1, len(y)+1), dtype=int)
D[0, 1:] = range(1, len(y)+1)
D[1:, 0] = range(1, len(x)+1)
for i in range(1, len(x)+1):
    for j in range(1, len(y)+1):
        delt = 1 if x[i-1] != y[j-1] else 0
        D[i, j] = min(D[i-1, j-1]+delt, D[i-1, j]+1, D[i, j-1]+1)
return D[len(x), len(y)]

有人可以建议一种替代方法来有效计算编辑距离。我对此的看法是我们知道edDist(q,s[900:1000]). 我们能否以某种方式使用这些知识来计算edDist[(q,s[899:999])]...因为我们只有 1 个字符的差异，然后向后继续edDist[(q,s[1:100])]使用之前计算的编辑距离？

Answer 1

提高空间复杂性

提高编辑距离算法效率的一种方法是减少计算所需的内存量。

要使用整个矩阵，需要利用O(n * m)内存，其中表示第一个字符串和第二个字符串n的长度。m

如果您考虑一下，我们真正关心的矩阵的唯一部分是我们正在检查的最后两列 -前一列和当前列。

知道了这一点，我们可以假装我们有一个矩阵，但实际上只创建了这两列；当我们需要更新数据时重写数据。

这里我们需要的是两个大小为 的数组n + 1：

var column_crawler_0 = new Array(n + 1);
var column_crawler_1 = new Array(n + 1);

初始化这些伪列的值：

for (let i = 0; i < n + 1; ++i) {
  column_crawler_0[i] = i;
  column_crawler_1[i] = 0;
}

然后执行正常的算法，但只需确保在我们进行过程中使用新值更新这些数组：

for (let j = 1; j < m + 1; ++j) {
  column_crawler_1[0] = j;
  for (let i = 1; i < n + 1; ++i) {
    // Perform normal Levenshtein calculation method, updating current column
    let cost = a[i-1] === b[j-1] ? 0 : 1;
    column_crawler_1[i] = MIN(column_crawler_1[i - 1] + 1, column_crawler_0[i] + 1, column_crawler_0[i - 1] + cost);
  }

  // Copy current column into previous before we move on
  column_crawler_1.map((e, i) => {
    column_crawler_0[i] = e;
  });
}

return column_crawler_1.pop()

如果您想进一步分析这种方法，我使用这种特定技术编写了一个小型开源库，所以如果您好奇的话，请随意查看。

提高时间复杂度

没有什么特别的方法可以改进 Levenshtein 距离算法以使其执行速度比O(n^2). 有一些复杂的方法，其中一种使用VP-Tree 数据结构。如果您有兴趣在这里和这里阅读，有一些很好的资源，并且这些方法可以达到 的渐近速度O(nlgn)。