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

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


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

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

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