6 Replies - 2492 Views - Last Post: 03 March 2012 - 11:53 PM Rate Topic: -----

#1 rmendoza  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 4
  • Joined: 03-March 12

Huffman Tree decoding

Posted 03 March 2012 - 02:54 PM

I want to write a program that is similar to the Huffman tree in that it only has the characters: lower case letters and the space. Your program should be able to receive a coded word i.e. 0011 01101 0110 might be the word dog. Also it should be able to receive a pharse and give the code: i.e. He wins might be 1101 10101 111 001 11010 01010. The user should be given the choice if they are going to enter a string or a code. It needs to be implemented using an array list or a linked list.

I tried to implement a binary tree with an array list but I'm not sure on how to go about the decoding. Any ideas on how I could go about that?

Is This A Good Question/Topic? 0
  • +

Replies To: Huffman Tree decoding

#2 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10486
  • View blog
  • Posts: 38,858
  • Joined: 27-December 08

Re: Huffman Tree decoding

Posted 03 March 2012 - 07:45 PM

The binary digits tell you the order to traverse the tree to find the letters. The 0 means go left, and the 1 means go right.
Was This Post Helpful? 0
  • +
  • -

#3 rmendoza  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 4
  • Joined: 03-March 12

Re: Huffman Tree decoding

Posted 03 March 2012 - 10:30 PM

This is what I have so far. I'm not sure about how to go through the tree and obtain the characters with the if statements.

-Thank you!

import java.util.*;
import java.lang.*;

public class HuffmanTree {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
   
      Node head = new Node (null);
        
        head.left = new Node<Character>(null);
              head.left.left = new Node<Character>(null);
              head.left.left.left = new Node<Character>(null);
              head.left.left.left.left = new Node<Character>(null);
              head.left.left.left.left.left = new Node<Character>("u");
              head.left.left.left.left.right = new Node<Character>("c");
              head.left.left.left.right = new Node<Character>("c");
              head.left.left.right = new Node<Character>(null);
              head.left.left.right.left = new Node<Character>("c");
              head.left.left.right.right = new Node<Character>("c");
              head.left.right = new Node<Character>(null);
              head.left.right.left = new Node<Character>("c");
              head.left.right.right = new Node<Character>(null);
              head.left.right.right.left = new Node<Character>("c");
              head.left.right.right.right = new Node<Character>("c");
              head.right = new Node<Character>(null);
              head.right.left = new Node<Character>(null);
              head.right.left.left = new Node<Character>(null);
              head.right.left.left.left = new Node<Character>(null);
              head.right.left.left.left.left = new Node<Character>(null);
              head.right.left.left.left.left.left = new Node<Character>("c");
              head.right.left.left.left.left.right = new Node<Character>("c");
              head.right.left.left.left.right = new Node<Character>(null);
              head.right.left.left.left.right.left = new Node<Character>("c");
              head.right.left.left.left.right.right = new Node<Character>("c");
              head.right.left.left.right = new Node<Character>("c");
              head.right.left.right = new Node<Character>(null);
              head.right.left.right.left = new Node<Character>("c");
              head.right.left.right.right = new Node<Character>(null);
              head.right.left.right.right.left = new Node<Character>("c");
              head.right.left.right.right.right = new Node<Character>("c");
              head.right.right = new Node<Character>(null);
              head.right.right.left = new Node<Character>(null);
              head.right.right.left.left = new Node<Character>(null);
              head.right.right.left.left.left = new Node<Character>(null);
              head.right.right.left.left.left.left = new Node<Character>(null);
              head.right.right.left.left.left.left.left = new Node<Character>("c");
              head.right.right.left.left.left.left.right = new Node<Character>(null);
              head.right.right.left.left.left.left.right.left = new Node<Character>(null);
              head.right.right.left.left.left.left.right.left.left = new Node<Character>(null);
              head.right.right.left.left.left.left.right.left.left.left = new Node<Character>("c");
              head.right.right.left.left.left.left.right.left.left.right = new Node<Character>("c");
              head.right.right.left.left.left.left.right.left.right = new Node<Character>(null);
              head.right.right.left.left.left.left.right.left.right.left = new Node<Character>("c");
              head.right.right.left.left.left.left.right.left.right.right = new Node<Character>("c");
              head.right.right.left.left.left.left.right.right = new Node<Character>("c");
              head.right.right.left.left.left.right = new Node<Character>("c");
              head.right.right.left.left.right = new Node<Character>(null);
              head.right.right.left.left.right.left = new Node<Character>("c");
              head.right.right.left.left.right.right = new Node<Character>("c");
              head.right.right.left.right = new Node<Character>("c");
              head.right.right.right = new Node<Character>(" ");
              
              Scanner scan = new Scanner(System.in);
              
        System.out.println("Enter Huffman Code ");
        String code = scan.nextLine(); 
        System.out.println(code);
        String codeAr[] = code.split(" ");
    
      
        
    }
    
}

class Node<E> {
    Node left;
 
    Node right;
 
   String let;
 
    public Node(String let) {
      this.let = let;
    }

}


Was This Post Helpful? 0
  • +
  • -

#4 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10486
  • View blog
  • Posts: 38,858
  • Joined: 27-December 08

Re: Huffman Tree decoding

Posted 03 March 2012 - 10:47 PM

Visualize the binary search tree:
              Root
             /    \
            0      1
           / \    / \
          0   1  0   1
         /\  /\ /\  /\
        0 1 0 1 0 1 0 1 



Now if you are given 010, the 0's mean go left, and the 1's mean go right. So from the root, we would go left. Then from that Node, go right. Then go left once more. KYA also has a good blog entry on the Huffman problem.
Was This Post Helpful? 0
  • +
  • -

#5 rmendoza  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 4
  • Joined: 03-March 12

Re: Huffman Tree decoding

Posted 03 March 2012 - 11:33 PM

I understand how that works but I'm still having problems. How can I check each 1 or 0 at a time?
Was This Post Helpful? 0
  • +
  • -

#6 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10486
  • View blog
  • Posts: 38,858
  • Joined: 27-December 08

Re: Huffman Tree decoding

Posted 03 March 2012 - 11:34 PM

If you treat the binary as Strings, you can use the String charAt() method.
Was This Post Helpful? 1
  • +
  • -

#7 rmendoza  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 4
  • Joined: 03-March 12

Re: Huffman Tree decoding

Posted 03 March 2012 - 11:53 PM

Ok does this look about right? Also, how do I tell it to go right or left? Do I need a method for that?

  for (int i = 0; i < codeAr.length; i++) {
            for (int j = 0; j < code.length(); j++) {
                if (code.charAt(j) == '0') {
                    //go left;
                }
                else if (code.charAt(j) == '1') {
                // go right
                }



Thank you for replying so quickly, it is greatly appreciated since this is due in a few hours.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1