Расстояние редактирования: три операции в одной таблице

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

Как думаешь, почему база не нулевая

У LCS база была простая: с пустой строкой общего ничего, значит нули. Здесь задача другая - превратить одну строку в другую, и вопрос «сколько правок нужно, чтобы превратить «КОШ» в пустую строку» нулевого ответа не имеет.

Прежде чем читать дальше: чему равна первая строка и первый столбец таблицы и почему?

На что это похоже

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

Механизм: три операции, переход, лестница в базе

СОСТОЯНИЕ
d[i][j] = минимальное число правок, чтобы превратить
          первые i символов строки a в первые j символов строки b

состояний (n+1) × (m+1), переход O(1) ⇒ цена Θ(n·m)

ПЕРЕХОД - минимум из трёх

d[i][j] = min(
    d[i−1][j]   + 1,                  УДАЛИТЬ a[i]
    d[i][j−1]   + 1,                  ВСТАВИТЬ b[j]
    d[i−1][j−1] + (0 если a[i] == b[j] иначе 1)   ЗАМЕНИТЬ (или совпало - бесплатно)
)

база - ЛЕСТНИЦА, а не нули:
    d[i][0] = i     превратить i символов в пустую строку = i удалений
    d[0][j] = j     превратить пустую строку в j символов = j вставок

ТРИ СТРЕЛКИ И ИХ СМЫСЛ ПРИ ВОССТАНОВЛЕНИИ
по диагонали без роста значения   → символ оставили
по диагонали с ростом на 1        → замена
сверху                            → удаление символа первой строки
слева                             → вставка символа второй строки

ВАРИАНТЫ ЗАДАЧИ - МЕНЯЕТСЯ ТОЛЬКО ШТРАФ
своя цена операций        замена дороже вставки (у клавиатур - своя матрица)
+ транспозиция            Дамерау-Левенштейн: «ано» ↔ «аон» за одну правку
выравнивание ДНК          Нидлман-Вунш: штраф за пропуск и матрица замен
только вставки/удаления   получается n + m − 2·LCS - связь с прошлым уроком

Правило

Расстояние Левенштейна - минимальное число вставок, удалений и замен, превращающих одну строку в другую. Состояние - пара префиксов (i, j); переход - минимум из трёх: удалить (d[i−1][j] + 1), вставить (d[i][j−1] + 1), заменить (d[i−1][j−1] + 1), причём при совпадении символов диагональ идёт БЕЗ штрафа. База - лестница d[i][0] = i и d[0][j] = j, а не нули: превратить строку в пустую стоит столько правок, сколько в ней символов. Цена Θ(n·m). Список правок восстанавливают обратным проходом, сравнивая значение клетки с тремя источниками. Если запретить замену, расстояние становится n + m − 2·LCS - та же задача, что в прошлом уроке.

Разбор: «КОШКА» → «ЛОЖКА» за две правки

        _   Л   О   Ж   К   А
    _   0   1   2   3   4   5
    К   1   1   2   3   3   4
    О   2   2   1   2   3   4
    Ш   3   3   2   2   3   4
    К   4   4   3   3   2   3
    А   5   5   4   4   3   2

Ответ в правом нижнем углу: 2. Разберём три клетки.

d[1][1] - превратить «К» в «Л»:
    удалить К → d[0][1] + 1 = 2
    вставить Л → d[1][0] + 1 = 2
    заменить К на Л → d[0][0] + 1 = 1       ← минимум
    итог 1

d[2][2] - превратить «КО» в «ЛО»:
    символы совпали (О == О) → диагональ без штрафа: d[1][1] = 1
    удалить  → d[1][2] + 1 = 3
    вставить → d[2][1] + 1 = 3
    итог 1 - одна правка (К→Л), и она уже сделана

d[5][5] - превратить «КОШКА» в «ЛОЖКА»:
    А == А → диагональ без штрафа: d[4][4] = 2
    итог 2

Восстановление - идём от правого нижнего угла и каждый раз спрашиваем, из какой клетки пришли:

d[5][5] = 2, А == А и d[4][4] = 2   → символ оставили:  =А
d[4][4] = 2, К == К и d[3][3] = 2   → оставили:         =К
d[3][3] = 2, Ш ≠ Ж, d[2][2] + 1 = 2 → ЗАМЕНА:           Ш→Ж
d[2][2] = 1, О == О и d[1][1] = 1   → оставили:          =О
d[1][1] = 1, К ≠ Л, d[0][0] + 1 = 1 → ЗАМЕНА:           К→Л

