Расстояние редактирования Левенштейна-расстояния между списками является хорошо изученной проблемой. Но я не могу найти много о возможных улучшениях, если известно, что ни один элемент не встречается более одного раза в каждом списке .
Также предположим, что элементы сопоставимы / сортируемы (но списки для сравнения не сортируются с самого начала).
В частности, меня интересует, позволяет ли уникальность элементов улучшить алгоритм Укконена для редактирования расстояния, который имеет временную сложность и пространственная сложность , где - минимум стоимость шагов редактирования .
Более формально,
насколько эффективно мы можем вычислить расстояние редактирования между двумя заданными строками с обещанием, что у них нет повторяющихся букв?
это очень большой алфавит.
источник
Ответы:
TL; DR: немного более ограничивающий тип расстояния редактирования, на котором мы можем вставлять и удалять только отдельные символы, может быть вычислен за линейное время, когда обе (или даже только одна) строки имеют уникальные символы. Это дает полезные верхние и нижние границы на расстоянии редактирования Левенштейна.
Вставить / удалить расстояние редактирования и самые длинные общие подпоследовательности
Расстояние редактирования Левенштейна позволяет вставлять, удалять и заменять односимвольные символы, назначая каждому стоимость в 1. Если мы ограничиваемся только вставками и удалениями, мы получаем аналогичную меру расстояния, которая теперь приводит к тому, что замены имеют стоимость 2 (поскольку любая подстановка может подражать с использованием вставки и удаления). Я не знаю стандартного имени для этого более ограничительного вида расстояния редактирования, поэтому я назову его «вставить / удалить расстояние редактирования». Это близко соответствует проблеме самой длинной общей подпоследовательности (LCS) , в которой нам даны две строки, длины и соответственно, и мы хотим узнать длину самой длинной подпоследовательности, которая появляется в обеих. Если две строки имеют LCSm n L , тогда у них есть расстояние редактирования вставки / удаленияn+m−2L : самый простой способ увидеть это - выровнять строки так, чтобы символы в LCS выглядели сложенными друг над другом, в то время как символы не в LCS появляются напротив
-
пробела персонаж. Тогда будет очевидно, что мы можем отредактировать первую строку во вторую, сделав вставку, где есть-
в верхней строке, и удаление, где есть-
в нижней строке. Например:Здесь LCS of6+7−2∗4=5
CIRCLE
иTRICKLE
,ICLE
имеет длину 4, и расстояние редактирования действительно равно .Самые длинные увеличивающиеся подпоследовательности
Причина этого обхода заключается в том, что существует очень эффективный способ вычисления LCS (и, следовательно, расстояния редактирования вставки / удаления), когда хотя бы одна из последовательностей содержит только отдельные символы: в этом случае проблему LCS можно преобразовать в проблема нахождения максимально увеличивающейся подпоследовательности , которая может быть решена за время . Предположим, нам даны две строки и , а строка имеет разные символы. Мы можем переименовать первый символ в в 1, второй в 2 и так далее, отслеживая, какое число мы присвоили каждому символу в таблице. Потом вO(nlogn) A B A A B мы переименовываем его символы, используя эту таблицу (т. е. каждое вхождение того, в чём был первый символ, O(n+mlogm) A B n m
A
изменяется на 1 и т. д.). Наконец, мы ищем самую длинную возрастающую подпоследовательность вB
. Это соответствует LCS междуA
иB
, и оттуда мы можем сразу вычислить расстояние редактирования вставки / удаления. Общее необходимое время составляет всего если и имеют длины и соответственно.Границы Левенштейна редактируют расстояние
Расстояние вставки / удаления четко обеспечивает верхнюю границу расстояния Левенштейна (поскольку любая действительная последовательность операций редактирования под расстоянием вставки / удаления также является допустимой последовательностью операций редактирования Левенштейна). Разделение расстояния редактирования вставки / удаления на 2 также дает нижнюю границу, поскольку в худшем случае любую операцию редактирования Левенштейна можно изменить на 2 операции редактирования вставки / удаления.
Обобщения
Уже в 1977 году Хант и Шимански придумали алгоритм, который можно рассматривать как обобщение алгоритма с наибольшей возрастающей подпоследовательностью. Это эффективно всякий раз, когда количество пар совпадающих позиций символов между двумя строками мало. Если таких пар , их алгоритм занимает времени. (Обратите внимание, что если все символы в одной строке различны.) Этот алгоритм был основой исходной программы, которая рассматривала целые строки текста как отдельные символы. позже переключился на использование алгоритма Майерса, гдеr O((r+n)logn) r≤n O(nd) d это расстояние редактирования вставки / удаления, так как оно работает лучше, когда общие различия невелики, но некоторые «символы» (текстовые строки) появляются часто (например, строка, содержащая только открывающую фигурную скобку в программном коде на Си).
diff
diff
источник