Huffman encoding

This is a discussion on Huffman encoding within the C++ Programming forums, part of the General Programming Boards category; I am working on huffman encoding and i am a little confused on how to transverse a tree to encode ...

  1. #1
    Registered User
    Join Date
    Nov 2011
    Posts
    118

    Huffman encoding

    I am working on huffman encoding and i am a little confused on how to transverse a tree to encode string of bits for a particular character.I already have my tree built.

  2. #2
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,263
    To encode, start at the leaf which corresponds to the symbol you are going to encode. Then walk the tree upward to the root, keeping track of whether each child is a left child (zero bit) or a right child (one bit) of its parent. This will produce a bit string, which you must reverse the order of to give the Huffman code.

    The problem is how to locate the correct leaf, given a symbol. You can store that in some kind of map, but it's actually easier to walk the tree top-down, building an encoding table as you go, then use the table during the actual encoding. In pseudocode it might look like this:

    Code:
    BuildHuffmanEncodingTable(root, code = ''):
        if root.HasChildren:
            BuildHuffmanEncodingTable(root.Left, code + '0')
            BuildHuffmanEncodingTable(root.Right, code + '1')
        else:
            # Reached a leaf, which means 'code' contains the actual code for this symbol
            InsertHuffmanCodeIntoTable(root.Symbol, code)
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  3. #3
    Registered User
    Join Date
    Nov 2011
    Posts
    118
    Quote Originally Posted by brewbuck View Post
    To encode, start at the leaf which corresponds to the symbol you are going to encode. Then walk the tree upward to the root, keeping track of whether each child is a left child (zero bit) or a right child (one bit) of its parent. This will produce a bit string, which you must reverse the order of to give the Huffman code.

    The problem is how to locate the correct leaf, given a symbol. You can store that in some kind of map, but it's actually easier to walk the tree top-down, building an encoding table as you go, then use the table during the actual encoding. In pseudocode it might look like this:

    Code:
    BuildHuffmanEncodingTable(root, code = ''):
        if root.HasChildren:
            BuildHuffmanEncodingTable(root.Left, code + '0')
            BuildHuffmanEncodingTable(root.Right, code + '1')
        else:
            # Reached a leaf, which means 'code' contains the actual code for this symbol
            InsertHuffmanCodeIntoTable(root.Symbol, code)
    Hi i am a little bit confused.Do you mind explaining further

  4. #4
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    What exactly confuses you?
    Put in some effort, man!
    You could post your code, too.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. How to convert string in url encoding to html encoding?
    By Jerel2k11 in forum C Programming
    Replies: 6
    Last Post: 11-06-2011, 09:05 AM
  2. HUffman encoding(data compression)
    By jia in forum C++ Programming
    Replies: 4
    Last Post: 06-01-2010, 04:44 PM
  3. Huffman coding
    By misplaced in forum C++ Programming
    Replies: 2
    Last Post: 04-21-2005, 02:14 PM
  4. huffman encoding help
    By Unregistered in forum C Programming
    Replies: 6
    Last Post: 04-17-2002, 01:51 PM
  5. Huffman Encoding
    By Unregistered in forum C Programming
    Replies: 7
    Last Post: 10-29-2001, 02:31 PM

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