Мотивация: соавтор редактирует рукопись, и я хотел бы увидеть четкое резюме изменений. Все инструменты, подобные "diff", как правило, бесполезны, если вы одновременно перемещаете текст (например, реорганизуете структуру) и делаете локальные правки. Неужели так сложно понять это правильно?
Определения: я хотел бы найти минимальное расстояние редактирования, где разрешены операции:
«дешевые» операции: добавление / изменение / удаление одного символа (обычные операции Левенштейна),
«дорогой»: операции: переместить подстроку в новое место ( для любых строк a , b , c , d ).
Учитывая две строки и y и целые числа k и K , я хотел бы решить следующую проблему:
- Вы можете преобразовать в y, используя не более k дешевых операций и не более K дорогих операций?
Вопросов:
У этой проблемы есть имя? (Это звучит как очень стандартный вопрос в контексте выравнивания последовательностей.)
Это сложно?
Если это сложно, можно ли с фиксированным параметром трактоваться с помощью в качестве параметра?
Существуют ли эффективные алгоритмы аппроксимации? (Например, найти решение с не более чем дешевыми и 2 К дорогим операциям , если решение с K дешевыми и K дорогих операциями существуют.)
Я пытался взглянуть на строковые метрики, перечисленные в Википедии , но ни один из них не выглядел правильно.
Ответы:
Как прокомментировал Серж Гасперс, для проблема заключается в сортировке по транспозициям , которая была введена Бафной и Певзнером в 1995 году. Ее NP-твердость была доказана только в 2010 году; см. Laurent Bulteau, Guillaume Fertin и Irena Rusu, «Сортировка по транспозиции затруднительна» .k=0
источник
Проблема становится проще, если мы рассмотрим длинные удаления и копирование подстрок вместо транспозиций. Предположим, что мы используем стандартный алгоритм динамического программирования для вычисления расстояния редактирования и что дорогая операция длины увеличивает расстояние на a k + b , для некоторых констант a , b ≥ 0 . Эти константы могут быть разными для длинных удалений и копирования подстрок.k ak+b a,b≥0
Длинное удаление - это удаление произвольной подстроки из . Поддержать их легко, если мы разбиваем их на два вида простых операций: удаление первого символа (стоимость a + b ) и расширение удаления на один символ (стоимость a ). В дополнение к стандартному массиву A , где A [ i , j ] - расстояние редактирования между префиксами x [ 1 … i ] и y [ 1 … jx a+b a A A[i,j] x[1…i] , мы используем другой массив A dy[1…j] Ad сохранить расстояние редактирования, когда последней использованной операцией было длительное удаление. С этим массивом мы должны смотреть только на , A [ i - 1 , j - 1 ] , A [ i , j - 1 ] и A d [ i - 1 , j ] при вычислении A [ i , j ] и A d [ iA[i−1,j] A[i−1,j−1] A[i,j−1] Ad[i−1,j] A[i,j] , что позволяет нам сделать это за O ( 1 ) раз.Ad[i,j] O(1)
Копирование подстроки означает вставку произвольной подстроки в редактируемую строку. Как и в случае длинных удалений, мы разбиваем операцию на две простые операции: вставка первого символа и расширение вставки на один символ. Мы также используем массив A s для хранения расстояния редактирования между префиксами при условии, что последней использованной операцией было копирование подстроки.x As
Эффективно сделать это сложнее, чем с длинными удалениями, и я не уверен, сможем ли мы получить амортизированное раз на ячейку. Мы строим дерево суффиксов для x , которое занимает время O ( | x | ) , предполагая алфавит постоянного размера. Мы сохраняем указатель на текущий узел дерева суффиксов в A s [ i , j - 1 ] , что позволяет нам проверять в постоянное время, можем ли мы расширить вставку символом y [ j ] . Если это правда, мы можем вычислить A [ IO(1) x O(|x|) As[i,j−1] 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] z As[i,j−1] x z′ z z′y[j] x O(|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,j−1] z′ O(1) As[i,j] O(|z′|) Время. Вероятно, есть какой-то способ сделать это более эффективно, но я не могу найти это прямо сейчас.
источник