Сжатие данных и код Хаффмана
💻 Информатика · 10 класс
Зачем сжимать данные
Сжатие данных — это представление информации меньшим числом бит без потери (или с допустимой потерей) её содержания. Сжатие экономит память и ускоряет передачу по сети. Различают сжатие без потерь (текст, программы — данные восстанавливаются точно) и с потерями (звук, фото — часть информации отбрасывается).
Идея неравномерного кодирования
При обычном (равномерном) кодировании каждый символ занимает одинаковое число бит. Но символы встречаются с разной частотой: в тексте буква «о» гораздо чаще, чем «ф». Логично частым символам дать короткие коды, а редким — длинные. Это неравномерное кодирование, и в среднем оно даёт выигрыш.
Условие Фано
Чтобы неравномерный код можно было однозначно раскодировать, он должен удовлетворять условию Фано (префиксному условию): ни один код не является началом другого кода. Тогда поток бит читается слева направо без разделителей.
| Символ | Частота | Код |
|---|---|---|
| А | высокая | 0 |
| Б | средняя | 10 |
| В | низкая | 110 |
| Г | низкая | 111 |
Ни один из кодов не является началом другого, поэтому запись 010110 читается однозначно: А, Б, В.
Алгоритм Хаффмана
Алгоритм Хаффмана строит оптимальный префиксный код. Шаги: подсчитать частоту каждого символа; выбрать два самых редких и объединить их в один узел с суммарной частотой; повторять, пока не останется один узел — корень дерева. Спускаясь по дереву, левым ветвям дают 0, правым — 1; путь до символа и есть его код.
Результат: чем чаще символ, тем короче его код, и средняя длина записи минимальна среди всех префиксных кодов.
Оценка выигрыша
Пусть в сообщении из 100 символов буква А встречается 60 раз, Б — 25, В — 10, Г — 5. При равномерном коде каждому символу нужно 2 бита, всего 200 бит. При кодах из таблицы выше длина составит 60·1 + 25·2 + 10·3 + 5·3 = 155 бит. Экономия — почти четверть объёма, и достигнута она только за счёт учёта частот, без всякой потери информации.
Другие методы сжатия
Помимо кода Хаффмана, существуют и другие подходы. Метод RLE заменяет цепочки одинаковых символов парой «символ и число повторений» — он хорош для изображений с большими однотонными областями. Словарные методы (семейство LZ) заменяют повторяющиеся фрагменты ссылками на ранее встреченные. Сжатие с потерями для звука и фото отбрасывает детали, незаметные человеку, и потому даёт гораздо более сильное уменьшение объёма.
Частые ошибки. Построение кода, нарушающего условие Фано — тогда раскодировать однозначно нельзя. Попытка применить сжатие без потерь там, где приемлемы потери (звук), теряя выигрыш. Забывают, что уже сжатые данные почти не сжимаются повторно.
Кратко о главном
- Сжатие уменьшает объём данных; бывает без потерь и с потерями.
- Частым символам выгодно давать короткие коды.
- Условие Фано: ни один код не начало другого — нужно для однозначного декодирования.
- Алгоритм Хаффмана строит оптимальный префиксный код через дерево.