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

Исследуется оптимальное соотношение между степенью сжатия и сложностью для алгоритмов сжатия данных с потерями, основанных на случайных кодовых книгах или случайных базах данных. Отправной точкой для исследования частично послужили недавние результаты Гупты–Верду–Вайссмана (GVW-алгоритм) и их связи со схемой сравнения с эталоном в алгоритме Контоянниса сжатия с потерями типа Лемпеля–Зива. Предложен неуниверсальный вариант метода сжатия с потерями типа Лемпеля–Зива (LLZ-алгоритм). Устанавливается оптимальность LLZ-метода для источников без памяти, и его эффективность сравнивается с эффективностью GVW-подхода типа “разделяй и властвуй”. Результаты экспериментов показывают, что GVW-подход зачастую дает лучшее сжатие, чем LLZ, но за счет гораздо большего объема требуемой памяти. Чтобы объединить преимущества обоих методов, вводится гибридный алгоритм (HYB-алгоритм), использующий как идею “разделяй и властвуй” GVW-алгоритма, так и структуру единой базы данных LLZ-алгоритма. Доказано, что HYB-алгоритм имеет в точности такое же соотношение между скоростью и искажением и такую же вычислительную сложность, что и GVW-алгоритм, но в то же время, как и LLZ-алгоритм, требует меньшего объема памяти, причем необходимая память отличается на множитель, неограниченно растущий при подходящем выборе параметров конструкции. Приведены результаты экспериментов, иллюстрирующие эффективность всех трех методов для данных, порождаемых простыми дискретными источниками без памяти. В частности, показано, что HYB-алгоритм превосходит по эффективности существующие схемы сжатия для некоторых простых дискретных источников при хэмминговом критерии искажения.