Словарное кодирование

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

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

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

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

История

Первые теоретические работы по словарному сжатию появились в 1970-х годах. В 1977 году Джейкоб Зив и Абрахам Лемпел опубликовали алгоритм LZ77, основанный на скользящем окне и неявном словаре. В 1978 году они представили алгоритм LZ78, который использовал явно формируемый словарь. Эти две работы заложили основу для целого семейства алгоритмов LZ (Lempel-Ziv).

В 1984 году Терри Уэлч модифицировал LZ78, создав алгоритм LZW (Lempel-Ziv-Welch), который стал широко использоваться в форматах GIF и TIFF. В 1990-х годах на основе LZ77 были разработаны алгоритмы Deflate (используется в ZIP, PNG, gzip) и LZMA (используется в 7z, XZ). Словарные методы продолжают совершенствоваться, включая варианты с адаптивным размером словаря, многопоточным сжатием и поддержкой больших объёмов данных.

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

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

Статическое словарное кодирование

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

Адаптивное (динамическое) словарное кодирование

Словарь строится в процессе сжатия и распаковки на лету. Алгоритм начинает с пустого или минимального словаря и добавляет новые фразы по мере их появления во входном потоке. Это позволяет адаптироваться к локальным закономерностям данных без предварительного анализа. Большинство современных алгоритмов (LZ77, LZ78, LZW, LZMA) являются адаптивными.

Основные алгоритмы

LZ77

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

LZ78

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

LZW

Модификация LZ78, предложенная Терри Уэлчем. В LZW словарь инициализируется всеми возможными одиночными символами (обычно 256 байтами). При сжатии алгоритм ищет самую длинную строку, уже присутствующую в словаре, и выводит её код, после чего добавляет в словарь новую строку, состоящую из найденной плюс следующий символ. LZW широко применялся в форматах GIF и TIFF, но в настоящее время уступает по эффективности более современным алгоритмам.

Deflate

Гибридный алгоритм, используемый в форматах ZIP, gzip и PNG. Deflate комбинирует LZ77 (с размером окна до 32 КБ) с кодированием Хаффмана. Сначала LZ77 заменяет повторяющиеся последовательности ссылками, затем статистический кодер Хаффмана сжимает полученные коды и литералы. Deflate обеспечивает хорошее сжатие при умеренном потреблении памяти.

LZMA (Lempel-Ziv-Markov chain Algorithm)

Разработан Игорем Павловым в 1998 году для архиватора 7-Zip. LZMA использует LZ77 с большим скользящим окном (до 4 ГБ), а также марковскую модель для предсказания следующих символов и арифметическое кодирование. LZMA обеспечивает высокую степень сжатия, но требует значительных вычислительных ресурсов при сжатии.

Применение

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

• Архивация данных: форматы ZIP, 7z, RAR, gzip, bzip2 (последний использует преобразование Барроуза — Уиллера в сочетании со словарными методами).
• Графические форматы: GIF (LZW), PNG (Deflate), TIFF (LZW, Deflate).
• Сжатие текста: алгоритмы LZ77 и LZW применяются в протоколах HTTP (сжатие gzip), в файловых системах (ZFS, NTFS) и в базах данных.
• Сжатие аудио и видео: некоторые кодеки (например, FLAC для аудио) используют словарные методы для сжатия без потерь.
• Сетевое сжатие: протоколы SSH, SSL/TLS могут использовать словарное сжатие для уменьшения объёма передаваемых данных.

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

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

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

Недостатки

• Степень сжатия ниже, чем у статистических методов, на данных с равномерным распределением символов (например, зашифрованные или сжатые ранее данные).
• Потребление памяти для хранения словаря или скользящего окна.
• Для некоторых алгоритмов (LZW, LZ78) возможен рост словаря до неоправданно больших размеров, что снижает эффективность.

Сравнение со статистическими методами

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

Источники

• Зив Дж., Лемпел А. (1977). «A Universal Algorithm for Sequential Data Compression». IEEE Transactions on Information Theory.
• Зив Дж., Лемпел А. (1978). «Compression of Individual Sequences via Variable-Rate Coding». IEEE Transactions on Information Theory.
• Уэлч Т. (1984). «A Technique for High-Performance Data Compression». Computer.
• Саломон Д. (2007). «Сжатие данных, изображений и звука». — М.: Техносфера.
• ГОСТ Р 50922-2006. «Защита информации. Основные термины и определения».