Великая русская работа со словом

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

Вот насколько похожи слова
🌟"кот" 🐈 и "код" 🖥 или
🌟"привет" и "превед" ?
Как-то интиутивно понятно что первая пара ближе между собой чем вторая, да? Но хочется какое-то число.

В 1965 году Владимир Левенштейн предложил способ определения расстояния между строками из нулей и единиц, который потом был обобщён на естественный язык для измерения расстояния между словами. Идея простая — считать минимальное количество операций изменения, необходимых для превращения одной строки в другую. Используя примеры выше:

🌟"кот" ➡️ "код": одна операция
(заменить "т" на "д")

🌟"привет" ➡️ "превед": 2 операции
(заменить "и" на "е" и "т" на "д")

Операций может быть всего три: вставка, удаление или замена символа. Поэтому между "муха" и "слоны" расстояние вообще 5: нужно 4 замены и одна дополнительная буква, вставленная в конец.

Простейшая наивная рекурсивная неоптимизированная реализация тоже простая, буквально 10 строчек, что-то типа такого:

def lvnsht(a, b):
    if len(a) == 0: return len(b)
    if len(b) == 0: return len(a)
    
    cost = (1, 0)[a[0] == b[0]]
    уда = lvnsht(a[1:], b) + 1
    вст = lvnsht(a, b[1:]) + 1
    зам = lvnsht(a[1:], b[1:]) + cost
    return min(уда, вст, зам)

всегда использую шанс использовать кириллические имена переменных 😈. Это наивная реализация, в реальных системах тут используют то самое динамическое программирование, ну и в реальных системах не используют конечно кириллические имена переменных.

Почему расстояние Левенштейна так часто цитируют и его знает любой датасайнтист и почти любой программист? Да потому что оно везде:

📱 Автокоррекция в телефоне ищет слова с минимальным расстоянием от напечатанного ⌨️
🌐 Поисковики по нему понимают, что "абибас" это может быть и "адидас" 👟
👩‍🔬 Биоинформатики считают "edit distance" между последовательностями ДНК 🧬

В общем, сплошь и рядом. Отличная красивая штука, в каком-то смысле такая мощная что можно сказать пробила даже железный занавес.

О самом изобретателе метрики в открытых источниках информации не то чтобы много, но что-то есть, вот хорошая статья на N+1:
https://nplus1.ru/material/2017/09/25/vladimir-levenshtein

А про исправлятор опечаток есть хорошая статья от Питера Норвига с примерами кода и прочими приколами:
https://norvig.com/spell-correct.html
мы в Ламоде использовали это за основу в месте где пользователь как раз часто вводил "абибас"

Забавно, что алгоритм, изначально придуманный для исправления ошибок в двоичном коде (например, чтобы разобраться, превратилось ли "01101" в "01111" из-за одной опечатки), теперь помогает писать сообщения без опечаток (мне не помогает, как вы можете заметить по частым опечаткам) и находить похожие песни по названиям. Не такая уж и бесполезная штука этот двоичный код, получается!