Информатика · объяснение и практика

Расстояние редактирования: вставить, удалить или заменить символ

Как получается расстояние Левенштейна: префиксы строк, вставка, удаление, замена и проверка минимального пути.

Синие фигурные скобки держат между собой оранжевый квадрат.

В теме Методы алгоритмов: углубление · Учебная карта

В маршруте Сортировки и сравнение строк · 10 тем

Главная мысль

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

Решаем маленькие задачи для префиксов

Обозначим через D(i,j) расстояние между первыми i символами исходной строки и первыми j символами нужной. Если одна часть пуста, ответ уже известен: для построения j символов нужны j вставок, а для удаления i символов — i удалений. Эти значения заполняют края таблицы.

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

Отличаем готовый путь от доказанного минимума

Слово «дом» можно превратить в «дым» одной заменой среднего символа. Нулём действий обойтись нельзя: строки не совпадают. Поэтому найденная стоимость один одновременно является нижней и верхней границей. Для более длинных строк одну красивую последовательность правок недостаточно объявить минимальной без дополнительного обоснования.

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

Пример

«краб» → «раб» требует одного удаления начальной к. «раб» → «храб» требует одной вставки х.

Обе стоимости равны 1. Направление превращения меняет название действия: удаление в одну сторону соответствует вставке в обратную.

Какие различия модель видит и не видит

При работе с Unicode нужно заранее выбрать единицу сравнения. Отдельная кодовая точка, видимый символ и байт не всегда совпадают. Буква с отдельным комбинируемым знаком может занимать две кодовые точки. Если приложение не нормализует строки, визуально похожие записи способны получить ненулевое расстояние.

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

От чтения к действию

А теперь — вы

Из строки «мост» требуется получить «ост». Какова минимальная стоимость при единичных вставке, удалении и замене?

Частые вопросы

Перестановка соседних букв всегда стоит одно действие?

Нет. В обычной модели Левенштейна отдельной операции перестановки нет.

Может ли один ответ иметь несколько оптимальных путей?

Да. Разные последовательности вставок, удалений и замен иногда дают одну минимальную стоимость.

Углублённый разбор

Аффинный штраф пропуска требует трёх состояний

Одна длинная серия пропусков может стоить дешевле нескольких отдельных. Чтобы динамика помнила, открыт ли уже пропуск, она хранит три типа окончания выравнивания вместо одной стоимости префиксов.

Перед началом: Редакционная динамика; Глобальное выравнивание.

Цена серии не равна цене каждого символа

Пусть серия k≥1 удалений или вставок стоит a+(k−1)b, где a>0 оплачивает открытие, b>0 — продолжение. При a>b дробление одной длинной серии увеличивает стоимость. Одна клетка обычного редакционного расстояния не сообщает, закончился ли лучший предыдущий путь тем же типом пропуска, поэтому не позволяет правильно выбрать следующий тариф.

Обозначим M(i,j) минимум при окончании парой символов, D(i,j) при удалении символа A и I(i,j) при вставке символа B. Совпадение либо замена переходит из любого предыдущего диагонального состояния в M. Продолжение D→D или I→I платит b, а открытие нового типа из другого состояния платит a. Смена D↔I открывает новую серию, если такая соседняя смена разрешена моделью.

Границы должны оплачивать одну серию

В начале M(0,0)=0, а невозможные состояния бесконечны. На границе D(i,0)=a+(i−1)b для i>0 и I(0,j)=a+(j−1)b для j>0. Повторное начисление a в каждой граничной клетке превратило бы аффинный штраф в линейный с иной ценой. Нулевой длине серии не назначают цену a: это отсутствие пропуска.

Итоговый ответ равен min(M(m,n),D(m,n),I(m,n)). Восстановление должно хранить и тип состояния, иначе одинаковая численная стоимость может привести к неверному начислению открытия на обратном пути. Нужно также назвать соглашение о штрафе: другая распространённая запись a+kb имеет иной смысл первого символа и требует согласованного пересчёта параметров.

