Thread: Help Huffman Coding>>

You need to show the code you have with comments that describe how you are implementing the algorithm and your questions about the problems you are having.

You better put in a little more effort than this post shows if you want it done so soon.

Please edit your code and wrap it in code tags. Use Go Advanced and the # icon.

This is Node class

What is your problem with the code you posted? I don't see any questions about your code.

main class

import java.io.*;
import java.util.*;     
 
class HuffmanApp
   {
   public static void main(String[] args) throws IOException
      {
      Huffman huff = null;
      int value;
      String str;
 
      while(true)
         {
         System.out.print("Enter first letter of ");
         System.out.print("enter, show, code, or decode: ");
         int choice = getChar();
         switch(choice)
            {
            case 'e':
               System.out.println(
                  "Enter text lines, terminate with $");
               str = getText();
               huff = new Huffman(str);
               break;
            case 's':
               huff.displayTree();
               break;
            case 'c':
               huff.code();
               break;
            case 'd':
               huff.decode();
               break;
            default:
               System.out.print("Invalid entry\n");
            }  // end switch
         }  // end while
      }  // end main()
// -------------------------------------------------------------
   public static String getString() throws IOException
      {
      InputStreamReader isr = new InputStreamReader(System.in);
      BufferedReader br = new BufferedReader(isr);
      String s = br.readLine();
      return s;
      }
// -------------------------------------------------------------
   public static String getText() throws IOException
      {
      String outStr="", str = "";
      while(true)
         {
         str = getString();
         if( str.equals("$") )
            return outStr;
         outStr = outStr + str + "\n";
         }
      }  // end getText()
// -------------------------------------------------------------
   public static char getChar() throws IOException
      {
      String s = getString();
      return s.charAt(0);
      }
//-------------------------------------------------------------
   public static int getInt() throws IOException
      {
      String s = getString();
      return Integer.parseInt(s);
      }
// -------------------------------------------------------------
   }  // end class HuffmanApp

will do
thx

Thanks for using code tags.

What is your problem with the code you posted? I don't see any questions about your code.

actually nothing is wrong put u could see in post # 4
there 4 empty functions need to fill them up and run the programme

Are you thinking that someone here is going to write the code for your "functions"? (methods in java)

Originally Posted by Norm

Are you thinking that someone here is going to write the code for your "functions"? (methods in java)

7
hmmmmmmmmmmmmm
then i'm in the wrong forum

i'm in the wrong forum

Yes, If you expect someone here to write your code for you.

Originally Posted by Norm

Yes, If you expect someone here to write your code for you.

ok be a dear
and help me
in the following code is it correct

