---

Разделы На главную Логика нейросетей Виды логики Вопросы логики Логика Учебник логики Наука логики Задачи логики Нечеткая Логика

---

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

Классификация коллекций

Коллекции — фундаментальный тип данных, поддерживаемый популярными языками моделирования и программирования для спецификации и реализации в приложениях агрегированных структурированных данных. Как иллюстрируют примеры предыдущего раздела, сравнение коллекций должно проходить в строгом соответствии с их семантикой. В противном случае результаты рискуют быть неадекватными исходной проблеме и теряют смысл для целевого приложения и пользователя. Сравнение коллекций может рассматриваться в качестве частной задачи более общей проблемы семантического сопоставления (matching) и сравнения (differencing) расходящихся реплик структурированных данных, например, популяций объектов, заданных некоторой объектно-ориентированной моделью. Несмотря на многообразие частных типов коллекций, встречаемых в приложениях, можно выделить несколько фундаментальных свойств, в соответствии с которыми их анализ может проводиться содержательным образом. К таким свойствам мы относим уникальность элементов коллекции, упорядочение, возможную сортировку элементов коллекции, а также ограниченный размер коллекции. Декларативные языки объектно-ориентированного моделирования, как правило, предоставляют некоторый набор абстрактных или конкретных типов коллекций с априори заданным набором семантических свойств. В производных пользовательских типах, определяемых на основе базовых, семантика коллекций может быть сохранена или уточнена. Однако выделенные фундаментальные свойства остаются принципиальными для содержательного анализа коллекций. Так, декларативный язык ограничений OCL [17] определяет абстрактный интерфейс коллекций Collection и четыре конкретных класса Bag, Set, Sequence и OrderedSet для представления мультимножеств, множеств, последовательностей и упорядоченных множеств соответственно. Все виды коллекций задаются в обобщенном виде с возможностью параметризации типом элементов. Set — коллекция, по семантике соответствующая математическому понятию множества. Она не допускает дупликации элементов. OrderedSet — специализация данного типа для упорядоченных множеств.
Ограничение уникальности необходимо поддерживается данным типом коллекции. Bag — мультимножество с возможным повторением элементов. Sequence — упорядоченное мультимножество или последовательность, допускающая повторение элементов. Таким образом, виды коллекций OCL могут быть классифицированы в соответствии с таблицей 1. Язык моделирования EXPRESS [18] предоставляет иной набор типов коллекций, а именно: Aggregate, Bag, Set, Array и List. Абстрактный тип Aggregate определяет базовый набор методов оперирования с элементами коллекций. Bag — специализация данного типа для представления мультимножеств. Set — специализация типа Aggregate для произвольных множеств, исключающая дупликацию элементов и игнорирующая их порядок. Тип данных List применяется для представления последовательностей. Допустимое количество элементов в списках, множествах и мультимножествах задается дополнительными ограничениями. Коллекции имеют строго фиксированный размер в тех случаях, когда нижний и верхний пределы их размера совпадают. Array — специализация типа Aggregate для массивов фиксированной длины. С учетом индексации порядок элементов в массивах имеет существенное значение. Возможна организация разреженных массивов с неустановленными значениями элементов при помощи специального спецификатора. Также возможно определение производных типов массивов и списков с наложенным ограничением уникальности элементов. Базовые типы коллекций, предоставляемые языком моделирования EXPRESS, приведены в таблице 1.

UNIQUE	ORDERED	SORTED	FIXED	Используемые сокращения	Коллекции OCL	Коллекции EXPRESS
-	-	-	-	BAG	BAG	BAG
+	-	-	-	SET	SET	SET
-	-	-	+	FIXED BAG
+	-	-	+	FIXED SET
-	+	-	-	LIST	SEQUENCE	LIST
+	+	-	-	ORDERED SET	ORDERED SET	UNIQUE LIST
-	+	-	+	ARRAY		ARRAY
+	+	-	+	UNIQUE ARRAY		UNIQUE ARRAY
-	+	+	-	SORTED LIST
+	+	+	-	SORTED SET
-	+	+	+	SORTED ARRAY
+	+	+	+	SORTED UNIQUE ARRAY

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

Сравнение множеств

