这里是算法(用Ruby编写)
#http://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance
def self.dameraulevenshtein(seq1, seq2)
oneago = nil
thisrow = (1..seq2.size).to_a + [0]
seq1.size.times do |x|
twoago, oneago, thisrow = oneago, thisrow, [0] * seq2.size + [x + 1]
seq2.size.times do |y|
delcost = oneago[y] + 1
addcost = thisrow[y - 1] + 1
subcost = oneago[y - 1] + ((seq1[x] != seq2[y]) ? 1 : 0)
thisrow[y] = [delcost, addcost, subcost].min
if (x > 0 and y > 0 and seq1[x] == seq2[y-1] and seq1[x-1] == seq2[y] and seq1[x] != seq2[y])
thisrow[y] = [thisrow[y], twoago[y-2] + 1].min
end
end
end
return thisrow[seq2.size - 1]
end
我的问题是,对于长度为780的seq1和长度为7238的seq2,在i7笔记本电脑上运行大约需要25秒。理想情况下,我希望将其缩短到约1秒,因为它作为Web应用程序的一部分运行。
我发现有一种方法可以优化vanilla levenshtein距离,使得运行时间从O(n*m)降至O(n + d^2),其中n是较长字符串的长度,d是编辑距离。因此,我的问题是,我所拥有的Damerau版本是否可以应用同样的优化?