Расстояние Дамерау–Левенштейна

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

Начнем с задания 2. Расстояние Дамерау–Левенштейна между двумя словами — это минимальное количество элементарных операций, которые необходимо совершить, чтобы получить одно слово из другого. Элементарные операции таковы: удаление одного символа; добавление одного символа; замена одного символа другим; перестановка двух соседних символов. (Если сократить число разрешенных операций до трех, убрав перестановку, то получится мера, которую называют просто расстоянием Левенштейна.)

Соответственно, четыре класса опечаток, которые выделил Дамерау, разрабатывая алгоритм их автоматического исправления, — это пропуск символа; лишний символ; замена символа на другой; перепутанный порядок двух соседних символов.

Иногда решатели, выполняя задание 2, пытаются вместо определения изложить алгоритм, который позволял бы находить расстояние Дамерау–Левенштейна. Это, однако, довольно сложно, и для решения данной задачи совершенно не необходимо, достаточно дать определение в духе изложенного выше.

Теперь мы можем выполнить задание 1:

Некоторые пары заслуживают дополнительного комментария. Поскольку менять местами можно только соседние символы (это следует из пары peat–tape в условии: расстояние 4, а не 2), расстояние между eel и lee — 2, а не 1.

Поскольку все операции проводятся над одиночными символами, а не над произвольными последовательностями символов (это опять же видно из пары peat–tape), расстояние между seatback и backseat — не 1 (как интуитивно кажется человеку), и не 4, как нередко отвечают решатели, а 8.

Еще одна распространенная ошибка — считать, что расстояние между ape и ea равняется 3. Те, кто предлагают такое решение, исходят из того, что алгоритм движется по строке строго в одном направлении (слева направо или справа налево) и возвращаться не может, то есть однажды редактированную подстроку нельзя редактировать второй раз. Если, редактируя ape, мы пропустили a и удалили p (получив ae), то, следуя этой логике, мы уже не можем использовать операцию перестановки, вовлекающую a. В определении расстояния Дамерау–Левенштейна, однако, такого ограничения не содержится (это видно из пары lyra–lay), так что ответ всё же 2. Расстояние же, рассчитываемое с учетом этого ограничения, — это другая мера, которую иногда называют ограниченным редакционным расстоянием. Интересно, что некоторые доступные в интернете алгоритмы, заявленные как определяющие расстояние Дамерау–Левенштейна, на самом деле определяют именно ограниченное редакционное расстояние (видимо, потому, что его определить технически проще).

Наконец, задание 3 — чисто математическое упражнение. Очевидно, расстояние Дамерау–Левенштейна не может превышать длину более длинного слова (заменой всех символов из него заведомо можно получить всё, что угодно), таким образом максимальное расстояние — m. Минимальное же расстояние — m – n (число символов, которое необходимо добавить к короткому слову, чтобы получить длинное). Часто дается ответ 1, однако он не годится, так как в условии требуется выразить ответ через m и n.

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

Левенштейн в 1965 году рассматривал свойства двоичных кодов, способных исправлять заданное число изменений s (V. I. Levenshtein, 1966. Binary codes capable of correcting deletions, insertions, and reversals). Под двоичным кодом здесь подразумевается произвольное множество слов фиксированной длины l в двоичном алфавите (то есть алфавите из символов 0 и 1), под способностью исправлять — возможность получить любое слово длины l из одного и только одного слова данного кода не более чем за s изменений, а под изменениями — вставка, удаление и замена.

Дамерау в 1963 году решал более конкретную задачу — как улучшить систему информационного поиска, научив компьютер распознавать ошибки (Fred J. Damerau. A technique for computer detection and correction of spelling errors). Ручное исправление, отмечал Дамерау, скоро станет невозможным из-за увеличения объемов лексической информации, которую обрабатывают компьютеры. Он обнаружил, что более 80% слов, которые система не могла распознать из-за опечаток, попадали в один из четырех классов (одна буква отсутствует, одна буква лишняя, одна буква заменена на другую, две соседних буквы переставлены местами), и разработал алгоритм, который позволял исправлять большинство таких опечаток.

Иллюстрация из статьи Фредерика Дамерау 1963 года

В истории, однако, их имена остались связанными в первую очередь с расстояниями. Расстояние Левенштейна — наверное, самый известный и широко используемый способ сравнить две строки. Расстояние Дамерау–Левенштейна используется реже (и, как читатель может убедиться даже на примерах из задачи, часто совпадает с классическим расстоянием Левенштейна). Еще одно известное расстояние — расстояние Хэмминга (в честь знаменитого ученого Ричарда Хэмминга, много работавшего над исправлением ошибок). Оно используется только для сравнения двух слов одинаковой длины и определяется просто как количество необходимых замен. (Имя Хэмминга носит также престижная медаль, ежегодно присуждаемая за вклад в информатику, которую в 2006 году получил и Левенштейн.)

