Huffman coding

This is a discussion on Huffman coding within the C++ Programming forums, part of the General Programming Boards category; i just read the definition for the huffman coding algortihm and it says Code: Definition: A minimal variable-length character coding ...

  1. #1
    Registered User
    Join Date
    Sep 2004
    Posts
    719

    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?
    i seem to have GCC 3.3.4
    But how do i start it?
    I dont have a menu for it or anything.

  2. #2
    Super Moderater.
    Join Date
    Jan 2005
    Posts
    374
    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


  3. #3
    Registered User
    Join Date
    Mar 2004
    Posts
    220
    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.
    OS: Windows XP Pro CE
    IDE: VS .NET 2002
    Preferred Language: C++.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 9
    Last Post: 03-20-2009, 06:22 PM
  2. Before Coding
    By cyberCLoWn in forum C++ Programming
    Replies: 16
    Last Post: 12-15-2003, 02:26 AM
  3. Huffman coding
    By fatinez in forum C Programming
    Replies: 4
    Last Post: 11-04-2003, 05:03 PM
  4. Coding Contest....
    By Koshare in forum A Brief History of Cprogramming.com
    Replies: 46
    Last Post: 10-14-2001, 05:32 PM
  5. Huffman compression
    By SMurf in forum C Programming
    Replies: 2
    Last Post: 09-01-2001, 08:30 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21