Сжатие данных и код Хаффмана
💻 Информатика · 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) заменяют повторяющиеся фрагменты ссылками на ранее встреченные. Сжатие с потерями для звука и фото отбрасывает детали, незаметные человеку, и потому даёт гораздо более сильное уменьшение объёма.
Частые ошибки. Нарушение условия Фано лишает гарантии немедленного декодирования слева направо, но само по себе не доказывает неоднозначность кода. Попытка применить сжатие без потерь там, где приемлемы потери (звук), теряя выигрыш. Забывают, что уже сжатые данные почти не сжимаются повторно.
Проверка условия Фано и декодирование
Прямое условие Фано: ни одно кодовое слово не является началом другого. Оно достаточно для однозначного чтения потока слева направо без разделителей. Проверяют именно пары кодов, а не только различие их длин.
Оригинальный код и сообщение
| Символ | Код |
|---|---|
| К | 00 |
| Л | 01 |
| М | 10 |
| Н | 110 |
| О | 111 |
Здесь слова 00,01,10 заканчиваются до ветвей 110 и 111 и не служат их началами. Поток 011111000 читаем так: 01 | 111 | 10 | 00, то есть ЛОМК. Код «ЛОМК» занимает 2 + 3 + 2 + 2 = 9 бит. Служебная таблица кодов в этот подсчёт не включена.
Как выбрать новый код
Если уже заняты 00 и 1, код 0 не подходит: он начало 00. Код 10 тоже не подходит: начинается с уже занятого 1. Код 01 подходит, потому что ни он не начало занятых кодов, ни они не его начало. После выбора проверьте оба направления сравнения.
Когда условие нарушено
Для А → 0, Б → 01, В → 1 поток 01 имеет два чтения: Б или АВ. Это конкретное доказательство неоднозначности. Но само нарушение префиксного условия ещё не доказывает неоднозначность любого кода: условие Фано достаточно, а не необходимо. Например, А → 0, Б → 01 не префиксный код, однако чтение целого корректного сообщения определяется однозначно: каждая 1 относится к стоящему перед ней 0, остальные нули обозначают А.
Обратное условие Фано запрещает кодовым словам быть окончаниями друг друга и позволяет аналогичное чтение справа налево. Для задачи, в которой прямо требуется префиксный код, заменять проверку прямого условия обратным нельзя.
Справочные материалы: Зачем сжимать данные — исходная тема. Связанные уроки: Что такое логические операции, Алгоритмы и их эффективность.
Кратко о главном
- Сжатие уменьшает объём данных; бывает без потерь и с потерями.
- Частым символам выгодно давать короткие коды.
- Условие Фано: ни один код не начало другого; это достаточное условие однозначного декодирования.
- Алгоритм Хаффмана строит оптимальный префиксный код через дерево.