Редактировать расстояние с помощью операций перемещения

13

Мотивация: соавтор редактирует рукопись, и я хотел бы увидеть четкое резюме изменений. Все инструменты, подобные "diff", как правило, бесполезны, если вы одновременно перемещаете текст (например, реорганизуете структуру) и делаете локальные правки. Неужели так сложно понять это правильно?


Определения: я хотел бы найти минимальное расстояние редактирования, где разрешены операции:

  • «дешевые» операции: добавление / изменение / удаление одного символа (обычные операции Левенштейна),

  • «дорогой»: операции: переместить подстроку в новое место ( для любых строк a , b , c , d ).abcdacbdabcd

Учитывая две строки и y и целые числа k и K , я хотел бы решить следующую проблему:xykK

  • Вы можете преобразовать в y, используя не более k дешевых операций и не более K дорогих операций?xykK

Вопросов:

  1. У этой проблемы есть имя? (Это звучит как очень стандартный вопрос в контексте выравнивания последовательностей.)

  2. Это сложно?

  3. Если это сложно, можно ли с фиксированным параметром трактоваться с помощью K в качестве параметра?

  4. Существуют ли эффективные алгоритмы аппроксимации? (Например, найти решение с не более чем дешевыми и 2 К дорогим операциям , если решение с K дешевыми и K дорогих операциями существуют.)2k2KkK

Я пытался взглянуть на строковые метрики, перечисленные в Википедии , но ни один из них не выглядел правильно.

Юкка Суомела
источник
3
Для проблема состоит в сортировке по транспозициям. См., Например, web.cs.dal.ca/~whidden/HThesis07.pdf Я не сталкивался с вашей проблемой, но она выглядит очень хорошо мотивированной. k=0
Серж Гасперс
4
NP-сложность задачи сортировки по транспозициям была доказана в 2010 г., см. Сортировка по транспозициям затруднена .
Марцио де Биаси
3
Перестановки сложны, но вставки и удаления - нет. Если вы допускаете, чтобы дорогой операцией было либо удаление произвольной подстроки, либо вставка любой подстроки другой строки, проблема должна стать довольно простой. Однако полученное расстояние не будет симметричным.
Джоуни Сирен,
Мне более любопытно, что трактуемость с фиксированными параметрами. Есть ли новое открытие?
Исинь Цао

Ответы:

5

Как прокомментировал Серж Гасперс, для проблема заключается в сортировке по транспозициям , которая была введена Бафной и Певзнером в 1995 году. Ее NP-твердость была доказана только в 2010 году; см. Laurent Bulteau, Guillaume Fertin и Irena Rusu, «Сортировка по транспозиции затруднительна» .k=0

Марцио де Биаси
источник
4

Проблема становится проще, если мы рассмотрим длинные удаления и копирование подстрок вместо транспозиций. Предположим, что мы используем стандартный алгоритм динамического программирования для вычисления расстояния редактирования и что дорогая операция длины увеличивает расстояние на a k + b , для некоторых констант a , b 0 . Эти константы могут быть разными для длинных удалений и копирования подстрок.kak+ba,b0

Длинное удаление - это удаление произвольной подстроки из . Поддержать их легко, если мы разбиваем их на два вида простых операций: удаление первого символа (стоимость a + b ) и расширение удаления на один символ (стоимость a ). В дополнение к стандартному массиву A , где A [ i , j ] - расстояние редактирования между префиксами x [ 1 i ] и y [ 1 jxa+baAA[i,j]x[1i] , мы используем другой массив A dy[1j]Adсохранить расстояние редактирования, когда последней использованной операцией было длительное удаление. С этим массивом мы должны смотреть только на , A [ i - 1 , j - 1 ] , A [ i , j - 1 ] и A d [ i - 1 , j ] при вычислении A [ i , j ] и A d [ iA[i1,j]A[i1,j1]A[i,j1]Ad[i1,j]A[i,j] , что позволяет нам сделать это за O ( 1 ) раз.Ad[i,j]O(1)

Копирование подстроки означает вставку произвольной подстроки в редактируемую строку. Как и в случае длинных удалений, мы разбиваем операцию на две простые операции: вставка первого символа и расширение вставки на один символ. Мы также используем массив A s для хранения расстояния редактирования между префиксами при условии, что последней использованной операцией было копирование подстроки.xAs

Эффективно сделать это сложнее, чем с длинными удалениями, и я не уверен, сможем ли мы получить амортизированное раз на ячейку. Мы строим дерево суффиксов для x , которое занимает время O ( | x | ) , предполагая алфавит постоянного размера. Мы сохраняем указатель на текущий узел дерева суффиксов в A s [ i , j - 1 ] , что позволяет нам проверять в постоянное время, можем ли мы расширить вставку символом y [ j ] . Если это правда, мы можем вычислить A [ IO(1)xO(|x|)As[i,j1]y[j] и A s [ i , j ]A[i,j]As[i,j] в постоянном времени.

В противном случае , где z - вставленная подстрока, которая использовалась для вычисления A s [ i , j - 1 ] , не является подстрокой x . Мы используем дерево суффиксов, чтобы найти самый длинный суффикс z в z , для которого z y [ j ] является подстрокой x в O ( | z | - | z | )zy[j]zAs[i,j1]xzzzy[j]xO(|z||z|) времени. Вычислить , теперь нам нужно взглянуть на ячейки A [ i , j - | z | - 1 ] до A [ i , j - 1 ] . Нахождение суффикса z требует только амортизированного времени O ( 1 ) на ячейку, но вычисление A s [ i , j ] с использованием метода грубой силы требует O ( | z)As[i,j]A[i,j|z|1]A[i,j1]zO(1)As[i,j]O(|z|) Время. Вероятно, есть какой-то способ сделать это более эффективно, но я не могу найти это прямо сейчас.

O(min(|x||y|2,|x|2|y|)) time, but a better analysis should be possible. The resulting edit distance with long deletions and substring copying is not symmetric, but that should not be a problem. After all, it is usually easier to reach the empty string from a nonempty one than the other way around.

Jouni Sirén
источник