Коды префиксов
Как вы указали, код префикса - это код, в котором данный код не является префиксом для любого другого заданного кода.
Это очень общее определение. Кодировка Хаффмана - это ограниченная форма префиксного кода.
Обычное использование для кодирования Хаффмана - минимизация (оптимизация) общего количества битов, необходимых для кодирования «сообщения».
«Сообщение» обычно представляет собой последовательность символов, и оно кодируется путем сопоставления каждого вхождения символа с
конкретный префиксный код и запись префиксного кода на его место. Можно использовать любой набор префиксных кодов.
сделать это. Но кодирование Хаффмана приведет к получению кратчайшего сообщения на основе количества битов.
Например, набор символов ASCII можно рассматривать как отображение символов на набор 8-битных префиксных кодов.
Это можно даже считать кодировкой Хаффмана при условии, что закодированное сообщение содержит точно
одинаковое количество каждого возможного символа.
Интересный материал начинается, когда кодируемое сообщение содержит неравные частоты символов. В этот
Во-первых, можно уменьшить общую длину сообщения в битах, используя префиксные коды различной длины. Используйте короткие
префиксные коды для более частых символов и более длинные префиксные коды для менее частых символов.
Из вашего примера есть 8 символов для кодирования. Символы, сопоставленные с префиксными кодами «11» и «10», будут наиболее
частые символы в сообщении. Аналогично, символы, отображаемые на «0111», «0110», «1010» и «0100», будут наименее частыми.
Чем выше частота, тем короче код префикса.
«Уловка» в создании кодирования Хаффмана состоит в том, чтобы создать набор кодов префиксов таким образом, чтобы после отображения
каждый символ в сообщении связан с префиксными кодами, которые сообщение содержит как можно меньше битов.
Я считаю полезным просматривать префиксные коды в виде двоичного дерева, где каждый листовой узел отображается на символ.
Например, двоичное дерево, соответствующее префиксным кодам, приведенным в вашем вопросе (01, 11, 000, 001,
0100, 0101, 0110, 0111) будет:
+-- (11)
+--+
| +-- (10)
|
| +-- (0111)
--+ +--+
| | +-- (0110)
| +--+
| | | +-- (0101)
| | +--+
+--+ +-- (0100)
|
| +-- (001)
+--+
+-- (000)
Чтобы получить значения в скобках, вы просто присваиваете «1», когда следует верхний край, или «0», если нижний
край сопровождается.
Как построить такое дерево?
Начнем со структур данных, представляющих двоичное дерево и список.
Двоичное дерево будет содержать два типа узлов. 1) Конечный узел, представляющий
символ и его частота и 2) внутренний узел, представляющий совокупную частоту
из всех узлов под ним (ему также нужны два указателя, один для левой ветви и один для правой ветви).
Список содержит упорядоченный набор узлов из двоичного дерева. Узлы в списке упорядочены
на основе значения частоты узла, на который они указывают. Узлы с самой низкой частотой встречаются в начале списка
и увеличьте к концу списка. Связанный список указателей на узлы дерева может быть полезным
реализация - но подойдет любая упорядоченная структура списка.
В приведенном ниже алгоритме используются два списка: «справочный» и «рабочий» список. Как узлы
обработанные из «справочного» списка, новые узлы создаются и вставляются в «рабочий» список таким образом, чтобы
«рабочий» список остается упорядоченным по частоте узла.
Используйте эти структуры данных и следующий алгоритм для создания кодировки Хаффмана.
0. Initialize the "reference" list by creating a leaf node for each symbol
then add it into this list such that nodes with the lowest frequency
occur at the front of the list and those with the highest frequency
occur at the back (basically a priority queue).
1. Initialize the "working" list to empty.
2. Repeat until "reference" list contains 1 node
2.1 Set MaxFrequency to the sum of the first 2 node frequencies
2.1 Repeat until "reference" list is empty
If ("reference" list contains 1 node) OR
(sum of the next two nodes frequency > MaxFrequency)
Move remaining nodes to the "working" list
Set "reference" list to empty
Else
Create a new internal node
Connect the first "reference" node to the left child
Connect the second "reference" node to the right child
Set the new node frequency to the sum of the frequencies of the children
Insert the new node into the "working" list
Remove the first and second nodes from the "reference" list
2.2 Copy the "working" list to the "reference" list
2.3 Set the "working" list to empty
В конце этого процесса отдельный элемент «ссылки» будет корнем дерева Хаффмана. Вы можете перечислить
Префикс кодирует, выполняя первый обход дерева по глубине. Запишите '0' для каждой левой ветви
принято и «1» для каждой правой ветви. Код завершен, когда лист встречается. Символ на
лист кодируется только что сгенерированным кодом Хаффмана.
Какая оптимальная кодировка
Интересное вычисление, которое можно выполнить, - это вычисление «битового веса» кодирования префикса. Немного вес
это общее количество бит, необходимое для представления набора префиксных кодов.
Посмотрите на свое оригинальное дерево выше.Вес этого дерева составляет (2 бита * 2) + (4 бита * 5) + (3 бита * 2) = 30 бит.Вы использовали 30 бит для представления 8 значений префикса.Какое минимальное количество битов вы могли бы использовать?Подумайте об этом, поскольку дерево становится неуравновешенным, длина пути к некоторым листьям становится длиннее - это увеличивает вес.Например, наихудший случай для дерева 4-значного префикса:
+-- (1 bit)
--+
| +-- (2 bits)
+--+
| +-- (3 bits)
+--+
+-- (3 bits)
, что дает общий вес (1 бит * 1) + (2 бита * 1) + (3 бита * 2) = 9биты
Балансировать дерево:
+-- (2 bits)
+--+
| +-- (2 bits)
--+
| +-- (2 bits)
+--+
+-- (2 bits)
, что дает общий вес (2 бита * 4) = 8 бит.Обратите внимание, что для сбалансированных деревьев все префиксные коды имеют одинаковое количество битов.
Вес бита дерева - это просто сумма длин пути ко всем листьям.Вы минимизируете вес в битах, минимизируя общую длину пути - и это делается путем балансировки дерева.
Как видите, в минимизации любого заданного префиксного дерева нет особой ценности, вы просто получаетекодирование символов фиксированной длины.Значение приходит, когда вы учитываете битовый вес результирующего закодированного сообщения.Сведение к минимуму приводит к кодированию Хаффмана.
Сколько существует различных кодировок?
Префиксные коды могут быть сгенерированы путем обхода двоичного дерева и выдачи '0' для каждогозатем следовала нижняя ветвь и «1» для каждой верхней ветки, пока не встретился лист.Как в:
+--+ (1)
|
--+
| +-- (01)
+--+
+-- (00)
В качестве альтернативы мы можем «перевернуть» это правило и назначить «1» для каждой нижней ветви и «0» для верхней ветви:
+-- (0)
|
--+
| +-- (10)
+--+
+-- (11)
Этигенерировать два разных набора префиксных кодов.Дополнительные наборы могут быть сгенерированы путем прохождения всех возможных 1/0 назначений ветвям и последующего обхода дерева.Это даст вам 2 ^ n наборов.Но если вы сделаете это, вы обнаружите, что одинаковые префиксные коды могут быть сгенерированы, но в другом порядке.Например, предыдущее дерево даст следующие наборы: {(0, 10, 11), (0, 11, 01), (1, 01, 00), (1, 00, 01)}.Затем переверните дерево:
+-- (??)
+--+
| +-- (??)
--+
|
+-- (?)
, и вы получите: {(11, 10, 0), (10, 11, 0), (01, 00, 1), (00, 01, 1))}.Положите их вместе на 2 ^ 3 = 8 комплектов.Однако если вы хотите, чтобы уникальные наборы не учитывали порядок, есть только 2 набора: {(0, 10, 11), (1, 00, 01)}.Пройдите то же упражнение для сбалансированного дерева, и есть только 1 сет.Все это приводит меня к мысли, что количество уникальных кодировок связано со структурой баланса дерева, используемого для генерации префиксных кодов.К сожалению, у меня нет точной формулы или расчета.На догадке я бы предположил, что число будет 2 ^ (количество различных длин кода - 1).Для сбалансированного дерева это: 2 ^ (1 - 1) = 1;для дерева с двумя разными длинами кода (как в примере выше): 2 ^ (2 - 1) = 2;и для вашего примера: 2 ^ (3 - 1) = 4.