Cython Дамерау-Левенштейн ускорение

Question

У меня есть следующая реализация Cython для вычисления расстояния Дамерау – Левенштейна из 2 строк на основе этой статьи в Википедии , но в настоящее время она слишком медленная для моих нужд.У меня есть список около 600000 строк, и я должен найти опечатки в этом списке.

Я был бы рад, если бы кто-нибудь мог предложить какие-либо алгоритмические улучшения или некоторую магию python / cython, которая могла бы уменьшить время выполнения скрипта.Меня не волнует, сколько места занимает только время, которое требуется для вычисления.

Согласно профилированию скрипта с использованием около 2000 строк, он тратит 80% полного времени выполнения (24 из 30 секунд) вdamerauLevenshteinDistance функция, и у меня нет идей, как сделать это быстрее.

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

Если в вашем поиске возвращается несколько слов (если вам нужно несколько раз вычислить расстояние Дамерау Левенштейна для одного и того же значения входных строк), вы можете использовать словарь (или хэш-карту) для кэширования ваших результатов.Вот реализация в 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;
        }
    }

Answer 2

Я только недавно открыл реализацию Cython для алгоритма Дамерау-Левенштейна. Я включаю источник Pyx и C.

https://github.com/gfairchild/pyxDamerauLevenshtein

Answer 3

Запустите его через "cython -a", который даст вам аннотированную HTML-версию с красивыми желтыми аннотированными строками. Чем темнее цвет, тем больше операций Python происходит в этой строке. Обычно это очень помогает в поиске трудоемких преобразований объектов и т. П.

Однако я почти уверен, что самая большая проблема - это ваша структура данных. Попробуйте использовать массивы NumPy вместо вложенных списков или просто использовать динамически выделяемый блок памяти C.

Answer 4

Полагаю, что самым большим улучшением в вашем текущем коде стало бы использование массива C вместо списка списков для матрицы h.

Answer 5

Кажется, что вы могли бы статически набрать больше кода, чем в настоящее время, что увеличило бы скорость.

Вы также можете проверить реализацию расстояния Левенштейна в Cython в качестве примера: http://hackmap.blogspot.com/2008/04/levenshtein-in-cython.html

Answer 6

По крайней мере для более длинных строк вы должны получить лучшую производительность, используя другой алгоритм, который не должен вычислять все значения в матрице lena & sdot; 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 module