Временная сложность
Лучший: O(n log n)
Средний: O(n log n)
Худший: O(n log n)
Кодирование Хаффмана — это жадный алгоритм сжатия данных без потерь. Он назначает более короткие двоичные коды часто встречающимся символам и более длинные — редким, уменьшая общее количество битов, необходимых для представления данных.
Как работает алгоритм:
1. Подсчитать, сколько раз встречается каждый символ
2. Создать листовой узел для каждого символа и поместить их в очередь с минимальным приоритетом
3. Последовательно извлекать два узла с наименьшей частотой и объединять их под новым родительским узлом, частота которого равна сумме их частот
4. Когда останется один узел, использовать его в качестве корня дерева
5. Назначить коды, обходя дерево: влево = 0, вправо = 1
Почему это работает:
Ни один код не является префиксом другого, поэтому закодированный поток битов можно однозначно декодировать. Жадное объединение гарантирует оптимальный префиксный код для заданного распределения частот.
Временная сложность:
Лучшая: O(n log n)
Средняя: O(n log n)
Худшая: O(n log n)
Пространственная сложность: O(n)
Свойства:
- Сжатие без потерь: исходные данные восстанавливаются в точности
- Оптимален среди префиксных кодов для известного распределения частот
- Используется в DEFLATE (ZIP, gzip, PNG), JPEG и MP3
Алгоритм был изобретён Дэвидом А. Хаффманом в 1952 году, когда он учился в Массачусетском технологическом институте (MIT). Он до сих пор остаётся одной из основ современных методов сжатия данных.
Похожие алгоритмы
Частые вопросы
- Что такое Кодирование Хаффмана?
- Кодирование Хаффмана — это жадный алгоритм сжатия данных без потерь. Он назначает более короткие двоичные коды часто встречающимся символам и более длинные — редким, уменьшая общее количество битов, необходимых для представления данных.
- Какова сложность Кодирование Хаффмана?
- Время (среднее): O(n log n) · Память: O(n)
- Для кого предназначена визуализация Кодирование Хаффмана?
- Визуализация Кодирование Хаффмана рассчитана на продвинутый уровень в категории «Сжатие данных». Полезна для студентов, подготовки к собеседованиям и практического изучения.
- Какие алгоритмы связаны с Кодирование Хаффмана?
- В той же категории (Сжатие данных) вы можете изучить: Run-Length Encoding, LZ77, LZW. Каждый из них имеет интерактивную визуализацию.