Implement Huffman Encoding using java
CODE:
import java.util.Comparator;
import java.util.HashMap;
import java.util.Scanner;
import java.util.Map;
import java.util.PriorityQueue;
class Node
{
Character ch;
Integer freq;
Node left = null, right = null;
Node(Character ch, Integer freq)
{
this.ch = ch;
this.freq = freq;
}
public Node(Character ch, Integer freq, Node left, Node right)
{
this.ch = ch;
this.freq = freq;
this.left = left;
this.right = right;
}
}
class Main
{
public static void encode(Node root, String str,
Map<Character, String> huffmanCode)
{
if (root == null) {
return;
}
if (isLeaf(root)) {
huffmanCode.put(root.ch, str.length() > 0 ? str : "1");
}
encode(root.left, str + '0', huffmanCode);
encode(root.right, str + '1', huffmanCode);
}
public static boolean isLeaf(Node root) {
return root.left == null && root.right == null;
}
public static void build(String text)
{
if (text == null || text.length() == 0) {
return;
}
Map<Character, Integer> freq = new HashMap<>();
for (char c: text.toCharArray()) {
freq.put(c, freq.getOrDefault(c, 0) + 1);
}
PriorityQueue<Node> pq;
pq = new PriorityQueue<>(Comparator.comparingInt(l -> l.freq));
for (var entry: freq.entrySet()) {
pq.add(new Node(entry.getKey(), entry.getValue()));
}
while (pq.size() != 1)
{
Node left = pq.poll();
Node right = pq.poll();
int sum = left.freq + right.freq;
pq.add(new Node(null, sum, left, right));
}
Node root = pq.peek();
Map<Character, String> huffmanCode = new HashMap<>();
encode(root, "", huffmanCode);
StringBuilder arr = new StringBuilder();
for (char c: text.toCharArray()) {
arr.append(huffmanCode.get(c));
}
System.out.println(arr);
}
public static void main(String[] args)
{
String s="Huffman coding is a data compression algorithm";
build(s);
}
}
INPUT:
Huffman coding is a data compression algorithm
OUTPUT:
0011111010100010001101101001111000010111100001110011101101001110101010001010000000101100001010000101111101111011111001001101010101011101111011110001011011001101111110011110110001101001011
Contributed by a student of NIT SILCHAR, INDIA
0 Comments