python - Cython Damerau-Levenshtein 加速

Question

我有以下 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

Answer 1

至少对于较长的字符串，您应该通过使用不必计算 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模块