Вычисление расстояния Левенштейна с использованием массивов NumPy

Сколько правок необходимо внести в одно слово, чтобы получить другое? Чем меньше правок нужно сделать, тем выше уровень сходства. В этой статье рассмотрим вариант вычисления расстояния Левенштейна — метрики для измерения разности между двумя строками.

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

Рассмотрим реализацию алгоритма Фишера-Вагнера. Понадобится NumPy и одна матрица для выполнения вычислений.

Давайте вычислим редакторское расстояние между словами «программирование» и «минирование». Реализация начинается с пустой матрицы, размер которой соответствует длине строк. И первая строка, и столбец, начиная с нуля, индексируются по возрастанию:

       м   и   н   и   р   о   в   а   н   и   е
[[ 0.  1.  2.  3.  4.  5.  6.  7.  8.  9. 10. 11.]
п[ 1.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.]
р[ 2.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.]
о[ 3.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.]
г[ 4.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.]
р[ 5.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.]
а[ 6.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.]
м[ 7.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.]
м[ 8.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.]
и[ 9.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.]
р[10.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.]
о[11.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.]
в[12.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.]
а[13.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.]
н[14.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.]
и[15.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.]
е[16.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.]]

Далее следуют два цикла, сравнивающие строки по буквам: по строкам и по столбцам. Если две буквы совпадают, новое значение в позиции [x, y] приобретает минимальное из значений в позициях [x-1, y] + 1, [x-1, y-1] и [x, у-1] + 1. В противном случае рассчитывается минимум между значениями в позициях [x-1, y] + 1, [x-1, y-1] + 1 и [x, y-1] + 1.

Существует три возможных типа изменений, если два символа неодинаковые — вставка, удаление и замена.

Финальная матрица выглядит следующим образом:

       м   и   н   и   р   о   в   а   н   и   е
[[ 0.  1.  2.  3.  4.  5.  6.  7.  8.  9. 10. 11.]
п[ 1.  1.  2.  3.  4.  5.  6.  7.  8.  9. 10. 11.]
р[ 2.  2.  2.  3.  4.  4.  5.  6.  7.  8.  9. 10.]
о[ 3.  3.  3.  3.  4.  5.  4.  5.  6.  7.  8.  9.]
г[ 4.  4.  4.  4.  4.  5.  5.  5.  6.  7.  8.  9.]
р[ 5.  5.  5.  5.  5.  4.  5.  6.  6.  7.  8.  9.]
а[ 6.  6.  6.  6.  6.  5.  5.  6.  6.  7.  8.  9.]
м[ 7.  6.  7.  7.  7.  6.  6.  6.  7.  7.  8.  9.]
м[ 8.  7.  7.  8.  8.  7.  7.  7.  7.  8.  8.  9.]
и[ 9.  8.  7.  8.  8.  8.  8.  8.  8.  8.  8.  9.]
р[10.  9.  8.  8.  9.  8.  9.  9.  9.  9.  9.  9.]
о[11. 10.  9.  9.  9.  9.  8.  9. 10. 10. 10. 10.]
в[12. 11. 10. 10. 10. 10.  9.  8.  9. 10. 11. 11.]
а[13. 12. 11. 11. 11. 11. 10.  9.  8.  9. 10. 11.]
н[14. 13. 12. 11. 12. 12. 11. 10.  9.  8.  9. 10.]
и[15. 14. 13. 12. 11. 12. 12. 11. 10.  9.  8.  9.]
е[16. 15. 14. 13. 12. 12. 13. 12. 11. 10.  9.  8.]]

Сложность реализации — O(N * M), где N и M — длины строк.

Расстояние редактирования — это значение в позиции [11, 16], равное 8.

import numpy as np

def fisher_wagner(seq1, seq2):
    size_x = len(seq1) + 1
    size_y = len(seq2) + 1
    matrix = np.zeros((size_x, size_y))
    for x in range(size_x):
        matrix[x, 0] = x
    for y in range(size_y):
        matrix[0, y] = 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]