我有一个长度为1000的字符串S和一个长度为100的查询字符串Q。我想计算长度为100的字符串S的每个子字符串的查询字符串Q的编辑距离。一种简单的方法是动态计算编辑距离每个子串的独立,即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])]
使用先前计算的编辑距离?
使Levenshtein距离算法更有效的一种方法是减少计算所需的内存量。
若要使用整个矩阵,则需要利用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)
。
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句