Питон как найти расстояние между подстроками

Способ интерпретации вывода следующий:

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

Нахождение наименьшего расстояния между строками и максимального номера строки для уникальных элементов массива

Требуется вычислить наименьшее расстояние между строками и максимальный номер строки, для каждого уникального элемента массива посредством Pandas и/или Numpy Исходные данные:

Row - номер строки c1, c2, c3 - столбцы с данными Row, c1, c2, c3 1, 3, 5, 6 2, 2, 3, 8 3, 5, 4, 9 4, 2, 6, 8 

Ожидаемый результат

Elem, Dist, Row 2, 2, 4 3, 1, 2 4, 0, 3 5, 2, 3 6, 3, 4 8, 2, 4 9, 0, 3 

Доп. условия В случае если элемент встречается в массиве не больше одного раза, то значение расстояние для него = 0. Каждая строка содрежит неповторяющиеся элементы.

Расстояние Левенштейна для чайников

Когда я взялась решать задачку по динамическому программированию — реализовать алгоритм, который рассчитывает расстояние Левенштейна — мне пришлось послушать пару небольших лекций и прочесть несколько статей (приведу их в конце), чтобы разобраться. Я решила попытаться пересказать алгоритм настолько просто, чтобы по этому объяснению можно было снять ролик для тиктока (когда он снова возобновит свою деятельность в РФ). Дальше — мало формул и много картинок.

Понятие редакционного расстояния

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

Например, LEV(’БИБА’, ‘БОБА’) = 1, так как потребуется провести одну замену ‘И’ на ‘О’:

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

А вот между котиком и скотиной — 3 — две вставки и одна замена:

Существует также модификация метрики — расстояние Дамерау — Левенштейна, в котором добавлена операции перестановки символов. В данной статье мы не будем его рассматривать.

Практическое применение

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

Метрика названа в честь советского математика, выпускника мехмата МГУ Владимира Иосифовича Левенштейна. Он всю жизнь проработал в Институте Прикладной Математики им. М.В.Келдыша, умер в 2017 году.

Алгоритм Вагнера — Фишера

Итак, вычислим расстояние между двумя строками методом Вагнера — Фишера: составим матрицу D и каждый её элемент вычислим по рекуррентной формуле:

Немного пугает? Разберёмся, как использовать формулу для заполнения таблицы.

Ясно, что первые три строчки рекуррентной формулы помогут нам заполнить только первый столбец и первую строку таблицы. Для всех остальных ячеек мы будем пользоваться четвёртой строкой — той, что с минимумом. Здесь— символы, соответствующие ячейкам i и j. Оператор если символы и не равны друг другу, и если равны.

Обратите внимание, что первый символ последовательности будет иметь индекс 1, как принято в математике, а не 0.

Будем заполнять таблицу построчно.

Рассчитаем D(1,1), это символы ‘Г’ и ‘Л’. Они не равны друг другу, значит m(’Г’, ‘Л’) = 1. Тогда D(1,1) — это минимум между значениями D(0,1) + 1, D(1,0) + 1 и D(0, 0) + m(’Г’, ‘Л’) = D(0, 0) + 1. Эти клетки выделены голубым. То есть min(1+1, 1+1, 0+1) = min(2, 2, 1) = 1.

Рассчитаем следующую клетку, D(1, 2). Для этого просто сдвинем голубой уголок на одну клетку вправо:

Так как символы ‘Г’ и ‘А’ не равны, используем ту же формулу:

D(1, 2) = min(D(0,2) + 1; D(1,1) + 1; D(0, 1) + 1) = min(2+1; 1+1; 1+1) = 2.

Передвигая голубой уголок, аналогично заполним первые две строки и начало третьей, пока не доберёмся до совпадающих символов ‘Б’ в D(3,3):

Из-за того, что символы совпадают, замена этим двум символам не нужна, поэтому при подсчёте минимума число в розовой ячейке не увеличивается на единицу, т.е. D(3, 3) = min(D(2,3) + 1; D(3,2) + 1; D(2, 2) + 0) = min(3+1; 3+1; 2+0) = 2.

Заполняем таким образом таблицу до самого конца.

Расстояние Левенштейна в этой мартице — нижняя правая ячейка, D(9,8):

Ура! Нам понадобится 5 шагов, чтобы превратить Гибралтар в лабрадора.

Если вас интересует только понимание алгоритма, а не его реализация в коде, на этом всё.

Реализация в динамическом программировании

Если же реализовать всё-таки нужно, посмотрим, как это сделать на Python.

Так как мы заполняем матрицу, нам понадобится 2 цикла, длины которых равны длинам символьных последовательностей, которые мы хотим сравнить или преобразовать.

В целях минимизации используемой памяти мы располагаем строковые последовательности так, чтобы длины строк были минимальны. Это необязательно, но существенно сэкономит память, если одна из последовательностей длинная, а другая короткая.

