Trying to figure out how to do this based on the code below for huffman tree, -

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.

-Therefore, BEFORE building the tree, the frequency must be sorted as well as the characters depending on which character occurs first before the next one. Since character 'x' occurs before character ';' the encoded / binary value of 'x' is bigger than '?', and since character '?' OCCURS before ';' the binary value of character '?' weighs more than ';'

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 138133

Explanation / Answer

To do this you have to check the frequency of each variable.
then go for the weight assign to them and sort according to that
below are simple steps

Steps to build Huffman Tree
Input is array of unique characters along with their frequency of occurrences and output is Huffman Tree.

1. Create a leaf node for each unique character and build a min heap of all leaf nodes (Min Heap is used as a priority queue. The value of frequency field is used to compare two nodes in min heap. Initially, the least frequent character is at root)

2. Extract two nodes with the minimum frequency from the min heap.

3. Create a new internal node with frequency equal to the sum of the two nodes frequencies. Make the first extracted node as its left child and the other extracted node as its right child. Add this node to the min heap.

4. Repeat steps#2 and #3 until the heap contains only one node. The remaining node is the root node and the tree is complete.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.