Huffman coding algoritnm

Huffman coding algorithm:-

Huffman coding. Huffman Algorithm was developed by David Huffman in 1951. This is a technique which is used in a data compression or it can be said that it is a coding technique which is used for encoding data.

Huffman is widely used in all the mainstream compression formats that you might encounter - from GZIP, PKZIP (winzip etc) and BZIP2, to image formats such as JPEG and PNG.

algorithm:-

     Huffman(c)
     {
         n = |c|   //where mod of c is set of character
         make a min heap 'Q' with c       [O(n)]
         for i in range n-1
         // allocated a new node z 
         z.left = x = extract - min(Q)
         z.rigth=y= extract - min(Q)
         z.freg = x.freg + y.freg
         Insert(Q,z)
         return extract - min(Q)
     }

Let see java program using Huffman coding algorithm:-

import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.Comparator;
//createting node 
class HuffmanNode{
int data;
char c;

HuffmanNode left;
HuffmanNode right;
}  
//compare to node
class MyComparator implements Comparator<HuffmanNode>{
public int compare(HuffmanNode x, HuffmanNode y){
return x.data - y.data;
}
}

class Huffman{
public static void printCode(HuffmanNode root , String s){
        if(root.left == null && root.right == null && Character.isLetter(root.c)){
        System.out.println(root.c+ ":" + s);
        return ;
        }
    printCode(root.left, s + "0");
    printCode(root.right, s+ "1");
} 
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
        System.out.println("Enter the totle character:");
int n = sc.nextInt();

System.out.println("Enter the Characters");
        String str = sc.next();
        char[] charArray = new char[str.length()]; 
        for (int i = 0; i < str.length(); i++) { 
            charArray[i] = str.charAt(i); 
        } 
System.out.println("Enter the frequency");
int[] charfreq = new int[n];
for(int i=0; i<n; i++){
charfreq[i] = sc.nextInt();
}
        PriorityQueue<HuffmanNode> q = new PriorityQueue<HuffmanNode>(n, new MyComparator());
for(int i=0; i<n; i++){
HuffmanNode hn = new HuffmanNode();
hn.c = charArray[i];
hn.data = charfreq[i];
hn.left = null;
hn.right = null;
q.add(hn);
}
HuffmanNode root  = null;
while(q.size() > 1){
HuffmanNode x = q.peek();
q.poll();
HuffmanNode y = q.peek();
q.poll();
HuffmanNode f = new HuffmanNode();
f.data = x.data+y.data;
f.c = '-';
f.left = x;
f.right = y;
root = f;
q.add(f);
}
printCode(root, "");
}

}

Comments

Post a Comment

Popular posts from this blog

Caesar Cipher Algo

Image
Algorithm  of  Caesar Cipher Caesar Cipher  Technique is the simple and easy method of  encryption  technique. It is simple type of substitution  cipher . Each letter of plain text is replaced by a letter with some fixed number of positions down with alphabet. package clg.Cypto.assignment; import java.util.Scanner; public class CaesarCipher { // Encrypts text using shift public static StringBuffer encrypt(String text, int shift) { StringBuffer result = new StringBuffer(); for (int i = 0; i < text.length(); i++) { if (Character.isUpperCase(text.charAt(i))) { char ch = (char) (((int) text.charAt(i) + shift - 65) % 26 + 65); result.append(ch); } else { char ch = (char) (((int) text.charAt(i) + shift - 97) % 26 + 97); result.append(ch); } } return result; } // Decrypts cipher using shift public static StringBuffer decrypt(String cipher, int shift) { StringBuffer result = new StringBuffer(); for (int...
Read more

PlayFairCipher algorytham

Image
 Playfair is one of the popular cryptographic software security algorithms. This technique encrypts pairs of letters at a time and generates more secure encrypted text compare to  the simple substitution cipher like Caesar. Implementation of playfaircipher:- package com.clg.PlayFair; import java.util.Scanner; public class PlayFairCipher { static char[][] Matrix = new char[5][5];   // A 5*5 matrix of letter based on a keywords static String Alphabats = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; static String cipher = ""; static String plain = ""; public static void main(String[] args) { Scanner sc = new Scanner(System.in); System.out.println("Enter the plainText "); String plainText = sc.nextLine(); System.out.println("Enter the Key "); String key = sc.nextLine(); String encrypted = Encrypt(plainText, key);  //Encrypt method return to plain text to cipher text  System.out.println("Encrypted Massage"); Syste...
Read more