Чтобы оно само занимало как можно меньшее число байт?
(Дерево записывается в начало файла и требуется для разархивации).

Сам я придумал только, что можно хранить вместо дерева сами записи и их длины.
Массив длин занимает 3бита * 256 = 96 байт, массив записей — от 1 до 256 байт, итого 256+96 — как-то многовато...

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

Плз, хелп.

Здравствуйте, ultrator, Вы писали:

U>В каком формате хранить дерево Хаффмана?
U>Чтобы оно само занимало как можно меньшее число байт?
U>...
U>Наверняка есть более лучший "формат", который используется в настоящих архиваторах, но погуглив, я нашел только способ хранить не дерево и не записи а саму таблицу частот (что ещё хуже).

Поизучай, как происходит энтропийное (де)кодирование в JPEG. Можно, например, по книжке Дж. Миано «Форматы и алгоритмы сжатия изображений».

Здравствуйте, ultrator, Вы писали:

U>Чтобы оно само занимало как можно меньшее число байт?

http://www.haskell.org/bz/lzh.7z

appnote.txt метод 6

Здравствуйте, ultrator, Вы писали:

U>Чтобы оно само занимало как можно меньшее число байт?
U>(Дерево записывается в начало файла и требуется для разархивации).

U>Сам я придумал только, что можно хранить вместо дерева сами записи и их длины.
U>Массив длин занимает 3бита * 256 = 96 байт, массив записей — от 1 до 256 байт, итого 256+96 — как-то многовато...

U>Наверняка есть более лучший "формат", который используется в настоящих архиваторах, но погуглив, я нашел только способ хранить не дерево и не записи а саму таблицу частот (что ещё хуже).

U>Плз, хелп.

Когда я писал свой архиватор я хранил дерево как дерево. Т.е. бит 1 что у текущего узла два потомка и нужно сместиться (вызовом рекурсии) на один бит и парсить его значение. бит 0 означает что далее записаны восемь бит закодированного символа.
Итого 2+8 бит на каждый символ, т.е. не более 320 байт на всё дерево.

Здравствуйте, potapov.d, Вы писали:


PD>Когда я писал свой архиватор я хранил дерево как дерево. Т.е. бит 1 что у текущего узла два потомка и нужно сместиться (вызовом рекурсии) на один бит и парсить его значение. бит 0 означает что далее записаны восемь бит закодированного символа.
PD>Итого 2+8 бит на каждый символ, т.е. не более 320 байт на всё дерево.

Ой, не догоняю...
Покажите на примере, плз, если не трудно:

*
/ \
a *
/ \
b c

Что будет в файле?

1[a].. а дальше?

Здравствуйте, ultrator, Вы писали:

U> *
U> / \
U> a *
U> / \
U> b c

U>Что будет в файле?

10[a]10[b]0[c]

PD>Когда я писал свой архиватор я хранил дерево как дерево. Т.е. бит 1 что у текущего узла два потомка и нужно сместиться (вызовом рекурсии) на один бит и парсить его значение. бит 0 означает что далее записаны восемь бит закодированного символа.
PD>Итого 2+8 бит на каждый символ, т.е. не более 320 байт на всё дерево.

Неправильно посчитал я. Требуется (2*256 — 1) бит + 1684 бита на хранения номера перестановки из 256 элементов, тогда потребуется ещё меньше памяти для хранения кодов (неполных 275 байт). Другое дело что вряд ли такой изват будет оправдан.

Здравствуйте, potapov.d, Вы писали:

PD>>Когда я писал свой архиватор я хранил дерево как дерево. Т.е. бит 1 что у текущего узла два потомка и нужно сместиться (вызовом рекурсии) на один бит и парсить его значение. бит 0 означает что далее записаны восемь бит закодированного символа.
PD>>Итого 2+8 бит на каждый символ, т.е. не более 320 байт на всё дерево.

PD>Неправильно посчитал я. Требуется (2*256 — 1) бит + 1684 бита на хранения номера перестановки из 256 элементов, тогда потребуется ещё меньше памяти для хранения кодов (неполных 275 байт). Другое дело что вряд ли такой изват будет оправдан.

Теперь ясно (Вы храните бинарное дерево "по ярусам").
Спасибо.
(Да, кстати, а если в дереве не все 256 символов? Число используемых символов придётся тоже хранить, например в первом байте.)

Здравствуйте, ultrator, Вы писали:

U>Теперь ясно (Вы храните бинарное дерево "по ярусам").
U>Спасибо.
U>(Да, кстати, а если в дереве не все 256 символов? Число используемых символов придётся тоже хранить, например в первом байте.)

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

Здравствуйте, potapov.d, Вы писали:

PD>Здравствуйте, ultrator, Вы писали:

U>>Теперь ясно (Вы храните бинарное дерево "по ярусам").
U>>Спасибо.
U>>(Да, кстати, а если в дереве не все 256 символов? Число используемых символов придётся тоже хранить, например в первом байте.)

PD>Как правило, сжатие Хаффманом делают когда данные уже исковерканы до неузнаваемости и присутствуют все значения байт в частотах, так что я не думаю что это оправдано.

Ой, да и вобще не надо (хоть все, хоть нет). Когда пропарсена каждая 1 — значит дерево кончилось .