Восстановить дерево Хаффмана по столу Хаффмана
Я написал программу для кодирования статьи в код Хаффмана и вывода таблицы кодов.
Н: 000 д: 1011 е: 100 л: 11 О: 01 г: 1 010 ш: 001 Всего битов: 27 Кодированный код: 000100111101001011010111011
и я хочу написать программу, которая принимает файл в качестве входных данных и декодирует его.
Но я понятия не имею, как его восстановить.
У меня вопрос, как свергнуть дерево Хаффмана?
Решение
Вам не нужно перестраивать дерево Хаффмана, если код был построен каноническим образом, что делает более короткие коды численно меньшими, чем более длинные коды. Есть много способов произвольно присвоить 0 и 1 каждой ветви двоичного дерева Хаффмана, и все они приводят к одинаковой оптимальности кода. Выбор одного из множества вариантов дает преимущества при декодировании и передаче кода.
Единственная информация, необходимая из алгоритма Хаффмана, это длины кода, то есть количество битов для каждого символа. Таким образом, вы можете создать канонический код Хаффмана, продвигаясь от более коротких кодов к более длинным кодам и сортируя символы в лексическом порядке по любой заданной длине кода (например, сортируйте все коды длины 3 в порядке H, e, w). Смысл сортировки в пределах длины кода заключается в том, чтобы уменьшить объем данных, отправляемых получателю, чтобы восстановить код.
Затем вы получите этот альтернативный код:
l:00
o:01
H:100
e:101
w:110
d:1110
r:1111
Теперь декодирование может быть выполнено с помощью двух простых таблиц, одна из которых содержит только эти символы по порядку, то есть «loHewdr», и значения кода, при которых вы переходите к следующей длине кода. Шаги 0000 от одного до двух битов, 1000 до трех бит, 1110 до четырех бит. Вы читаете достаточное количество битов для самого длинного кода (добавляйте нули, если необходимо, в конце, но не используйте их в качестве начала кода на следующем шаге). Затем, если значение меньше, чем значение начала следующей длины кода, используйте это значение в качестве индекса в таблице, учитывая текущее количество битов в коде. В противном случае добавьте число значений до этого следующего значения в индекс и проверьте следующий шаг. Вычисление количества пропущенных значений требует также отслеживания количества битов в коде на текущем шаге.
Как только вы расшифруете символ, вы узнаете, сколько это было битов. Удалите эти биты из потока и повторите.
Этот подход также имеет то преимущество, что является самым быстрым для самых коротких кодов, которые являются наиболее распространенными. В результате скорость декодирования очень хорошая. (Существуют и другие табличные методы, которые работают быстрее, но они намного сложнее.)
Другие решения
У меня вопрос, как свергнуть дерево Хаффмана?
Это будет двоичное дерево. Создайте корневой узел и поместите все буквы, чьи коды начинаются с 0 в левое поддерево, и те, которые начинаются с 1 в правильное поддерево. Промойте и повторите (рекурсивно), удаляя первую цифру каждого кода. Как только у вас закончатся цифры в каком-либо конкретном коде, создайте листовой узел для соответствующей буквы.