Как хранить дерево хаффмана

Обновлено: 18.09.2024

Что является лучшим способом обезвоживания дерева Хаффмана, под обезвоживанием я подразумеваю заданное дерево Хаффмана и символы на каждом листе, как вы можете эффективно сохранить структуру этого дерева, а затем восстановить его.

возьмите дерево ниже:

Одной из идей может быть сохранение символа на каждом уровне, а затем использование этой информации для восстановления дерева.
В этом случае:
A1B2C2.
Итак, как я могу сначала получить уровни и связать каждый уровень с персонажем.

Решение

Вам почти наверняка не нужно хранить само дерево. Вы могли бы сделать, и это не должно занимать место, которое вы думаете, что оно делает, но это обычно не необходимо.

Если ваши коды Хаффмана канонические, вам нужно хранить только битовые длины для каждого символа, так как это вся информация, необходимая для генерации канонического кодирования. Это относительно небольшое количество бит на символ, поэтому оно должно быть достаточно компактным. Вы также можете дополнительно сжать эту информацию (см. ответ от Аки Суйхконен ).

Естественно, битовая длина кода, по сути, равна глубине дерева, поэтому я думаю, что это примерно то, о чем вы спрашиваете. Важная часть состоит в том, чтобы знать, как построить канонический код, учитывая длины — это не обязательно совпадает с кодами, полученными при обходе дерева. Вы могли бы восстановить дерево из этого, но это не обязательно дерево, с которого вы начали — однако обычно вам не нужно дерево, кроме как для определения длины кода в первую очередь.

Алгоритм генерации канонических кодов довольно прост:

  1. Возьмите все символы, для которых вы хотите сгенерировать коды, отсортированные сначала по длине кода (сначала самое короткое), а затем по самому символу.
  2. Начните с кода нулевой длины.
  3. Если для следующего символа требуется больше битов, чем в настоящее время в коде, добавляйте нули справа (наименее значимые биты) вашего кода до тех пор, пока он не станет нужной длины.
  4. Свяжите код с текущим символом и увеличьте код.
  5. Вернитесь к (3), пока не сгенерируете все символы.

Так что дерево может выглядеть так:

Наивно, что могли бы дать коды:

Однако, если вместо этого вы просто используете длину в битах в качестве входных данных для генерации канонического кода, вы получите следующее:

Это другой код, но, очевидно, он будет выдавать сжатый вывод одинаковой длины. Более того, вам нужно только хранить длины кода, чтобы воспроизвести код.

Так что вам нужно только сохранить последовательность:

Метод должен начинаться с корневого узла и для каждого узла:

  • Если узел является родительским, выведите 0, а затем выведите левых и правых потомков.
  • Если узел является листом, выведите 1, а затем выведите символ

Чтобы восстановить, выполните аналогичную рекурсивную процедуру, но, очевидно, читая данные и выбирая, создавать ли рекурсивно дочерние элементы или читать по символу, в зависимости от ситуации.

Для приведенного выше примера поток битов для дерева будет выглядеть примерно так:

Это 5 битов для дерева, плюс 3 байта для символов, округляя до 4 байтов памяти. Однако он будет быстро расти по мере того, как вы будете добавлять больше символов, в то время как сохранение длин кода не будет.

Другие решения

спецификация zlib объясняет, что для хранения дерева Хаффмана нужны только длины битов каждого символа. Например. если построить дерево для A = 101, B = 111, C = 110, D = 01, он просто посчитает длины битов и восстановит дерево по длинам так, чтобы ключевые слова были последовательными -> A = 101, B = 110, С = 111, D = 01. (или что когда-либо производит следующий код)

Подскажите по реализации сжатия статическим методом Хаффмана. Каким образом оптимально хранить в файле дерево Хаффмана?


Что Вы имеете ввиду, когда пишите "оптимально"? Вам нужен наименьший размер файла или скорость обработки этого файла при загрузке и последующего построения дерева?

Пока мне представляется оптимальным такое решение. Храним в файле информацию о структуре дерева. Для узла записываем левое поддерево, правое поддерево и бит "0", для листа записываем сам символ и бит "1". Начинаем сохранение, очевидно, с записи корня. Такая сериализация дерева позволит восстановить его однозначно.

Делать проход по дереву нужно. Налево идем - ноль ставим, направо - единицу. Так каждый символ код получит свой. Связав же символы да их коды построить Хоффмана таблицу уж не проблема. Хранить оную нужно вместе со строкой закодированной. Когда декодировку делать нужно будет, то обратно дерево построить выйдет только сворачивая в соответствующую для бита сторону.

