Нечеткое сравнение коллекций: семантический и алгоритмический аспекты

Семенов В.А., Морозов С.В., Тарлапан О.А., Энкович И.В.
Труды Института системного программирования РАН
Работа коллектива поддержана РФФИ (грант 07-01-00427).

Назад Содержание Вперёд

7. Сравнение упорядоченных множеств

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

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

 =    

Операция перестановки  однократно циклически переставляет элементы исходного множества , приводя к следующему результату: . Операция  вставляет упорядоченный набор элементов модифицированного списка  с индексами в отрезке  в позицию i-ого элемента исходного множества . Операция  удаляет элементы исходного множества  с индексами, принадлежащими отрезку .

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

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

Все значения индексов позиций указываются в представлении дельты относительно исходных версий коллекции. При выполнении дельты индексные параметры всех последующих операций должны корректироваться с учетом ранее примененных. Данная корректировка заключается в увеличении или уменьшении индексов элементов исходного множества на количество выполненных вставок или удалений. При выполнении перестановок корректировка состоит в циклическом распространении индекса для каждого последующего элемента группы перестановки.

Любое изменение порядка элементов в упорядоченном множестве может быть представлено композицией циклических перестановок. Причем при отсутствии пересечений по индексам перестановки удовлетворяют требованию коммутативности и могут применяться в произвольном порядке независимым друг от друга образом [19]. Тем самым удовлетворяется требование конструктивной декомпозиции и реконсиляции транзакций, связанное с возможностью независимого применения их отдельных операций. При этом наличие одного и того же индекса в разных группах перестановок дельты  должно быть запрещено:

Данное условие не является обременительным, поскольку существует четкая методика разложения перестановки произвольного упорядоченного множества на группы циклических перестановок. Данная методика приводится в [19] как доказательство теоремы о единственности специально заданного соединительного произведения перестановки линейно упорядоченного мультимножества.

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

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

1. обобщение операции перестановки таким образом, чтобы обеспечить циклическую перестановку не отдельных элементов, а целых групп;
2. соблюдение условия предшествования операций перестановки операциям вставки.

На наш взгляд, второй способ более предпочтителен, поскольку контроль частичного порядка операций при выполнении не вызывает дополнительных сложностей в реализации в отличие от обобщенных перестановок.

Проиллюстрируем вычисление и применение дельты для упорядоченных множеств на следующем примере. Пусть  — основная и модифицированная версии коллекции символов, представленные следующими последовательностями элементов: , . Тогда дельта, вычисленная в соответствии с вышеописанной семантикой операций, представляется как

В ходе применения дельты к основной версии  операции  переставляют элементы a, e и c, d исходного множества, приводя к промежуточным представлениям коллекции  и  соответственно. Операции  добавляют элементы g, h, k, l перед d и элемент m перед a, формируя последовательности  и . Наконец, операции ,  удаляют элементы b и f, приводя к окончательному представлению модифицированной версии коллекции .

Опишем возможный способ формирования дельты двух упорядоченных множеств в соответствии с перечисленными выше условиями:

1. Поиск идентичных подмножеств  и  исходных множеств, , сохраняющих оригинальный порядок следования элементов:

   ,

   

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

2. Поиск циклической перестановки элементов множества , приводящей к последовательности элементов множества . Наиболее простым способом реализации данного этапа видится предварительная замена алфавита исходного множества  на последовательность натуральных чисел  и применение методики, применяемой в доказательстве теоремы о единственности специальной формы соединительного произведения перестановки линейно упорядоченного мультимножества [19].
3. Определение множества операторов вставки , упорядоченного по индексам вставки элементов, используя структуры соответствия индексов элементов множеств  и .
4. Определение множества операторов удаления , упорядоченного по индексам удаляемых элементов, используя структуры соответствия индексов элементов множеств  и .
5. Формирование единого списка операций дельты в соответствии с принятым порядком исполнения: сначала следуют операции перестановок, затем — операции вставок и в конце — операции удаления.

Сформированная таким образом дельта состоит из множества независимых операций, каждая из которых может быть принята или отклонена в рамках результирующей транзакции независимо от статуса остальных операций.

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

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

1. Вставка тождественных элементов в разные позиции. Стандартным способом разрешения конфликта является принятие одной из операций или отмена обеих.
2. Вставка нетождественных последовательностей элементов в одну и ту же позицию. Варианты разрешения — те же самые, что и при сравнении списков.
3. Удаление элемента в одной транзакции при его перестановке в другой. Способ разрешения — стандартный.
4. Неэквивалентная перестановка одного и того же элемента в разных транзакциях. Принятие одной из циклических перестановок, в которых участвует элемент, является наиболее простым и очевидным способом разрешения подобного конфликта. Альтернативой ему может служить решение, основанное на декомпозиции конфликтных операций перестановки на элементарные транспозиции и выделение неэквивалентных цепочек транспозиций для заданного элемента. В этом случае разрешение конфликта сводится к отмене одной из конфликтных транспозиций и формированию итоговой консолидирующей перестановки.

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

Назад Содержание Вперёд