Редакционное расстояние

Наберите «балконский». Спеллер ниже знает 47 585 слов «Войны и мира» и через несколько миллисекунд предлагает «болконский»: до него одна замена буквы. Чтобы это утверждать, он должен знать, что все остальные слова дальше, — то есть хоть как-то сравнить опечатку с каждым из них. Рядом — таблица, которой сравнивают два слова, под ней — выравнивание, ещё ниже — на каком расстоянии опечатка от каждого слова словаря. Попробуйте свои опечатки и другой предел правок.

Посмотрите на нижний график. Из 47 585 слов романа в двух правках от «балконского» всего пять: «болконский», «волконский» и ещё три формы фамилии Болконских. Остальные далеко, чаще всего — в девяти правках. Значит, почти вся работа спеллера уходит на то, чтобы убедиться, что слово не подходит. Полная таблица для каждого слова — это 4 017 020 клеток на одну опечатку. Спеллер считает 353 105, в одиннадцать раз меньше, и ответ при этом точный. Как он это делает, разберём после того, как поймём саму таблицу.

Идея

Редакционное расстояние, или расстояние Левенштейна, между двумя строками — наименьшее число правок, которыми одна превращается в другую. Правка — вставить букву, удалить букву или заменить одну букву другой. От «балконский» до «болконский» — одна замена, от «одьютант» до «адъютант» — две, от «kitten» до «sitting» — три.

Посмотрим, что стало с последней буквой первого слова. Её либо удалили, либо заменили последней буквой второго слова (может быть, бесплатно — если они совпадают), либо она осталась, а в конец вставили последнюю букву второго слова. В каждом случае остаётся та же задача для более коротких начал слов. Значит, расстояние между всеми началами можно записать в таблицу и заполнить её строка за строкой: каждая клетка — минимум из трёх соседних плюс цена последней правки.

Таблица и пути по ней

Пусть a длины m и b длины n. Клетка D[i][j] таблицы — расстояние между первыми i буквами a и первыми j буквами b:

Края понятны: i букв превращаются в пустую строку i удалениями, пустая строка в j букв — j вставками. Вот таблица для «одьютант» и «адъютант» из листинга ниже:

        а  д  ъ  ю  т  а  н  т
     0  1  2  3  4  5  6  7  8
  о  1  1  2  3  4  5  6  7  8
  д  2  2  1  2  3  4  5  6  7
  ь  3  3  2  2  3  4  5  6  7
  ю  4  4  3  3  2  3  4  5  6
  т  5  5  4  4  3  2  3  4  5
  а  6  5  5  5  4  3  2  3  4
  н  7  6  6  6  5  4  3  2  3
  т  8  7  7  7  6  5  4  3  2

Таблицу удобно читать как карту. Из каждой клетки можно шагнуть вниз — удалить букву первого слова, вправо — вставить букву второго, по диагонали — оставить букву, если она совпадает, или заменить. Каждый способ превратить одно слово в другое — это путь из левого верхнего угла в правый нижний, а его цена — сумма шагов. Расстояние — цена самого дешёвого пути, и на этой карте его можно было бы искать алгоритмом Дейкстры. Но граф здесь особенный: все шаги ведут вниз и вправо, поэтому клетки можно просто обойти по строкам, и к каждой клетке все её предшественницы уже готовы.

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

Расстояние — настоящая метрика: оно ноль только для равных строк, симметрично (вставку и удаление можно поменять местами) и подчиняется неравенству треугольника: d(a, c) ≤ d(a, b) + d(b, c), потому что правки из a в b и из b в c вместе превращают a в c. Последнее свойство пригодится, когда будем строить индекс.

Цены правок и выравнивание

Ничто не мешает правкам стоить по-разному. Секвенаторы Illumina чаще путают буквы, чем теряют их, — для них замена дешевле пропуска; у нанопоровых наоборот. Человек на клавиатуре чаще промахивается на соседнюю клавишу — значит, замена «а» на «ф» дешевле замены «а» на «щ». Формула остаётся той же, только вместо единиц — цены. Поменяйте их ниже и посмотрите, как меняется самый дешёвый путь.