def levenshtein(str_1, str_2): n, m = len(str_1), len(str_2) if n > m: str_1, str_2 = str_2, str_1 n, m = m, n

Ясно, что хранить всю матрицу в памяти не нужно* — достаточно текущей и предыдущей строк. Циклы начинаются с 1 — так же, как индексы в таблице:

*нужно в случае, если задача стоит не посчитать расстояние, а составить редакционное предписание: последовательность односимвольных операций (вставок, удалений и замен), в результате которой одна последовательность превратится в другую. Эта задача сложнее формализуется, поэтому выходит за рамки данной статьи.

 current_row = range(n + 1) for i in range(1, m + 1): previous_row, current_row = current_row, [i] + [0] * n

Проще основным случаем считать тот, когда символы равны, и в случае, если нет — прибавлять к ячейке в предыдущей строке по диагонали (розовой) единицу:

for j in range(1, n + 1): add, delete, change = previous_row[j] + 1, current_row[j - 1] + 1, previous_row[j - 1] if str_1[j - 1] != str_2[i - 1]: change += 1 current_row[j] = min(add, delete, change)

Весь алгоритм в таком случае будет выглядеть так:

def levenstein(str_1, str_2): n, m = len(str_1), len(str_2) if n > m: str_1, str_2 = str_2, str_1 n, m = m, n current_row = range(n + 1) for i in range(1, m + 1): previous_row, current_row = current_row, [i] + [0] * n for j in range(1, n + 1): add, delete, change = previous_row[j] + 1, current_row[j - 1] + 1, previous_row[j - 1] if str_1[j - 1] != str_2[i - 1]: change += 1 current_row[j] = min(add, delete, change) return current_row[n]

В данной реализации цены замены, удаления и вставки равны друг другу и единице, но, в зависимости от задачи, они могут принимать неравные значения.

Время работы этого алгоритма — m*n, т.е. равно произведению длин символьных последовательностей.

Когда не нужно изобретать велосипед

В коммерческой разработке и/или при обработке больших массивов слов писать метод самостоятельно чаще всего нет смысла. В Python есть библиотека, в оригинале написанная на C, а также библиотека, содержащая разные метрики оценки сходства строк. Также можно посчитать расcтояние в NLTK.

Заключение

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

Здорово, когда не просто пользуешься реализацией алгоритма из коробки, но и понимаешь, как именно всё работает. Надеюсь, после этой статьи у вас стало на один такой алгоритм больше.

Литература

• https://medium.com/analytics-vidhya/levenshtein-distance-for-dummies-dd9eb83d3e09
• https://habr.com/ru/post/117063/
• https://tirinox.ru/levenstein-python/

Расстояние Левенштейна на Python

Как понять насколько близки две строки? Как поисковая система все равно находит то, что надо, даже если вы совершили пару опечаток в запросе? В этом вопросе нам поможет расстояние по Левенштейну или редакционное расстояние. Почему редакционное? Потому что мы считаем, сколько действий по редактированию одной строки нужно совершить, чтобы получить другую строку. Действия бывают следующими: вставка символа, удаление символа и замена одного символа другим.

Одинаковые строки имеют нулевое расстояние: не нужно ничего редактировать, первая и так равна второй. « Привет » и « Привт » имеют расстояние 1 (пропущена одна буква, остальное не изменилось). « Привет » и « привты » имеют расстояние 3 (одна замена «П» на «п», удаление буквы «е» и вставка «ы» на конце). Мы будем считать

Я не буду сюда копировать теорию и тем более доказательства, это вы можете изучить в Вики.

Давайте попробуем реализовать этот алгоритм в лоб по формуле:

Функция m – возвращает единицу, если символы не равны, иначе 0. Вот такой код получится:

def my_dist(a, b): def recursive(i, j): if i == 0 or j == 0: # если одна из строк пустая, то расстояние до другой строки - ее длина # т.е. n вставок return max(i, j) elif a[i - 1] == b[j - 1]: # если оба последних символов одинаковые, то съедаем их оба, не меняя расстояние return recursive(i - 1, j - 1) else: # иначе выбираем минимальный вариант из трех return 1 + min( recursive(i, j - 1), # удаление recursive(i - 1, j), # вставка recursive(i - 1, j - 1) # замена ) return recursive(len(a), len(b))

Вспомогательная функция, чтобы протестировать производительность:

from timeit import timeit def test_lev_dist(f: callable, a, b, n=1): tm = timeit("f(a, b)", globals=< 'f': f, 'a': a, 'b': b >, number=n) r = f(a, b) print(f'a = and b = and = and time = ') test_lev_dist(my_dist, "hello world", "bye world!") # a = 'hello world' and b = 'bye world!' and my_dist = 6 and time = 1.3829

