20 мая 1935 года родился Владимир Иосифович Левенштейн - человек, чью идею использует почти каждый поиск, мессенджер и телефон на планете.

Имени его почти никто не знает. А идеей пользуются миллиарды людей каждый день, даже не догадываясь об этом. И самое интересное здесь не то, что он сделал, а то, для чего он это делал.

В 1965 году в Докладах АН СССР вышла его статья "Двоичные коды с исправлением выпадений, вставок и замещений символов". Название звучит как что-то про текст и опечатки. На деле работа была про связь.

Шестидесятые: спутники, телеграф, военные радиоканалы. Сигнал передаётся битами. По дороге часть битов пропадает, часть появляется лишняя, часть инвертируется. Приёмник должен восстановить исходное сообщение. Левенштейн придумал, как кодировать данные, чтобы это было возможно.

В качестве инструмента он ввёл метрику: минимальное число вставок, удалений и замен, чтобы превратить одну последовательность символов в другую. Её назвали расстоянием Левенштейна.

Пример из учебника:
"кот" → "кит"
Заменили одну букву, расстояние равно 1.

Дальше произошёл странный поворот. Метрика, придуманная для битовых потоков в каналах связи, идеально легла на строки букв. И её стали использовать совсем не для того, для чего она писалась.

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

В задачах, где важен не только набор символов, но и контекст, его потеснили языковые модели:
- автозамена в телефоне: первые поколения считали именно edit distance и превращали "прювет" в "привет", сейчас SwiftKey и Gboard работают на нейросетевых языковых моделях
- подсказки поисковика "возможно, вы имели в виду..."
- дедупликация текстов для обучения LLM: на современных масштабах применяют MinHash и LSH, но логика "найти почти дубликат" та же самая

История с Google показательна. В начале двухтысячных под капотом "Did you mean" стоял именно Левенштейн плюс частотность слов. Питер Норвиг, директор по исследованиям Google, тогда показал, что весь спелл-корректор умещается в 36 строк Python. Языковые модели и анализ кликов пришли позже, когда у компании накопилось достаточно поведенческих данных. Сейчас расстояние Левенштейна там - один сигнал из многих, но фундамент был заложен именно им.

Маленькая, но важная поправка. Левенштейн не придумал способ быстро считать это расстояние. Привычный код на динамическом программировании за O(m*n) - это работа Вагнера и Фишера, 1974 год. Левенштейн дал метрику. Алгоритм её вычисления появился девятью годами позже.

В 2006 году IEEE вручила ему медаль Хэмминга - одну из главных наград в теории информации. На церемонию он не приехал: после инсульта почти не мог работать. Умер в Москве в сентябре 2017-го.

Человек проектировал коды для спутниковой связи. А в итоге дал миру первый язык, на котором компьютеры научились говорить "это почти то же самое". Дальше пришли нейросети и языковые модели, но точка отсчёта осталась за ним.