Модель допустимых переходов не универсальна

Некоторые схемы запрещают соседние противоположные пропуски и не включают прямые переходы D↔I. Другие разрешают все глобальные выравнивания. При большой цене замены эти два договора могут давать разные ответы. Поэтому трёхбуквенное имя алгоритма не заменяет описание допустимых действий и стоимости каждого перехода.

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

Одно открытие на четыре удаления

Условие. A=ABBBBC,B=AC. Совпадение бесплатно, замена стоит 5, серия пропусков k стоит 3+(k−1). Найдите минимальную стоимость глобального выравнивания.

  1. Совмещаем начальные A и конечные C. Четыре B удаляются одной непрерывной серией между ними.
  2. Её цена 3+3·1=6. По состояниям D после первых, вторых, третьих и четвёртых удалений стоимости равны 3,4,5,6.
  3. Любое выравнивание должно иметь как минимум четыре удаления по разности длин. При хотя бы одной серии их цена не меньше 4+(3−1)=6.
  4. Дополнительные вставки либо замены имеют неотрицательную цену и не уменьшают эту границу. Показанное выравнивание достигает 6, поэтому оно оптимально.

Ответ. Минимальная стоимость 6; одна серия четырёх удалений.

Проверка. Сумма тарифов открытие 3 и три продолжения 1 даёт 6. Ошибочное открытие на каждом B дало бы 12, а простая цена 1 за каждый символ дала бы 4: обе схемы отличаются от заданной.

Где легко ошибиться. Соглашения a+(k−1)b и a+kb отличаются ценой первого пропуска. Не смешивайте их границы, рекурсии и подписи параметров в одной задаче.

Проверьте понимание

Какова цена одной серии четырёх пропусков в задаче?

Вопросы к этой главе

Достаточно ли хранить длину всей серии в отдельной координате?

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

Почему при восстановлении нужно знать тип состояния?

Одинаковая итоговая сумма может прийти из открытой серии или из сопоставления символов. Следующая правка имеет разную добавочную цену, и без типа нельзя корректно восстановить тарифы.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • C.Burge, MIT7.91: Global Alignment of Protein Sequences

    Первичные лекционные материалы MIT: вебом прочитано определение affine gap penalty и различие открытия/продления. В главе явно оговорена модель допустимых переходов между тремя состояниями; собственные строки не взяты из лекции.

Редакционное расстояние при пороге и диагональная полоса

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

Перед началом: Единичное расстояние Левенштейна; Пороговая задача.

Разность длин префиксов даёт нижнюю границу

В глобальном выравнивании клетка(i,j) означает обработанные префиксы длин i,j. Чтобы получить разницу j−i, нужно как минимум|i−j|вставок или удалений, каждая стоит единицу. Поэтому D(i,j)≥|i−j|. Любой путь с полной стоимостью≤k может проходить только по клеткам|i−j|≤k, поскольку частичная стоимость не уменьшается.

Это обосновывает вычисление полосы ширины 2k+1 вместо полной таблицы. Внеполосные клетки считаются недопустимыми для порогового запроса. Если уже |m−n|>k, ответ отрицателен без динамики. Но обратное неверно: близкие длины не гарантируют сходства самих символов.

Обрезанный ответ имеет ограниченный смысл

Значения больше k можно насыщать маркером k+1. Если конечная клетка≤k, получено точное расстояние; если больше, доказано только превышение порога. Нельзя выдавать k+1 как точное расстояние, потому что настоящий ответ может быть намного больше. Такой интерфейс отличается от полного вычисления произвольного расстояния.

Если все допустимые клетки одной строки имеют стоимость>k, ни один будущий путь бюджета k не сможет пересечь эту строку. Можно завершить работу раньше. При этом нужно учитывать все активные клетки строки, а не одно текущее положение: другой сдвиг способен сохранить дешёвый путь, которого ещё не достиг выбранный столбец.

Условия полосы связаны с ценой операций

