Поскольку вам уже нужно реализовать код для обработки побитового слоя поверх вашего организованного байта потока / файла, вот мое предложение.
Не храните фактические частоты, они не нужны для декодирования. Вам, однако, нужно фактическое дерево.
Так для каждого узла, начиная с корня:
- Если конечный узел: вывод 1-бит + N-битный символ / байт
- Если не конечный узел, вывести 0-битный. Затем закодируйте оба дочерних узла (сначала слева, затем справа) одинаково
Чтобы прочитать, сделайте это:
- Читать бит. Если 1, то читать N-битный символ / байт, вернуть вокруг него новый узел без дочерних элементов
- Если бит равен 0, декодировать левый и правый дочерние узлы одинаково, и возвращать вокруг них новый узел с этими дочерними элементами, но без значения
Конечный узел - это, по сути, любой узел, у которого нет дочерних элементов.
При таком подходе вы можете рассчитать точный размер вашей продукции перед ее записью, чтобы выяснить, достаточно ли усиления, чтобы оправдать усилия. Это предполагает, что у вас есть словарь пар ключ / значение, который содержит частоту каждого символа, где частота - это фактическое количество вхождений.
Псевдокод для расчета:
Tree-size = 10 * NUMBER_OF_CHARACTERS - 1
Encoded-size = Sum(for each char,freq in table: freq * len(PATH(char)))
При расчете размера дерева учитываются листовые и неконечные узлы, а встроенного узла на один меньше, чем символов.
SIZE_OF_ONE_CHARACTER будет числом бит, и эти два дадут вам общее количество бит, которое мой подход к дереву + кодированные данные будет занимать.
PATH (c) - это функция / таблица, которая выдала бы битовый путь от корня до этого символа в дереве.
Вот псевдокод для поиска на 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);
}
}
Пример (упрощенный, использовать свойства и т. Д.) Реализация узла:
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
Частота:
Каждый символ составляет всего 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 символов без кодировки, вы сэкономите 8 байтов.
Окончательный вывод, включая начальное дерево, выглядит следующим образом. Каждый символ в потоке (A-E) кодируется как 8 битов, тогда как 0 и 1 - это просто один бит. Пространство в потоке просто отделяет дерево от закодированных данных и не занимает места в конечном выводе.
001A1C01E01B1D 0000000000001100101010101011111111010101010
Для конкретного примера, который у вас есть в комментариях, AABCDEF, вы получите это:
Ввод: AABCDEF
Частота:
- A: 2
- B: 1
- С: 1
- D: 1
- E: 1
- F: 1
Дерево:
7
-------------
| 4
| ---------
3 2 2
----- ----- -----
A B C D E F
2 1 1 1 1 1
Дорожка:
- A: 00
- B: 01
- С: 100
- D: 101
- E: 110
- F: 111
Дерево: 001A1B001C1D01E1F = 59 бит
Данные: 000001100101110111 = 18 бит
Сумма: 59 + 18 = 77 бит = 10 байтов
Так как оригинал состоял из 7 символов по 8 бит = 56, у вас будет слишком много служебных данных для таких маленьких фрагментов данных.