читаем в прямом порядке:  К→Л  =О  Ш→Ж  =К  =А

Две замены - ровно то число, что в углу. Обрати внимание, что таблица не только считает расстояние, но и говорит, ГДЕ именно правки: это и показывает проверка орфографии, подчёркивая конкретные буквы.

Разбор: почему без замены получается LCS

Допустим, замену запретили - остались только вставка и удаление. Тогда любое преобразование выглядит так: часть символов осталась на месте, остальные удалены из первой строки и вставлены из второй.

осталось на месте: это общая подпоследовательность, пусть её длина L
удалено из a:      n − L
вставлено из b:    m − L
правок всего:      (n − L) + (m − L) = n + m − 2L

минимум правок ⇔ МАКСИМУМ L ⇒ L = LCS
расстояние без замены = n + m − 2·LCS

Проверим на «АЛГОРИТМ» и «ЛОГАРИФМ» из прошлого урока: LCS = 5, обе строки по 8 символов, значит 8 + 8 − 10 = 6 правок. А с разрешённой заменой Левенштейн даёт меньше - и дальше разберём, почему именно.

«АЛГОРИТМ» → «ЛОГАРИФМ»
без замены (через LCS):  8 + 8 − 2·5 = 6 правок
Левенштейн:              4 правки

Разница в две правки, и причина тоньше, чем «замена экономит пару операций». Разрешив замену, алгоритм выбирает ДРУГОЕ выравнивание строк - то, где друг против друга стоит больше символов. Здесь оптимальный путь оставляет на месте четыре символа (Г, Р, И, М) и делает четыре замены:

А→Л  Л→О  =Г  О→А  =Р  =И  Т→Ф  =М      итого 4 правки

А путь через LCS оставляет на месте пять символов (ЛГРИМ), но платит за остальные шесть операций удаления и вставки. Пять совпадений оказались дороже четырёх.

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

Что ломается без этого

Первое: заполнить базу нулями по аналогии с LCS. Таблица посчитается, и ответ будет заниженным - алгоритм решит, что превратить строку в пустую бесплатно. Второе: при совпадении символов всё равно прибавлять единицу: расстояние станет равным длине, и это видно только на похожих строках. Третье: перепутать, какая стрелка что значит: «сверху» - это удаление из ПЕРВОЙ строки, и при восстановлении правок ошибка даёт инструкцию, которая не превращает a в b. Четвёртое: считать расстояние по символам, когда данные - строки файла или слова: таблица по символам даст бессмысленные правки внутри слов. Пятое: применять Θ(n·m) к длинным текстам: два текста по сто тысяч символов - это 10^10 клеток. Для таких случаев есть ограничение полосой (O(n·k), если известно, что ответ не больше k) и приближённые методы. Шестое: называть Левенштейном расстояние с транспозицией - это Дамерау-Левенштейн, и его переход содержит четвёртый вариант.

Зачем это в работе

Расстояние редактирования стоит под всем нечётким сравнением строк: проверка орфографии (подсказка «возможно, имелось в виду другое слово»), поиск с опечатками, дедупликация адресов и имён в базах, сопоставление названий товаров из разных источников. В прикладных библиотеках оно почти всегда уже реализовано - rapidfuzz, python-Levenshtein, расширение fuzzystrmatch в PostgreSQL, - и знание устройства нужно для двух вещей. Первое: выбрать правильную метрику. Для опечаток пальцами на клавиатуре нужна транспозиция (Дамерау), для сравнения коротких имён - нормированное расстояние, для адресов - своя цена операций (пропущенный дефис дешевле перепутанной цифры дома). Второе: понимать цену. Θ(n·m) на пару строк - мгновенно, но сравнение каждого с каждым в таблице из миллиона строк - это 10^12 ПАР, и у каждой пары своя таблица, поэтому в реальных системах сначала отбирают кандидатов по быстрому признаку (блокировка по первым буквам, триграммы, MinHash), а расстояние считают только внутри небольшой группы.

Теперь сам

Строки «ДОМ» и «ГНОМ». Заполни таблицу и назови расстояние с правками.

        _   Г   Н   О   М
    _   0   1   2   3   4
    Д   1   1   2   3   4
    О   2   2   2   2   3
    М   3   3   3   3   2

d[3][4] = 2, М == М, d[2][3] = 2   → =М
d[2][3] = 2, О == О, d[1][2] = 2   → =О
d[1][2] = 2, Д ≠ Н, d[0][1] + 1 = 2 → Д→Н
d[0][1] = 1, вставка                → +Г

в прямом порядке:  +Г  Д→Н  =О  =М