Question

*Java*

You will write a program to do the following: 1. Read an input file with a single line of text. Create a method named load_data. 2. Determine the frequency distribution of every symbol in the line of text. Create a method named 3. Construct the Huffman tree. 4. Create a mapping between every symbol and its corresponding Huffman code. 5. Encode the line of text using the corresponding code for every symbol. 6. Display the results on the screen. One of the reasons why design is such an important aspect of Software Engineering is that it helps you organize your logic. By following the 6 steps above, you should be able to neatly organize your code into the following 6 methods: 1. load_data: Receives a file name (including its path) and returns a single string with the contents.

Answer 1

Before running the below code, please create a file stringData.txt with a single line of data to encode in Huffman Encoding.

Java Code:

import java.util.PriorityQueue;

import java.io.BufferedReader;

import java.io.File;

import java.io.FileReader;

import java.io.IOException;

import java.util.Collections;

import java.util.Comparator;

import java.util.HashMap;

import java.util.LinkedHashMap;

import java.util.LinkedList;

import java.util.Map;

import java.util.Map.Entry;

//Tree Node Structure

class TreeNode {

int data;

char c;

TreeNode left;

TreeNode right;

}

//MyComparator class as an Comparator Operator on Priority Queue

class MyComparator implements Comparator<TreeNode> {

public int compare(TreeNode x, TreeNode y)

{

return x.data - y.data;

}

}

public class HuffmanEncoding {

//load_data to read the line from the file

public static String load_data(String file_name) throws IOException

{

File file=new File(file_name);

FileReader fr=new FileReader(file);

BufferedReader br=new BufferedReader(fr);

String line=br.readLine();

fr.close();

return line;

}

//Computing the Symbol Frequency Distribution

public static Map<Character, Integer> compute_fd(String content)

{

Map<Character, Integer> symbol_frequency_distribution_map=new HashMap<Character, Integer>();

for(int i=0;i<content.length();i++)

{

char c=content.charAt(i);

if(symbol_frequency_distribution_map.containsKey(c))

{

symbol_frequency_distribution_map.put(c, symbol_frequency_distribution_map.get(c)+1);

}

else

{

symbol_frequency_distribution_map.put(c,1);

}

}

return symbol_frequency_distribution_map;

}

//Forming HuffMan Tree

public static TreeNode huffman_tree(Map<Character,Integer> symbol_frequency_distribution_map)

{

TreeNode root = null;

int size = symbol_frequency_distribution_map.size();

// Min priority queue for min-heap Creation.

PriorityQueue<TreeNode> q = new PriorityQueue<TreeNode>(size, new MyComparator());

//Adding elements to Min priority queue

for (Map.Entry mapElement : symbol_frequency_distribution_map.entrySet())

{

TreeNode tn = new TreeNode();

tn.c = (char)mapElement.getKey();

tn.data = (int)mapElement.getValue();

tn.left = null;

tn.right = null;

q.add(tn);

}

// Forming the Min Heap Tree

while (q.size() > 1) {

TreeNode x = q.peek();

q.poll();

TreeNode y = q.peek();

q.poll();

TreeNode intermediate = new TreeNode();

intermediate.data = x.data + y.data;

intermediate.c = '\0';

intermediate.left = x;

intermediate.right = y;

root = intermediate;

q.add(intermediate);

}

return root;

}

//Getting Huffman Codes

public static Map<Character, String> huffman_code(TreeNode root)

{

Map<Character, String> symbol_huffman_code_map=new HashMap<Character, String>();

return getHuffManCodes(root,"",symbol_huffman_code_map);

}

//Used by Huffman Codes function for recursively getting the codes and updating in symbol_huffman_code_map

public static Map<Character, String> getHuffManCodes(TreeNode root, String s,Map<Character, String> symbol_huffman_code_map)

{

if (root.left == null && root.right == null)

{

symbol_huffman_code_map.put(root.c, s);

return symbol_huffman_code_map;

}

getHuffManCodes(root.left, s + "0",symbol_huffman_code_map);

getHuffManCodes(root.right, s + "1",symbol_huffman_code_map);

return symbol_huffman_code_map;

}

//Encoding the String

public static String encode(Map<Character, String> huffman_code_map, String content)

{

String encoded_string = "";

for(int i=0;i<content.length();i++)

{

encoded_string=encoded_string+huffman_code_map.get(content.charAt(i));

}

return encoded_string;

}

//Printing Output

public static void process_results(Map<Character, Integer> symbol_frequency_distribution_map,String content,String encoded_string)

{

//For Sorting the symbol_frequency_distribution_map in decending Order.

LinkedList<Entry<Character, Integer>> ele_list =new LinkedList<Map.Entry<Character, Integer> >(symbol_frequency_distribution_map.entrySet());

Collections.sort(ele_list, new Comparator<Map.Entry<Character, Integer> >() {

public int compare(Map.Entry<Character, Integer> o1,

Map.Entry<Character, Integer> o2)

{

return (o2.getValue()).compareTo(o1.getValue());

}

});

HashMap<Character, Integer> descending_order_symbol_frequency_distribution_map = new LinkedHashMap<Character, Integer>();

for (Map.Entry<Character, Integer> m : ele_list) {

descending_order_symbol_frequency_distribution_map.put(m.getKey(), m.getValue());

}

System.out.println("Frequency distribution table, in non-ascending order by frequency.");

for (Map.Entry mapElement : descending_order_symbol_frequency_distribution_map.entrySet())

{

System.out.println("\""+(char)mapElement.getKey()+"\" : "+(int)mapElement.getValue());

}

System.out.println(content);

System.out.println(encoded_string);

//Multiply actual string length with 8 as it takes 8 bits for each character

int original_bytes=content.length()*8;

int encoded_bytes=encoded_string.length();

System.out.println("The amount of bytes needed to store the encoded text:"+encoded_bytes);

float saving_percentage=(original_bytes-encoded_bytes)*100/((float)original_bytes);

System.out.println("Saving percentage compared to the amount of bytes needed for the original text:"+saving_percentage+"%");

}

// Driver Function

public static void main(String[] args) throws IOException

{

String content=load_data("stringData.txt");

Map<Character, Integer> symbol_frequency_distribution_map=compute_fd(content);

TreeNode root=huffman_tree(symbol_frequency_distribution_map);

Map<Character, String> huffman_code_map=huffman_code(root);

String encoded_string=encode(huffman_code_map,content);

process_results(symbol_frequency_distribution_map,content,encoded_string);

}

}

Output:

Frequency distribution table, in non-ascending order by frequency. "": 4 "0" : 30 "a" : 2 "S" : 2 "i" : 2 "b" : 1 "d" : 1 "g" : 1 "y" : 1 "." : 1 sai is a good boy. 010011100001000100001100110011111111011001101011110101011 The amount of bytes needed to store the encoded text:57 Saving percentage compared to the amount of bytes needed for the original text:60.416668%