2

根据这篇维基百科文章，我有以下计算 2 个字符串的 Damerau-Levenshtein 距离的 cython 实现，但目前它对我的需求来说太慢了。我有一个大约 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
4

6 回答 6

1

如果在您的搜索中返回了几个单词（如果您需要为输入字符串的相同值多次计算 Damerau Levenshtein 距离），您可以考虑使用字典（或哈希图）来缓存您的结果。这是 C# 中的一个实现：

    private static Dictionary<int, Dictionary<int, int>> DamerauLevenshteinDictionary = new Dictionary<int, Dictionary<int, int>>();

    public static int DamerauLevenshteinDistanceWithDictionaryCaching(string word1, string word2)
    {
        Dictionary<int, int> word1Dictionary;

        if (DamerauLevenshteinDictionary.TryGetValue(word1.GetHashCode(), out word1Dictionary))
        {
            int distance;

            if (word1Dictionary.TryGetValue(word2.GetHashCode(), out distance))
            {
                // The distance is already in the dictionary
                return distance;
            }
            else
            {
                // The word1 has been found in the dictionary, but the matching with word2 hasn't been found.
                distance = DamerauLevenshteinDistance(word1, word2);
                DamerauLevenshteinDictionary[word1.GetHashCode()].Add(word2.GetHashCode(), distance);
                return distance;
            }
        }
        else
        {
            // The word1 hasn't been found in the dictionary, we must add an entry to the dictionary with that match.
            int distance = DamerauLevenshteinDistance(word1, word2);
            Dictionary<int, int> dictionaryToAdd = new Dictionary<int,int>();
            dictionaryToAdd.Add(word2.GetHashCode(), distance);
            DamerauLevenshteinDictionary.Add(word1.GetHashCode(), dictionaryToAdd);
            return distance;
        }
    }
于 2011-10-14T15:30:11.857 回答
0

至少对于较长的字符串，您应该通过使用不必计算 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模块
于 2011-04-07T13:21:10.193 回答
0

似乎您可以静态键入比当前更多的代码，这会提高速度。

您还可以查看 Cython 中 Levenshtein 距离的实现作为示例： http ://hackmap.blogspot.com/2008/04/levenshtein-in-cython.html

于 2011-04-07T13:23:19.227 回答
0

我的猜测是，您当前代码的最大改进将来自使用 C 数组而不是h矩阵的列表列表。

于 2011-04-07T13:27:36.077 回答
0

通过“cython -a”运行它，这将为您提供带有黄色注释行的 HTML 注释源版本。颜色越深，该行中发生的 Python 操作就越多。这通常有助于查找耗时的对象转换等。

但是，我很确定最终会发现最大的问题是您的数据结构。考虑使用 NumPy 数组而不是嵌套列表，或者只使用动态分配的 C 内存块。

于 2011-04-16T15:03:10.327 回答
0

我最近刚刚开源了 Damerau-Levenshtein 算法的 Cython 实现。我包括了 pyx 和 C 源代码。

https://github.com/gfairchild/pyxDamerauLevenshtein

于 2013-07-11T20:05:18.937 回答