Изменить расстояние списка с уникальными элементами

12

Расстояние редактирования Левенштейна-расстояния между списками является хорошо изученной проблемой. Но я не могу найти много о возможных улучшениях, если известно, что ни один элемент не встречается более одного раза в каждом списке .

Также предположим, что элементы сопоставимы / сортируемы (но списки для сравнения не сортируются с самого начала).

В частности, меня интересует, позволяет ли уникальность элементов улучшить алгоритм Укконена для редактирования расстояния, который имеет временную сложность O(min(m,n)s) и пространственная сложность O(min(s,m,n)s) , где s - минимум стоимость шагов редактирования .

Более формально,

насколько эффективно мы можем вычислить расстояние редактирования между двумя заданными строками s,tΣ с обещанием, что у них нет повторяющихся букв?

Σ это очень большой алфавит.

user362178
источник
Какой у тебя вопрос сейчас? Как ускорить попарное редактирование расстояния или как ускорить вычисление всех попарных расстояний в списке строк?
Рафаэль
2
Я подозреваю, что вопрос заключается в следующем: как вычислить расстояние редактирования между , где - строки в очень большом алфавите , и мы гарантируем, что ни одна буква не появится дважды в или в (OP представляет каждую строку как список букв, то есть список элементов). Но это требует подтверждения. s,ts,tΣΣst
DW
Да, в этом случае большой алфавит состоит из индексов базы данных, а «строки», s и t, представляют собой списки, содержащие эти индексы.
user362178
Для тех, кто интересуется сложностями: и - это длина входных строк, а - фактическое расстояние редактирования, поэтому оно включено в сложность. Стоимость каждого редактирования считается 1 , но, вероятно , не имеет значения для вычисления этого расстояния (количество правок ). mnss
Альберт Хендрикс

Ответы:

3

TL; DR: немного более ограничивающий тип расстояния редактирования, на котором мы можем вставлять и удалять только отдельные символы, может быть вычислен за линейное время, когда обе (или даже только одна) строки имеют уникальные символы. Это дает полезные верхние и нижние границы на расстоянии редактирования Левенштейна.

Вставить / удалить расстояние редактирования и самые длинные общие подпоследовательности

Расстояние редактирования Левенштейна позволяет вставлять, удалять и заменять односимвольные символы, назначая каждому стоимость в 1. Если мы ограничиваемся только вставками и удалениями, мы получаем аналогичную меру расстояния, которая теперь приводит к тому, что замены имеют стоимость 2 (поскольку любая подстановка может подражать с использованием вставки и удаления). Я не знаю стандартного имени для этого более ограничительного вида расстояния редактирования, поэтому я назову его «вставить / удалить расстояние редактирования». Это близко соответствует проблеме самой длинной общей подпоследовательности (LCS) , в которой нам даны две строки, длины и соответственно, и мы хотим узнать длину самой длинной подпоследовательности, которая появляется в обеих. Если две строки имеют LCSmnL, тогда у них есть расстояние редактирования вставки / удаленияn+m2L : самый простой способ увидеть это - выровнять строки так, чтобы символы в LCS выглядели сложенными друг над другом, в то время как символы не в LCS появляются напротив -пробела персонаж. Тогда будет очевидно, что мы можем отредактировать первую строку во вторую, сделав вставку, где есть -в верхней строке, и удаление, где есть -в нижней строке. Например:

-C-IRC-LE
T-RI-CKLE

Здесь LCS of CIRCLEи TRICKLE, ICLEимеет длину 4, и расстояние редактирования действительно равно .6+724=5

Самые длинные увеличивающиеся подпоследовательности

Причина этого обхода заключается в том, что существует очень эффективный способ вычисления LCS (и, следовательно, расстояния редактирования вставки / удаления), когда хотя бы одна из последовательностей содержит только отдельные символы: в этом случае проблему LCS можно преобразовать в проблема нахождения максимально увеличивающейся подпоследовательности , которая может быть решена за время . Предположим, нам даны две строки и , а строка имеет разные символы. Мы можем переименовать первый символ в в 1, второй в 2 и так далее, отслеживая, какое число мы присвоили каждому символу в таблице. Потом вO(nlogn)ABAABмы переименовываем его символы, используя эту таблицу (т. е. каждое вхождение того, в чём был первый символ, Aизменяется на 1 и т. д.). Наконец, мы ищем самую длинную возрастающую подпоследовательность в B. Это соответствует LCS между Aи B, и оттуда мы можем сразу вычислить расстояние редактирования вставки / удаления. Общее необходимое время составляет всего если и имеют длины и соответственно.O(n+mlogm)ABnm

Границы Левенштейна редактируют расстояние

Расстояние вставки / удаления четко обеспечивает верхнюю границу расстояния Левенштейна (поскольку любая действительная последовательность операций редактирования под расстоянием вставки / удаления также является допустимой последовательностью операций редактирования Левенштейна). Разделение расстояния редактирования вставки / удаления на 2 также дает нижнюю границу, поскольку в худшем случае любую операцию редактирования Левенштейна можно изменить на 2 операции редактирования вставки / удаления.

Обобщения

Уже в 1977 году Хант и Шимански придумали алгоритм, который можно рассматривать как обобщение алгоритма с наибольшей возрастающей подпоследовательностью. Это эффективно всякий раз, когда количество пар совпадающих позиций символов между двумя строками мало. Если таких пар , их алгоритм занимает времени. (Обратите внимание, что если все символы в одной строке различны.) Этот алгоритм был основой исходной программы, которая рассматривала целые строки текста как отдельные символы. позже переключился на использование алгоритма Майерса, гдеrO((r+n)logn)rndiffdiffO(nd)d это расстояние редактирования вставки / удаления, так как оно работает лучше, когда общие различия невелики, но некоторые «символы» (текстовые строки) появляются часто (например, строка, содержащая только открывающую фигурную скобку в программном коде на Си).

Хант, Дж .; Шиманский Т. (1977), «Быстрый алгоритм вычисления самых длинных общих подпоследовательностей», Сообщения ACM, 20 (5): 350–353, doi: 10.1145 / 359581.359603

j_random_hacker
источник