3 ответа 3

Не обязательно сохранять дерево. Можно просто хранить счетчики для каждого символа в начале файла, а дерево восстанавливать перед декодингом. Eсли хранить счетчики по 8 байт, то потребуется 8B * 256 = 2KiB, что совсем не много.

UPD: если жалко 2KiB, то можно хранить счетчики более компактно. Например, ввести следующий формат для счетчика: префикс + счетчик. Префикс представляет собой трехбитовое целое число, равное размеру счетчика в байтах. Примеры:

  • Счетчик равен 0. Сохраняется в 000 (3 бита).
  • Счеткик равен 222. Сохраняется в 00111011110 (11 бит).
  • Счетчик равен 1024. Cохраняется в 0100000010000000000 (19 бит).

Т.е. размер сохраненных данных для счетчика n будет равен ceil(ceil(log_2(n)) / 8) * 8 + 3 бит.

UPD2: придумал еще один способ, который, как мне кажется, лучше предыдущего. Для начала опишу какую реализацию алгоритма построения дерева я собираюсь использовать:

Если внимательно посмотреть на код, то можно понять, что для восстановления топологии дерева нам достатоточно знать начальную расстановку символов в nodes и insert_index на каждом из шагов. Посчитаем сколько на это надо памяти.

Для хранения изначальной перестановки понадобится 255 байт (первый/последний символ можно не хранить, а получить методом исключения).

Далее замечаем, что число итераций в алгоритме фиксировано (255) и на i-ой итерации (считая с нуля) insert_index лежит в диапазоне [0, 255 - i), поэтому мы можем на поздних итерациях выделять меньше бит на хранения insert_index . А конкретно:

Т.е. для хранeния индексов вставки нужно 127 * 8 + 64 * 7 + 32 * 6 + 16 * 5 + 8 * 4 + 4 * 3 + 2 * 2 = 1784 бит = 223 байт.

Итого получаем 255 + 223 = 478 байт, причем это число не зависит от размера входных данных, в отличии от способа описанного выше.

Я пишу инструмент кодирования/декодирования Хаффмана и ищу эффективный способ хранения дерева Хаффмана, созданного для хранения внутри выходного файла.

В настоящее время есть две разные версии, которые я реализую.

  1. этот считывает весь файл в память символ за символом и строит таблицу частот для всего документа. Это потребует вывода дерева только один раз, и, следовательно, эффективность не так велика, кроме того, если входной файл небольшой.
  2. другой метод, который я использую, - это чтение куска данных размером около 64 килобайт и запуск частотного анализа, создание дерева и его кодирование. Однако в этом случае перед каждым куском мне нужно будет вывести мое дерево частот, чтобы декодер смог заново построить свое дерево и правильно декодировать закодированный файл. Это где эффективность приходит на место, так как я хочу сохранить столько места, сколько вероятный.

в моих поисках до сих пор я не нашел хорошего способа хранения дерева в как можно меньшем пространстве, я надеюсь, что сообщество StackOverflow может помочь мне найти хорошее решение!

поскольку вам уже нужно реализовать код для обработки немного мудрого слоя поверх вашего байтового потока / файла, вот мое предложение.

Не храните фактические частоты, они не нужны для декодирования. Однако вам нужно настоящее дерево.

Итак, для каждого узла, начиная с root:

  1. If leaf-node: вывод 1-бит + N-битный символ / байт
  2. если не leaf-node, выведите 0-бит. Затем кодируйте оба дочерних узла (сначала слева правильно) таким же образом

читать, сделайте следующее:

  1. читать немного. Если 1, то прочитайте N-битный символ / байт, верните новый узел вокруг него без детей
  2. если бит равен 0, декодируйте левый и правый дочерние узлы таким же образом и верните новый узел вокруг них с этими дочерними узлами, но без значения

лист-узел-это в основном любой узел, у которого нет детей.

С помощью этого подхода вы можете рассчитать точный размер вашего вывод перед написанием, чтобы выяснить, достаточно ли прибыли, чтобы оправдать усилия. Предполагается, что у вас есть словарь пар ключ / значение, содержащий частоту каждого символа, где частота-это фактическое количество вхождений.

псевдо-код для расчета:

расчет размера дерева учитывает листовые и нелистовые узлы, и есть один меньше встроенного узла, чем есть символы.

SIZE_OF_ONE_CHARACTER будет количество бит, и эти два дадут вам общее количество бит, которое займет мой подход к дереву + закодированные данные.

PATH (c)-это функция/таблица, которая даст бит-путь от корня до этого символа в дереве.

