Huffman Encoding implementation in java

 Huffman Encoding is an algorithm which provides compression of data. The encoding deals with the character frequencies to reduce the size of data.

Java implementation:

              This process starts with finding the frequency of each character. Next, it creates the Huffman Tree by the use of a  priority  queue.

Finally, it develops the binary codes for each character.

Program:

import java.util.PriorityQueue;

import java.util.HashMap;

import java.util.Map;

// let us create the class with character with its frequency

class HuffmanNode implements Comparable<HuffmanNode> {

    char h_char;

    int h_freq;

    HuffmanNode h_left, h_right;

    HuffmanNode(char h_char, int h_freq) {

        this.h_char = h_char;

        this.h_freq = h_freq;

    }

 

    @Override

    public int compareTo(HuffmanNode other) {

        return this.h_freq - other.h_freq;

    }

}

 

// class for Huffman Encoding technique

public class HuffmanEncodingEg {

    public static Map<Character, String> huffmanCodes = new HashMap<>();

    // recursive method to generate Huffman code

    public static void generateIt(HuffmanNode root, String code) {

        if (root == null) return;

        if (root.h_left == null && root.h_right == null) {

            huffmanCodes.put(root.h_char, code);

        }

        generateIt(root.h_left, code + "0");

        generateIt(root.h_right, code + "1");

    }

    // Develop the Huffman Tree and code

    public static Map<Character, String> buildHuffmanTree(Map<Character, Integer> freqMap) {

        PriorityQueue<HuffmanNode> pq1 = new PriorityQueue<>();

        for (Map.Entry<Character, Integer> entry : freqMap.entrySet()) {

            pq1.add(new HuffmanNode(entry.getKey(), entry.getValue()));

        }

        while (pq1.size() > 1) {

            HuffmanNode h_left = pq1.poll();

            HuffmanNode h_right = pq1.poll();

            HuffmanNode newNode = new HuffmanNode('-', h_left.h_freq + h_right.h_freq);

            newNode.h_left = h_left;

            newNode.h_right = h_right;

            pq1.add(newNode);

        }

        HuffmanNode root = pq1.poll();

        generateIt(root, "");

        return huffmanCodes;

    }

    public static void main(String[] args) {

        String txt = "It is huffman coding Sample";

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

        for (char c : txt.toCharArray()) {

            freqMap1.put(c, freqMap1.getOrDefault(c, 0) + 1);

        }

        Map<Character, String> huffmanCodes = buildHuffmanTree(freqMap1);

        System.out.println("The Huffman Codes are:");

        for (Map.Entry<Character, String> entry : huffmanCodes.entrySet()) {

            System.out.println(entry.getKey() + ": " + entry.getValue());

        }

    }

}

Output:

C:\raji\blog>javac HuffmanEncodingEg.java

C:\raji\blog>java HuffmanEncodingEg

The Huffman Codes are:

p: 00

a: 101

S: 111

e: 110

l: 100

m: 01

Hope this code will help you! Keep coding!!!!