Как рассчитать расстояние левенштейна в python

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

Слово «модификации» включает замены, вставки и удаления.

Например, предположим, что у нас есть следующие два слова:

• НА ВЕЧЕРИНКУ
• ПАРК

Расстояние Левенштейна между двумя словами (то есть количество изменений, которые нам нужно сделать, чтобы превратить одно слово в другое) будет равно 2 :

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

В этом руководстве объясняется, как вычислить расстояние Левенштейна между строками в Python с помощью модуля python-Levenshtein.

Для установки этого модуля вы можете использовать следующий синтаксис:

 pip install python-Levenshtein

Затем вы можете загрузить функцию для расчета расстояния Левенштейна:

 from Levenshtein import distance as lev

Следующие примеры показывают, как использовать эту функцию на практике.

Пример 1: Расстояние Левенштейна между двумя строками

Следующий код показывает, как вычислить расстояние Левенштейна между двумя строками «вечеринка» и «парк»:

 #calculate Levenshtein distance
lev(' party ', ' park ')

2

Расстояние Левенштейна оказывается равным 2 .

Пример 2: Расстояние Левенштейна между двумя таблицами

Следующий код показывает, как вычислить расстояние Левенштейна между каждой парной комбинацией строк в двух разных массивах:

 #define arrays
a = ['Mavs', 'Spurs', 'Lakers', 'Cavs']
b <- ['Rockets', 'Pacers', 'Warriors', 'Celtics']

#calculate Levenshtein distance between two arrays
for i,k in zip (a,b):
  print (lev(i, k))

6
4
5
5

Интерпретация результата следующая:

• Расстояние Левенштейна между «Мавс» и «Рокетс» составляет 6 .
• Расстояние Левенштейна между «Шпорами» и «Пэйсерс» составляет 4 .
• Расстояние Левенштейна между «Лейкерс» и «Уорриорз» составляет 5,5 метра .
• Расстояние Левенштейна между «Кавс» и «Селтикс» составляет 5 .

Дополнительные ресурсы

Как рассчитать расстояние Хэмминга в Python
Как рассчитать евклидово расстояние в Python
Как рассчитать расстояние Махаланобиса в Python