Кодировка Хаффмана - заголовок и EOF

Question

В настоящее время я работаю над реализацией программы, основанной на алгоритме Хаффмана в Java, и я нахожусь на этапе, когда мне нужно вывести закодированное содержимое в файл.Я немного запутался в том, как реализовать заголовок и eof, необходимые для декодирования.Для моего заголовка на данный момент у меня есть все уникальные значения, которые происходят из входного файла и их частота, но в некоторых статьях я видел, как люди делают это с 0 или 1 представляет узлы, а затем частоту (которую я немного озадачил).как это не говорит, что символ).

Кроме того, для EOF, как я понимаю, я кодирую его, как символы, чтобы он читался и декодировался, однако я не уверен, какое значение я могу использовать для него, которое определенно не появится?Я знаю, что ему нужно весить 1, но я не был уверен, как убедиться, что его на самом деле не будет в файле.

Answer 1

Я должен был сделать это один раз для задания, и именно этот подход мы использовали.

Кодирование заголовка было выполнено с использованием 0 и 1 для кодирования структуры дерева (а не частот). «0» обозначает перемещение по дереву, «1» обозначает, что мы находимся в листовом узле. Это привело к своего рода предварительному обходу дерева, однозначно его кодирующего.

Например, дерево, подобное (((ab) c) (de)), будет закодировано как «0001 a 1 b 1 c 01 d 1 e», где a, b, c, d, e - их ASCII-формы.

Вот дерево в графической форме:

     / \
   /\   /\
 /\  c d  e
a  b 

Для EOF мы использовали последние 3 бита в файле, чтобы указать, сколько из последних двух байтов необходимо прочитать. Как только мы прочитали последний байт (поэтому мы работали над вторым последним байтом), мы проверили последние 3 бита: они закодировали, сколько еще битов нужно прочитать, минус 6. Так что 110101xxxxxxx000 означало «чтение 110101 (6 бит) и отказаться от всего остального ". 1101011xxxxxx001 означало «прочитать 1101011 (7 бит) и отбросить остальные» и т. Д.

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

(Что касается EOF, я не читал ваши статьи, поэтому не знаю, работает ли наша идея с вашим подходом.)

Answer 2

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

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

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

Затем существует адаптивное кодирование Хаффмана , которое неДерево вообще не требуется, но сложнее.

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

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