PHP Code:

 private void queueTrees()             // put trees in queue
      {
       HuffmanApp a = new HuffmanApp();
      for (int i =0;i<freqTable.length;i++){
          if (freqTable[i]==0)
              continue;
          else{
              char l = codeTable[i].charAt(i);
              Node newNode = new Node (l,freqTable[i]);
              
              Tree t1 = new Tree(newNode);
              theQueue.insert(t1);
          }
      } 


PHP Code:

 private void makeHuffTree()           // make Huffman tree
      {
       for (int i=1;i<alphabetSize;i++){
           Tree a=theQueue.remove();
           int freq1=a.getFreq();
           Tree b =theQueue.remove();
           int freq2=b.getFreq();
           int newfreq =freq1+freq2;
           Node newNode = new Node(' ',newfreq);
           Tree c = new Tree(newNode);
           theQueue.insert(c);
       }
      

      } 


PHP Code:

 private void makeCodeTable(Node nd, String bc)
      {
       if (nd.leftChild!=null && nd.rightChild!=null){
           makeCodeTable(nd.leftChild,bc+"0");
           makeCodeTable(nd.rightChild,bc+"1");
       }
       else 
           codeTable=codeTable+bc;

  }  // end makeCodeTable() 


this one don't know what to do with it

PHP Code:

  public void decode()
      {
      }  // end decode() 


the following code is it correct

Does your program output the correct result?
If not, please explain what is wrong with the output and show what it needs to look like.

You've posted bits and pieces of your code, but I'm not sure if it is all here for anyone to compile and execute and test with.

Originally Posted by cool_97

here is the class huffman where i need help in the following functions
private void queueTrees(){
for each char in the frequancy table loop{
if freq =0 do nothing
else
creat a new node contains the char and the frequency
creat a tree for the node
insert node in priority queue
}

}

private void makeHuffTree(){
loop until one tree in the queue {
dequeu first node
deququ second node
add the frequency of one and two
creat a new tree with new frequencies as it's root
connect the new tree in the correct place in the queue
}
}
private void makeCodeTable(Node nd, String bc)
{
if the node is not a leaf{
(external node ) (add symbol like + to make it recognizable, nd.ch=='+')
call it recursively
makecodetable (nd.leftchild,bc+"0");

makecodetable (nd.rightchild,bc+"0");
}
else it is aa leaf node so put it in code table
}
public void decode()

-----------------------------------------------------------------------

import java.io.*;
import java.util.*;     
class Huffman
   {
   private PriorityQ theQueue;
   private String inString;        // input from user
   private int strlen;
   private String capsString;      // converted to all caps
   private Tree[] treeArray;
   private Tree huffTree;          // Huffman tree
   private int freqTable[];        // letter frequencies
   private int alphabetSize;       // size of frequency table
   private String codeTable[];     // code for each letter
   private String codedMsg;        // binary string
   private String decodedMsg;      // back to original msg
// -------------------------------------------------------------
   Huffman(String s)                     // constructor
      {
      inString = s;
      strlen = inString.length();
      alphabetSize = 28;                 // 26 letters, cr, lf
      theQueue = new PriorityQ(alphabetSize); // make the queue
      capsString = "";
      codeTable = new String[alphabetSize];   // make code table
 
      makeFreqTable();          // construct frequency table
      queueTrees();             // put one-node trees in queue
      makeHuffTree();           // construct Huffman tree
      }  // end constructor
// -------------------------------------------------------------
   public void displayTree()
      {
      if(huffTree != null)
         huffTree.display();
      }
// -------------------------------------------------------------
  private void makeFreqTable()
      {
      freqTable = new int[alphabetSize];
      int temp;
      char sp = 32;                      // space
      for(int j=0; j<strlen; j++)        // for every char
         {                               // of user's input msg
         char ch = inString.charAt(j);
         if(ch>96 && ch<123)             // lowercase (97-122)
            {
            temp = (int)ch - 32;         // convert to upper
            ch = (char)temp;             //    (65-90)
            }
         if(ch==32)                      // space becomes 91
            ch = 91;
         else if(ch==10)                 // linefeed becomes 92
            ch = 92;
         else if(ch<65 || ch>92)         // if not uppercase
            continue;                    // letter, ignore it
         capsString = capsString + ch;   // add to caps string
         int index = (int)ch - 65;       // convert to 0 to 27
         freqTable[index]++;             // keep count in
         }  // end for                   //    frequency table
      System.out.println(capsString);    // all-caps string
      for(int j=0; j<28; j++)            // row of characters
         System.out.print( (char)(j+65) + " ");
      System.out.println("");
      for(int j=0; j<28; j++)            // row of frequencies
         System.out.print(freqTable[j] + " ");
      System.out.println("");
      }  // end makeFreqTable()
// -------------------------------------------------------------
   private void queueTrees()             // put trees in queue
      {
// for each char in frequency table forget unused characters
 
// make node
 
// make tree
// put  the tree in queue
 
      }  // end queueTrees()
// -------------------------------------------------------------
   private void makeHuffTree()           // make Huffman tree
      {
 
 
      }  // end makeHuffTree()
// -------------------------------------------------------------
   private void makeCodeTable(Node nd, String bc)
      {
 
      }  // end makeCodeTable()
// -------------------------------------------------------------
   public void code()                    // encode the msg
      {
      makeCodeTable(huffTree.root, "");
      for(int j=0; j<alphabetSize; j++)  // display code table
         {
         if(codeTable[j] == null)
            continue;
         char ch = (char)(j+65);
         System.out.println(ch + " " + codeTable[j]);
         }
      codedMsg = "";                     // encode the msg
      for(int j=0; j<capsString.length(); j++)   // for each char
         {                                       // get the code
         int index = (int)capsString.charAt(j) - 65;
         codedMsg = codedMsg + codeTable[index]; // add to msg
         }
      System.out.println("Coded message:\n" + codedMsg);
      }  // end code()
// -------------------------------------------------------------
   public void decode()
      {
      }  // end decode()
// -------------------------------------------------------------
   }  // end class Huffman

Originally Posted by cool_97

This is Node class
----------------

// huffman.java
// demonstrates Huffman trees
// to run this program: C>java HuffmanApp
import java.io.*;
import java.util.*;               // for Stack class
////////////////////////////////////////////////////////////////
class Node
   {
   public char ch;                // letter
   public int freq;               // instances of this letter
   public Node leftChild;         // this node's left child
   public Node rightChild;        // this node's right child
// -------------------------------------------------------------
   Node(char c, int f)            // constructor
      {
      ch = c;
      freq = f;
      }
// -------------------------------------------------------------
   public void displayNode()      // display ourself
      { System.out.print( ch + "" + freq ); }
   }  // end class Node
////////////////////////////////////////////////////////////////
class Tree
   {
   public Node root;              // first node of tree
// -------------------------------------------------------------
   public Tree(Node nd)           // constructor
      { root = nd; }              // root of tree from argument
// -------------------------------------------------------------
   public int getFreq()           // returns node's word freq
      { return root.freq; }
// -------------------------------------------------------------
   public void display()
      {
      Stack globalStack = new Stack();
      globalStack.push(root);
      int nBlanks = 32;
      boolean isRowEmpty = false;
      System.out.println(
      "......................................................");
      while(isRowEmpty==false)
         {
         Stack localStack = new Stack();
         isRowEmpty = true;
 
         for(int j=0; j<nBlanks; j++)
            System.out.print(' ');
 
         while(globalStack.isEmpty()==false)
            {
            Node temp = (Node)globalStack.pop();
            if(temp != null)
               {
               temp.displayNode();
               localStack.push(temp.leftChild);
               localStack.push(temp.rightChild);
 
               if(temp.leftChild != null ||
                                   temp.rightChild != null)
                  isRowEmpty = false;
               }
            else
               {
               System.out.print("--");
               localStack.push(null);
               localStack.push(null);
               }
            for(int j=0; j<nBlanks*2-2; j++)
               System.out.print(' ');
            }  // end while globalStack not empty
         System.out.println();
         nBlanks /= 2;
         while(localStack.isEmpty()==false)
            globalStack.push( localStack.pop() );
         }  // end while isRowEmpty is false
      System.out.println(
      "......................................................");
      }  // end displayTree()
// -------------------------------------------------------------
   }  // end class Tree
////////////////////////////////////////////////////////////////
class PriorityQ
   {
   // array in sorted order, from max at 0 to min at size-1
   private int maxSize;
   private Tree[] queArray;
   private int nItems;
//-------------------------------------------------------------
   public PriorityQ(int s)          // constructor
      {
      maxSize = s;
      queArray = new Tree[maxSize];
      nItems = 0;
      }
//-------------------------------------------------------------
   public void insert(Tree item)    // insert item
      {
      int j;
 
      if(nItems==0)                         // if no items,
         queArray[nItems++] = item;         // insert at 0
      else                                  // if items,
         {
         for(j=nItems-1; j>=0; j--)      // start at end,
            {                            // if new item larger,
            if( item.root.freq > queArray[j].root.freq )
               queArray[j+1] = queArray[j]; // shift upward
            else                            // if smaller,
               break;                       // done shifting
            }  // end for
         queArray[j+1] = item;              // insert it
         nItems++;
         }  // end else (nItems > 0)
      }  // end insert()
//-------------------------------------------------------------
   public Tree remove()             // remove minimum item
      { return queArray[--nItems]; }
//-------------------------------------------------------------
   public Tree peekMin()            // peek at minimum item
      { return queArray[nItems-1]; }
//-------------------------------------------------------------
   public boolean isEmpty()         // true if queue is empty
      { return (nItems==0); }
//-------------------------------------------------------------
   public boolean isFull()          // true if queue is full
      { return (nItems == maxSize); }
//-------------------------------------------------------------
   public int getSize()
      { return nItems; }
//-------------------------------------------------------------
   }  // end class PriorityQ

////////////////////////////////////////////////////////////////

Originally Posted by cool_97

main class

import java.io.*;
import java.util.*;     
 
class HuffmanApp
   {
   public static void main(String[] args) throws IOException
      {
      Huffman huff = null;
      int value;
      String str;
 
      while(true)
         {
         System.out.print("Enter first letter of ");
         System.out.print("enter, show, code, or decode: ");
         int choice = getChar();
         switch(choice)
            {
            case 'e':
               System.out.println(
                  "Enter text lines, terminate with $");
               str = getText();
               huff = new Huffman(str);
               break;
            case 's':
               huff.displayTree();
               break;
            case 'c':
               huff.code();
               break;
            case 'd':
               huff.decode();
               break;
            default:
               System.out.print("Invalid entry\n");
            }  // end switch
         }  // end while
      }  // end main()
// -------------------------------------------------------------
   public static String getString() throws IOException
      {
      InputStreamReader isr = new InputStreamReader(System.in);
      BufferedReader br = new BufferedReader(isr);
      String s = br.readLine();
      return s;
      }
// -------------------------------------------------------------
   public static String getText() throws IOException
      {
      String outStr="", str = "";
      while(true)
         {
         str = getString();
         if( str.equals("$") )
            return outStr;
         outStr = outStr + str + "\n";
         }
      }  // end getText()
// -------------------------------------------------------------
   public static char getChar() throws IOException
      {
      String s = getString();
      return s.charAt(0);
      }
//-------------------------------------------------------------
   public static int getInt() throws IOException
      {
      String s = getString();
      return Integer.parseInt(s);
      }
// -------------------------------------------------------------
   }  // end class HuffmanApp

these are the classes that i have u could compile but 3 out of four functions don't work

PHP Code:

Enter first letter of enter, show, code, or decode: e
Enter text lines, terminate with $
cool
$
COOL\
A B C Exception in thread "main" java.lang.NullPointerException
    at Huffman.queueTrees(Huffman.java:76)
    at Huffman.<init>(Huffman.java:27)
    at HuffmanApp.main(HuffmanApp.java:23)
D E F G H I J K L M N O P Q R S T U V W X Y Z [ \ 
0 0 1 0 0 0 0 0 0 0 0 1 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 1 


actually this function was working and it did decode them but after modifying some functions it didn't

java.lang.NullPointerException
at Huffman.queueTrees(Huffman.java:76)

For this error, look at line 76 and see what variable can be null. Then back track to see why that variable does not have a valid value.
If you can't tell which variable is null, add a println before line 76 to print out the values of all the variables.

To test your code there needs to be correct input. Here is a technique to make sure that everyone uses the same input. Put the input into a String and use the Scanner class.

   static Scanner scnr = new Scanner("e\ncool\n$\n\n");  // preload the responses
 
// -------------------------------------------------------------
   public static String getString() { //throws IOException       {
//      InputStreamReader isr = new InputStreamReader(System.in);
//      BufferedReader br = new BufferedReader(isr);
//      String s = br.readLine();
      return scnr.nextLine();  // get the response from the String above
   }

You have too many "magic" numbers in your code in place of self defining literals. That makes it impossible for anyone reading the code to easily understand what it is doing.
For example:
char sp = 32;
vs
char sp = ' ';

What does this 65 represent?
int index = (int)ch - 65; // convert to 0 to 27

Ok let me explain
these three classes were given to us in class to complete the missing functions

the programme do the following
take a line of charecters then print them and encode them to 0's and 1's
after that printing them
there is a frequency table to check how many times each letter occuer and code table to save them
it also decode wich convert them from 1's and 0's to the letters
and that's that

Another comment on the coding style: too many methods are static. There should be a short main and the rest of the code should be in the constructor:

  public static void main(String[] args) {    //<<<<<<<<<<<<<<
       new HuffmanApp();
   }
 
   Huffman huff = null;        //<<<<<<<<<<<<< an instance variable NOTE<<<
 
   //-------------------------
   public HuffmanApp() {

The idea of this forum is that you post the code that isn't working and we help you figure out what's wrong with it so you can fix it. We're not generally that interested in writing it for you - neither of us will learn anything useful.

If you can't post up your effort at writing the code, try explaining which specific parts of the task you don't understand. If you have an algorithm for decoding Huffman Code, post it and explain where you're having difficulty translating it to Java. If you don't have an algorithm, you need to find one (not really a Java problem).

You need to know how to do the tasks required by those methods before writing any code. If you can't write out a detailed step-by-step sequence in English for each task, focus on that first. Then we can help you translate your steps into Java.

plz visit thread # 14 i posted my effort
and i have already posted the algorithm
og each function and the purpose of it
thx

queueTrees()
makeHuffTree()
makeCodeTable
but not sure if it's correct

i meant 13#
sry