# Huffman coding

• 04-21-2005
misplaced
Huffman coding
i just read the definition for the huffman coding algortihm and it says

Code:

`Definition: A minimal variable-length character coding based on the frequency of each character. First, each character becomes a trivial binary tree, with the character as the only node. The character's frequency is the tree's frequency. Two trees with the least frequencies are joined as the subtrees of a new root that is assigned the sum of their frequencies. This is repeated until all characters are in one tree. One code bit represents each level. Thus more frequent characters are near the root and are coded with few bits, and rare characters are far from the root and are coded with many bits.`
i'm not quiet sure on this algorithm. i want to know if this is correct. it's pseudo-pseudo-code. (i hope you like it ;) )

say i had a file that only consisted of the letters "abcde":

Code:

`beeaacdbbbcccca`
for reference:
x : occurs
a : 3
b : 4
c : 5
d : 1
e : 2

i have already created 5 binary trees named a,b,c,d and e.
the nodes are struct{ int frequency, int character; }.

i make a new tree named "de" because those are the least frequent characters.

de.freq = e.freq + d.freq;
de.insert(e)
de.insert(d)

Actually, I'll stop here for now. Do i have the right idea so far?
If so, do i now make an "ade" tree since d+e = 3 and a = 3 are still the lowest frequencies... or do i make an "ab" tree?
• 04-21-2005
treenef
I'm probably gonna get told off advertising a site which is in direct competition with Cprogramming but I don't mind lol.

http://www.codeproject.com/cpp/Huffman_coding.asp

:confused:
• 04-21-2005
Tronic
We have a tutorial on Huffman coding on this site:
http://www.cprogramming.com/tutorial...y/huffman.html

It's better if you solve this one yourself, it's not too difficult, give it a try ;) It'll be good if you do.