Словарные методы сжатия

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

История

Идея словарного сжатия восходит к работам Клода Шеннона (1948 год), который предложил использовать «словарь» для кодирования сообщений. Однако практические алгоритмы начали развиваться в 1970-х годах. В 1977 году израильские учёные Якоб Зив и Абрахам Лемпель опубликовали алгоритм LZ77, который стал основой для большинства современных словарных методов. В 1978 году они представили модификацию — LZ78, где словарь строился не из скользящего окна, а из явно задаваемых фраз. В 1984 году Терри Уэлч разработал алгоритм LZW (Lempel-Ziv-Welch), который стал широко использоваться в форматах GIF и Unix-утилитах compress. В 1990-х годах алгоритмы LZ77 и LZ78 легли в основу стандартов сжатия данных (PKZIP, gzip, PNG, Deflate). В 2000-х годах появились более совершенные реализации, такие как LZMA (Lempel-Ziv-Markov chain algorithm) в архиваторе 7-Zip и Brotli, используемый в веб-сжатии.

Основные принципы

Словарные методы сжатия делятся на два основных подхода: алгоритмы на основе скользящего окна (LZ77) и алгоритмы на основе явного словаря фраз (LZ78). В обоих случаях сжатие достигается за счёт замены повторяющихся последовательностей символов на ссылки, которые короче самих последовательностей.

Алгоритмы на основе скользящего окна (LZ77)

В алгоритме LZ77 сжатие выполняется с помощью двух буферов: «словаря» (скользящее окно, содержащее уже обработанные данные) и «буфера предварительного просмотра» (look-ahead buffer), содержащего ещё не закодированные символы. Алгоритм ищет самую длинную подстроку в буфере предварительного просмотра, которая совпадает с подстрокой в словаре. Если такая подстрока найдена, она кодируется как триплет (смещение, длина, следующий символ), где:

• смещение — расстояние от текущей позиции до начала найденной подстроки в словаре;
• длина — количество совпадающих символов;
• следующий символ — первый символ после совпадения, который не удалось найти в словаре.

Если совпадение не найдено, символ кодируется как литерал (сам символ) с флагом, указывающим на отсутствие ссылки. После кодирования словарь сдвигается вперёд на один или несколько символов.

Алгоритмы на основе явного словаря (LZ78)

В алгоритме LZ78 словарь строится динамически из фраз, которые встречаются в данных. Каждая новая фраза добавляется в словарь и получает уникальный индекс. Кодирование происходит путём отправки пары (индекс, следующий символ), где индекс ссылается на предыдущую фразу в словаре, а следующий символ — это новый символ, который расширяет фразу. Например, если в словаре уже есть фраза «ab» с индексом 5, а следующая фраза — «abc», то кодируется как (5, «c»). В отличие от LZ77, словарь не ограничен скользящим окном и может расти неограниченно, что может привести к переполнению памяти.

Классификация

Словарные методы сжатия можно классифицировать по нескольким признакам:

По способу построения словаря

• Статические словари — словарь фиксирован и известен как кодировщику, так и декодировщику заранее (например, словарь для сжатия английского текста). Используются редко из-за низкой адаптивности.
• Динамические (адаптивные) словари — словарь строится в процессе сжатия на основе уже обработанных данных. Это основной тип, используемый в LZ77, LZ78, LZW.
• Полуадаптивные словари — словарь строится на основе анализа всего входного потока перед сжатием, а затем передаётся вместе с данными.

По типу ссылок

• Ссылки на позицию в окне (LZ77) — указывают смещение и длину совпадения в скользящем окне.
• Ссылки на индекс в словаре (LZ78, LZW) — указывают номер фразы в словаре.

По алгоритму кодирования

• Чисто словарные — используют только замену фраз на ссылки (базовые LZ77, LZ78).
• Гибридные — комбинируют словарный метод с энтропийным кодированием (например, Deflate использует LZ77 + кодирование Хаффмана; LZMA использует LZ77 + марковское моделирование).

Применение

Словарные методы сжатия широко применяются в различных областях информационных технологий:

Архивация данных

• PKZIP (формат ZIP) — использует алгоритм Deflate (LZ77 + кодирование Хаффмана).
• gzip — использует Deflate для сжатия потоков данных.
• 7-Zip — использует LZMA (LZ77 с улучшенным поиском совпадений и марковским моделированием).
• RAR — использует собственный словарный алгоритм (PPMd и LZSS).

Форматы изображений

• GIF — использует алгоритм LZW (LZ78 с фиксированным размером словаря).
• PNG — использует Deflate для сжатия растровых данных после фильтрации.
• TIFF — поддерживает сжатие LZW.

Веб-сжатие

• HTTP-сжатие — алгоритмы gzip, deflate, Brotli (Brotli использует LZ77 с предопределённым словарём для HTML, CSS, JavaScript).
• WebP — использует алгоритм сжатия на основе LZ77 для изображений.

Сжатие текста и программного кода

• Unix-утилиты compress — используют LZW.
• Сжатие исполняемых файлов — UPX использует LZ77 для упаковки PE, ELF и Mach-O файлов.

Примеры алгоритмов

LZ77

• Принцип: скользящее окно размером 4–32 КБ, поиск совпадений.
• Кодирование: триплет (смещение, длина, следующий символ).
• Декодирование: простое восстановление по ссылкам.
• Достоинства: высокая скорость декодирования, низкая сложность.
• Недостатки: ограниченный размер окна, неэффективность при длинных повторениях.

LZ78

• Принцип: динамический словарь фраз, растущий неограниченно.
• Кодирование: пара (индекс, следующий символ).
• Декодирование: требуется восстановление словаря.
• Достоинства: не зависит от размера окна.
• Недостатки: риск переполнения памяти, сложность управления словарём.

LZW

• Модификация LZ78: словарь инициализируется всеми возможными символами (например, 256 байт), а новые фразы добавляются только при их появлении.
• Применение: GIF, compress.
• Особенность: не требует передачи начального словаря — он восстанавливается на стороне декодировщика.

Deflate

• Гибридный алгоритм: сначала LZ77 (с окном 32 КБ), затем кодирование Хаффмана для сжатия ссылок и литералов.
• Используется: ZIP, gzip, PNG, HTTP deflate.
• Степень сжатия: средняя, скорость высокая.

LZMA (Lempel-Ziv-Markov chain algorithm)

• Улучшение LZ77: использует цепь Маркова для предсказания следующего символа, большие окна (до 4 ГБ), битовое кодирование.
• Применение: 7-Zip, XZ Utils.
• Степень сжатия: высокая, скорость сжатия низкая, декодирование быстрое.

Интересные факты

• Алгоритм LZW был запатентован компанией Unisys, что привело к юридическим спорам и ограничениям на использование формата GIF в 1990-х годах. В 2003 году срок действия патента истёк.
• Алгоритм Deflate, разработанный Филом Кацем для PKZIP, стал стандартом де-факто для сжатия данных в интернете.
• В алгоритме Brotli, используемом в Google Chrome, предопределённый словарь содержит более 13 000 часто встречающихся фраз из HTML, CSS и JavaScript, что повышает сжатие для веб-трафика.
• Словарные методы сжатия являются основой для многих современных архиваторов, обеспечивая сжатие текстовых файлов в 2–5 раз, а программных файлов — в 1,5–3 раза.

Критика и ограничения

• Ограниченная эффективность на случайных данных: словарные методы плохо сжимают данные, в которых нет повторяющихся последовательностей (например, зашифрованные или сжатые файлы).
• Проблема с памятью: в алгоритмах LZ78 и LZW словарь может расти неограниченно, что требует управления памятью (например, сброс словаря при достижении лимита).
• Зависимость от размера окна: в LZ77 слишком маленькое окно снижает степень сжатия, слишком большое — увеличивает время поиска совпадений.
• Необходимость баланса: гибридные алгоритмы (Deflate, LZMA) требуют настройки параметров для достижения оптимального сжатия.

Источники

• Зив Я., Лемпель А. «A Universal Algorithm for Sequential Data Compression» (1977).
• Зив Я., Лемпель А. «Compression of Individual Sequences via Variable-Rate Coding» (1978).
• Уэлч Т. «A Technique for High-Performance Data Compression» (1984).
• Саломон Д. «Сжатие данных, изображений и звука» (2004).
• Сейди Д. «Алгоритмы сжатия данных» (2007).