Префиксные коды и алгоритм Хаффмана: Математика сжатия данных
Цифровая вселенная ежеминутно генерирует эксабайты данных. Хранение и передача таких объемов немыслимы без алгоритмов сжатия. Теоретический предел сжатия информации был описан Клодом Шенноном в его концепции информационной энтропии, но именно дискретная математика предоставила практические инструменты для достижения этого предела. Одним из величайших достижений в этой области является Алгоритм Хаффмана, создающий оптимальные префиксные коды.
В стандартной кодировке, такой как ASCII, каждый символ (буква) кодируется фиксированным количеством бит (обычно 8 бит). Это крайне неэффективно. Буква «О» встречается в русском языке гораздо чаще, чем буква «Ф». Логично предположить: если частые символы кодировать короткими последовательностями бит, а редкие — длинными (коды переменной длины), то общий объем файла существенно уменьшится. Именно на этом принципе построено статистическое сжатие.
Однако при использовании кодов переменной длины возникает проблема раскодирования: если «0» — это буква А, а «01» — буква Б, то как прочитать последовательность «01»? Это «А» и еще что-то, или это «Б»? Чтобы избежать этой неоднозначности, коды должны удовлетворять условию Фано (префиксному свойству): никакое кодовое слово не должно совпадать с началом (префиксом) другого кодового слова.
В 1952 году Дэвид Хаффман разработал жадный алгоритм для построения минимально избыточных префиксных кодов на основе частот символов в тексте. Алгоритм Хаффмана элегантен и строит бинарное дерево снизу вверх:
- Каждый уникальный символ текста помещается в отдельный узел-лист, а его «весом» становится частота его появления в файле.
- Алгоритм находит два узла с наименьшим весом и объединяет их в новый родительский узел, вес которого равен сумме весов потомков.
- Этот процесс повторяется, пока все узлы не будут объединены в одно большое корневое дерево.
- Наконец, каждому левому ребру дерева присваивается бит «0», а правому — «1». Путь от корня до листа-символа формирует его уникальный префиксный код.
Доказано математически, что дерево Хаффмана генерирует самый оптимальный код среди всех возможных посимвольных кодировок для заданного набора частот. Идеи Хаффмана не устарели до сих пор. Хотя сегодня существуют и более сложные методы (арифметическое кодирование), код Хаффмана остается обязательной, финальной стадией в современных алгоритмах сжатия: он интегрирован в алгоритм Deflate, который является "сердцем" форматов ZIP, GZIP, PNG-изображений и даже протоколов сжатия веб-трафика.
