Расстояние Левенштейна между двумя строками — это минимальное количество односимвольных правок, необходимых для превращения одного слова в другое.
Слово «редактирование» включает замены, вставки и удаления.
Например, предположим, что у нас есть следующие два слова:
- ПАРТИЯ
- ПАРК
Расстояние Левенштейна между двумя словами (то есть количество правок, которые мы должны сделать, чтобы превратить одно слово в другое) будет равно 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 .
Дополнительные ресурсы
Как рассчитать расстояние Хэмминга в Python
Как рассчитать евклидово расстояние в Python
Как рассчитать расстояние Махаланобиса в Python