Начнем рассмотрение с наиболее простого типа коллекций  — множества элементов типа T, предполагающего неявное задание и выполнение единственного семантического ограничения уникальности элементов . Дельта для двух версий множества  может быть естественным образом представлена в виде неупорядоченного набора операций добавления и удаления соответствующих элементов коллекции: Корректное представление дельты  предполагает, что выполняется условие , означающее, что один и тот же элемент не может одновременно участвовать в операции добавления и удаления. Более того, будем исключать повторение операций добавления и удаления с одним и тем же элементом, которое при исполнении операций противоречило бы определению множества:  и . Применение операций, определяемых дельтой, довольно прозрачно. К заданному исходному множеству добавляются элементы, определяемые операциями ins, и удаляются элементы, определяемые операциями del. Тем самым, гарантируется тождественность условия , в котором функция  возвращает модифицированное представление коллекции, полученное в  результате применения дельты к заданному представлению коллекции X. Две конкурентные транзакции  могут оказаться конфликтными в случае , когда в одной транзакции некоторый элемент добавляется в коллекцию, а в другой транзакции тот же самый элемент удаляется. Однако, если обе дельты вычислялись относительно общей версии коллекции в рамках распространенной схемы слияния “3-way Merge”: , , то подобные конфликты исключены в силу того, что удаляемый элемент обязан принадлежать базовой версии коллекции X и не может быть добавлен в нее повторно вследствие ограничения уникальности элементов множества. В случае иных схем слияния с участием нескольких базовых версий, например, схемы “4-way Merge”, подобные конфликты должны идентифицироваться и корректно разрешаться. Тривиальными способами разрешения являются следующие опции , предполагающие игнорирование обеих конфликтных операций или принятие одной из них. Сложность вычисления дельты  определяется, прежде всего, способом представления исходных множеств (список, массив, сбалансированное дерево), а также алгоритмами поиска добавляемых и удаляемых элементов.
Вычислительная сложность наивной реализации, основанной на простом поиске элемента в неупорядоченном списке и не требующей определения на элементах множеств полного порядка может быть оценена как . Сложность оптимальной реализации, основанной на предварительной сортировке исходных множеств, например, методом пирамидальной сортировки или методом слияния списков, можно оценить как . А в случае использования для работы с множеством сбалансированного дерева, хранящего элементы в уже отсортированном порядке, сложность операции построения дельты оценивается как . Понятно, что последняя оценка не может рассматриваться как реальная оценка, поскольку в данном случае основная часть затрат перенесена на стадию формирования исходных множеств. Наиболее корректной оценкой в данном случае является также . Ниже приведен пример сравнения двух версий множества натуральных чисел . Пусть  — основная и модифицированная версии коллекции, содержащие следующие элементы: , . Тогда дельта, вычисленная путем сравнения двух версий множества, представляется как .

Сравнение мультимножеств

Перейдем к задаче сравнения мультимножеств  с функцией  для подсчета числа вхождений элемента  в коллекцию . При модификации коллекции данного типа дельта представляется как неупорядоченный набор множественного добавления и удаления элементов. Пусть  — две версии мультимножества, тогда дельта может быть сформирована как В используемых обозначениях Z — множество целых чисел. Положительное значение параметра n в операции изменения кардинальности card(x,n) указывает на добавление элемента в коллекцию соответствующее число раз, отрицательное значение — на удаление элемента из коллекции. Нулевое значение n не содержательно для представления дельты, поскольку означает, что количество экземпляров элемента в коллекции не изменилось. В корректно сформированном представлении дельты  предполагается, что элемент мультимножества не может одновременно участвовать в нескольких операциях . В противном случае сравнение идентичных версий коллекции могло бы привести к неожиданному результату, отличному от пустого представления дельты, например: . Применение базовой операции дельты card(x,n) состоит в кратном добавлении соответствующего элемента x при положительном значении параметра n и в его кратном удалении при отрицательном значении параметра. Это гарантирует выполнение необходимого тождества . Две операции  конфликтуют друг с другом, если параметры кратности перемещения экземпляров одного и того же элемента в конкурентных транзакциях отличаются друг от друга . Тривиальные способы разрешения конфликта состоят в выборе одной из опций . Вместе с тем, логичным представляется расширение возможных опций путем назначения параметру кратности всего интервала значений, порождающего конфликтную ситуацию: . Это означает, что может быть выбрано любое число кратности для операции перемещения, лежащее в интервале между соответствующими параметрами конфликтных операций. В случаях, когда обе конфликтные операции являются родственными, конфликт целесообразно разрешать, исходя из промежуточных значений.
В случаях, когда одна из конфликтных операций — операция добавления, а другая — операция удаления, допустимым является также весь диапазон значений параметра кратности, означая удаление или добавление числа элементов, не превышающего используемое значение соответствующей операции. Сложность построения  определяется теми же факторами, что и сложность вычисления дельты обычного множества. Имеет место незначительное увеличение числа операций, однако это не влияет на асимптотическую оценку, которая в среднем выражается как . В качестве примера рассмотрим процедуру сравнения двух версий мультимножества символов. Пусть  — основная и модифицированная версии коллекции, содержащие следующие натуральные элементы , . Тогда дельта, вычисленная в результате сравнения двух версий коллекции, представляется как .

