Взвешенное расстояние редактирования неупорядоченной строки

Question

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

Поскольку то, что я пытаюсь выполнить, очень похоже на вычисление расстояния редактирования строки, я подумал, что это можно назвать неупорядоченным расстоянием редактирования строки или просто установить расстояние редактирования. Однако Google ничего не находит с этими поисковыми терминами, поэтому мне интересно узнать, известна ли проблема под другим именем?

Чтобы уточнить, проблема будет решена путем

def unordered_edit_distance(target, source):
    return min(edit_distance(target, source_perm) 
               for source_perm in permuations(source))

Так, например, unordered_edit_distance('abc', 'cba') было бы 0, в то время как edit_distance('abc', 'cba') является 2, К сожалению, число перестановок растет очень быстро и нецелесообразно даже для входов среднего размера.

РЕДАКТИРОВАТЬ Проясните, что операции связаны с различными затратами.

Answer 1

Давайте на мгновение проигнорируем замены.

Теперь это становится довольно тривиальной проблемой определения элементов только в первом наборе (которые будут считаться удалениями) и элементов только во втором наборе (которые будут считаться вставками). Это легко сделать одним из следующих способов:

• Сортировка наборов и повторение обоих одновременно, или
• Вставка каждого элемента из первого набора в хеш-таблицу, затем удаление каждого элемента из второго набора из хеш-таблицы, причем каждый элемент, который не был найден, является вставкой, а каждый элемент, остающийся в хеш-таблице после того, как мы закончили, является удалением

Теперь, чтобы включить подстановки, остается только найти оптимальное сопряжение вставленных элементов с удаленными элементами. На самом деле это проблема стабильного брака:

Проблема стабильного брака (SMP) - это проблема поиска стабильного соответствия между двумя наборами элементов с учетом набора предпочтений для каждого элемента. Сопоставление - это сопоставление элементов одного набора с элементами другого набора. Сопоставление стабильно всякий раз, когда это не так, что оба:

1. Некоторый заданный элемент A первого сопоставленного набора предпочитает некоторый заданный элемент B второго сопоставленного набора над элементом, которому уже сопоставлен A, и
2. B также предпочитает A элементу, которому B уже соответствует

Что можно решить с помощью алгоритма Гейла-Шепли:

Алгоритм Гейла – Шепли включает в себя ряд "раундов" (или "итераций"). В первом раунде сначала а) каждый незанятый мужчина предлагает женщине, которую он предпочитает больше всего, а затем б) каждая женщина отвечает "возможно" своему поклоннику, которого она больше всего предпочитает, и "нет" всем остальным женихам. Затем она временно "помолвлена" с истцом, которого она больше всего предпочитает, и этот истец также временно помолвлен с ней. В каждом последующем раунде сначала а) каждый не состоящий в браке мужчина предлагает самой предпочтительной женщине, которой он еще не предложил (независимо от того, была ли женщина уже помолвлена), а затем б) каждая женщина отвечает "возможно" своему жениху большинство предпочитает (будь то ее существующий временный партнер или кто-то еще) и отвергает остальное (опять же, возможно, включая ее нынешнего временного партнера). Временный характер обязательств сохраняет за собой право уже занятой женщины "поменяться" (и, в процессе, "сдать" ее до тех пор, пока она не станет партнером).

Нам просто нужно правильно оценить стоимость. Чтобы связать вставку и удаление, сделав его заменой, мы потеряем как стоимость вставки, так и удаления, и получим стоимость замены, поэтому чистая стоимость соединения будет substitutionCost - insertionCost - deletionCost,

Теперь вышеприведенный алгоритм гарантирует, что все вставки или удаления будут сопряжены - мы не обязательно этого хотим, но есть простое решение - просто создайте набор элементов "оставайтесь как есть" (как на стороне вставки, так и на стороне удаления) - любая вставка или удаление в паре с элементом "оставайся как есть" будет иметь стоимость 0 и приведет к тому, что он останется вставкой или удалением, и ничего не произойдет для двух элементов "оставайся как есть", которые в конечном итоге окажутся в паре.

Answer 2

Сортируйте их (не обязательно), затем удалите элементы, которые являются одинаковыми (и в равном количестве!) В обоих наборах. Тогда, если наборы равны по размеру, вам нужно это количество замен; если один больше, то вам также нужны некоторые вставки или удаления. В любом случае вам нужно количество операций, равное размеру большего набора, оставшегося после первого этапа.

Answer 3

Хотя ваше наблюдение является верным, но вы на самом деле делаете простую задачу более сложной.

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

Пусть две карты на каждой карте подсчитывают количество отдельных символов в вашей целевой и исходной строке:

например: a: 2 c: 1 d: 100

Теперь сравните две карты, если вам не хватает какого-либо символа, конечно, вам нужно вставить его, и если у вас есть дополнительный символ, вы удалите его. Это оно.

Answer 4

Ключевое наблюдение: вас интересует только количество символов "a", "b",..., "z" или других букв алфавита, так как вы можете переупорядочить все символы в каждой строке.

Итак, проблема сводится к следующему: s['a'] символы "а", s['b'] символы 'b',..., s['z'] символы "Z", преобразовать их в t['a'] символы "а", t['b'] символы 'b',..., t['z'] символы 'z'. Если ваш алфавит короткий, s[] а также t[] могут быть массивы; как правило, они являются преобразованиями алфавита в целые числа, например map <char, int> в C++, dict в Python и т. д.

Теперь для каждого персонажа c, ты знаешь s[c] а также t[c], Если s[c] > t[c]Вы должны удалить s[c] - t[c] персонажи c из первой неупорядоченной строки (s). Если s[c] < t[c], вы должны добавить t[c] - s[c] персонажи c ко второй неупорядоченной строке (t).

принимать X, сумма s[c] - t[c] для всех c такой, что s[c] > t[c], и вы получите количество символов, которые вы должны удалить из s в целом. принимать Y, сумма t[c] - s[c] для всех c такой, что s[c] < t[c], и вы получите количество символов, которые вы должны удалить из t в целом.

Теперь пусть Z = min (X, Y), Мы можем иметь Z замены, и что осталось X - Z вставки и Y - Z удаления. Таким образом, общее количество операций Z + (X - Z) + (Y - Z), или же X + Y - min (X, Y),