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


         

и модифицированные версии некоторого списка


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


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

Содержание  Назад  





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