Сжатие данных с конечными окнами

Представлено несколько методов адаптивного обратимого сжатия данных в стиле первого предложения Лемпеля и Зива по текстовой замене. Для первых двух методов описаны модификации структуры данных «суффиксное дерево» МакКрейта, поддерживающие циклическое ведение окна, содержащего наиболее последние символы исходных данных. Для удержания позиций узлов внутри окна используется перколирующее обновление; показано, что процесс обновления имеет постоянную амортизированную стоимость. В других методах исследуются компромиссы между временем сжатия, временем распаковки, размером структуры данных и достигнутой степенью сжатия. Статья включает графо-теоретический анализ потерь сжатия, обусловленных нашей политикой выбора кодовых слов, по сравнению с оптимальной политикой, а также эмпирические исследования производительности различных адаптивных компрессоров, описанных в литературе.