пример (упрощенный, используйте свойства и т. д.) Узел реализация:

вот пример вывода из конкретного примера.

каждый персонаж имеет всего 8 бит, поэтому размер дерева будет 10 * 5 - 1 = 49 бит.

дерево может выглядеть так:

так пути к каждому символу следующие (0 слева, 1 справа):

Итак, чтобы рассчитать размер вывода:

  • A: 6 вхождений * 2 бита = 12 бит
  • B: 1 вхождение * 3 бита = 3 бита
  • C: 6 вхождений * 2 бита = 12 бит
  • D: 2 вхождения * 3 бита = 6 бит
  • E: 5 вхождений * 2 бита = 10 бит

сумма закодированных байтов 12+3+12+6+10 = 43 бит

добавьте это к 49 битам из дерева, и результат будет 92 бит или 12 байт. Сравните это с 20 * 8 байтами, необходимыми для хранения исходных 20 символов unencoded, вы сохраните 8 байтов.

конечный результат, включая дерево для начала, выглядит следующим образом. Каждый символ в потоке (A-E) кодируется как 8 бит, тогда как 0 и 1-это всего лишь один бит. Пространство в потоке просто отделяет дерево от закодированных данных и не занимает места в конечном выходе.

для конкретного примера, который у вас есть в комментариях, AABCDEF, вы получите следующее:

дерево: 001A1B001C1D01E1F = 59 бит
Данные: 000001100101110111 = 18 бит
Сумма: 59 + 18 = 77 бит = 10 байт

так как оригинал был 7 символов 8 бит = 56, у вас будет слишком много накладных расходов такого малого часть данных.

Если у вас есть достаточный контроль над поколением дерева, вы можете сделать его каноническим деревом (таким же образом сдуется, например), который в основном означает, что вы создаете правила для разрешения любых неясных ситуациях при построении дерева. Затем, как и DEFLATE, все, что вам действительно нужно сохранить, - это длины кодов для каждого символа.

то есть, если у вас было дерево / коды Лассе, упомянутые выше:

тогда вы можете хранить их как: 2, 3, 2, 3, 2

и это на самом деле достаточно информации для регенерации таблицы Хаффмана, предполагая, что вы всегда используете один и тот же набор символов-скажем, ASCII. (Это означает, что вы не можете пропустить буквы-вам придется перечислить длину кода для каждого из них, даже если она равна нулю.)

Если вы также устанавливаете ограничение на длины битов (скажем, 7 бит), вы может хранить каждое из этих чисел, используя короткие двоичные строки. Таким образом, 2,3,2,3,2 становится 010 011 010 011 010-что соответствует 2 байтам.

Если вы хотите получить действительно сумасшедший, вы можете сделать то, что делает DEFLATE, и сделать еще одну таблицу Хаффмана длин этих кодов и сохранить ее длины кода заранее. Тем более, что они добавляют дополнительные коды для "вставки нуля N раз подряд", чтобы сократить вещи дальше.

ветви 0 листья 1. Сначала пересечь глубину дерева, чтобы получить его "форму"

Если вы разделяете его, вы можете проверить, что сохранение дерева для следующего Чак так же эффективен, как просто повторно использовать дерево для предыдущего куска и иметь форму дерева "1" в качестве индикатора, чтобы просто повторно использовать дерево из предыдущего куска.

дерево обычно создается из таблицы частот байтов. Поэтому сохраните эту таблицу или просто сами байты, отсортированные по частоте, и воссоздайте дерево на лету. Это, конечно, предполагает, что вы строите дерево для представления одиночных байтов, а не больших блоков.

обновление: как указал j_random_hacker в комментарии, вы на самом деле не можете этого сделать: вам нужны сами значения частоты. Они объединены и "пузырь" вверх, как вы строите дерево. на этой странице описывает способ построения дерева из таблицы частот. В качестве бонуса он также сохраняет этот ответ от удаления, упомянув способ сохранения дерева:

самый простой способ вывести само дерево Хаффмана-это, начиная с корня, сбросить сначала левую сторону, а затем правую сторону. Для каждого узла выводится 0, для каждого листа выводится 1, за которым следует N битов, представляющих значение.

дерево: Семь ------------- | 4 | --------- 3 2 2 ----- ----- ----- A B C D E F 2 1 1 1 1 1 : частоты 2 2 3 3 3 3 : глубина дерева (кодирования битов)

теперь просто выведите эту таблицу: глубина количество кодов