Для единичных вставок и удалений доказательство прямо использует нижнюю границу|i−j|. При иных ценах ширина зависит от минимальной положительной стоимости изменения длины. Бесплатная вставка или удаление вообще разрушает такое ограничение. Для локального поиска подстроки начальные условия тоже иные, поэтому глобальную полосу нельзя переносить без нового вывода.

На каждом из m рядов считается не больше 2k+1 клеток, что даёт O(km) время в пороговом режиме и линейную по k рабочую память для двух строк. Для восстановления скрипта потребуются дополнительные данные либо повторные вычисления. Если k сравним с длиной строк, преимущество перед полной таблицей исчезает.

Порог не определяется одной длиной

Условие. Сравните stone и atones при единичных правках. Проверьте пороги k=1 и k=2, не объявляя маркер отказа точным расстоянием.

  1. Длины 5 и 6 различаются на 1, поэтому начальный тест не отвергает k=1. Но это только необходимая граница.
  2. Одна правка для увеличения длины могла бы быть только вставкой. Тогда stone должна быть подпоследовательностью atones, чего нет: s стоит только в конце, посленегонет t.
  3. Значит расстояние>1, и полоса k=1 законно отказывает. Для верхней границы заменяем первый s на a, получая atone, затем вставляем s вконец.
  4. Получены atones двумя правками. Поэтому истинное расстояние 2, полоса k=2 егосодержит, а отказ первой полосы означал лишь превышение 1.

Ответ. d(stone,atones)=2; порог 1 не проходит, порог 2 проходит.

Проверка. Нижняя граница исключает единственную возможную модель с одной правкой по длине, а явный скрипт даёт верхнюю 2. Их совпадение проверяет результат независимо от полосовой реализации.

Где легко ошибиться. Маркер k+1 в пороговом решателе не является полным расстоянием. Он означает только, что ни один путь бюджета k не найден в доказанно достаточной полосе.

Проверьте понимание

Что корректно сообщает отказ полосы k=1 взадаче?

Вопросы к этой главе

Можно повторять с удвоением k?

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

Почему нельзя выйти за полосу и затем вернуться бесплатно?

Выход потребовал бы уже больше k единичных изменений длины. Дальнейшие совпадения могут стоить ноль, но не возвращают потраченный бюджет назад.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • Steven Skiena: Dynamic Programming, Banded Alignment

    Первичные авторские лекции: вебом прочитан PDF раздел BandedAlignment с ограниченной диагональной полосой и удвоением ширины. Конкретная пороговая задача и доказательство отказа при k=1 подготовлены отдельно.

Редактирование через самые дальние точки диагоналей

При небольшом расстоянии редактирования полезно хранить не всю полосу DP, а самые дальние достигнутые точки диагоналей. Один платный шаг редактирования сменяется длинным бесплатным пробегом по точным совпадениям. Волновой фронт растёт по числу правок и впервые достигает полного конца на точном расстоянии.

Перед началом: Расстояние Левенштейна; Префикс строки.

Координаты считаются по уже потреблённым символам

Пусть A,B имеют длины n,m. Точка(i,j) означает выравнивание префиксов A[0:i),B[0:j). Диагональ k=i−j. Совпавшие символы двигают обе координаты на1 без платы. Замена тоже двигает обе, но стоит 1; удаление символа A двигает только i, вставка нужного символа B — только j. Здесь все три правки имеют единичную стоимость, глобальное выравнивание начинается строго в(0,0).

Для бюджета e сохраняем на каждой достижимой диагонали наибольшую координату i, затем однозначно j=i−k. Более ранняя точка той же диагонали не нужна для самого дальнего фронта. После каждого платного шага максимально продлеваем точное совпадение — snake, или LCE-прыжок. На нулевом слое это просто общий префикс A,B.

Три правки порождают соседние диагонали

Из точки(i,j) предыдущего фронта рассматриваем замену в(i+1,j+1), удаление в(i+1,j) и вставку в(i,j+1), если требуемые символы и координаты находятся внутри строк. Затем выполняем точный пробег и оставляем максимальный i для каждой новой диагонали. При соглашении «не больше e правок» также сохраняется прежняя достижимость. Знаки диагоналей лучше выводить из координат, чем запоминать по названиям вставки и удаления.