Сравнение списков

Для сравнения списков (или последовательностей) могут быть задействованы классические алгоритмы минимального редакторского расстояния (edit-distance (ed)) и алгоритмы нахождения наибольшей общей последовательности (longest-common-subsequence (lcs)), нашедшие применение в самых разных приложениях [20, 21]. Поскольку данные семейства алгоритмов достаточно хорошо проработаны и изучены, мы ограничимся вопросами их использования в общем контексте решения задач сравнения и слияния коллекций на основе семантики модели. Пусть элементы списка  предварительно последовательно пронумерованы, начиная с единицы, и каждый элемент  индексируется в соответствии с положением в списке. Далее  обозначается i-ый элемент коллекции,  — число элементов коллекции и  — упорядоченное подмножество элементов коллекции , начинающееся в позиции i и заканчивающееся в позиции . Тогда дельта, полученная в результате сравнения двух версий коллекции , может быть представлена множеством операций вставки новых элементов в соответствующие позиции исходного списка и удаления элементов с соответствующих позиций подобно тому, как это осуществляется в алгоритмах минимального редакторского расстояния:   Здесь операция  вставляет упорядоченный набор элементов модифицированного списка  с индексами в отрезке  в позицию i исходного списка . Операция  удаляет элементы исходного списка с индексами, принадлежащими отрезку , и, наконец, операция  переносит элементы с индексами в отрезке  в модифицируемый список без изменений. Последний тип операций избыточен при практической реализации, поскольку подмножество переносимых элементов может быть вычислено путем анализа интервалов индексов для удаляемых элементов. Тем не менее, здесь они используются с методической целью. Все значения индексов позиций элементов рассчитываются относительно исходных версий коллекции. Корректное представление дельты  предполагает, что выполняются следующие условия: означающие, что индексы позиций вставки элементов не повторяются, а интервалы вставляемых и удаляемых элементов не пересекаются в разных операциях. Будем считать также, что аналогичное условие выполняется для операций переноса элементов, индексы которых в исходном списке дополняют индексы удаляемых элементов: Применение дельты предполагает предварительное упорядочение операций по индексам вставки и удаления элементов в исходной коллекции  таким образом, что при совпадении индексов операции вставки предшествуют соответствующим операциям удаления.
Сами операции последовательно выполняются со значениями индексов, скорректированными с учетом предшествующих результатов. При подобной интерпретации каждая операция вставки элементов  может рассматриваться в качестве композиции элементарных операций вставки отдельных элементов   с наложенными отношениями предшествования между ними. Используемый символ отношения  означает, что операции ,  должны выполняться таким образом, чтобы в результирующем представлении коллекции элемент  предшествовал элементу  при условии, что обе операции применяются. Последнее замечание существенно, поскольку одна из операций может быть не включена в результирующую транзакцию. Тем не менее, транзитивные отношения предшествования определяют частичный порядок между операциями транзакции, который должен соблюдаться независимо от того, какие операции применяются, а какие — нет. Таким образом, установленные отношения предшествования гарантируют, что элементы  будут вставлены в результирующий список, не нарушая исходный порядок. Подобные отношения могут конструктивно использоваться при выполнении операций. Например, если операция реализуется как вставка в указанную позицию списка, то при условии  операция  должна применяться до операции . Две конкурентные операции с пересекающимися значениями интервалов индексов могут приводить к ситуациям, допускающим неоднозначное решение. Две операции удаления  и  с пересекающимися интервалами индексов  допускают консолидированное исполнение  в виде . Однако полный перечень опций применения определяется как множество всех простых сочетаний (сочетаний без повторений) операций удаления, включая пустое множество: . Число возможных сочетаний может быть слишком велико для выбора необходимого варианта в ходе интерактивной сессии. Поэтому более естественным может оказаться представление конкурентных операций в более компактном виде с меньшим числом альтернатив выбора, а именно: Отметим, что агрегированная операция удаления общих элементов  может рассматриваться как консолидированное действие, не требующее в большинстве случаев дополнительного согласования.


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


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

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

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

