Наименьшее количество редактирования редактирования между двумя словами

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

• добавить букву на одной из конечностей (например, AB -> ABC),
• продублировать и объединить все слово (например, ABC -> ABCABC),
• разрезать слово на две части (двойной ход дублирования, ABCABC -> ABC + ABC),
• удалить одну из букв (например, ABC -> AC) и
• повторите одну из букв (например, ABC -> ABBC).

Например, минимальная последовательность шагов от ABC к BCBC - ABC -> BC (удалить A) -> BCBC (дублирование).

У меня нет опыта в информатике. Возможно, это хорошо известная проблема, но мой поиск в Google ничего не дал мне.

Знаете ли вы некоторые связанные, четко определенные проблемы?

Редактировать : Как предложено в ответе Энтони Лабарре, я прочитал некоторые статьи о проблеме перестановки / расположении наборов, которая похожа на проблему, описанную выше. Кто-нибудь знает больше об этой проблеме? Это актуально?

Я не знаю, была ли изучена именно эта проблема, но Chaudhuri et al. изучил связанную проблему тандемного дублирования - случайной потери : вам дана перестановка, и вы хотите преобразовать ее в перестановку идентификаторов, (1) дублируя сегмент любой длины и добавляя копию сразу после оригинала, затем (2) удаляя элементы, так что вы получите новую перестановку вместо строки. Обратите внимание, что применение (1), затем (2) учитывает одну операцию.

Различные варианты могут быть определены в зависимости от веса каждой операции, который в их документе зависит от ширины дублированных сегментов. Они также изучают аналогичную проблему с дублированием всего генома , что является именно тем типом дублирования, который вы допускаете. Я не помню, чтобы читал о работе над этой проблемой в контексте строк, но я надеюсь, что это может, по крайней мере, дать вам отправную точку для ваших поисков.

Как уже указывалось, эта проблема аналогична более известной проблеме расстояния редактирования (лежащей в основе расстояния Левенштейна ). Он также имеет общие черты, например, с расстоянием динамического коробления во времени (дублирование или «заикание» в вашем последнем требовании).

Шаги к динамическому программированию

$x=x_1\ldots x_n$$y=y_1\ldots y_m$$d(x,y)$

$$\min \begin{cases} d(x,y_1\ldots y_{m-1})+1 & &\text{▻ Add letter at end}\\ d(x,y_2\ldots y_m)+1 & & \text{▻ Add letter at beginning}\\ d(x,y_1\ldots y_{m/2})+1 & \text{if $y=y_1\ldots y_{m/2}y_1\ldots y_{m/2}$} & \text{▻ Doubling}\\ d(x_1\ldots x_{n/2},y)+1 & \text{if $x=x_1\ldots x_{n/2}x_1\ldots x_{n/2}$} & \text{▻ Halving}\\ d(x_1\ldots x_n,y) + 1 && \text{▻ Deletion}\\ d(x_1\ldots x_{n-1},y_1\ldots y_{m-1}) & \text{if $y_n = y_m$} & \text{▻ Ignoring last elt.}\\ \end{cases}$$

Здесь последний вариант в основном говорит, что преобразование FOOX в BARX эквивалентно преобразованию FOO в BAR. Это означает, что вы можете использовать опцию «добавить букву в конце», чтобы добиться эффекта заикания (дублирования) и удаления в точке. Проблема заключается в том, что она автоматически позволяет добавлять произвольный символ в середине строки , а , что - то вы , вероятно , не хотите. (Это «игнорирование идентичных последних элементов» является стандартным способом достижения удаления и заикания в произвольных позициях. Оно действительно запрещает произвольные вставки, хотя допускает добавления на любом конце, хотя и немного сложно, но…)

Я включил эту разбивку, даже если она не выполняет всю работу полностью, на случай, если кто-то другой может каким-то образом ее «спасти», и потому что я использую ее в своем эвристическом решении ниже.

(Конечно, если бы вы могли получить такую ​​разбивку, которая фактически определяла ваше расстояние, вам нужно было бы только добавить памятку, и у вас было бы решение. Однако, поскольку вы работаете не только с префиксами, я не Не думаю, что вы могли бы использовать только индексы для своей заметки; вам, возможно, придется хранить фактические, измененные строки для каждого вызова, которые будут огромными, если ваши строки имеют значительный размер.)

Шаги к эвристическому решению

Другой подход, который может быть проще для понимания и который может занимать немного меньше места, - это поиск кратчайшего «пути редактирования» от вашей первой строки ко второй, используя алгоритм (в основном, лучше всего первая ветвь и связка). Пространство поиска будет определяться непосредственно вашими операциями редактирования. Теперь, для большой строки, вы бы$A^\ast$получить большую окрестность, так как вы можете удалить любой символ (давая вам соседа для каждого потенциального удаления), или дублировать любой символ (опять же, давая вам линейное число соседей), а также добавить любой символ на любом конце, что будет дать вам количество соседей, равное удвоенному размеру алфавита. (Просто надеюсь, что вы не используете полный Unicode ;-) С таким большим разветвлением, вы можете достичь довольно существенного ускорения, используя двунаправленный или некоторый родственник$A^*$ .

Чтобы заставить работать, вам понадобится нижняя граница для оставшегося расстояния до вашей цели. Я не уверен, есть ли здесь очевидный выбор, но вы могли бы реализовать решение для динамического программирования, основанное на рекурсивной декомпозиции, которую я дал выше (опять же, с возможными проблемами с пространством, если ваши строки очень длинные). Несмотря на то , что разложение не точно вычислить дистанцию, то это гарантированно будет нижней границей (потому что это более снисходительными), что означает , что он будет работать как эвристика в . (Насколько это будет сложно, я не знаю, но это было бы правильно.) Конечно, памятка о вашей связанной функции может быть общей для всех вычислений границы во время вашего$A^*$$A^*$$A^*$запустить. (Временной / пространственный компромисс там.)

Так…

Эффективность предложенного мной решения, похоже, сильно зависит от (1) длины ваших строк и (2) размера вашего алфавита. Если ни один не огромен, это могло бы работать. Это:

• Реализуйте нижнюю границу вашего расстояния, используя мою рекурсивную декомпозицию и динамическое программирование (например, используя запомненную рекурсивную функцию).
• Реализуйте (или двунаправленный ) с вашими операциями редактирования в виде «перемещений» в пространстве состояний и нижней границей на основе динамического программирования.$A^*$$A^*$

Я не могу дать никаких гарантий того, насколько эффективно это будет, но это должно быть правильно, и это, вероятно, будет намного лучше, чем решение методом перебора.

Если ничего другого, я надеюсь, что это даст вам некоторые идеи для дальнейших исследований.

Некоторая связанная, хорошо определенная проблема будет проблемой выравнивания последовательности . Это отличается, потому что это не использует операцию дублирования. Определенные операции: вставка символа, удаление символа, преобразование символа. Популярным алгоритмом решения этой проблемы является Needleman-Wunsch .

За исключением дублирования, расстояние Левенштейна может стоить посмотреть: http://en.wikipedia.org/wiki/Levenshtein_distance