За e правок отклонение |i−j| не больше e, поэтому на слое лишь O(e) диагоналей, а до бюджета k — O(k²) фронтовых значений. Стоимость каждого LCE зависит от реализации: наивный посимвольный пробег может повторять сравнения, индекс точных общих префиксов требует отдельной подготовки. Поэтому число фронтов нельзя безусловно называть полным временем работы. Это другая экономия состояния, чем заполнение каждой ячейки узкой полосы DP.

Первое достижение цели даёт и нижнюю границу

Если цель(n,m) не достигнута на слоях меньше e и достигнута на e, расстояние равно e. Если остановиться после заданного бюджета, недостижение означает только «расстояние больше бюджета», а не конкретное число. Для небольшого примера удобно подтвердить нижнюю границу отдельным рассуждением о видах одной правки и верхнюю — явным сценарием. Такое свидетельство не зависит от тонкостей сдвига индексов во фронтовой реализации.

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

Условие. Найдите расстояние между A=abxcd и B=abycde волновыми фронтами и проверьте минимальность двух правок.

  1. Нулевой слой бесплатно проходит общий префикс ab и заканчивается в(2,2) на диагонали 0. Следующие символы x,y не равны.
  2. На слое 1 замена x→y даёт(3,3), после чего snake по cd достигает(5,5). Вставка вместо замены ведёт в(2,3), удаление в(3,2); там немедленного совпадения нет.
  3. На слое 2 из(5,5) вставляем завершающую e и достигаем цели(5,6) на диагонали−1. Имеется сценарий из двух правок.
  4. Одна правка должна увеличить длину на1, то есть быть вставкой. Тогда A была бы подпоследовательностью B, но символ x в B вообще отсутствует. Следовательно одна правка невозможна, и точное расстояние 2.

Ответ. Расстояние Левенштейна равно 2; сценарий — заменить x на y и вставить e в конец.

Проверка. Независимая полная таблица DP даёт 2. Три координаты фронта слоя 1 сверены отдельно, а нижний запрет одной вставки проверяется отсутствием x, без повторения фронтовой рекурсии.

Где легко ошибиться. Не меняйте знак диагонали по интуитивному названию правки и не объявляйте отказ на бюджете точным расстоянием. Фиксируйте координаты потреблённых префиксов.

Проверьте понимание

Каково глобальное расстояние между abxcd и abycde при единичных вставке, удалении и замене?

Вопросы к этой главе

Почему замена не меняет диагональ?

Она потребляет по одному символу обеих строк, поэтому разность i−j сохраняется. Удаление увеличивает её на1, вставка уменьшает на1 при принятом направлении A→B.

Подходит ли тот же фронт для локального поиска образца внутри текста?

Начальные условия будут другими: локальный поиск разрешает старт с разных позиций текста. Здесь начало фиксировано в(0,0), и нулевой слой не содержит бесплатных пропусков произвольного префикса.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • Mihai Pop: CMSC701 Computational Genomics, §4.3.4

    Прочитаны Landau–Vishkin: самая дальняя точка диагонали и LCP-прыжки. Нотация переходов в PDF неоднозначна по сдвигам индексов; здесь они заново заданы координатами трёх правок и проверены полной Levenshtein-DP. Собственные строки abxcd/abycde не взяты из примера источника.

Левенштейнов автомат ищет близкие слова в словаре

Поиск всех близких слов словаря не требует заново строить таблицу расстояния для каждого слова. Общий префикс trie получает одну строку динамики, которую используют все его продолжения. Минимум этой строки даёт безопасное отсечение целой ветви, даже если её конечные слова ещё не прочитаны.

Перед началом: Расстояние Левенштейна с единичными правками; Trie и отметка окончания слова.

Состояние хранит расстояния до всех префиксов запроса

