我有以下 cython 实现计算 2 个字符串的 Damerau–Levenshtein 距离，基于 this Wikipedia article ，但目前它对我的需求来说太慢了。我有一个大约 600000 个字符串的列表，我必须在该列表中找到拼写错误。
如果有人可以建议任何算法改进或一些可以减少脚本运行时间的 python/cython 魔术，我将很高兴。我真的不关心它使用了多少空间，只关心计算所花费的时间。
根据使用大约 2000 个字符串对脚本进行分析，它在 damerauLevenshteinDistance 函数中花费了整个运行时间的 80%(30 秒中的 24 秒)，我完全不知道如何制作它更快。
def damerauLevenshteinDistance(a, b, h):
"""
a = source sequence
b = comparing sequence
h = matrix to store the metrics (currently nested list)
"""
cdef int inf,lena,lenb,i,j,x,i1,j1,d,db
alphabet = getAlphabet((a,b))
lena = len(a)
lenb = len(b)
inf = lena + lenb + 1
da = [0 for x in xrange(0, len(alphabet))]
for i in xrange(1, lena+1):
db = 0
for j in xrange(1, lenb+1):
i1 = da[alphabet[b[j-1]]]
j1 = db
d = 1
if (a[i-1] == b[j-1]):
d = 0
db = j
h[i+1][j+1] = min(
h[i][j]+d,
h[i+1][j]+1,
h[i][j+1]+1,
h[i1][j1]+(i-i1-1)+1+(j-j1-1)
)
da[alphabet[a[i-1]]] = i
return h[lena+1][lenb+1]
cdef getAlphabet(words):
"""
construct an alphabet out of the lists found in the tuple words with a
sequential identifier for each word
"""
cdef int i
alphabet = {}
i = 0
for wordList in words:
for letter in wordList:
if letter not in alphabet:
alphabet[letter] = i
i += 1
return alphabet
请您参考如下方法:
至少对于较长的字符串，您应该通过使用不必计算 lena⋅lenb 矩阵中的所有值的不同算法来获得更好的性能。例如，可能通常没有必要计算 [lena][0] 的确切成本。矩阵的一角，表示从删除a中的所有字符开始的成本.
更好的算法可能是始终查看迄今为止计算出的权重最低的点，然后从那里向各个方向进一步移动。这样您就可以在不检查矩阵中所有位置的情况下到达目标位置:
此算法的实现可以使用优先级队列，如下所示:
from heapq import heappop, heappush
def distance(a, b):
pq = [(0,0,0)]
lena = len(a)
lenb = len(b)
while True:
(wgh, i, j) = heappop(pq)
if i == lena and j == lenb:
return wgh
if i < lena:
# deleted
heappush(pq, (wgh+1, i+1, j))
if j < lenb:
# inserted
heappush(pq, (wgh+1, i, j+1))
if i < lena and j < lenb:
if a[i] == b[i]:
# unchanged
heappush(pq, (wgh, i+1, j+1))
else:
# changed
heappush(pq, (wgh+1, i+1, j+1))
# ... more possibilities for changes, like your "+(i-i1-1)+1+(j-j1-1)"
这只是一个粗略的实现，还可以改进很多:
- 向队列添加新坐标时，检查:
- 如果之前已经处理过坐标，则不再添加
- 如果坐标当前在队列中，则只保留附加权重较好的实例
- 使用用 C 实现的优先级队列而不是
heapq模块
