Алгоритм LZW и сжатие с потерями
Как словарь сжимает текст без потерь — и что выбрасывают JPEG и MP3.
11 класс, углублённый уровень — пара третья.
Уроки 5–6 поурочного плана: «Алгоритм LZW» и «Алгоритмы сжатия данных с
потерями». Задачи на глубину цвета и битрейт — те же расчёты, что в задании 7
ЕГЭ про объём изображения и звука.
Словарное сжатие: идея
В тексте повторяются не только буквы, но и целые фразы. Если фразе дать
номер, вместо неё можно записать один код.
LZW: повторяющиеся фразы заменяются номерами из
словаря. В начале в словаре только отдельные буквы алфавита.
Хитрость в том, что словарь не передаётся. Кодер и декодер строят
его одинаково, по ходу работы — по одному правилу. Получатель видит только
последовательность кодов.
LZW сжимает без потерь: из кодов восстанавливается
исходный текст знак в знак. На нём основаны форматы GIF и TIFF.
Кодирование LZW по шагам
- взять с текущего места самую длинную фразу, которая уже есть в словаре;
- выдать её код;
- занести в словарь новую фразу: эта фраза + следующий символ;
- продолжить с символа, на котором остановились.
Сообщение 
, словарь А = 1, Б = 2:
Каждый код, кроме последнего, добавляет в словарь
одну фразу: за последней фразой нет следующего символа.
Декодирование LZW
Читаем коды по одному и выписываем фразы. Словарь декодер строит сам:
после каждой фразы, начиная со второй, в словарь
добавляется предыдущая фраза + первая буква текущей.
Коды 
, словарь А = 1, Б = 2:
Словарь тот же, что был у кодера: 3 = АБ, 4 = БА, 5 = АБА, 6 = АА.
Поэтому его и не нужно передавать.
Букву считай в раскрытом сообщении, а не среди
кодов: код 3 — это целая фраза АБ.
Сколько бит на код
Все коды одной длины. Кодом из b бит можно пронумеровать 2b фраз.
2b ≥ N
В словаре 600 фраз: 29 = 512 — мало, 210 = 1024 —
хватает. Код длиной 10 бит.
Текст из 1000 символов по 8 бит, после LZW — 400 кодов по 12 бит:
Код LZW длиннее одного символа. Выигрыш — за счёт
того, что кодов намного меньше, чем символов.
Сжатие с потерями
Без потерь
RLE, Хаффман, LZW, ZIP, PNG, FLAC:
данные восстанавливаются бит в бит. Годится для текста и программ.
С потерями
JPEG, MP3, AAC, MPEG-4: отбрасывается
то, чего человек почти не замечает. Назад это не вернуть.
Зачем терять? Фото и звук — для глаза и уха, а у них есть пределы: оттенки
цвета мы различаем хуже, чем яркость, а тихий звук рядом с громким не слышим
вовсе. Выброшенное этим пределом файл почти не портит, а сжатие в разы
сильнее.
Глубина кодирования цвета
i бит на пиксель — 2i цветов. Объём изображения:
V = ширина · высота · i
Самый простой способ сжатия с потерями — уменьшить i. С 24 до 8 бит:
Объём уменьшается во столько раз, во сколько уменьшилась
глубина, а экономия на каждом пикселе — разница бит.
Палитра из 256 цветов — это 8 бит на пиксель
(256 = 28). Если дано число цветов, сначала переведи его в биты.
Ответ в Кбайтах: биты : 8 : 1024.
Идеи JPEG
- Яркость и цвет отдельно. Изображение переводится в яркость Y и две
цветовые составляющие Cb и Cr. Яркость хранится для каждого пикселя, цвет —
одно значение на квадрат 2 × 2: к цвету глаз менее чувствителен.
- Блоки 8 × 8. Изображение делится на квадраты 8 × 8 пикселей, каждый
обрабатывается отдельно.
- Квантование. Коэффициенты блока делятся на шаг и округляются —
здесь и теряется информация; потом всё сжимается без потерь.
MP3 и битрейт
MP3 отбрасывает звуки, которых ухо не различает: тихие рядом с громкими,
слишком высокие. Размер файла задаёт битрейт — сколько бит уходит на
секунду звучания.
V = битрейт · время
128 Кбит/с : 8 = 16 Кбайт/с. Минута звучания — 16 · 60 = 960 Кбайт.
От частоты дискретизации и разрядности исходной записи
размер MP3 уже не зависит — только битрейт и время. Кбиты в Кбайты — делить
на 8.
Что делаем дальше
- Обзорный практикум — шесть задач, все сразу на странице, в любом
порядке: кодирование и декодирование LZW, объём после LZW, глубина цвета,
идеи JPEG, MP3 и форматы.
- LZW удобнее расписывать на черновике таблицей: фраза, код, в словарь.
- Ответ везде — целое число, без единиц:
, а не «48 Кбайт».
Ошибся — сразу виден разбор, а «Новые числа» дают ту же задачу с другими
данными. Отметка: закрыто 6 из 6 — «5», 5 — «4», 3 или 4 — «3».
За работу
Практикум «Алгоритм LZW и сжатие с потерями» — в общей папке и на
сайте. Не успел на уроке — пройди дома: вариант будет другой, сдаётся тем же
кодом.
Карточку в тетрадь можно взять с собой: на ней LZW по шагам с примером,
правило декодера, глубина цвета, идеи JPEG и MP3.