Улучшение производительности Левенштейна на расстоянии в numpy

Question

У меня есть следующая функция:

def levenshtein(seq1, seq2):
    size_x = len(seq1) + 1
    size_y = len(seq2) + 1
    matrix = np.zeros ((size_x, size_y))
    matrix[: , 0] = np.arange(size_x)
    matrix[0, :] = np.arange(size_y)

    for x in range(1, size_x):
        for y in range(1, size_y):
            if seq1[x-1] == seq2[y-1]:
                matrix [x,y] = min(
                    matrix[x-1, y] + 1,
                    matrix[x-1, y-1],
                    matrix[x, y-1] + 1
                )
            else:
                matrix [x,y] = min(
                    matrix[x-1,y] + 1,
                    matrix[x-1,y-1] + 1,
                    matrix[x,y-1] + 1
                )
    return (matrix[size_x - 1, size_y - 1])

И я хочу применить ее ко многим парам строк, чтобы сделать это как можно быстрее, я хочу удалить из нее циклы for и заменить их какой-то векторизацией, но я не мог найти хороший способ сделать это, есть идеи?

Answer 1

Лучше использовать уже написанное python mudule , чтобы решить вашу проблему, а не изобретать велосипед, как по мне. Вы сэкономите много времени.

Откройте cmd и напишите pip install python-Levenshtein, или, если вы используете git go, в папку проекта и введите git clone https://github.com/ztane/python-Levenshtein.git ( ссылка на github ). Затем onen python file и:

import Levenshtein
Levenshtein.distance('Levenshtein', 'Lenvinsten')
# output will be 4
# ... your code ...

Но если вам нужно написать это вручную, вы можете увидеть, как это пишут другие разработчики или примеры использования модуля Левенштейна в том же самом ссылка.