Упорядоченные множества являются одновременно специализацией и множеств, и списков, поэтому процедуры сравнения, рассмотренные выше, могли бы применяться и для этого случая. Однако в силу сочетания свойств упорядочения и уникальности элементов, видится более содержательный способ представления и расчета изменений для данного типа коллекций не только в виде операций вставки и удаления, но и операций перестановок. Пусть  — исходная и модифицированная версии упорядоченного множества. Подобно спискам предполагается, что элементы коллекции последовательно перенумерованы, начиная с единицы, и с каждым элементом ассоциирован соответствующий индекс позиции. Тогда дельта может быть представлена как множество операций циклических перестановок, вставок новых элементов и удалений существующих элементов:  =     Операция перестановки  однократно циклически переставляет элементы исходного множества , приводя к следующему результату: . Операция  вставляет упорядоченный набор элементов модифицированного списка  с индексами в отрезке  в позицию i-ого элемента исходного множества . Операция  удаляет элементы исходного множества  с индексами, принадлежащими отрезку . Определим более точно семантику операций, исходя из требований предшествования группы новых элементов элементу исходного множества, в позицию которого происходит вставка, сохранения порядка вставляемых элементов относительно друг друга в соответствии с их позициями, а также непрерывности их следования в результирующем представлении множества независимо от применения или неприменения всех других операций дельты. Использование перестановок в представлении дельты упорядоченного множества позволяет изменить порядок элементов без их парных удалений и вставок, как это осуществлялось в случае списков. Более содержательный способ структуризации изменений, отражающий семантику данных, является принципиальным с учетом сложности приложений, оперирующих масштабными междисциплинарными информационными моделями. Все значения индексов позиций указываются в представлении дельты относительно исходных версий коллекции.
При выполнении дельты индексные параметры всех последующих операций должны корректироваться с учетом ранее примененных. Данная корректировка заключается в увеличении или уменьшении индексов элементов исходного множества на количество выполненных вставок или удалений. При выполнении перестановок корректировка состоит в циклическом распространении индекса для каждого последующего элемента группы перестановки. Любое изменение порядка элементов в упорядоченном множестве может быть представлено композицией циклических перестановок. Причем при отсутствии пересечений по индексам перестановки удовлетворяют требованию коммутативности и могут применяться в произвольном порядке независимым друг от друга образом [19]. Тем самым удовлетворяется требование конструктивной декомпозиции и реконсиляции транзакций, связанное с возможностью независимого применения их отдельных операций. При этом наличие одного и того же индекса в разных группах перестановок дельты  должно быть запрещено: Данное условие не является обременительным, поскольку существует четкая методика разложения перестановки произвольного упорядоченного множества на группы циклических перестановок. Данная методика приводится в [19] как доказательство теоремы о единственности специально заданного соединительного произведения перестановки линейно упорядоченного мультимножества. Для корректного применения дельты  операции могут быть частично упорядочены подобно тому, как это делалось для операций со списками. Предшествование операций циклической перестановки операциям вставки, а тех, в свою очередь, операциям удаления позволяет упростить реализацию применения дельты: Данное требование связано с принятой семантикой операций, допускающей непосредственную индексацию элементов в исходных коллекциях. Вставка группы элементов неявно подразумевает задание ограничения предшествования добавляемых элементов элементу, в позицию которого осуществляется вставка. Однако следующая за вставкой операция перестановки может нарушить это условие.


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

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

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

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


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

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

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

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

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

