Как автокоррекция измеряет сходство слов
Представим, что человек набрал «кошка», а в словаре есть слово «кочка». Чтобы превратить одно в другое, достаточно заменить одну букву. Метрика Левенштейна формализует такую «цену исправления»: она ищет самый короткий набор операций — вставок, удалений и замен символов, — необходимый для превращения одной строки в другую.
Важно, что считается не число несовпадающих позиций. Например, если в слове пропущена буква, все последующие символы могут сдвинуться, но одна вставка всё равно исправит ошибку. Поэтому метрика полезнее простого сравнения букв по местам.
Как получается минимальное число операций
Алгоритм сопоставляет слова по частям. Для каждой пары фрагментов он определяет, сколько операций нужно, чтобы превратить один фрагмент в другой. Затем выбирает самый дешёвый путь: сохранить совпавшую букву, заменить несовпавшую или добавить либо удалить символ.
Такие промежуточные результаты обычно записывают в таблицу. Ячейка показывает минимальную цену преобразования двух префиксов — начальных частей слов. Значение для полных слов и есть расстояние Левенштейна. Этот приём не перебирает всевозможные последовательности исправлений, а переиспользует уже найденные ответы для коротких фрагментов.
Почему одной метрики недостаточно
Автокоррекция может сравнить набранное слово со словами словаря и отдать предпочтение тем, до которых меньше операций. Но одинаковая цена не означает одинаковую вероятность ошибки: замена соседних клавиш обычно правдоподобнее, чем случайная замена на далёкую букву, а контекст фразы тоже подсказывает нужный вариант.
Поэтому расстояние Левенштейна — удобный способ отсеять слишком непохожие варианты, а не готовое решение о том, что хотел написать человек. Его практический смысл прост: даже если ошибка сдвинула всё слово, система может оценить, насколько коротким набором исправлений его можно привести к знакомому слову.