Зафиксируем запрос q длины m. Для словарного префикса p храним строку R[j]=dist(p,q[:j]), j=0,…,m. В корне p пуст, поэтому R=(0,1,…,m). При проходе ребра с буквой c новая строка начинается с R_new[0]=|p|+1.

Остальные значения вычисляются слева направо: R_new[j]=min(R[j]+1,R_new[j−1]+1,R[j−1]+[c≠q[j−1]]). Три слагаемых соответствуют удалению, вставке и совпадению либо замене. После прохода общего префикса эта строка уже готова для всех слов его поддерева, поэтому одинаковая работа не повторяется.

Минимум строки является нижней границей для продолжений

Пусть допустимо не более k правок. Если min_jR[j]>k, ни одно продолжение p не сможет дать словарное слово на расстоянии не больше k от полного запроса. Любое его выравнивание с запросом проходит границу после p в некоторой колонке j. Уже накопленная цена не меньше R[j], а последующие операции имеют неотрицательную цену.

Проверять только последний элемент R[m] для отсечения нельзя. Сейчас префикс может быть далеко от полного запроса, но его продолжение ещё допишет недостающие символы. Последний элемент используется для принятия именно законченного слова, когда у узла выставлен терминальный флаг. Минимум всей строки используется для запрета всех будущих продолжений.

Автоматное состояние и словарный узел решают разные части задачи

Строку динамики можно понимать как состояние переходной системы, читающей очередную словарную букву. Trie задаёт допустимые слова, а дистанционное состояние ограничивает их близость к запросу. Совместный обход возвращает только терминальные словарные узлы с R[m]≤k.

Для конечного k значения больше k можно насыщать значением k+1, если переходы и отсечение выполняются согласованно. Это уменьшает число разных состояний, но не разрешает менять стоимость операций. Перестановка соседних символов в базовое расстояние Левенштейна не входит. Если нужна другая модель опечаток, необходимо расширить состояние, а не молча добавить новое правило к старой строке.

Общий префикс обслуживает несколько слов

Условие. Для запроса cat и порога k=1 найдите подходящие слова в словаре {at,cart,cat,cats,coat,cut,dog}. Покажите строки для префиксов c,co,do и объясните отсечение.

  1. Корневая строка по префиксам пусто,c,ca,cat равна (0,1,2,3). После буквы c получаем (1,0,1,2); она общая для пяти слов на c.
  2. После co строка равна (2,1,1,2). Последний элемент два больше порога, но минимум один разрешает продолжить ветвь: слово coat находится на расстоянии один.
  3. В другой ветви префикс do даёт (2,2,2,3). Минимум два больше порога, поэтому можно не читать оставшуюся g и отсечь всю эту ветвь.
  4. Законченные слова cat,cart,cats,coat,cut,at имеют расстояния соответственно 0,1,1,1,1,1. Каждое удовлетворяет порогу.
  5. Для dog прямой независимый расчёт даёт расстояние три. Он подтверждает отказ, но обход trie уже доказал невозможность любого подходящего продолжения префикса do.

Ответ. Подходят at,cart,cat,cats,coat,cut; dog исключается. Ветвь do безопасно отсекается, а co — нет, несмотря на последний элемент два.

Проверка. Обычная полная DP для каждой из семи пар независимо проверяет результаты совместного обхода. Сравнение минимума и последнего элемента в co контролирует критическую ошибку отсечения.

Где легко ошибиться. Не отсекайте ветвь по расстоянию текущего префикса до всего запроса. Для безопасной нижней границы нужен минимум расстояний до всех префиксов запроса.

Проверьте понимание

Какой префикс можно безопасно отсечь для запроса cat и k=1?

Вопросы к этой главе

Почему отметка окончания слова всё ещё нужна?

Малое расстояние для префикса не делает его словом словаря. Результат выдаётся только в терминальном узле, иначе будут добавлены несуществующие словарные записи.

Обещает ли метод линейное время по всему словарю?

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

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • Schulz, Mihov: Fast string correction with Levenshtein automata

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

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться