Словарное сжатие

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

История

Идея использования словаря для сжатия восходит к ранним работам по теории информации. В 1977 году израильские учёные Якоб Зив и Абрахам Лемпел опубликовали алгоритм LZ77, который заложил основу для целого семейства словарных методов. Вместо построения явного словаря LZ77 использует скользящее окно — буфер, содержащий уже обработанные данные. Алгоритм ищет в этом окне самую длинную совпадающую подстроку и кодирует её парой (смещение от текущей позиции, длина совпадения). Если совпадение не найдено, символ кодируется как литерал (непосредственное значение).

В 1978 году те же авторы представили LZ78, который строит словарь явно, добавляя в него новые фразы по мере обработки. Каждая фраза кодируется ссылкой на индекс предыдущей фразы плюс новый символ. Этот подход стал основой для многих последующих реализаций.

Основные вехи развития:

• 1984 год: Терри Уэлч опубликовал LZW (Lempel-Ziv-Welch) — модификацию LZ78, которая устраняет необходимость хранения словаря в сжатом потоке. LZW стал широко известен благодаря использованию в формате GIF и утилите compress.
• 1990-е годы: Развитие алгоритмов семейства LZSS (Lempel-Ziv-Storer-Szymanski) — улучшенная версия LZ77, оптимизирующая кодирование за счёт минимальной длины совпадения и битовых флагов. LZSS лёг в основу форматов PKZIP, ARJ и многих других.
• 1993 год: Появление DEFLATE — гибридного алгоритма, объединяющего LZSS (словарное сжатие) и кодирование Хаффмана (статистическое сжатие). DEFLATE стал стандартом для форматов PNG, gzip и ZIP (в реализации Info-ZIP).
• 2000-е годы: Разработка LZMA (Lempel-Ziv-Markov chain algorithm) — эволюция LZ77 с увеличенным словарём (до 4 ГБ), улучшенным поиском совпадений и контекстным моделированием. LZMA используется в архиваторе 7-Zip и формате 7z.
• 2010-е годы: Появление Brotli (Google, 2013) и Zstandard (Facebook, 2015) — современных алгоритмов, сочетающих словарное сжатие с продвинутыми методами энтропийного кодирования и предопределёнными статическими словарями для веб-контента.

Принцип работы

Словарное сжатие основано на выявлении и устранении избыточности — повторяющихся паттернов в данных. Процесс сжатия включает три этапа:

1. Анализ входного потока: алгоритм последовательно читает данные, разбивая их на фразы (слова, фрагменты). Для каждой новой фразы проверяется, встречалась ли она ранее.
2. Поиск совпадений: если фраза уже есть в словаре (или в скользящем окне для LZ77), она заменяется ссылкой — указателем на предыдущее вхождение. Ссылка обычно состоит из двух чисел: идентификатора (индекса или смещения) и длины совпадения.
3. Кодирование: ссылки и литералы (уникальные фрагменты) упаковываются в сжатый поток. Для повышения эффективности часто применяется дополнительное энтропийное кодирование — например, кодирование Хаффмана, арифметическое кодирование или кодирование длин серий.

Пример

Рассмотрим строку: "abracadabra".

• Первый проход (LZ77): Алгоритм начинает с пустого окна. Первые символы a, b, r не имеют совпадений — кодируются как литералы. При появлении a (позиция 4) алгоритм находит совпадение с a в начале строки (смещение 3, длина 1). Далее c, a, d — литералы. При a (позиция 8) совпадение с a на позиции 4 (смещение 4, длина 1). Символы b, r, a (позиции 9-11) образуют последовательность "bra", которая уже встречалась на позициях 1-3 — кодируется как (смещение 8, длина 3).

Результат: литералы a, b, r, ссылка (3,1), литералы c, a, d, ссылка (4,1), ссылка (8,3). В реальных алгоритмах формат кодирования может отличаться.

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

Словарные методы делятся на два основных класса:

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

• LZ77: использует буфер (окно) фиксированного размера, содержащий уже обработанные данные. Словарь неявный — это само окно. Поиск совпадений ведётся только в пределах окна.
• LZSS: улучшенная версия LZ77, вводит минимальную длину совпадения (обычно 2-3 символа) и битовые флаги для различения литералов и ссылок.
• LZMA: расширение LZ77 с увеличенным окном (до 4 ГБ), улучшенным поиском (использование хеш-таблиц и бинарных деревьев) и марковским моделированием для выбора оптимального кодирования.
• DEFLATE: комбинирует LZSS с кодированием Хаффмана. Использует окно размером 32 КБ. Поддерживает три режима: без сжатия, сжатие фиксированными кодами Хаффмана, сжатие динамическими кодами.
• Brotli: использует окно до 16 МБ, предопределённый статический словарь (около 13 000 слов и фраз для веб-контента) и контекстное моделирование для улучшения сжатия текстов.
• Zstandard: окно до 2 ГБ, высокая скорость сжатия/распаковки, поддержка предопределённых словарей и репетиционных кодов (копирование повторяющихся последовательностей).

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

• LZ78: строит словарь фраз, добавляя каждую новую фразу как комбинацию существующей фразы и нового символа. Словарь растёт по мере обработки, но не ограничен размером окна.
• LZW: модификация LZ78, при которой словарь инициализируется всеми возможными символами (обычно 256 для байтового алфавита). Новые фразы добавляются в словарь, но не кодируются явно — декодер восстанавливает словарь синхронно. LZW широко использовался в форматах GIF, TIFF и утилите compress.
• LZMW: вариант LZW, который добавляет в словарь не только фразы из одного нового символа, но и более длинные последовательности, ускоряя адаптацию к данным.
• LZC: модификация LZW с возможностью очистки словаря при его заполнении, что улучшает сжатие для данных с меняющейся статистикой.

Применение

Словарное сжатие используется в широком спектре областей:

• Архивация файлов: форматы ZIP, gzip, 7z, RAR, tar.gz, bzip2 (BWT + словарное сжатие). Архиваторы, такие как 7-Zip, WinRAR, WinZip, являются стандартными инструментами в операционных системах семейства Windows и Linux.
• Графические форматы: GIF (LZW), PNG (DEFLATE), TIFF (LZW или DEFLATE). Словарное сжатие эффективно для изображений с большими областями однородного цвета или повторяющимися узорами.
• Сетевые протоколы: HTTP-сжатие (gzip, Brotli, Zstandard) — веб-серверы сжимают HTML, CSS, JavaScript и другие текстовые ресурсы перед отправкой клиенту. Brotli поддерживается всеми современными браузерами.
• Файловые системы: сжатие NTFS (LZNT1 — вариант LZ77), Btrfs (zstd), ZFS (LZ4, zstd). Прозрачное сжатие на уровне файловой системы позволяет экономить дисковое пространство без вмешательства пользователя.
• Базы данных: сжатие строковых полей, индексов и логов. Например, PostgreSQL поддерживает сжатие TOAST (The Oversized-Attribute Storage Technique) с использованием LZSS; MySQL — сжатие InnoDB (zlib).
• Программное обеспечение: упаковка исполняемых файлов (UPX — Ultimate Packer for eXecutables, использует LZMA), сжатие образов дисков (ISO, VHD).

Преимущества и недостатки

Преимущества

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

Недостатки

• Ограниченная эффективность для случайных данных: если данные не содержат повторяющихся фрагментов (например, уже сжатые файлы, зашифрованные данные), словарное сжатие может даже увеличить размер (из-за накладных расходов на кодирование ссылок).
• Память: для больших словарей (в LZMA, Zstandard) требуется значительный объём оперативной памяти как при сжатии, так и при распаковке.
• Скорость сжатия: поиск совпадений в большом окне или словаре может быть вычислительно затратным. Для ускорения используются хеш-таблицы, деревья и эвристики (например, ленивое сопоставление).
• Чувствительность к параметрам: эффективность сильно зависит от размера окна, минимальной длины совпадения и стратегии управления словарём. Неоптимальные параметры могут снизить степень сжатия.

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

• Алгоритм LZW был запатентован компанией Unisys, что привело к юридическим спорам и стимулировало разработку свободных альтернатив, таких как DEFLATE.
• Формат GIF изначально использовал LZW, но после истечения патента в 2004 году стал полностью свободным.
• Алгоритм Brotli был разработан Яковом Зивом (соавтором LZ77) и Йоавом Вайсом (Google). Его статический словарь включает не только английские, но и русские, китайские и другие часто используемые слова.
• Zstandard (zstd) от Facebook (организация Meta признана экстремистской и запрещена в РФ) в 2015 году был предложен как замена zlib и gzip для высокопроизводительных систем. Он поддерживает уровни сжатия от 1 (быстро) до 22 (максимально).
• В России словарное сжатие активно применяется в системах электронного документооборота (ЭДО) и архивации данных в государственных учреждениях, где форматы ZIP и 7z являются стандартными.

Источники

• Зив Я., Лемпел А. «A Universal Algorithm for Sequential Data Compression» (1977) — оригинальная статья LZ77.
• Зив Я., Лемпел А. «Compression of Individual Sequences via Variable-Rate Coding» (1978) — оригинальная статья LZ78.
• Уэлч Т. «A Technique for High-Performance Data Compression» (1984) — описание LZW.
• Дойч П. «DEFLATE Compressed Data Format Specification version 1.3» (RFC 1951, 1996).
• Google. «Brotli Compressed Data Format» (RFC 7932, 2016).
• Facebook (организация Meta признана экстремистской и запрещена в РФ). «Zstandard — Real-time compression algorithm» (2015).