When you're doing Huffman coding, how would you store the tree? The
whole thing is binary, and the output must be too. I'm not worried
about implementations, I'm using a prog language. Since it's binary,
any implementation that requires a special character is right out.

When you're doing Huffman coding, how would you store the tree? The
whole thing is binary, and the output must be too. I'm not worried
about implementations, I'm using a prog language. Since it's binary,
any implementation that requires a special character is right out.

Also with static huffman there is only thing you
can do that can not be done with the adaptive version. This is to write
a compression program that will compress as a static huffman but will
never pick table so file increased by more than one byte when compressed.

One other thing you can do with static huffman is have a degree
of random access to your data. In some applications, people care
about that.

When you're doing Huffman coding, how would you store the tree? The
whole thing is binary, and the output must be too. I'm not worried
about implementations, I'm using a prog language. Since it's binary,
any implementation that requires a special character is right out.

YoungerHacker wrote:

When you're doing Huffman coding, how would you store the tree? The
whole thing is binary, and the output must be too. I'm not worried
about implementations, I'm using a prog language. Since it's binary,
any implementation that requires a special character is right out.

Here are a couple of ways to store any in-memory binary tree
on disk:

(1) Create the tree in an array to start with. Instead of using
pointers, use array indices to indicate a node's children. Then,
you can just write out the elements of the array to the file,
using whatever representation you like for them.

(2) Given a regular tree (using pointers), recurse through all
the nodes in the tree, writing each leaf node as a record in the
file. If you pass the record number of each node to the caller,
the caller can safely write non-leaf nodes because the children
will have already been written and it will know the record numbers.
Using this method, the very last node written will be the root
of the tree. Of course, you will need to write out the count
of nodes in the tree before you start writing the nodes, so that
you know when you've reached the root. (You need to do that
in method #1 too...)

Neither of these methods is the most efficient possible. I'm
no expert, but I believe there are special ways specific to
huffman trees that can be used to store them. But if you just
want to get something working for your own amusement and
edification, the above should work fine.

- Logan

YoungerHacker <mathhurst@prodigy.net> wrote:
When you're doing Huffman coding, how would you store the tree? The
whole thing is binary, and the output must be too. I'm not worried
about implementations, I'm using a prog language. Since it's binary,
any implementation that requires a special character is right out.

You could store the shape of an n-leaf tree in 2n-1 bits

enumerating the nodes, breadth first, left to right,
writing 1 for inner nodes and 0 for leaves:

[] 1
/ \
[] [] 1 0
/ \
[] [] 0 1
/ \
[] [] 0 0

-> 1100100

You can drop the leading bit and two trailing bits
when n is fixed.

This leaves you with encoding what symbol each leaf
represents. The log2(n!) bits needed for that could
be approximated by an arithmetic range encoder. (But
if you have that, one wonders what huffman is doing
there in the first place)

Marcel
-- _ _
_| |_|_|
|_ |_ marcelk@bitpit.net
|_| Marcel van Kervinck

Marcel van Kervinck <marcelk@brick.bitpit.net> wrote in
news:3f736d4f$0$58697$e4fe514c@news.xs4all.nl:

YoungerHacker <mathhurst@prodigy.net> wrote:
When you're doing Huffman coding, how would you store the tree? The
whole thing is binary, and the output must be too. I'm not worried
about implementations, I'm using a prog language. Since it's binary,
any implementation that requires a special character is right out.

You could store the shape of an n-leaf tree in 2n-1 bits

Actually 2n-2 and n does not need to be known in advance
and can be gotten from string as read.

enumerating the nodes, breadth first, left to right,
writing 1 for inner nodes and 0 for leaves:

[] 1
/ \
[] [] 1 0
/ \
[] [] 0 1
/ \
[] [] 0 0

-> 1100100

Your spaceing does not show correctly on my screen I guess its
the font difference

but it looks but you send the tree shape as
6 bits for a tree thats 2 at length 3 and 1 at length 2 and 1 at
lenght 1 the code would be 111000 suspose

