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

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

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

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

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

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

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

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

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

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

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

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

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

    /\
   /\ A
  B /\
   C  D

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

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

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

Харисанкар Кришна болван

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