Welcome to the Treehouse Community

Want to collaborate on code errors? Have bugs you need feedback on? Looking for an extra set of eyes on your latest project? Get support with fellow developers, designers, and programmers of all backgrounds and skill levels here with the Treehouse Community! While you're at it, check out some resources Treehouse students have shared here.

Looking to learn something new?

Treehouse offers a seven day free trial for new students. Get access to thousands of hours of content and join thousands of Treehouse students and alumni in the community today.

Start your free trial

Java

Posted by Edward campbell malan van wyk
Edward campbell malan van wyk
6,403 Points

Huffman decoding

Hi,

I have an asignment I would like to complete on Huffman decoding. Now I do not want help with the assignment but what I do need is someone who is fammiliar with this to tell me if this assignment question is possible, as I have tried everything to understand it. I am fully capalble to encode any word or string using the huffman method but I cannot do this assignment that is asked. Am I missing something or is the question not complete. Any help will be appreciated.

Qeustion : 

 * When text is Huffman encoded, each symbol is replaced by a string of 0's and 1's called        a bit string. 

 * The replacement is done in such a way that the bit string of a symbol is never the prefix of the bit string of another symbol. 

 * You will be given a String archive and a String[] dictionary. 

 * The i-th element of dictionary will be the bit string of the i-th uppercase letter. 

 * Decode the archive using the dictionary and return the result as a single String.

 * Below is a C# class with a method Decode and a test TestHuffman. Implement the Decode method so that all the tests pass.

Code given

public class Huffman {

public String Decode(String archive, String[] dictionary)
{
    return "";
}

public void test() 
{
    Huffman t = new Huffman();

    assertEquals("BDC", t.Decode("101101", new String[] { "00", "10", "01", "11" }));
    assertEquals("CBAC", t.Decode("10111010", new String[] { "0", "111", "10" }));
    assertEquals("BBBABBAABBABBAAABBA", t.Decode("0001001100100111001", new String[] { "1", "0" }));
    assertEquals("EGGFAC", t.Decode("111011011000100110", new String[] { "010", "00", "0110", "0111", "11", "100", "101" }));
    assertEquals("DBHABBACAIAIC", t.Decode("001101100101100110111101011001011001010", new String[] { "110", "011", "10", "0011", "00011", "111", "00010", "0010", "010", "0000" }));

    assertEquals("NITXOQRE", t.Decode("01001111010010010011001000001010001101001000010",    new String[]
                                                                                                        {
                                                                                                            "01101", "01110", "01001110", "0100110", "00010", "01000", "0101", "0000",
                                                                                                            "001001", "111", "010011111", "1010", "100", "0100111101", "00101", "01100",
                                                                                                            "00011", "010010", "1011", "0011", "1101", "0100111100", "01111", "001000",
                                                                                                            "1100"
                                                                                                        }));
    assertEquals("BBBABBAABBABBAA", t.Decode("000100110010011", new String[] { "1", "0" }));
}

}

I would only like to know if this question is possible or am I missing something. The decode method should be empty as that is what i need to change to make this work.

Regards.

Jason Anello
Jason Anello
Courses Plus Student 94,610 Points

Hi Edward,

I'm not sure how much to say here so that I'm not spoiling it for you.

Yes, I think the question is possible given the information you've provided.

Let me know if you need a hint or maybe a walkthrough of the process for the first test case as an example. I won't give any code or implementation details, but just a higher level understanding of the process.

One part of the instructions states:

  • The i-th element of dictionary will be the bit string of the i-th uppercase letter.

Do you understand that part? You won't be able to solve this without knowing what that means.