Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Help building huffman tree

  1. Dec 16, 2007 #1
    Hi

    I'm playing around with Huffman encoding and am having a major problem getting my head around how to efficiently build the tree. I Googled "huffman coding" and have a basic grasp of what needs to be done but the actual process of walking through a list of sorted values has turned into a big headache.

    Assuming I start with a list of factored values and their rank, in either descending (or ascending) order, the algorithm I came up with takes almost 3 minutes on a dual core 2.16 ghz Macintosh. This is clearly ridiculous as it takes roughly half a second for the rest of my code to read the file and create the factored list of values and their frequencies.

    I tried writing to the model here but due to the large number of initial factors (3000+) I ran into a problem where the sum of the ranks grew so large over subsequent iterations that it didn't even fit in an unsigned long long value without truncation.

    Here's a snippet showing a section of the sorted, pre-Huffman data I'm starting with

    Code (Text):

    87 = ({rank = 87; word = hate; }, {rank = 87; word = GONZALEZ; });
    88 = ({rank = 88; word = one; });
    89 = ({rank = 89; word = mainstream; }, {rank = 89; word = "don't"; });
    90 = (
        {rank = 90; word = like; },
        {rank = 90; word = "it's"; },
        {rank = 90; word = his; }
    );
    91 = ({rank = 91; word = he; }, {rank = 91; word = all; });
    92 = ({rank = 92; word = legislation; });
    93 = (
        {rank = 93; word = by; },
        {rank = 93; word = more; },
        {rank = 93; word = had; },
        {rank = 93; word = report; },
        {rank = 93; word = at; }
    );
    94 = ({rank = 94; word = being; });
    95 = ({rank = 95; word = them; });
    96 = ({rank = 96; word = right; }, {rank = 96; word = crimes; });  
     
    What this shows is an associative array sorted and grouped by rank of each word in the source file. For example, under the key "93" we see that the five words "by," "more," "had," "report," and "at" all have the same frequency in the document

    From this, could someone help me out with a step by step on how to create the huffman tree?

    Thanks for any help

    Ken
     
    Last edited: Dec 16, 2007
  2. jcsd
  3. Dec 16, 2007 #2
    Never mind. I figured it out

    Turns out I wasn't properly grouping values after adding their ranks. I was just changing their rank without combining symbol pairs into a new node.

    Got the total encoding time down to .5 seconds for a 90K file. 5 seconds for a 10 MB file etc... Much better.
     
    Last edited: Dec 16, 2007
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Help building huffman tree
  1. Juggle trees help (Replies: 2)

  2. Huffman encoding (Replies: 1)

  3. Huffman Code. (Replies: 4)

Loading...