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

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

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

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

Для сравнения списков (или последовательностей) могут быть задействованы классические алгоритмы минимального редакторского расстояния (edit-distance (ed)) и алгоритмы нахождения наибольшей общей последовательности (longest-common-subsequence (lcs)), нашедшие применение в самых разных приложениях [20, 21]. Поскольку данные семейства алгоритмов достаточно хорошо проработаны и изучены, мы ограничимся вопросами их использования в общем контексте решения задач сравнения и слияния коллекций на основе семантики модели.

Пусть элементы списка  предварительно последовательно пронумерованы, начиная с единицы, и каждый элемент  индексируется в соответствии с положением в списке. Далее  обозначается i-ый элемент коллекции,  — число элементов коллекции и  — упорядоченное подмножество элементов коллекции , начинающееся в позиции i и заканчивающееся в позиции .

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

 

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

Корректное представление дельты  предполагает, что выполняются следующие условия:

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

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

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

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

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

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

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

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

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

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

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

   

Способы консолидации элементов из альтернативных списков задаются на основе  следующими размещениями:

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

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

и

.

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

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

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