Вставка тождественных элементов в разные позиции.


Стандартным способом разрешения конфликта является принятие одной из операций или отмена обеих.

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

Удаление элемента в одной транзакции при его перестановке в другой. Способ разрешения — стандартный.

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

Коллекции с ограниченной мощностью

Наконец, особым образом должны реализовываться процедуры применения дельты для коллекций с ограниченной мощностью. В предположении, что исходная и модифицируемая версия коллекции были корректны и удовлетворяли необходимым семантическим ограничениям, частичное применение операций дельты также должно удовлетворять наложенным ограничениям мощности (размера коллекции). Способы представления и вычисления дельты при этом не меняются и определяются иными семантическими свойствами (см. предыдущие разделы), однако применение отдельных операций удаления и добавления элементов должно проводиться в соответствии с дополнительными логическими отношениями, индуцируемыми соответствующими ограничениями. Пусть задано следующее ограничение мощности коллекции: , где . Частный случай  соответствует коллекции фиксированной мощности. Если  и  — соответствующие подмножества операций вставки и удаления исходного представления дельты , то должно выполняться следующее дополнительное условие: . Очевидно, что в случае фиксированной мощности  количество операций вставки и удаления в транзакции должно совпадать. Для мультимножеств условие представления дельты  приобретает вид . В случае конкурентных транзакций  приведенные выше условия должны выполняться для консолидированной дельты  и итогового представления коллекции . В случае  конфликт вызывает преобладание операций удаления над операциями вставки, в случае  — преобладание операций вставки. Логичным способом разрешения подобных конфликтов является исключение такого количества преобладающих операций, чтобы мощность итоговой коллекции удовлетворяла наложенному ограничению: . Очевидно, что при выборе исключаемых операций следует учитывать и другие ограничения, наложенные на коллекцию. Например, в случае ограничения уникальности операции вставки и удаления элемента с одним и тем же значением должны быть включены или исключены совместно. Рассмотрим следующий пример. Пусть  — базовая и модифицированные версии мультимножества символов с ограниченной мощностью : , , .
Тогда дельты, вычисленные путем сравнения модифицированных версий с базовой, представляются как , . Операции  и  эквивалентны, поэтому в результирующую дельту следует включить любую из них. Операция  не конфликтует ни с одной другой операцией, поэтому переносится в результат без изменений. Наконец, операции  и  конфликтуют друг с другом. Согласно рассмотренным выше методам согласования изменений для мультимножеств, конфликт можно разрешить выбором кратности вхождения элемента e из интервала [2, 4]. Однако выбор значения кратности, равного 4, приводит к нарушению ограничения мощности результирующего мультимножества, в которое в таком случае войдет 7 элементов. Следовательно, допустимыми значениями кратности вхождения элемента e в итоговую коллекцию являются 2 и 3. В случае принятия второго значения результирующая дельта приобретает вид: , а итоговое семантически корректное представление мультимножества — .

Последовательности фиксированной длины

Наличие у последовательности элементов статически фиксированной длины вносит коррективы в способ представления дельты, наиболее адекватно отражающий ее семантику. Коллекции данного типа будем называть статическими массивами. Для подобных случаев  будем использовать следующее представление дельты: , фиксирующее индексы измененных элементов. Здесь операция  заменяет значение элемента исходного массива  с индексом i значением соответствующего элемента модифицируемого массива . Корректное представление дельты  предполагает, что индексы модифицируемых элементов не повторяются в разных операциях: Две конкурентные операции  и  в соответствующих транзакциях  и  оказываются конфликтными в тех случаях, когда присваивают разные значения элементу с одним и тем же индексом: , , , , . Способ разрешения конфликтов подобного рода тривиален и состоит в игнорировании обеих конкурентных операций или принятии одной из них: . В частном случае  операции эквивалентны и не конфликтуют друг с другом. Рассмотрим следующий пример согласования изменений в массиве. Пусть  — базовая и модифицированные версии массива символов: , , . Тогда соответствующие дельты представляются как , . В данном случае операции  и  эквивалентны и, следовательно, в результат включается одна из них. Операция  переносится без изменений. Операции  и  конфликтны, поэтому лишь одна из них может быть включена в результирующую дельту. В случае принятия операции второй транзакции дельта приобретает вид , а итоговый массив — .