Когда замена стоит 1, выравнивание GCATGCG и GATTACA — четыре замены и цена 4. Поставьте цену замены 3: заменять стало дороже, чем удалить букву и вставить другую, и путь уходит с диагонали лестницей — три удаления и три вставки, цена 6. При замене ценой 2 и больше она вообще не нужна, и расстояние превращается в m + n − 2 · LCS, где LCS — длина наибольшей общей подпоследовательности: всё, что не вошло в общую часть, удаляют из одного слова и вставляют из другого.

Закрашенные клетки — те, через которые проходит хотя бы один самый дешёвый путь, и путей часто много. Расстояние единственно, выравниваний может быть десятки, и программа выбирает одно по правилу, в каком порядке проверять соседей. В листинге сначала диагональ, потом удаление, потом вставка; утилиты сравнения текстов выбирают по-своему, и поэтому две программы могут показать одну и ту же правку по-разному.

Код

Таблица целиком и путь назад от угла. В демо — таблица из начала статьи, выравнивания нескольких пар и выравнивание с дорогой заменой: в средней строке | — совпадение, * — замена, пробел — вставка или удаление.

Обратите внимание на «войнаимир»: ближайшее слово романа — «войнами», в двух правках. Пробелы опечаткой не считаются: «войнаимир» для спеллера — одно слово, которого нет, а не три слова без пробелов. Разбивать строку на слова — отдельная задача.

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

Как не сравнивать со всеми

У спеллера три приёма, и все три опираются на одно: нам не нужно точное расстояние до слов, которые дальше k. Достаточно знать, что они дальше.

1. Фильтр по длине. Каждая вставка или удаление меняет длину на единицу, замена не меняет, поэтому d(a, b) ≥ |m − n|. Слова, длина которых отличается больше чем на k, можно не смотреть. Для «балконского» из 47 585 слов остаётся 25 713.
2. Полоса. По той же причине D[i][j] ≥ |i − j|: клетки дальше k от главной диагонали заведомо больше k, и считать их незачем. Остаётся полоса шириной 2k + 1 — в сцене это клетки в рамках, серые числа вне её спеллер не вычисляет. Работа на одно слово падает с m · n до (2k + 1) · m.
3. Ранняя остановка. Любой путь к правому нижнему углу проходит через каждую строку таблицы, а по пути цена только растёт. Поэтому, если в очередной строке все числа больше k, итог тоже больше k, и слово можно бросить. На словах, не похожих на опечатку, строки переполняются через три-четыре буквы: для «балконского» спеллер в среднем считает 14 клеток на слово вместо 84 в полной таблице.

Вместе это 353 105 клеток вместо 4 017 020 — в 11 раз меньше. В браузере сцена тратит на это несколько миллисекунд, а гистограмме снизу, которой нужны точные расстояния до всех слов, приходится считать полные таблицы. Но перебор остаётся перебором: каждое слово словаря хоть раз да тронуто. Чтобы не трогать большинство слов вовсе, нужен индекс.

• BK-дерево (Буркхард и Келлер, 1973) раскладывает словарь по расстояниям от слов-узлов. Если до узла x от запроса d, то по неравенству треугольника интересны только поддеревья слов, чьё расстояние до x лежит в [d − k, d + k], остальные отбрасываются целиком. Подробности — в статье о BK-дереве.
• Автомат Левенштейна. Для запроса и предела k строят конечный автомат, который принимает ровно строки не дальше k, и прогоняют его по бору словаря, отсекая ветки, где автомат умер. Так с версии 4.0 работает нечёткий поиск в Lucene, на котором стоят Elasticsearch и Solr; поиск стал быстрее прежнего в сто с лишним раз. Больше двух правок Lucene не допускает.
• Симметричное удаление. Заранее для каждого слова словаря выписывают все строки, получающиеся удалением до k букв, и кладут слово в хеш-таблицу под каждой. Две строки на расстоянии не больше k обязательно имеют общую такую строку, поэтому кандидаты для запроса находятся несколькими поисками в таблице. Попробуйте в задаче о словаре опечаток.

