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


Сравнение списков - часть 4


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

и

.

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

.

Оценка вычислительной сложности классического алгоритма минимального редакторского расстояния с использованием метода динамического программирования составляет

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




Начало  Назад  



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