Нечеткое сравнение коллекций семантический и алгоритмический аспекты
Задача нечеткого сравнения в приложениях семантической реконсиляции
Обсудим особенности постановки задачи нечеткого сравнения коллекций в приложениях семантической реконсиляции. Напомним, что традиционная задача сравнения последовательностей обычно формулируется как задача отыскания минимального скрипта редактирования (последовательности элементарных команд, обеспечивающей преобразование исходной строки в заданную другую строку) [20, 21]. Множество найденных команд при соответствующей интерпретации может служить представлением изменений, внесенных в модифицированную версию коллекции относительно исходной. Отыскание наибольшей подпоследовательности также решает задачу нечеткого сравнения и позволяет представить изменения модифицированной коллекции в виде добавленных и удаленных фрагментов строк, дополняющих найденную общую подпоследовательность до заданных строк.
В отличие от традиционных постановок задач сравнения последовательностей, приложения реконсиляции оперируют с произвольными типами коллекций, и для адекватной реконструкции изменений требуется детальный семантический анализ. Другой важной особенностью рассматриваемой постановки является необходимость декомпозиции долгих транзакций на группы операций, которые могли бы быть представлены и применены независимым друг от друга образом. Это означает, что в ходе реконсиляции одна часть выявленных изменений может быть принята в итоговом представлении при отмене другой без каких-либо дополнительных ограничений. Выбранный базис элементарных операций должен удовлетворять данному требованию.
Итак, пусть
— некоторые версии коллекции элементов типа T, причем
— базовая версия, а
,
— версии, полученные в результате ее одновременной модификации в двух параллельных ветвях. Задача реконсиляции в наиболее распространенной постановке заключается в вычислении соответствующих изменений модифицированных версий относительно базовой
,
и в консолидации изменений
таким образом, чтобы сформировать итоговое представление коллекции
как результат применения согласованных изменений к базовой версии.
Это, так называемая, классическая “3-way Merge” схема реконсиляции в отличие от схем “2-way Merge” и “4-way Merge”, имеющих более узкое применение [15, 16].
Рис. 1. Пример консолидации изменений в итоговом текстовом документе
Например, если при одновременной модификации текстового файла в ходе выполнения одной транзакции была вставлена новая строка, а в ходе выполнения другой транзакции одна из строк была удалена, результатом консолидации изменений должен стать итоговый документ с внесенными общими изменениями (см. рис. 1), дополняющий его существующие версии новым согласованным вариантом.
Корректная идентификация изменений и реализация функции исполнения предполагают, что соответствующие тождества
,
необходимо удовлетворены.
Тривиальными случаями реализации функции реконсиляции являются
,
и
, приводящие к уже известным версиям коллекции
,
и
соответственно. Содержательная реализация функции реконсиляции
нетривиальна, поскольку
,
могут представлять собой иерархически структурированные изменения
,
,
,
и т.д. По существу, дельты
,
являются реконструируемым представлением конкурентных транзакций, примененных к исходным данным
и имеющих результатом
и
соответственно. В силу указанных причин реализация данной функции должна обеспечивать консолидацию как можно большего числа изменений при условии сохранения частичного порядка операций, индуцируемого семантикой приложений, и их бесконфликтности. В случаях, когда все конфликты разрешаются путем принятия изменений из первой версии, функция реконсиляции строится следующим образом:
,
где логическая функция
истинна в случае конфликта между изменениями
,
. Является открытым вопрос о том, какие ситуации следует считать конфликтными, и каким образом они могут быть разрешены: отменой всех операций, выделением и принятием бесконфликтного подмножества операций, или путем их коррекции.
В дальнейшем под конфликтом будем понимать бинарное или множественное отношение между наборами или последовательностями операций в конкурентных транзакциях
,
, одновременное принятие которых приводит к некорректной интерпретации операций и неоднозначности результата, или к нарушению семантических ограничений, накладываемых на результирующее представление данных
, где
.
Стандартный способ разрешения конфликта состоит в принятии одной из опций
.
При условии, что оригинальные транзакции приводят к корректным версиям
и
, а принимаемые операции не конфликтуют друг с другом, результирующая транзакция также будет корректна. В случае выявления конфликтов они разрешаются вплоть до достижения корректности итоговой транзакции. Заметим, что решение всегда существует, поскольку в качестве итоговой транзакции могут быть приняты
,
или
. Однако более содержательным была бы консолидация операций из обеих конкурентных транзакций.
Важной особенностью задачи нечеткого сравнения коллекций в приложениях реконсиляции является учет частичного порядка между операциями. Например, если при одновременном редактировании текста в одну и ту же позицию были добавлены отличные строки, то конфликт связан не с нарушением какого-либо ограничения для результирующего документа, а с неоднозначностью исполнения соответствующих операций
,
и с неопределенностью ожидаемого результата
. Возможным способом разрешения конфликта в данном случае являлась бы одна из опций:
, где символ
означает отношение предшествования между исполняемыми операциями. Результатом может стать исходный документ, одна из его модифицированных версий либо документ с двумя возможными вариантами вставки строк (см. рис. 2). Заметим, что совпадение добавленных строк в обеих версиях модифицируемого документа не приводит к конфликту, и вариантами реконсиляции являются тривиальные решения
, приводящие к уже существующим версиям документа.
Рис. 2. Пример многовариантной реконсиляции с учетом частичного порядка операций редактирования текстового документа
Приведем вариант предыдущего примера редактирования текстового документа, иллюстрирующего важность учета семантики модели данных при дополнительном ограничении уникальности элементов коллекции. Предположим, что документ представляет собой персонофицируемый список имен, формируемый путем согласования альтернативных рейтинговых показателей в параллельных версиях (см. рис. 3).
Рис. 3. Пример многовариантной реконсиляции с учетом семантики модели коллекции
В первой модифицируемой версии документа между персонами на первых двух позициях вставляется новое имя, после чего меняется порядок их следования.
Дельта представляется следующим образом:
, где
— операция вставки нового элемента в соответствующую позицию коллекции, а
— операция транспозиции пары элементов в заданных позициях коллекции. Во второй версии документа то же самое имя вставляется на позицию между последними персонами, а также меняется порядок их следования:
. Заметим, что изменение порядка следования элементов коллекции и вставка новых элементов согласно репродуцируемой семантике множества не должна приводить к дублированию имен в итоговом документе. Поэтому семантически корректными являются результаты
, приводящие, соответственно, к оригинальным версиям Original document, Version1, Version2, версиям Version1-1, Version1-2, Version2-1, Version2-2, полученным частичным принятием операций одной из транзакций, и версиям документа Merged document1, Merged document2, полученным возможной консолидацией операций из двух конкурентных транзакций.
