Алгоритмы сжатия данных

Слайд 1. Алгоритмы сжатия данных

Как упаковать информацию эффективно и без лишних затрат

Слайд 2. Что такое сжатие данных?

Сжатие (компрессия) — это процесс преобразования информации, при котором уменьшается её объём при сохранении основного содержания.

Главная цель: экономия места на диске и ускорение передачи данных по сети.

В основе любого сжатия лежит поиск и устранение избыточности.

Слайд 3. Два пути: Lossless vs Lossy

Данные восстанавливаются бит в бит. Используется для текстов, программ и баз данных, где важна абсолютная точность.

Часть «лишней» информации удаляется безвозвратно. Применяется для фото, видео и аудио, где человеческий глаз или ухо не заметят подвоха.

Слайд 4. Виды избыточности

Статистическая — одни символы встречаются чаще других.

Структурная — наличие повторяющихся фрагментов или паттернов.

Семантическая — информация, которую можно опустить без потери смысла.

Визуальная/Слуховая — детали, которые не воспринимаются органами чувств.

Слайд 5. Алгоритм RLE (Run-Length Encoding)

Самый простой метод сжатия без потерь. Он заменяет цепочки одинаковых символов на пару «символ + количество повторов».

Пример:

Строка `AAAAABBBCC` превращается в `5A3B2C`.

Эффективен там, где много длинных серий одинаковых данных (например, простые иконки).

Слайд 6. RLE на практике

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

Слайд 7. Алгоритм Хаффмана

Идея: часто встречающиеся символы кодируются короткими битовыми последовательностями, а редкие — длинными.

Это позволяет экономить место за счет частоты использования букв.

Для построения кодов используется бинарное дерево.

Слайд 8. Как строится код Хаффмана?

Подсчитываем частоту появления каждого символа в тексте и сортируем их.

Объединяем два самых редких символа в узел, суммируя их частоты, пока не останется один корень.

Присваиваем ветвям «0» и «1». Путь от корня к символу — это его новый код.

Слайд 9. Алгоритм LZW (Словарное сжатие)

Используется в форматах GIF и ZIP. Алгоритм не просто считает буквы, а ищет повторяющиеся подстроки.

Он строит «словарь» прямо в процессе сжатия. Если фраза встречается второй раз, вместо неё записывается короткий номер (индекс) из словаря.

Чем больше повторов фраз, тем лучше работает LZW.

Слайд 10. Логика работы LZW

Слайд 11. Сжатие с потерями: JPEG

Человеческий глаз лучше видит разницу в яркости, чем в цвете.

JPEG «выбрасывает» мелкие цветовые нюансы, которые мы все равно не заметим.

Степень сжатия можно регулировать: чем меньше файл, тем больше «артефактов» (квадратиков) на фото.

Слайд 12. Этапы сжатия JPEG

Переход от RGB к YCbCr (яркость и цвет отдельно).

Уменьшение разрешения цветовых каналов.

Применение ДКП (дискретного косинусного преобразования) к блокам $8\times 8$ пикселей.

Главный этап потерь: отбрасывание высокочастотных коэффициентов.

Слайд 13. Аудиосжатие (MP3)

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

MP3 просто не записывает те звуки, которые человеческое ухо не способно услышать в данном контексте.

Это позволяет уменьшить размер аудиофайла в 10 раз практически без потери качества.

Слайд 14. Сравнение популярных форматов

Слайд 15. Предел сжатия

Можно ли сжимать файл бесконечно, прогоняя его через архиватор снова и снова?

Нет. У каждого набора данных есть предел — информационная энтропия. Когда избыточность исчезает, файл становится похожим на случайный шум, и дальнейшее сжатие без потерь становится невозможным.

Слайд 16. Математический взгляд

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

Слайд 17. Будущее: Нейросетевое сжатие

Современные ИИ могут «догадываться», как должен выглядеть объект.

Вместо передачи пикселей мы передаем описание сцены, а нейросеть на устройстве пользователя восстанавливает картинку.

Это позволяет достигать невероятного сжатия видео для звонков даже при очень плохом интернете.

Слайд 18. Вопрос для обсуждения

Что для вас важнее при просмотре видео онлайн: идеальная картинка без искажений или отсутствие пауз на загрузку (буферизации)?

Слайд 19. Итоги занятия

Сжатие бывает без потерь (Lossless) и с потерями (Lossy).

RLE эффективно для длинных повторов, Хаффман — для часто встречающихся символов.

Сжатие с потерями использует особенности человеческого восприятия.

Существует математический предел сжатия, выше которого «прыгнуть» нельзя.

Будущее сжатия — за алгоритмами искусственного интеллекта.

Слайд 20. Спасибо за внимание! Время практических заданий.