Results 1 to 3 of 3

Math Help - Huffman Coding question

  1. #1
    Super Member angel.white's Avatar
    Joined
    Oct 2007
    Posts
    723
    Awards
    1

    Huffman Coding question

    Question: Construct two different Huffman codes for these symbols and frequencies: t: 0.2, u: 0.3, v: 0.2, w: 0.3



    I came up with the two on the top, the back of the book had the one on the bottom and said: "There are four possible answers in all, the one shown here and three more obtained from this one by swapping t and v and / or swapping u and w."



    I can't figure out how they got that graph, t and v should be the first combined, and their combined weight should be 0.4 forcing u and w to be the next two combined for .6 Then the two subgraphs should be combined.

    At least, thats how I understand it, I may be confused, but I got the other questions correct, so IDK.



    Edit: if anyone needs it, here is the algorithm they gave for Huffman Coding.

    Procedure Huffman(C: symbols a_i with frequencies w_i, i=1,...,n)
    F := forest of n rooted trees, each consisting of the single vertex a_i and assigned weight w_i
    while F is not a tree
    begin
    Replace the rooted trees T and T' of least weights from F with w(T) > w(T') with a tree
    having a new root that has T as its left subtree and T' as its right subtree. Label the new edge
    to T with 0 and the new edge to T' with 1
    Assign w(T) + w(T') as the weight of the new tree.
    end
    {the Huffman coding for the symbol a_i is the concatenation of the labels of the edges in the unique path from the root to the vertex a_i}
    Last edited by angel.white; April 6th 2008 at 09:38 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member angel.white's Avatar
    Joined
    Oct 2007
    Posts
    723
    Awards
    1
    Well, I've decided the book is wrong. I found this page here The Squeeze Page which gave the same answer I have (except backwards, but I checked their algorithm, and it codes in reverse order -- even though their explanation codes in the same order, I checked by plugging their example into their applet, and it spit out the reverse answer of their example as well -- so really it is the same answer)
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Feb 2008
    Posts
    51
    Quote Originally Posted by angel.white View Post
    Well, I've decided the book is wrong. I found this page here The Squeeze Page which gave the same answer I have (except backwards, but I checked their algorithm, and it codes in reverse order -- even though their explanation codes in the same order, I checked by plugging their example into their applet, and it spit out the reverse answer of their example as well -- so really it is the same answer)
    Here's an algorithm in Java..
    The Laws of Cryptography: Huffman Coding Algorithm
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Question on coding, syndomes, etc.
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: May 19th 2011, 09:24 AM
  2. Ternary Huffman Coding
    Posted in the Advanced Math Topics Forum
    Replies: 0
    Last Post: August 29th 2009, 12:42 PM
  3. Coding theory question
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: October 8th 2008, 06:26 PM
  4. Coding theory question
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: September 13th 2008, 05:31 PM
  5. Huffman Code?!?!
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 14th 2008, 09:44 PM

Search Tags


/mathhelpforum @mathhelpforum