Сортированные последовательности

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

Коллекции прямых и инверсных ассоциаций

Коллекции могут использоваться для реализации множественных ассоциативных связей между объектными типами. В языках объектно-ориентированного моделирования имеется возможность для каждой прямой ассоциации объявить соответствующую инверсную, которая представляется, как правило, неупорядоченным множеством или мультимножеством объектных ссылок и налагает дополнительные семантические ограничения (уникальности или мощности множественной ассоциации) на исходную модель. Пусть  и  — объектные типы,  — прямая множественная ассоциация,  — соответствующая ей инверсная. Будем считать, что в качестве прямой ассоциации может быть использована произвольная коллекция, в качестве инверсной — set или multiset. Поскольку модификация прямой ассоциации подразумевает симметричную коррекцию инверсной, операции установления и отмены ассоциативных отношений связаны логической эквивалентностью следующим образом: , , , . Поэтому данные операции обязаны совместно участвовать в итоговой транзакции. Если инверсная ассоциация представляется множеством, то дополнительно устанавливается ограничение уникальности инверсного отношения. При сочетании в качестве прямой и инверсных ассоциаций различных коллекций более строгое ограничение уникальности в итоге распространится на обе ассоциативные связи. Таким образом, возможны следующие варианты сочетания прямых и инверсных коллекций: «set–set», «multiset–multiset», «list–multiset», «ordered set–set». Нарушение ограничения уникальности прямой ассоциации автоматически приводит к аналогичному нарушению на стороне инверсной. Поэтому наличие инверсного ассоциативного отношения с уникальными элементами не вносит дополнительных корректив в способы представления и формирования дельты, а также в методы разрешения конфликтов, описанные в предыдущих разделах. Более интересным с этой точки зрения представляются ограничения мощности множественной ассоциации , , . В данном случае корректное представление дельты предполагает выполнение следующих условий: В силу отношений логической эквивалентности операций над прямыми и обратными ассоциациями, условия приобретают вид: В случае конкурентных транзакций  данные условия должны выполняться также для консолидированной дельты .

Таким образом, рассмотрены основные типы

Таким образом, рассмотрены основные типы коллекций, поддерживаемые популярными языками объектно-ориентированного моделирования. Для них определены способы представления, журнализации, вычисления, принятия и согласования изменений. Для каждого выделенного типа дается строгая, семантически состоятельная интерпретация конфликтов и предлагается конструктивный метод их идентификации и разрешения. Результаты предполагается использовать при создании универсальной, основанной на модельном представлении среды коллективной инженерии с развитыми возможностями семантически корректной и функционально содержательной реконсиляции дивергентных реплик данных.

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

Семенов В.А., Морозов С.В., Тарлапан О.А., Энкович И.В.
Труды Института системного программирования РАН
Работа коллектива поддержана РФФИ (грант 07-01-00427). Аннотация. Рассматривается задача нечеткого сравнения коллекций в приложениях реконсиляции. Задача возникает при оптимистической репликации структурированных данных и документов и имеет многочисленные приложения в таких актуальных областях, как управление конфигурацией программного обеспечения, управление мобильными базами данных, построение платформ и систем коллективной инженерии. В работе анализируются стандартные типы коллекций языков объектно-ориентированного моделирования, для которых описываются и обосновываются способы представления, журнализации, вычисления, принятия и согласования изменений. Для выделенных типов коллекций дается строгая, семантически содержательная интерпретация конфликтов и предлагаются конструктивные методы их идентификации и разрешения. Примеры иллюстрируют предлагаемые решения, а также служат мотивацией создания универсальной, основанной на модельном представлении оригинальной среды коллективной инженерии с развитыми возможностями семантически корректной и функционально содержательной реконсиляции дивергентных реплик данных.

Задача нечеткого сравнения в приложениях семантической реконсиляции

Обсудим особенности постановки задачи нечеткого сравнения коллекций в приложениях семантической реконсиляции. Напомним, что традиционная задача сравнения последовательностей обычно формулируется как задача отыскания минимального скрипта редактирования (последовательности элементарных команд, обеспечивающей преобразование исходной строки в заданную другую строку) [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, полученным возможной консолидацией операций из двух конкурентных транзакций.



---

---