вам не нужно использовать одно и то же двоичное дерево, просто сохраните вычисленную глубину дерева, т. е. количество кодирование битов. Поэтому просто держите вектор несжатых значений [A B C D E F] упорядоченным по глубине дерева, используйте относительные индексы вместо этого отдельного вектора. Теперь воссоздайте выровненные битовые шаблоны для каждой глубины:

глубина количество кодов

что вы сразу видите, так это то, что только первый битовый шаблон в каждой строке является значительным. Вы получаете следующую таблицу поиска:

этот LUT имеет очень малый размер (даже если ваши коды Huffman могут быть 32-битным, он будет содержать только 32 строки), и на самом деле первый шаблон всегда равен нулю, вы можете полностью игнорировать его при выполнении двоичного поиска шаблонов в нем (здесь нужно будет сравнить только 1 шаблон, чтобы узнать, является ли битовая глубина 2 или 3 и получить первый индекс, при котором связанные данные хранятся в векторе). В нашем примере вам нужно будет выполнить быстрый двоичный поиск входных шаблонов в пространстве поиска не более 31 значения, т. е. максимум 5 целочисленных сравнений. Эти 31 процедуры сравнения можно оптимизировать в 31 коде, чтобы избежать всех циклов и управлять состояниями при просмотре дерева поиска целых двоичных чисел. Вся эта таблица вписывается в небольшую фиксированную длину (LUT просто нуждается в 31 строке atmost для кодов Хаффмана не длиннее 32 бит, а 2 других столбца выше заполнят не более 32 строк).

другими словами, LUT выше требует 31 ints 32-битного размера каждый, 32 байта для хранения значений битовой глубины: но вы можете избежать этого, подразумевая столбец глубины (и первая строка для глубины 1):

таким образом, ваш LUT содержит [000, 100, 000(30times)]. Для поиска в нем вы должны найти позицию, в которой шаблон входных битов находится между двумя шаблонами: он должен быть ниже шаблона в следующей позиции в этом LUT, но все же выше или равен шаблону в текущей позиции (если обе позиции содержат один и тот же шаблон, текущая строка не будет совпадать, входной шаблон подходит ниже). Затем вы разделите и завоюете, и будете использовать 5 тесты не более (для двоичного поиска требуется один код с 5 вложенными уровнями if/then/else, он имеет 32 ветви, достигнутая ветвь указывает непосредственно на битовую глубину, которую не нужно хранить; вы выполняете один непосредственно индексированный поиск во вторую таблицу для возврата первого индекса; вы производите дополнительный конечный индекс в векторе декодированных значений).

как только вы получите позицию в таблице поиска (Поиск в 1-м столбце), у вас сразу же будет номер из битов, которые нужно взять с входа, а затем начать индекс вектора. Разрядность вас могут быть использованы для вывода непосредственно скорректированный индекс, основной bitmasking после вычитания первого индекса.

in summary: никогда не храните связанные двоичные деревья, и вам не нужен никакой цикл для выполнения thelookup, который просто требует 5 вложенных шаблонов сравнения ifs на фиксированных позициях в таблице 31 шаблонов и таблице 31 ints, содержащей начальное смещение в векторе декодированного значения (в первой ветви вложенных тестов if/then/else подразумевается начальное смещение вектора, оно всегда равно нулю; это также Самая частая ветвь, которая будет принята, поскольку она соответствует кратчайшему коду, который для наиболее частых декодированных значений).

Дерево Хаффмана, оптимальное бинарное дерево, дерево с наименьшей взвешенной длиной пути (WPL). Он не имеет точки степени 1 и является строгим двоичным деревом (полное двоичное дерево).

Чтобы понять деревья Хаффмана, нам сначала нужно знать несколько связанных терминов деревьев и понимать, что такое WPL.

  • Путь: ветвь от одного узла к другому в дереве составляет путь между двумя узлами
  • Длина пути: количество веток на пути : Сумма длины пути от корня дерева до каждого узла
  • Взвешенная длина пути дерева: сумма взвешенных путей всех листовых узлов дерева W P L = ∑ k = 1 n w k l k WPL=\sum_^n W P L = ∑ k = 1 n ​ w k ​ l k ​ который w k w_k w k ​ Вес k-го узла
  • Оптимальное бинарное дерево (дерево Хаффмана): наименьшее бинарное дерево с WPL

Примечание: концепция WPL для деревьев очень важна: эта формула напрямую создает применение кодированного сжатия данных Хаффмана.

Алгоритм Хаффмана


Кодирование Хаффмана

Прежде чем говорить о кодировании Хаффмана, давайте сначала разберемся с родственными концепциями кодирования.

