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

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

Пусть элементы списка

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

индексируется в соответствии с положением в списке. Далее

обозначается i-ый элемент коллекции,

— число элементов коллекции и

— упорядоченное подмножество элементов коллекции

, начинающееся в позиции i и заканчивающееся в позиции

Тогда дельта, полученная в результате сравнения двух версий коллекции

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

Здесь операция

вставляет упорядоченный набор элементов модифицированного списка

с индексами в отрезке

в позицию i исходного списка

. Операция

удаляет элементы исходного списка с индексами, принадлежащими отрезку

, и, наконец, операция

переносит элементы с индексами в отрезке

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

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

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

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

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

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

таким образом, что при совпадении индексов операции вставки предшествуют соответствующим операциям удаления.

Содержание Вперед

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