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

Question

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

Answer 1

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

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

Answer 2

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

Answer 3

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

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

Answer 4

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

Answer 5

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

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

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

Answer 6

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

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

/\ 
    /\ A 
    B /\ 
    C D 

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

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

Answer 7

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

Answer 8

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

Harisankar Krishna swamy

Answer 9

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