Question

IN JAVA:

Huffman Coding

Objective:

Implement the Huffman Coding algorithm, analyze a text file, and print out the codes for each letter. Huffman coding is used as a way to encode data in such a way that the symbols that appear more frequently have a smaller code representation vs. ones that appear more infrequently. This is generally done by constructing a binary tree, where each link has a value 0 or 1.

Demonstrate the algorithm works by printing out the frequency of each letter along with its code with at least 5 examples.

Answer 1

CODE

import java.util.PriorityQueue;

import java.util.Scanner;

import java.util.Comparator;

// node class is the basic structure

// of each node present in the Huffman - tree.

class HuffmanNode {

int data;

char c;

HuffmanNode left;

HuffmanNode right;

}

// comparator class helps to compare the node

// on the basis of one of its attribute.

// Here we will be compared

// on the basis of data values of the nodes.

class CustomComparator implements Comparator<HuffmanNode> {

public int compare(HuffmanNode x, HuffmanNode y)

{

return x.data - y.data;

}

}

public class Main {

// recursive function to print the

// huffman-code through the tree traversal.

// Here s is the huffman - code generated.

public static void printCode(HuffmanNode root, String s)

{

// base case; if the left and right are null

// then its a leaf node and we print

// the code s generated by traversing the tree.

if (root.left

== null

&& root.right

== null

&& Character.isLetter(root.c)) {

// c is the character in the node

System.out.println(root.c + ":" + s);

return;

}

// if we go to left then add "0" to the code.

// if we go to the right add"1" to the code.

// recursive calls for left and

// right sub-tree of the generated tree.

printCode(root.left, s + "0");

printCode(root.right, s + "1");

}

public static void generateHuffmanCode(char[] charArray, int[] charfreq, int n) {

// creating a priority queue q.

// makes a min-priority queue(min-heap).

PriorityQueue<HuffmanNode> q = new PriorityQueue<HuffmanNode>(n, new CustomComparator());

for (int i = 0; i < n; i++) {

// creating a Huffman node object

// and add it to the priority queue.

HuffmanNode hn = new HuffmanNode();

hn.c = charArray[i];

hn.data = charfreq[i];

hn.left = null;

hn.right = null;

// add functions adds

// the huffman node to the queue.

q.add(hn);

}

// create a root node

HuffmanNode root = null;

// Here we will extract the two minimum value

// from the heap each time until

// its size reduces to 1, extract until

// all the nodes are extracted.

while (q.size() > 1) {

// first min extract.

HuffmanNode x = q.peek();

q.poll();

// second min extarct.

HuffmanNode y = q.peek();

q.poll();

// new node f which is equal

HuffmanNode f = new HuffmanNode();

// to the sum of the frequency of the two nodes

// assigning values to the f node.

f.data = x.data + y.data;

f.c = '-';

// first extracted node as left child.

f.left = x;

// second extracted node as the right child.

f.right = y;

// marking the f node as the root node.

root = f;

// add this node to the priority-queue.

q.add(f);

}

// print the codes by traversing the tree

printCode(root, "");

}

// main function

public static void main(String[] args)

{

// number of characters.

int n = 6;

char[] charArray1 = { 'a', 'b', 'c', 'd', 'e', 'f' };

int[] charfreq1 = { 5, 9, 12, 13, 16, 45 };

generateHuffmanCode(charArray1, charfreq1, n);

System.out.println();

char[] charArray2 = { 'a', 'b', 'c', 'd', 'e', 'f' };

int[] charfreq2 = { 3, 6, 1, 9, 14, 7 };

generateHuffmanCode(charArray2, charfreq2, n);

System.out.println();

char[] charArray3 = { 'a', 'b', 'c', 'd', 'e', 'f' };

int[] charfreq3 = { 15, 17, 42, 1, 89, 11 };

generateHuffmanCode(charArray3, charfreq3, n);

System.out.println();

char[] charArray4 = { 'a', 'b', 'c', 'd', 'e', 'f' };

int[] charfreq4 = { 15, 14, 67, 11, 18, 9 };

generateHuffmanCode(charArray4, charfreq4, n);

System.out.println();

char[] charArray5 = { 'a', 'b', 'c', 'd', 'e', 'f' };

int[] charfreq5 = { 45, 13, 19, 15, 15, 10 };

generateHuffmanCode(charArray5, charfreq5, n);

}

}

OUTPUT

f:0

c:100

d:101

a:1100

b:1101

e:111

f:00

d:01

c:1000

a:1001

b:101

e:11

c:00

b:010

d:01100

f:01101

a:0111

e:1

c:0

b:100

a:101

e:110

f:1110

d:1111

a:0

e:100

d:101

c:110

f:1110

b:1111