Алгоритм LZW и сжатие с потерями

11 класс, углублённый уровень. Обзорный практикум к третьей паре: шесть задач по содержанию темы.

Что нужно сделать: Шесть задач — по одной на каждый вопрос темы, и все сразу на странице: решай в любом порядке. Ответил верно — вопрос закрыт. Ошибся — сразу видно, как это решается, а вопрос остаётся открытым: кнопка «Новые числа» даёт ту же задачу с другими данными, и её можно сдать ещё раз. Сколько закрыл, столько и наработал. Времени нужно около пятнадцати минут: LZW удобнее расписывать на черновике таблицей.
Отметка и добор: Закрыто 6 из 6 — «5», 5 — «4», 3 или 4 — «3». Кнопка «Получить код» внизу страницы появляется, как только закрыто три вопроса: можно забрать код сразу, а можно дорешать оставшиеся и получить код получше — решать самому, до какой отметки добирать.
Ответ — целое число: Без единиц измерения и без пробелов: 34, а не 34 бита. На КЕГЭ ответ читает машина, и здесь так же.
Как сдать: В конце появится код работы и кнопка «Сдать работу»: впишешь код ученика, кнопка сама откроет форму с уже вписанным кодом. Переписывать код руками не надо — на этом чаще всего и ошибаются.
Не успел на уроке: Открой эту же страницу дома и пройди целиком: вариант будет другой, а сдаётся всё так же — одним кодом.

Вопросы темы

наработано на—

Подсказка: LZW и сжатие с потерями

Словарное сжатие: алгоритм LZW

Идея: повторяющиеся фразы заменяются номерами из словаря. Словарь не передаётся — кодер и декодер строят его одинаково по ходу работы. В начале в словаре только отдельные символы алфавита.

взять с текущего места самую длинную фразу, которая уже есть в словаре;
выдать её код;
занести в словарь новую фразу: эта фраза + следующий символ;
продолжить с символа, на котором остановились.

Пример, словарь А = 1, Б = 2, сообщение АБАБААБ:

фраза	код	в словарь
А	1	3 = АБ
Б	2	4 = БА
АБ	3	5 = АБА
А	1	6 = АА
АБ	3	—

Выход 1 2 3 1 3: пять кодов вместо семи символов. Каждый код, кроме последнего, добавляет в словарь одну фразу.

Декодирование LZW

Читать коды по одному и выписывать фразы. После каждой фразы, начиная со второй, добавлять в словарь предыдущую фразу + первую букву текущей — получится тот же словарь, что был у кодера.

Коду из b бит хватает на 2^b фраз: словарь из N фраз требует кодов длиной ⌈log₂N⌉ бит.

Сжатие с потерями

Без потерь (RLE, Хаффман, LZW, ZIP, PNG, FLAC) данные восстанавливаются бит в бит. С потерями (JPEG, MP3, AAC, MPEG-4) отбрасывается то, что человек почти не замечает; назад это не вернуть. Годится для фото, звука и видео, но не для текста и программ.

глубина цвета: i бит на пиксель — 2ⁱ цветов; объём = ширина · высота · i. Уменьшили глубину — потеряли оттенки;
JPEG: яркость хранится для каждого пикселя, цветность — одна на квадрат 2 × 2; изображение делится на блоки 8 × 8; коэффициенты блока квантуются — делятся на шаг и округляются (здесь и теряется информация), затем сжимаются без потерь;
MP3: отбрасываются звуки, которые ухо не различает (тихие рядом с громкими). Размер задаёт битрейт: объём = битрейт · время, 128 Кбит/с = 16 Кбайт/с.

Материалы подготовлены с использованием технологий искусственного интеллекта.