Длина слова — дополнительный фактор при определении расстояний. Как мы знаем из третьего задания, максимальное расстояние зависит от длины наибольшего слова. Расстояние между словами я и ты — 2, а между словами яблоня и яблонька — 3, в то время как человеку очевидно, что в первой паре слова совсем непохожи, а во второй паре — похожи. Поэтому расстояние нередко нормализуется, то есть делится на длину наибольшего слова. Значение нормализованного расстояния лежит между 0 и 1, для пары я–ты оно составляет 1, а для пары яблоня–яблонька — 0,375.

Все перечисленные до сих пор расстояния относятся к классу редакционных расстояний, то есть определяются через число необходимых элементарных операций. Собственно последовательность операций, которую нужно выполнить, называют редакционным предписанием. Для расстояния Левенштейна редакционное предписание можно найти, используя алгоритм Вагнера–Фишера (см. Wagner–Fischer algorithm).

Очевидно, что в некоторых случаях расстояние Дамерау–Левенштейна возвращает неидеальный результат. Мы уже видели в задаче, что peat и tape, lee и eel и особенно seatback и backseat оказываются дальше друг от друга, чем, возможно, хотелось бы, но это лишь одна из возможных проблем.

Существуют десятки иных способов измерить схожесть двух строк (можно порекомендовать краткий обзор множества разных способов здесь или более основательное описание нескольких ключевых классов способов здесь).

В одном распространенном классе расстояний ключевую роль играет выравнивание последовательностей. В отличие от классических редакционных расстояний, методы выравнивания пришли из биоинформатики, то есть изначально были разработаны не для обработки текстов, а для сравнения белковых и нуклеотидных последовательностей. Известным примеров является алгоритм Нидлмана–Вунша. Он похож на вычисление расстояния Левенштейна, но операциям можно приписать разный вес. Кроме того, для каждой пары символов можно задать степень их похожести (то есть сказать, например, что b больше похоже на p, чем на a). Наконец, в целях выравнивания строку разрешается разрывать (получая, например, нечто вроде CRATE/C-AT), за что полагается штраф заданной величины.

Другое решение — представить строку как вектор. Это можно сделать, например, задав некоторый язык (множество слов), а затем подсчитав, сколько раз каждое слово данного языка встречается в качестве подстроки данной строки. Если, например, мы зададим язык {aaa, aab, aba, abb, baa, bab, bba, bbb} и векторизуем слова ababba и bababb, мы получим два восьмимерных вектора (0, 0, 1, 1, 0, 1, 1, 0) и (0, 0, 1, 1, 0, 2, 0, 0) (пример отсюда). Для того же, чтобы сравнить два вектора, существует множество математических способов: можно рассчитать косинус угла между ними (см. Cosine similarity), рассчитать Евклидово расстояние или воспользоваться какой-нибудь из более изощренных мер.

Встречаются более специфические решения. Так, например, есть способы сравнивать звучание двух слов, исходя из их записи: это полезно при проверке орфографии, поскольку люди склонны путать именно похоже звучащие слова. Недавно разработанный метод Most frequent k characters представляет слово как последовательность k самых частотных в данном слове символов с указанием их частотности, а затем специальным образом сравнивает эти представления. Так, например, при k = 2 слово Левенштейн будет представлено как е3н2, а слово Дамерау — как а2Д1 (Д берется как первый из равночастотных символов). Проверка, которую провели разработчики этой меры (используя различные расстояния в одном и том же алгоритме определения авторства текстов), показала, что она немного уступает расстоянию Левенштейна в точности, но зато требует меньше времени для вычисления.

Владимир Левенштейн (третий слева) на приеме в Университете Билефельда (Германия) в 2003 году

Последний пример особенно наглядно показывает, что любая попытка количественно измерить схожесть двух слов всегда повлечет за собой какую-нибудь потерю информации (расстояние Левенштейна «не видит» сходства seatback и backseat; описанный выше способ векторизации не учитывает порядка подстрок в строке; последний описанный метод просто отбрасывает значительную часть символов и т. п.). Таким образом, для любой меры найдутся пары слов, где ее значение будет не вполне интуитивно. Это, разумеется, учитывают, когда выбирают меру, лучше всего подходящую для конкретной задачи, будь то исправление опечаток, классификация текстов, определение родства языков, сравнение текстовых стимулов в психологических экспериментах, сравнение ДНК или что-нибудь еще.

Задача использовалась на Латвийской олимпиаде по лингвистике в 2015 году.