Нечеткое сравнение коллекций семантический и алгоритмический аспекты
Задача нечеткого сравнения в приложениях семантической реконсиляции
Обсудим особенности постановки задачи нечеткого сравнения коллекций в приложениях семантической реконсиляции. Напомним, что традиционная задача сравнения последовательностей обычно формулируется как задача отыскания минимального скрипта редактирования (последовательности элементарных команд, обеспечивающей преобразование исходной строки в заданную другую строку) [20, 21]. Множество найденных команд при соответствующей интерпретации может служить представлением изменений, внесенных в модифицированную версию коллекции относительно исходной. Отыскание наибольшей подпоследовательности также решает задачу нечеткого сравнения и позволяет представить изменения модифицированной коллекции в виде добавленных и удаленных фрагментов строк, дополняющих найденную общую подпоследовательность до заданных строк.
В отличие от традиционных постановок задач сравнения последовательностей, приложения реконсиляции оперируют с произвольными типами коллекций, и для адекватной реконструкции изменений требуется детальный семантический анализ. Другой важной особенностью рассматриваемой постановки является необходимость декомпозиции долгих транзакций на группы операций, которые могли бы быть представлены и применены независимым друг от друга образом. Это означает, что в ходе реконсиляции одна часть выявленных изменений может быть принята в итоговом представлении при отмене другой без каких-либо дополнительных ограничений. Выбранный базис элементарных операций должен удовлетворять данному требованию.
Итак, пусть
