Алгоритм преобразования дерева сжатия Хаффмана

Question

Я пытаюсь перепроектировать алгоритм сжатия текста, и я застрял в одном месте уже около месяца. В общем, here's Код декодера в C. Он отлично работает, но я до сих пор не понимаю, как работает схема сжатия. Проблема заключается в функции GetNextChararacter.

Я не понимаю этот формат битрейта итерации. Это похоже на двоичное дерево хаффмана, сериализованное странным образом. Таким образом, битовый поток итерации похож на дерево рекурсии, а алгоритм выполняет поиск, когда текущий узел проходит через все листы и выводит список листьев. После этого исходный битовый поток пропускает несколько бит в iterationBitStream. И если iterBit в текущей позиции установлен, мы пересекаем оставшуюся часть итерационного потока и добавляем результат к предыдущему смещению. И так далее, пока мы не достигли листа в итерационном смещении. Общее количество достигнутых листов - это смещение в списке символов для символа декодирования.

Так что это первый раз, когда я вижу, что дерево используется для хранения всего количества листьев в нем. С этой схемой сжатие выглядит сложнее. В то же время, я чувствую, код делает что-то очень основное, но мое понимание алгоритма просто неверно. Может ли кто-нибудь сказать мне, есть ли другое, более логичное объяснение этого алгоритма или, может быть, это просто описано где-то еще?

Answer 1

Спасибо всем, кто был вовлечен. Я понял это, как только я построил дерево и попытался залезть в него руками. В общем случае битовый поток итерации представляет собой двоичное дерево, сериализованное in pre-order traversal. Похоже, трудно распознать обход дерева в коде ассемблера. Исходный поток - это простой путь в этом дереве. Общая схема сжатия - всего лишь Хаффман, с отдельным деревом для каждого персонажа. Следующий символ текста декодируется на основе предыдущего дерева символов.