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


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


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

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

Проиллюстрируем вычисление и применение дельты для упорядоченных множеств на следующем примере. Пусть

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

В ходе применения дельты к основной версии

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

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

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

    ,

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


    Начало  Назад  Вперед



    Книжный магазин