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

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

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

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

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

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

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

,

фиксирующее индексы измененных элементов. Здесь операция  заменяет значение элемента исходного массива  с индексом i значением соответствующего элемента модифицируемого массива .

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

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

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

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

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

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

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

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

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

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