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

Question

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

Answer 1

Существует довольно стандартная реализация кодирования Хаффмана в Basic Compression Library (BCL) , включая рекурсивную функцию, которая записывает дерево в файл. Посмотрите на Хаффмана. Он просто записывает листья по порядку, чтобы декодер мог восстановить то же дерево.

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

Answer 2

Прежде всего, вы рассматривали возможность использования стандартного потока сжатия (например, GZipStream в .net)?

О том, как / где записывать ваши данные, вы можете манипулировать позицией Streams с помощью Seek (даже таким образом резервировать место). Если вы знаете размер дерева заранее, вы можете начать писать после этой позиции. Но вы можете расположить дерево кодирования после фактических данных и просто убедиться, что знаете, с чего оно начинается. Т.е. зарезервируйте немного места спереди, запишите сжатые данные, запишите положение, напишите дерево, перейдите вперед и выведите положение.

Answer 3

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

Answer 4

Предполагая, что вы сжимаете 8-битные символы (то есть байты), а алгоритм неадаптивный, самый простой способ - хранить не дерево, а распределение значений. Например, сохраняя, как часто вы находите байт 0, как часто байт 1, ..., как часто байт 255. Затем при чтении файла вы можете заново собрать дерево. Это простейшее решение, но оно требует наибольшего пространства для хранения (например, для покрытия больших файлов, вам потребуется 4 байта на значение, то есть 1 КБ).

Вы могли бы оптимизировать это, не сохраняя точно, как часто каждый байт был найден в файле, а вместо этого нормализуя значения до 0..255 (0 = найдено меньше, ...), в этом случае вы бы нужно всего лишь сохранить 256 байтов. Повторная сборка дерева на основе этих значений приведет к тому же дереву. (Это не будет работать, как указано Эдмундом и в вопросе 759707 - см. Дополнительные ссылки и ответы на ваш вопрос)

P.S .: И, как сказал Хенк, использование seek () позволяет вам оставить место в начале файла, чтобы сохранить значения в более позднем.

Answer 5

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

например. для этого дерева:

    /\
   /\ A
  B /\
   C  D

Вы можете сохранить 001 [B] 01 [C] 1 [D] 1 [A]

(Оказывается, это именно то, что происходит в примере huffman.c, опубликованном ранее, но не так, как это было описано выше).

Answer 6

Наиболее наивным решением было бы проанализировать дерево сжатия в предварительном порядке и записать 256 значений в заголовок вашего файла.

Answer 7

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

Answer 8

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

Answer 9

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

Харисанкар Кришна свами