| Символ | Количество | Код | Бит | Всего бит |
|---|
Конструктор кода Хаффмана
Почему частая буква вроде о должна занимать столько же битов, сколько редкая вроде ф? Кодирование Хаффмана даёт частым символам короткие коды, а редким — длинные, и делает это наилучшим возможным образом. Введите текст или выберите пример и стройте его дерево Хаффмана шаг за шагом: два самых лёгких дерева снова и снова объединяются под новым узлом, пока не останется одно дерево. Тогда каждый путь от вершины складывается в код, и вы можете проследить каждый символ в закодированных битах. Введите текст или выберите пример. Каждый символ начинает как лист со своим числом вхождений. Пройдите построение по шагам: на каждом шаге два самых лёгких дерева объединяются под новым узлом с их суммой, пока не останется одно дерево. Затем путь от вершины дерева к листу даёт его код: 0 — влево, 1 — вправо. Нажмите на лист, строку или фрагмент битов, чтобы проследить за одним символом, и сравните итог с кодом фиксированной длины и с энтропией.
Как это работает
- Введите или вставьте текст либо выберите готовый пример — скажем, ABRACADABRA или MISSISSIPPI RIVER.
- Проходите построение кнопкой «Следующий шаг» или нажмите «Пуск»: на каждом шаге два самых лёгких дерева объединяются под узлом с их суммой.
- Когда дерево построено, нажмите на лист, строку таблицы или фрагмент битов, чтобы проследить за одним символом, и сравните итоги на плашках.
Как строится дерево
Подсчитайте, сколько раз встречается каждый символ, и сделайте из каждого дерево из одного листа с весом, равным числу вхождений. Затем повторяйте один простой шаг: возьмите два дерева с наименьшими весами и подвесьте их под новый узел, вес которого равен их сумме. Каждый шаг уменьшает число деревьев на одно, поэтому для n символов после n − 1 шагов остаётся одно дерево. Редкие символы объединяются первыми и оказываются глубоко внизу; частые объединяются поздно и находятся близко к вершине.
Чтение кодов
Спускайтесь от вершины: шаг влево добавляет 0, шаг вправо — 1. Путь к листу — это код его символа. Поскольку символы находятся только в листьях, ни один код не является началом другого, поэтому строку битов можно декодировать без всяких разделителей: следуйте по битам вниз по дереву, а дойдя до листа, запишите его символ и начните снова с вершины. Для ABRACADABRA коду Хаффмана нужно 23 бита против 33 для кода фиксированной длины по 3 бита на букву.
Часто задаваемые вопросы
Почему код Хаффмана — наилучший из возможных?
Среди всех кодов, которые дают каждому символу собственную строку из целых битов, ни у одного нет меньшей суммарной длины при заданных частотах. Доказательство повторяет построение: в оптимальном коде два самых редких символа всегда можно сделать листьями-братьями на самом глубоком уровне, а их объединение оставляет меньшую задачу того же вида. Общее число битов равно сумме весов всех внутренних узлов дерева.
Что такое префиксный код?
Код, в котором ни одно кодовое слово не является началом другого, например 0, 10, 110 и 111. Это свойство позволяет декодеру читать поток битов без разделителей, потому что он всегда знает, где кончается кодовое слово. Любой код Хаффмана является префиксным: символы находятся только в листьях дерева.
Однозначно ли дерево Хаффмана?
Не совсем: когда у двух деревьев одинаковый вес, первым можно взять любое из них, а левую и правую ветви можно поменять местами. Разный выбор даёт разные коды, но всегда одно и то же общее число битов. Конструктор всегда разрешает такие ничьи одинаково, поэтому один и тот же текст всегда даёт одно и то же дерево.
Насколько близко Хаффман подходит к энтропии?
Средняя длина кода не меньше энтропии и превышает её меньше чем на один бит. Она равна энтропии, когда каждая вероятность — степень одной второй, как в примере с частотами, убывающими вдвое. Арифметическое кодирование и современные интервальные кодеры обходят ограничение целым числом битов и подходят ещё ближе.
Отправляется ли мой текст куда-нибудь?
Нет. Дерево и коды вычисляются в вашем браузере, а ваш текст остаётся в локальном хранилище этого браузера.
Готовы попробовать?
Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.
Перейти в редактор