Главная/ 11 класс/Урок #4

Урок #4. Алгоритм LZW: словарное сжатие

📘 11 класс · 🎯 Динамический словарь, проблема KWK

Введение

Алгоритм LZW (Lempel-Ziv-Welch) лежит в основе форматов GIF, TIFF, PDF и многих других. Его главная идея — замена повторяющихся последовательностей данных короткими кодами.

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

Как строится словарь

  1. Инициализация. В самом начале у алгоритма нет словаря. Он знает только базовые символы. Если мы работаем с текстом в кодировке ASCII, то в словаре изначально 256 записей: код 0 соответствует символу с кодом 0, код 1 — символу с кодом 1, и так до 255.
  2. Динамическое расширение. По мере чтения данных алгоритм создаёт новые записи. Если он встречает последовательность «АБ», которой нет в словаре, он записывает её под новым номером (например, 256). В следующий раз, встретив «АБ», он не будет передавать две буквы, а передаст один код 256.
  3. Размер кода. Обычно алгоритм начинает с 9-битных кодов (чтобы покрыть 256 базовых символов и иметь запас для новых). Когда коды заканчиваются (например, 9 бит позволяют записать числа до 511), алгоритм переходит на 10 бит, затем на 11 и так далее, пока не достигнет лимита (обычно 12 бит, то есть 4096 записей в словаре). Когда словарь заполняется, его либо очищают, либо начинают перезаписывать старые записи.

Практический пример сжатия

Давайте сожмём простую строку. Для наглядности возьмём короткую последовательность символов: А Б А Б А Б А Б.

Предположим, мы используем 9-битные коды. Наши базовые символы: A = 65, Б = 66. Алгоритм всегда считывает на один символ больше, чем нужно для проверки. Переменная ТекущаяСтрока (S) изначально пуста.

Шаг 1

  • Читаем «А». S = «А». В словаре есть.
  • Читаем следующий символ «Б». Проверяем, есть ли в словаре строка S + «Б», то есть «АБ».
  • Строки «АБ» (код 256) в словаре ещё нет.
  • Действие: В выходной поток записываем код строки S, то есть 65.
  • Обновление словаря: Добавляем новую запись: 256 = «АБ».
  • Сбрасываем S, записываем в неё текущий символ: S = «Б».

Шаг 2

  • Читаем «А». Проверяем «БА». В словаре нет.
  • Действие: Записываем код 66. Обновление словаря: 257 = «БА». S = «А».

Шаг 3

  • Читаем «Б». Проверяем «АБ». Строка «АБ» уже есть в словаре (мы добавили её на шаге 1, код 256). S становится «АБ».
  • Читаем следующий «А». Проверяем «АБА». В словаре нет.
  • Действие: Записываем код 256. Обновление словаря: 258 = «АБА». S = «А».

Шаг 4

  • Читаем «Б». Проверяем «АБ». Есть в словаре (256). S = «АБ».
  • Читаем «А». Проверяем «АБА». Есть в словаре (258). S = «АБА».
  • Читаем «Б». Проверяем «АБАБ». В словаре нет.
  • Действие: Записываем код 258. Обновление словаря: 259 = «АБАБ». S = «Б».

Итог сжатия. Входная строка (8 символов по 8 бит = 64 бита): А Б А Б А Б А Б. Выходной поток кодов: 65, 66, 256, 258. Если использовать 9 бит на код, мы потратим 36 бит. Степень сжатия составила почти 50 %.

Процесс распаковки (декодирование)

Распаковщик делает ровно обратное, причём он восстанавливает словарь на лету, не получая его по сети. Он знает то же правило: новый код в словаре — это предыдущий код + первый символ текущего кода.

Распаковщик получает: 65, 66, 256, 258.

  1. Читает 65. Пишет в результат «А». Предыдущий код (K1) = 65.
  2. Читает 66. Пишет «Б». Создаёт новую запись словаря 256. Она равна K1 + первый символ текущего кода = «А» + «Б» = «АБ». K1 = 66.
  3. Читает 256. Пишет «АБ». Создаёт запись 257. Она равна K1 + первый символ «АБ» = «Б» + «А» = «БА». K1 = 256.
  4. Читает 258. Пишет «АБА». Создаёт запись 259. Она равна K1 + первый символ «АБА» = «АБ» + «А» = «АБА».
🔑
Проблема KWK (KwKwK)Что делать, если распаковщик получает код, который он ещё не успел занести в словарь? Это случается, когда кодируется строка вида «S + первый_символ_S». В этом случае распаковщик берёт предыдущий код (K1), берёт его первый символ и приписывает к K1. Это знаменитая «проблема KWK», и алгоритм LZW элегантно её решает.

Почему это важно?

LZW не требует передачи словаря вместе с данными. Это асимметричный алгоритм: сжатие требует больше вычислительных ресурсов (поиск в таблице), чем распаковка. Именно поэтому он долгое время доминировал в графике (формат GIF) — картинку сжимают один раз при сохранении, а открывают миллионы раз.

Стоит отметить, что алгоритм LZW был защищён патентами в США до 2003–2004 годов. Это привело к тому, что в открытых системах широкое распространение получил алгоритм Deflate (используется в ZIP и gzip), который не нарушает патенты LZW, комбинируя методы LZ77 и кодирования Хаффмана.

⚙️
Попробуйте самиОткройте интерактивный тренажёр «LZW по шагам» — введите любой текст и посмотрите журнал сжатия, контракт «что передаётся», распаковку с эмуляцией KWK и проверку обратимости.