Бинарное кодирование равной длины

Для каждого символа в дискретном источнике без памяти, если для представления соответствующего символа используются разные кодовые слова одинаковой длины, это называется кодированием равной длины. Например: A / B / C / D использует кодирование 00/01/10/11 с кодированием равной длины.

Неравная длина двоичного кодирования

В процессе передачи данных нам нужно сжать файл, а затем мы можем использовать кодирование неравной длины.

Кодирование ХаффманаЭто разновидность неравного кодирования, определяющая длину кодирования каждого символа в соответствии с результатом анализа частоты слов.ХаффманЦелью изучения этого вида оптимального дерева является решение задачи оптимизации передачи данных междугородной связи (преимущественно телеграммы).

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

Чтобы решить проблему неоднозначности двоичного кодирования и декодирования неравной длины, нам необходимо ввести концепциюКод префикса

Код префиксаЭто неравное кодирование, оно гарантирует, что кодирование любого символа не является префиксом другого кодирования. Например, A (0), B (10), C (110) и D (1111) представляют собой набор кодов префиксов.

Построение дерева Хаффмана Кодирование Хаффмана

Прежде чем писать конкретный алгоритм, мы всегда должны подумать о носителе алгоритма - как хранятся данные. Ключевой структурой данных алгоритма Хаффмана является дерево Хаффмана, поэтому давайте рассмотрим хранение дерева Хаффмана.

Хранение дерева Хаффмана

Мы используем дочернее родительское представление для хранения дерева Хаффмана

Определите вторичный указатель типа char для хранения кода Хаффмана

Построение дерева Хаффмана


Хаффман дерево строительная мысльИспользовать неконечные узлы двоичного дерева для реализации структуры двоичного дерева (о чем я говорю

Некоторые детали этого кода описаны ниже:

  1. При передаче параметров используйте ссылки для непосредственного изменения переменных вне функции и устранения недостатка функции C, передаваемой по значению и имеющей только одно возвращаемое значение
  2. * w указывает массив символов для кодирования, n обозначает количество символов, а m = 2n-1 указывает количество узлов в дереве Хаффмана. Назначить m + 1 узлов Пробел должен соответствовать метке узла с индексом массива. 0-й элемент массива не используется ( Общее хранилище деревьев ） Возвращаемое значение void *, которое необходимо привести к указателю на HTNode, то есть тип HuffmanTree
  3. HuffmanTree p Он предназначен для прохождения и инициализации динамически распределенных блоков памяти. Указатель HTNode ， int i Предназначен для тиража Вспомогательная переменная

Кодирование Хаффмана

Следующий код основан на кодировании Хаффмана каждого символа в обратном порядке от листа к корню.

Аннотация:

  1. Точно так же пробел n + 1 char * открывается, чтобы соответствовать индексу массива i i-му символу, который должен быть закодирован.
  2. cd - это вспомогательный массив, используемый для кодирования одного символа. Поскольку длина кодирования каждого символа не была известна в начале, cd используется для открытия достаточно большого пространства кодирования n. После завершения кодирования строка кодирования определенной длины копируется в Часы Хаффман ХК в

Наконец, полный код алгоритма кодирования Хаффмана представлен

упражнение

Пример 2 Известно, что система может иметь только 8 символов в коммуникации, и ее распределение вероятностей составляет 0,05, 0,29, 0,07, 0,08, 0,14, 0,23, 0,03, 0,11.Дизайн Хаффмана, кодирование。

Анализ: Сначала установите веса 8 символов как w = , n = 8, затем m = 15, то есть в Ха с 8 листовыми узлами Дерево Хаффмана имеет 15 узлов, затем строится дерево Хаффмана и, наконец, получается код Хаффмана.

Сценарии применения дерева Хаффмана

На самом деле, существует довольно много вариантов использования деревьев Хаффмана, таких как базовый алгоритм балансировки нагрузки Apache в соответствии с политикой запроса весов, алгоритм маршрутизации маршрутизаторов в нашей жизни и реализация деревьев Хаффмана.Хранение сжатия глифа с матричной точкой китайских иероглифовНизкоуровневые алгоритмы оптимизации, такие как быстрый поиск информации и т. Д. Фактически, ядро ​​состоит в том, чтобы построить модель Хаффмана, потому что у цели есть веса, а также длина и расстояние такой информации.

PS: дерево Хаффмана Доказательство оптимальных свойств субструктуры Смотрите этот пост в блоге для деталейАлгоритм кодирования Хаффмана для алгоритма обучения

Читайте также: