Trying to figure out how to do this based on the code below for huffman tree, -
ID: 3904533 • Letter: T
Question
Trying to figure out how to do this based on the code below for huffman tree,
- the weight should be based on the frequency of occurrence and the order in which a node is encountered. So lets say 'a' has same frequency as 'd', but a occurs first, then 'a' weighs considered greater than the character 'd'
-Also when adding two nodes together, , the new weight should be the sum of the previous nodes weights but it should "weigh" less than something with the same weight that is already on the priority queue
-It is based on this input given by user: '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.
SHOULD LOOK LIKE THIS
CURRENTLY OUTPUTS
CODE (ALMOST FINISHED below)
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<MyCharNode.MyCharNode.frequency)
{
trav=trav.nextInQueue;
}
MyCharNode.nextInQueue=trav.nextInQueue;
trav.nextInQueue=MyCharNode;
}
}
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[];
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<s.length(); 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);
}
//queue.printTheQueue();
//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='';
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.printf("%30s%30s%30s ", "Character", "Frequency", "Encoded String");
for(int i=0; i<encodings.length; i++)
{
if(encodings[i]!=null)
{
System.out.printf("%30c%30s%30s ", i, frequencies[i], encodings[i]);
}
}
}
public void storeCharacterEncodings(HuffmanNode root, String encodedString)
{
if(root==null)
return;
if(root.MyCharNode.character!='')
{
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<input.length(); i++)
{
System.out.print(tree.getCharacterEncoding(input.charAt(i)));
}
}
}
x] occurs 1 time(s) [] occurs 1 time(s) [;] occurs 1 time(s) C'1 occurs 2 time(s) [:] occurs 2 time(s) p] occurs 3 time(s) -] occurs 3 timeCs) C] occurs 4 time(s) .1 occurs 5 time(s) v] occurs 6 time(s) [k] occurs 7 time(s) j] occurs8 time(s) [F] occurs 10 time(s) [1] occurs 11 time(s) [y] occurs 16 time(s) [c] occurs 16 time(s) C,] occurs 18 time(s) [g] occurs 21 time(s) occurs 21 time(s) [w] occurs 23 time(s) m occurs 26 time(s) ] occurs 30 time(s) [b] occurs 31 time(s) rl occurs 33 time(s) [d] occurs 33 time(s) nl occurs 36 time(s) i] occurs 37 time(s) [s] occurs 38 time(s) [o] occurs 53 time(s) [a] occurs 61 time(s) h] occurs 61 time(s) t] occurs 66 time(s) e] occurs 80 time(s) 1 occurs 193 time(s) SYMBOLS FREQUENCY ASCII BINARY CODE 0101000010 0101000011 010100000 010101010 010101011 01010001 01010100 11001010 11001011 0101001 0101011 1100100 1110100 1110101 101000 101001 110011 111011 01000 01001 01011 01110 11000 11010 11011 11100 0110 1001 1011 11339 2512351 2 8 3 1 111223345678016681136 0133678311 138133Explanation / Answer
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<MyCharNode.MyCharNode.frequency)
{
trav=trav.nextInQueue;
}
MyCharNode.nextInQueue=trav.nextInQueue;
trav.nextInQueue=MyCharNode;
}
}
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[];
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<s.length(); 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);
}
//queue.printTheQueue();
//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='';
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.printf("%30s%30s%30s ", "Character", "Frequency", "Encoded String");
for(int i=0; i<encodings.length; i++)
{
if(encodings[i]!=null)
{
System.out.printf("%30c%30s%30s ", i, frequencies[i], encodings[i]);
}
}
}
public void storeCharacterEncodings(HuffmanNode root, String encodedString)
{
if(root==null)
return;
if(root.MyCharNode.character!='')
{
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<input.length(); i++)
{
System.out.print(tree.getCharacterEncoding(input.charAt(i)));
}
}
}