Actually its more complicated than that but its
best to have a fixed table that you don't need to send at all.

Actually why not use a full arithmetic encoder from here
to the rest of file.

David A. Scott <daVvid_a_scott@email.com> wrote:
Marcel van Kervinck <marcelk@brick.bitpit.net> wrote in
news:3f736d4f$0$58697$e4fe514c@news.xs4all.nl:

YoungerHacker <mathhurst@prodigy.net> wrote:
When you're doing Huffman coding, how would you store the tree? The
whole thing is binary, and the output must be too. I'm not worried
about implementations, I'm using a prog language. Since it's binary,
any implementation that requires a special character is right out.

You could store the shape of an n-leaf tree in 2n-1 bits

Actually 2n-2 and n does not need to be known in advance
and can be gotten from string as read.

That is what I tried to say after the example: you can
drop some bits. 2n-1 is needed when n=1.

enumerating the nodes, breadth first, left to right,
writing 1 for inner nodes and 0 for leaves:

[] 1
/ \
[] [] 1 0
/ \
[] [] 0 1
/ \
[] [] 0 0

-> 1100100

Your spaceing does not show correctly on my screen I guess its
the font difference

The ascii diagram is best shown using a
fixed width font.

but it looks but you send the tree shape as
6 bits for a tree thats 2 at length 3 and 1 at length 2 and 1 at
lenght 1 the code would be 111000 suspose

It depends on the traversal order. You can traverse
depth-first or breadth first, or whatever pleases
you most. I don't 'see' how to arrive at '111000',
but there are more roads leading to Rome.

Actually its more complicated than that but its
best to have a fixed table that you don't need to send at all.

Actually why not use a full arithmetic encoder from here
to the rest of file.

Well, both seem off-topic for the thread. As far as the
original posting goes, the question was how to encode
a huffman tree. Not for arguments against what he is doing
in the first place (encoding the tree) or counter proposals
for what he might be doing after he has encoded the tree
but hasn't told us yet (the rest).

Thank you for mentioning 'bijective' in your posting.
I was starting to miss it. Ofcourse,

You let n start at 2 since that is the smallest tree
00 could flag a copy with no real binary tree
01 could signal only one symbol type used in file

David A. Scott <daVvid_a_scott@email.com> wrote:

You let n start at 2 since that is the smallest tree
00 could flag a copy with no real binary tree
01 could signal only one symbol type used in file

You are absolutely right ofcourse. I realized too
late I forgot to the delete that erroneous side
remark. Lets attribute it to bad proof reading or
sloppy editting, which is no real excuse, but
often people get away with it anyway.

Marcel

YoungerHacker <mathhurst@prodigy.net> wrote:
When you're doing Huffman coding, how would you store the tree? The
whole thing is binary, and the output must be too. I'm not worried
about implementations, I'm using a prog language. Since it's binary,
any implementation that requires a special character is right out.

You could store the shape of an n-leaf tree in 2n-1 bits
enumerating the nodes, breadth first, left to right,
writing 1 for inner nodes and 0 for leaves:

[] 1
/ \
[] [] 1 0
/ \
[] [] 0 1
/ \
[] [] 0 0

-> 1100100

You can drop the leading bit and two trailing bits
when n is fixed.

To reproduce the shape of the tree all we need to know is the number of
leaf
nodes at each depth. For this tree that would be 0, 1, 1, 2. We know the
range of possible values to restrict it further. The number of leaf nodes
at
any level cannot be more than twice the number of internal nodes on the
previous level. So at the root it either is 0 or 1. For the next level it
is
0, 1, or 2. If you know the total number of leaves you can restrict this
further. So in this case if we knew that n was 4 we know at each level the
possible range of number of leaf nodes is:

[] { 0 }
/ \
[] [] { 1, 2 }
/ \
[] [] { 1 }
/ \
[] [] { 2 }

Since only one of the values can change that means there are only 2 shapes
for a Canonical Huffman tree with 4 leaves, which is true.