Сколько это стоит

Приём Хиршберга (1975) нужен, когда строки длинные, а выравнивание нужно целиком: таблицу считают от начала до средней строки и от конца до неё же, находят, где лучший путь пересекает середину, и решают две половины отдельно. Квадрат m·n клеток в памяти не держится никогда.

Замер: две версии случайной строки ДНК длины n, в каждой сотой позиции другая буква. Полная таблица против полосы шириной 17 клеток (k = 8).

Наклон полной таблицы — 2: вдвое длиннее строки, вчетверо больше клеток. Наклон полосы — 1. На строках из 800 букв полоса в Python быстрее в 62 раза, и разрыв растёт с длиной. Но полоса годится, только если заранее известен предел k. Если он неизвестен, его удваивают: 1, 2, 4, … , пока расстояние не окажется в пределах полосы, — суммарная работа всё равно O(d · n), где d — ответ. Считать только полосу и расширять её, пока ответ в неё не поместится, предложил Эско Укконен в 1985 году.

Варианты

Перестановки. Фред Дамерау в 1964 году, изучая ошибки набора, насчитал больше 80 % опечаток, которые сводятся к одной вставке, одному удалению, одной замене или перестановке двух соседних букв. По Левенштейну перестановка — две правки: «кнзяь» отстоит на две и от «князь», и от «князя», и от «казнь». Включите в первой сцене «перестановка — одна правка»: в таблицу добавляется четвёртый переход, из клетки через одну по диагонали, и «князь» уходит в отрыв. Такая версия называется расстоянием оптимального выравнивания строк. Она проста, но уже не метрика: у «CA» и «AC» расстояние 1, у «AC» и «ABC» — 1, а у «CA» и «ABC» — 3, и неравенство треугольника нарушено. Полное расстояние Дамерау — Левенштейна, где переставленные буквы можно потом ещё и править, считают сложнее (Лоуренс и Вагнер, 1975).

Веса. Настоящие спеллеры ценят правки по вероятности: соседние клавиши, безударные гласные («карова»), удвоенные согласные. Формула та же, меняются цены.

Выравнивание в биологии. В последовательностях белков и ДНК замены одних букв на другие тоже имеют разную цену, а пропуск подряд нескольких букв дешевле, чем столько же разрозненных. Это алгоритм Нидлмана — Вунша (1970) для выравнивания целиком и Смита — Уотермана (1981) для поиска самого похожего куска; оба — в статье о выравнивании последовательностей. Попробуйте сами в задаче об ошибках секвенатора.

Сравнение файлов. diff сравнивает строки файлов, а не буквы, и разрешает только вставки и удаления. Это та же таблица, но Юджин Майерс в 1986 году нашёл способ обходить её за O((m + n) · d), где d — число отличий: так работает git. Подробнее — diff Майерса.

История

Расстояние придумывали несколько раз, в разных науках и для разных нужд. Владимир Левенштейн ввёл его в 1965 году в «Докладах Академии наук», когда искал коды, исправляющие не только искажения символов, но и выпадения и вставки; историю этой работы подробно рассказывает глава курса о динамическом программировании. Годом раньше Фред Дамерау из IBM опубликовал способ находить и исправлять опечатки, где перестановка соседних букв считалась одной ошибкой. Таблицу для вычисления находили независимо: Тарас Винцюк в 1968 году — для распознавания речи, Сол Нидлман и Кристиан Вунш в 1970-м — для сравнения белков, Роберт Вагнер и Майкл Фишер в 1974-м — для исправления строк, и в информатике её часто называют их именами. В 1983 году Дэвид Санкофф и Джозеф Краскал собрали эти открытия в одну книгу, «Time Warps, String Edits, and Macromolecules», и показали, что речь, тексты и молекулы сравнивают одной и той же таблицей.

Задачи

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