Question: Given the string given by the input user which is the following : 'twas brillig, and the slithy toves did gyre and gimble in the
Given the string given by the input user which is the following :
'twas brillig, and the slithy toves did gyre and gimble in the wabe: all mimsy were the borogoves, and the mome raths outgrabe. "beware the jabberwock, my son! the jaws that bite, the claws that catch! beware the jubjub bird, and shun the frumious bandersnatch!" he took his vorpal sword in hand: long time the manxome foe he sought -- so rested he by the tumtum tree, and stood awhile in thought. and, as in uffish thought he stood, the jabberwock, with eyes of flame, came whiffling through the tulgey wood, and burbled as it came! one, two! one, two! and through and through the vorpal blade went snicker-snack! he left it dead, and with its head he went galumphing back. "and, has thou slain the jabberwock? come to my arms, my beamish boy! o frabjous day! callooh! callay!" he chortled in his joy. 'twas brillig, and the slithy toves did gyre and gimble in the wabe; all mimsy were the borogoves, and the mome raths outgrabe.
-Trying to figure out how to do this based on the code below for huffman tree:
-The weight (BINARY VALUE) should be based on the frequency of occurrence and the order in which a node is encountered. Since character 'x' has SAME FREQUENCY as character '?', but characer 'x' occurs first, then the character 'x' BINARY CODE / BINARY VALUE is bigger than the character '?' BINARY CODE/ BINARY VALUE. Since character '?' APPEARS before ';' BUT HAS same frequency of character '?', then BINARY CODE VALUE of '?' is bigger than ';'
CURRENT OUTPUTS BELOW:
EXPECTED OUTPUT BELOW
CODE
import java.util.Arrays;
import java.util.Scanner;
class MyCharNode{
char character;
int frequency;
}
class HuffmanNode{
MyCharNode MyCharNode;
HuffmanNode left;
HuffmanNode right;
HuffmanNode nextInQueue;
}
class Queue{
private HuffmanNode head;
private int size;
public Queue()
{
size=0;
}
public HuffmanNode removeCharacterNode(char ch)
{
HuffmanNode prev=head;
HuffmanNode trav=head;
if(head==null)
return null;
if(head.MyCharNode.character==ch)
{
head=head.nextInQueue;
size--;
return prev;
}
while(trav!=null)
{
if(trav.MyCharNode.character==ch)
{
prev.nextInQueue=trav.nextInQueue;
trav.nextInQueue=null;
size--;
return trav;
}
prev=trav;
trav=trav.nextInQueue;
}
return null;
}
public int getSize()
{
return size;
}
public void sortedAddInQueue(HuffmanNode MyCharNode)
{
size++;
if(head==null)
{
head=MyCharNode;
}
else if(head.MyCharNode.frequency>MyCharNode.MyCharNode.frequency)
{
MyCharNode.nextInQueue=head;
head=MyCharNode;
}
else {
HuffmanNode trav=head;
while(trav.nextInQueue!=null && trav.nextInQueue.MyCharNode.frequency
{
trav=trav.nextInQueue;
}
MyCharNode.nextInQueue=trav.nextInQueue;
trav.nextInQueue=MyCharNode;
}
}
public char[] StoreTheQueue()
{
HuffmanNode trav=head;
char chars[] = new char[size];
int i=0;
while(trav!=null)
{
chars[i] = trav.MyCharNode.character;
i++;
trav=trav.nextInQueue;
}
return chars;
}
public void printTheQueue()
{
HuffmanNode trav=head;
while(trav!=null)
{
System.out.println(trav.MyCharNode.character+" "+trav.MyCharNode.frequency);
trav=trav.nextInQueue;
}
}
public HuffmanNode removeFront()
{
if(head==null)
return null;
HuffmanNode front=head;
head=head.nextInQueue;
size--;
return front;
}
public boolean isEmpty()
{
return head==null;
}
}
class HuffmanTree{
private String s;
private Queue queue;
private HuffmanNode rootOfTree;
private String encodings[];
private int frequencies[];
private char chars[];
public HuffmanTree(String s)
{
this.s=s;
queue=new Queue();
encodings=new String[255];//for 255 ascii characetrs
frequencies=new int[255];
}
public void buildTree()
{
for(int i=0; i
{
HuffmanNode hnode=queue.removeCharacterNode(s.charAt(i));
if(hnode==null)
{
MyCharNode MyCharNode=new MyCharNode();
MyCharNode.character=s.charAt(i);
MyCharNode.frequency=1;
hnode=new HuffmanNode();
hnode.MyCharNode=MyCharNode;
hnode.left=null;
hnode.right=null;
}
else {
hnode.MyCharNode.frequency++;
}
queue.sortedAddInQueue(hnode);
}
chars = queue.StoreTheQueue();
//build the tree
while(queue.getSize()>=2)
{
HuffmanNode node1=queue.removeFront();
HuffmanNode node2=queue.removeFront();
//create a new Huffman Node
MyCharNode node=new MyCharNode();
node.frequency=node1.MyCharNode.frequency + node2.MyCharNode.frequency;
node.character='\0';
HuffmanNode newNode=new HuffmanNode();
newNode.MyCharNode=node;
newNode.left=node1;
newNode.right=node2;
//add in queue
queue.sortedAddInQueue(newNode);
}
rootOfTree=queue.removeFront();
}
public void printEncodedCharacters()
{
storeCharacterEncodings(rootOfTree, "");
//print all encodings
System.out.println("--------------------------------------------------------------------------");
System.out.printf("%15s%15s%15s%20s ", "SYMBOLS", "Frequency", "ASCII", "BINARY CODE");
System.out.println("--------------------------------------------------------------------------");
for(int i=0; i
{
if(chars[i]!='\0')
{
System.out.printf("%15c%15s%15d%20s ", chars[i], frequencies[chars[i]], (int)chars[i], encodings[chars[i]]);
}
}
}
public void storeCharacterEncodings(HuffmanNode root, String encodedString)
{
if(root==null)
return;
if(root.MyCharNode.character!='\0')
{
encodings[root.MyCharNode.character]=encodedString;
frequencies[root.MyCharNode.character]=root.MyCharNode.frequency;
}
storeCharacterEncodings(root.left, encodedString+"0");//add 0 for left child
storeCharacterEncodings(root.right, encodedString+"1");//add 1 for right child
}
public void printQueue()
{
queue.printTheQueue();
}
public String getCharacterEncoding(char ch)
{
if(encodings[ch]==null)
return "";
return encodings[ch];
}
}
public class HuffmanTreeArrayTest {
public static void main(String[] args) {
Scanner obj=new Scanner(System.in);
System.out.println("Enter a string to encode.");
String input=obj.nextLine();
HuffmanTree tree=new HuffmanTree(input);
tree.buildTree();
System.out.println("The encoded strings for characters are: ");
tree.printEncodedCharacters();
//encode the complete string
System.out.println("The encoded string is: ");
for(int i=0; i
{
//System.out.print(tree.getCharacterEncoding(input.charAt(i)));
}
}
}
101110110110 1 0 111e) 0 1 1 0111 ? ? 1 1 1 1 1 1 0 0 1 1 1 0001100110000011111 R | 1 1 0 0 0 1 1 1 100111 ??-110011 -11000 1-00 | | | 3 9 9 8 2 5 4 6 8 7 6 2 3 1 9 4 3 7 9 9 884005517 | | | 6 5 2 3 5 1 4 3 4 1 ? ? ? 3 2 9 4 ? 1 1 ? ? 9 1 0 10119 1 1 1 -y| 1 1 1 2 2 3 3 4 5 6 7 8 1 6 6 8 1 1 3 6 0 1 3 3 6 7 8 31 111112222333333356 -F -L 101110110110 1 0 111e) 0 1 1 0111 ? ? 1 1 1 1 1 1 0 0 1 1 1 0001100110000011111 R | 1 1 0 0 0 1 1 1 100111 ??-110011 -11000 1-00 | | | 3 9 9 8 2 5 4 6 8 7 6 2 3 1 9 4 3 7 9 9 884005517 | | | 6 5 2 3 5 1 4 3 4 1 ? ? ? 3 2 9 4 ? 1 1 ? ? 9 1 0 10119 1 1 1 -y| 1 1 1 2 2 3 3 4 5 6 7 8 1 6 6 8 1 1 3 6 0 1 3 3 6 7 8 31 111112222333333356 -F -L
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help