Задачи на «Элементах» (№55)

Решение

Начнем с задания 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.