Write the following in Java Write a program which implements

Write the following in Java: Write a program which implements Huffman Encoding assuming a code alphabet of Z2, ie, binary codewords. You should start with a class called HuffmanNode.java, which contains the required fields S, P, C, L, as well as a left and a right child HuffmanNode. The algorithm should proceed as follows: First, the user selects a text file, which is read into your program. Each line of the text file will have a symbol, sk S, and a probability, pk P. Each line should be written to a distinct HuffmanNode, (leaving Ck and lk blank for later). The newly semi-filled HuffmanNodes should be added, in increasing order of pk into a HuffmanNode list: an ArrayList of HuffmanNodes. Then the Huffman tree is created by following the Huffman Algorithm. After the tree is created, the tree is traversed recursively in order that the codewords and lengths may be added to the HuffmanNodes. Finally, print your symbols and codes to the screen or to a file for verification. Also, you should traverse your Huffman Tree in order to compute the average codeword length of your new code, (the ACWL(C)).

Solution

import java.util.Scanner; public class createHuffmanCode { public static void main(String[] args) { Scanner input = new Scanner(System.in); System.out.print(\"firstly please Enter a text: \"); String texthere = input.nextLine(); int[] totalcounts = togetCharacterFrequency(texthere ); // This is used to count frequency System.out.printf(\"%-15s%-15s%-15s%-15s\ \", \"The ASCII Code\", \"The Character\", \"The Frequency\", \"Code\"); Tree tree = togetHuffmanTree(totalcounts); // This ise used to create a Huffman tree String[] totalcoded = togenerateCode(tree.root); // we will get totalcoded for (int i = 0; i < totalcoded.length; i++) if (totalcounts[i] != 0) // (char)i is not in text if totalcounts[i] is 0 System.out.printf(\"%-15d%-15s%-15d%-15s\ \", i, (char)i + \"\", totalcounts[i], totalcoded[i]); } /** In order to get Huffman totalcoded for the characters * now,this method is called once after a Huffman tree is built */ public static String[] togenerateCode(Tree.createNode root) { if (root == null) return null; String[] totalcoded = new String[2 * 128]; letsassignCode(root, totalcoded); return totalcoded; } /* now we will recursively get totalcoded to the leaf node */ private static void letsassignCode(Tree.createNode root, String[] totalcoded) { if (root.left != null) { root.left.code = root.code + \"0\"; assignCode(root.left, totalcoded); root.right.code = root.code + \"1\"; assignCode(root.right, totalcoded); } else { totalcoded[(int)root.element] = root.code; } } /**This function is used to get a Huffman tree from the totalcoded */ public static Tree getHuffmanTree(int[] totalcounts) { // let is create a heap to hold trees Heap heap = new Heap(); for (int i = 0; i < totalcounts.length; i++) { if (totalcounts[i] > 0) heap.add(new Tree(totalcounts[i], (char)i)); // This is a leaf node tree } while (heap.getSize() > 1) { Tree t1 = heap.remove(); // Remove the smallest weight tree Tree t2 = heap.remove(); // Remove the next smallest weight heap.add(new Tree(t1, t2)); // Combine two trees } return heap.remove(); // The final tree } /** This function is used to get the frequency of the characters */ public static int[] togetCharacterFrequency(String texthere) { int[] totalcounts = new int[256]; // 256 ASCII characters for (int i = 0; i < text.length(); i++) totalcounts[(int)text.charAt(i)]++; // Count the character in text return totalcounts; } /**This will define a Huffman coding tree */ public static class Tree implements Comparable { createNode roothere; // The root of the tree /** First we will create a tree with two subtrees */ public Tree(Tree p1, Tree p2) { roothere = new createNode(); roothere.left = p1.roothere; roothere.right = p2.roothere; roothere.weight = p1.roothere.weight + p2.roothere.weight; } /**The next step is to create a tree containing a leaf node */ public Tree(int weight, char element) { roothere = new createNode(weight, element); } @Override /**Finally we will compare trees based on their weights */ public int compareTo(Tree p) { if (roothere.weight < p.roothere.weight) // Purposely reverse the order return 1; else if (roothere.weight == p.roothere.weight) return 0; else return -1; } public class createNode { char element; //This Stores the character for a leaf node int weight; //This is the weight of the subtree rooted at this node Node left; // This is the feference to the left subtree Node right; //This is the reference to the right subtree String code = \"\"; // The code of this node from the root /** firstly we will create an empty node */ public createNode() { } /** now we will create a node with the specified weight and character */ public createNode(int weight, char element) { this.weight = weight; this.element = element; } } } }