Как можете видеть, первый вариант кода работает экстремально медленно, потому что много раз вычисляет функцию при одних и тех же входных параметрах. Давайте узнаем, сколько раз вызывается внутренняя функция. Для этого добавим декоратор, который считает число вызовов:

def count_calls(f): @wraps(f) def wrapped(*args, **kwargs): wrapped.n_calls += 1 return f(*args, **kwargs) wrapped.n_calls = 0 return wrapped def my_dist(a, b): @count_calls def recursive(i, j): . # прочий код пропущен r = recursive(len(a), len(b)) print('calls =', recursive.n_calls) return r my_dist("hello world", "bye world!") # calls = 3317804

Более 3 миллионов вызовов! И большинство из них с одинаковыми параметрами. А так как они повторяются, то можно их закешировать (при помощи lru_cache). Здесь размер кэша примерно равен числу различных комбинаций входных параметров.

from functools import lru_cache def my_dist_cached(a, b): @count_calls @lru_cache(maxsize=len(a) * len(b)) def recursive(i, j): if i == 0 or j == 0: return max(i, j) elif a[i - 1] == b[j - 1]: return recursive(i - 1, j - 1) else: return 1 + min( recursive(i, j - 1), recursive(i - 1, j), recursive(i - 1, j - 1) ) r = recursive(len(a), len(b)) print('calls = ', recursive.n_calls) return r my_dist_cached("hello world", "bye world!") # calls = 212

Количество вызовов сократилось до 212, а скорость работы увеличилась на порядки. Выкинем count_calls и проведем замеры времени для 10000 повторных вызовов.

def my_dist_cached(a, b): @lru_cache(maxsize=len(a) * len(b)) def recursive(i, j): if i == 0 or j == 0: return max(i, j) elif a[i - 1] == b[j - 1]: return recursive(i - 1, j - 1) else: return 1 + min( recursive(i, j - 1), recursive(i - 1, j), recursive(i - 1, j - 1) ) return recursive(len(a), len(b)) test_lev_dist(my_dist_cached, "hello world", "bye world!", n=10000) # a = 'hello world' and b = 'bye world!' and my_dist_cached = 6 and time = 0.9740

Производительность улучшилась радикально (в прошлый раз мы прогоняли один вызов функции, а теперь 10000 раз, и то выходит быстрее). Однако, пока что объем требуемой памяти растет как O(len(a) * len(b)) . Иными словами, для двух мегабайтных строк потребуются гигабайты памяти. Фактически в кэше будет хранится почти все матрица редактирований, а она нам не нужна целиком. Наша цель – правый нижний элемент.

Для его поиска можно обойтись лишь парой рядов: текущим и предыдущим. А остальные ряды не хранить в памяти. Так мы дойдем до конца таблицы, и нижний правый угол и будет искомым значением.

Вот пример реализации:

def distance(a, b): n, m = len(a), len(b) if n > m: # убедимся что n 
Объяснение. Сначала, чтобы использовать еще меньше памяти, мы можем поменять местами наши строки, чтобы длина рядов была минимальна. Это существенно экономит память, если одна из строк длинная, а другая короткая.
Затем мы понимаем, что нулевой ряд или столбец матрицы – просто восходящая последовательность. Потому что, чтобы из пустой строки получить любую не пустую, нужно ровно то число вставок, сколько символов в не пустой строке. И наоборот: n удалений из строки длины n приведут неизбежно к пустой строке.
 
Потом мы шагаем по рядам матрицы, помня только текущий ряд и предыдущий, мы заполняем неизвестные клетки текущего ряда. Соседние клетки отвечают за вставку одного символа, удаление или замену (если символы неравны). Из трех возможных изменений мы выбираем то, чья стоимость наименьшая.
Эта версия еще быстрее, чем кэшированная:
test_lev_dist(distance, "hello world", "bye world!", n=10000) # a = 'hello world' and b = 'bye world!' and distance = 6 and time = 0.7374
Сложность этого алгоритма растет как произведение длин строк: O(n*m) . Это еще не самый эффективный алгоритм. Для дальнейшего ускорения нужно воспользоваться древовидной структурой данных. Также неплохо бы учесть то, что на известном словаре можно заранее вычислить расстояния между словами.
Наконец-то, когда мы разобрались с принципом работы алгоритма, вспомним, что все велосипеды уже написаны до нас, да еще и на языке Си. Воспользуемся библиотечными функциями, установив пакет:
pip install python-Levenshtein
import Levenshtein test_lev_dist(Levenshtein.distance, "hello world", "bye world!", n=10000) # a = 'hello world' and b = 'bye world!' and distance = 6 and time = 0.0032
Специально для канала @pyway. Подписывайтесь на мой канал в Телеграм @pyway ��


Похожие публикации:

Habr как стать data scientist
Idmsa apple com что это
Show text id что это
Как отвязать карту в литрес