Алгоритмы сжатия данных: Опиши простыми словами, как работает код Хаффмана (Squeeze) и где мы сталкиваемся с ним в повседневной жизни?
Код Хаффмана — это один из самых элегантных алгоритмов сжатия данных без потерь. Его придумал студент Массачусетского технологического института Дэвид Хаффман ещё в 1952 году, и с тех пор он не теряет актуальности.
## Главная идея: частые символы — короткие коды
Представьте, что вы пишете азбукой Морзе. Буква «Е» — самая частая в русском языке — обозначается одной точкой, а редкая «Ъ» — длинной последовательностью. Хаффман сделал то же самое, но для компьютерных данных.
Обычно каждый символ занимает 8 бит (один байт). Код Хаффмана говорит: зачем тратить 8 бит на букву «а», если она встречается в тексте каждые 5 символов? Дадим ей код из 2–3 бит, а редкой букве «щ» — код из 10–12 бит. В итоге суммарный объём данных уменьшается.
## Как строится дерево Хаффмана: пошагово
1. **Подсчёт частот.** Алгоритм сканирует весь текст и считает, сколько раз встречается каждый символ.
2. **Создание очереди приоритетов.** Каждый символ становится отдельным «листом» с весом, равным его частоте.
3. **Построение дерева.** Берём два символа с наименьшей частотой, объединяем их в один узел (их частоты складываются). Повторяем, пока не останется один корневой узел.
4. **Назначение кодов.** Проходим по дереву: каждый левый переход — это «0», правый — «1». Путь от корня до символа и есть его код.
В результате частые символы оказываются ближе к корню (короткий путь = короткий код), а редкие — глубоко в дереве.
## Пример на пальцах
Возьмём слово «АБРАКАДАБРА». Считаем частоты: А — 5, Б — 2, Р — 2, К — 1, Д — 1. Строим дерево: К и Д объединяются первыми (суммарный вес 2), затем к ним присоединяются Б и Р, и наконец А. В итоге А получает код «0» (1 бит), а остальные — коды из 3–4 бит. Исходное слово из 11 символов по 8 бит = 88 бит. После сжатия — около 25–30 бит. Экономия почти в 3 раза!
## Где мы встречаем код Хаффмана в жизни
— **ZIP и GZIP архивы.** Когда вы упаковываете файлы в архив на Windows или Linux, внутри работает Хаффман (в составе алгоритма DEFLATE).
— **JPEG изображения.** Финальный этап сжатия JPEG использует именно код Хаффмана для кодирования коэффициентов.
— **MP3 аудио.** Часть алгоритма сжатия звука также опирается на принципы Хаффмана.
— **PDF документы.** Внутри PDF-файлов данные часто сжаты с помощью DEFLATE.
— **HTTP-сжатие.** Когда браузер загружает сайт, сервер может отправлять страницы в GZIP — и снова Хаффман.
— **Форматы PNG.** Lossless-сжатие изображений PNG использует DEFLATE.
## Ограничения алгоритма
Код Хаффмана отлично работает с текстами и данными, где символы повторяются. Но если все символы встречаются одинаково часто, сжатие будет минимальным или вовсе нулевым. Именно поэтому в современных архиваторах Хаффман используется в связке с другими алгоритмами (например, LZ77), которые сначала находят повторяющиеся фрагменты, а уже потом Хаффман кодирует результат.