Эффективный способ хранения дерева Хаффмана

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

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

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

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

Ответ 1

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

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

Итак, для каждого node, начиная с корня:

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

Чтобы прочитать, сделайте следующее:

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

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

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

Псевдокод для вычисления:

Tree-size = 10 * NUMBER_OF_CHARACTERS - 1
Encoded-size = Sum(for each char,freq in table: freq * len(PATH(char)))

В результате вычисления размера дерева учитываются листовые и нелистовые узлы, а также меньше встроенных node, чем символы.

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

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

Здесь псевдо-код для просмотра С#, который предполагает один символ, представляет собой просто простой байт.

void EncodeNode(Node node, BitWriter writer)
{
    if (node.IsLeafNode)
    {
        writer.WriteBit(1);
        writer.WriteByte(node.Value);
    }
    else
    {
        writer.WriteBit(0);
        EncodeNode(node.LeftChild, writer);
        EncodeNode(node.Right, writer);
    }
}

Чтобы прочитать его еще:

Node ReadNode(BitReader reader)
{
    if (reader.ReadBit() == 1)
    {
        return new Node(reader.ReadByte(), null, null);
    }
    else
    {
        Node leftChild = ReadNode(reader);
        Node rightChild = ReadNode(reader);
        return new Node(0, leftChild, rightChild);
    }
}

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

public class Node
{
    public Byte Value;
    public Node LeftChild;
    public Node RightChild;

    public Node(Byte value, Node leftChild, Node rightChild)
    {
        Value = value;
        LeftChild = leftChild;
        RightChild = rightChild;
    }

    public Boolean IsLeafNode
    {
        get
        {
            return LeftChild == null;
        }
    }
}

Здесь образец выводится из конкретного примера.

Вход: AAAAAABCCCCCCDDEEEEE

Частоты:

A: 6
B: 1
C: 6
D: 2
E: 5

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

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

      20
  ----------
  |        8
  |     -------
 12     |     3
-----   |   -----
A   C   E   B   D
6   6   5   1   2

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

A: 00
B: 110
C: 01
D: 111
E: 10

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

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 незашифрованных 20 символов, вы сохраните 8 байтов.

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

001A1C01E01B1D 0000000000001100101010101011111111010101010

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

Вход: AABCDEF

Частоты:

A: 2
B: 1
C: 1
D: 1
E: 1
F: 1

Дерево:

        7
  -------------
  |           4
  |       ---------
  3       2       2
-----   -----   -----
A   B   C   D   E   F
2   1   1   1   1   1

Paths:

A: 00
B: 01
C: 100
D: 101
E: 110
F: 111

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

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

Ответ 2

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

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

A: 00
B: 110
C: 01
D: 111
E: 10

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

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

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

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

RFC для DEFLATE не так уж плох, если вы уже знакомы с кодировкой huffman: http://www.ietf.org/rfc/rfc1951.txt

Ответ 3

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

e.g. the shape for this tree

0 - 0 - 1 (A)
|    \- 1 (E)
  \
    0 - 1 (C)
     \- 0 - 1 (B)
         \- 1 (D)

would be 001101011

Следуйте за этим битами для символов с одинаковой глубиной первого порядка AECBD (при чтении вы будете знать, сколько символов ожидать от формы дерева). Затем выведите коды для сообщения. Затем у вас есть длинная серия бит, которую вы можете разделить на символы для вывода.

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

Ответ 4

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

ОБНОВЛЕНИЕ. Как указано j_random_hacker в комментарии, вы фактически не можете этого сделать: вам сами нужны значения частоты. Они объединяются и "пузырятся" вверх, когда вы строите дерево. Эта страница описывает способ построения дерева из таблицы частот. В качестве бонуса он также сохраняет этот ответ от удаления, указав способ сохранения дерева:

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

Ответ 5

Лучший подход

Дерево:

           7
     -------------
     |           4
     |       ---------
     3       2       2
   -----   -----   -----
   A   B   C   D   E   F
   2   1   1   1   1   1 : frequencies
   2   2   3   3   3   3 : tree depth (encoding bits)

Теперь просто получим эту таблицу:

   depth number of codes
   ----- ---------------
     2   2 [A B]
     3   4 [C D E F]

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

   depth number of codes
   ----- ---------------
     2   2 [00x 01x]
     3   4 [100 101 110 111]

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

    first pattern depth first index
    ------------- ----- -----------
    000           2     0
    100           3     2

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

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

    first pattern (depth) first index
    ------------- ------- -----------
    (000)          (1)    (0)
     000           (2)     0
     100           (3)     2
     000           (4)     6
     000           (5)     6
     ...           ...     ...
     000           (32)    6

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

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

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