Skip to content

Instantly share code, notes, and snippets.

@ahmedengu
Last active March 9, 2022 20:15
Show Gist options
  • Save ahmedengu/aa8d85b12fccf0d08e895807edee7603 to your computer and use it in GitHub Desktop.
Save ahmedengu/aa8d85b12fccf0d08e895807edee7603 to your computer and use it in GitHub Desktop.
Huffman coding and decoding in java
import java.io.File;
import java.io.FileNotFoundException;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.TreeMap;
/* Huffman coding , decoding */
public class Huffman {
static final boolean readFromFile = false;
static final boolean newTextBasedOnOldOne = false;
static PriorityQueue<Node> nodes = new PriorityQueue<>((o1, o2) -> (o1.value < o2.value) ? -1 : 1);
static TreeMap<Character, String> codes = new TreeMap<>();
static String text = "";
static String encoded = "";
static String decoded = "";
static int ASCII[] = new int[128];
public static void main(String[] args) throws FileNotFoundException {
Scanner scanner = (readFromFile) ? new Scanner(new File("input.txt")) : new Scanner(System.in);
int decision = 1;
while (decision != -1) {
if (handlingDecision(scanner, decision)) continue;
decision = consoleMenu(scanner);
}
}
private static int consoleMenu(Scanner scanner) {
int decision;
System.out.println("\n---- Menu ----\n" +
"-- [-1] to exit \n" +
"-- [1] to enter new text\n" +
"-- [2] to encode a text\n" +
"-- [3] to decode a text");
decision = Integer.parseInt(scanner.nextLine());
if (readFromFile)
System.out.println("Decision: " + decision + "\n---- End of Menu ----\n");
return decision;
}
private static boolean handlingDecision(Scanner scanner, int decision) {
if (decision == 1) {
if (handleNewText(scanner)) return true;
} else if (decision == 2) {
if (handleEncodingNewText(scanner)) return true;
} else if (decision == 3) {
handleDecodingNewText(scanner);
}
return false;
}
private static void handleDecodingNewText(Scanner scanner) {
System.out.println("Enter the text to decode:");
encoded = scanner.nextLine();
System.out.println("Text to Decode: " + encoded);
decodeText();
}
private static boolean handleEncodingNewText(Scanner scanner) {
System.out.println("Enter the text to encode:");
text = scanner.nextLine();
System.out.println("Text to Encode: " + text);
if (!IsSameCharacterSet()) {
System.out.println("Not Valid input");
text = "";
return true;
}
encodeText();
return false;
}
private static boolean handleNewText(Scanner scanner) {
int oldTextLength = text.length();
System.out.println("Enter the text:");
text = scanner.nextLine();
if (newTextBasedOnOldOne && (oldTextLength != 0 && !IsSameCharacterSet())) {
System.out.println("Not Valid input");
text = "";
return true;
}
ASCII = new int[128];
nodes.clear();
codes.clear();
encoded = "";
decoded = "";
System.out.println("Text: " + text);
calculateCharIntervals(nodes, true);
buildTree(nodes);
generateCodes(nodes.peek(), "");
printCodes();
System.out.println("-- Encoding/Decoding --");
encodeText();
decodeText();
return false;
}
private static boolean IsSameCharacterSet() {
boolean flag = true;
for (int i = 0; i < text.length(); i++)
if (ASCII[text.charAt(i)] == 0) {
flag = false;
break;
}
return flag;
}
private static void decodeText() {
decoded = "";
Node node = nodes.peek();
for (int i = 0; i < encoded.length(); ) {
Node tmpNode = node;
while (tmpNode.left != null && tmpNode.right != null && i < encoded.length()) {
if (encoded.charAt(i) == '1')
tmpNode = tmpNode.right;
else tmpNode = tmpNode.left;
i++;
}
if (tmpNode != null)
if (tmpNode.character.length() == 1)
decoded += tmpNode.character;
else
System.out.println("Input not Valid");
}
System.out.println("Decoded Text: " + decoded);
}
private static void encodeText() {
encoded = "";
for (int i = 0; i < text.length(); i++)
encoded += codes.get(text.charAt(i));
System.out.println("Encoded Text: " + encoded);
}
private static void buildTree(PriorityQueue<Node> vector) {
while (vector.size() > 1)
vector.add(new Node(vector.poll(), vector.poll()));
}
private static void printCodes() {
System.out.println("--- Printing Codes ---");
codes.forEach((k, v) -> System.out.println("'" + k + "' : " + v));
}
private static void calculateCharIntervals(PriorityQueue<Node> vector, boolean printIntervals) {
if (printIntervals) System.out.println("-- intervals --");
for (int i = 0; i < text.length(); i++)
ASCII[text.charAt(i)]++;
for (int i = 0; i < ASCII.length; i++)
if (ASCII[i] > 0) {
vector.add(new Node(ASCII[i] / (text.length() * 1.0), ((char) i) + ""));
if (printIntervals)
System.out.println("'" + ((char) i) + "' : " + ASCII[i] / (text.length() * 1.0));
}
}
private static void generateCodes(Node node, String s) {
if (node != null) {
if (node.right != null)
generateCodes(node.right, s + "1");
if (node.left != null)
generateCodes(node.left, s + "0");
if (node.left == null && node.right == null)
codes.put(node.character.charAt(0), s);
}
}
}
class Node {
Node left, right;
double value;
String character;
public Node(double value, String character) {
this.value = value;
this.character = character;
left = null;
right = null;
}
public Node(Node left, Node right) {
this.value = left.value + right.value;
character = left.character + right.character;
if (left.value < right.value) {
this.right = right;
this.left = left;
} else {
this.right = left;
this.left = right;
}
}
}
Ahmed Kamel Taha
2
Kamel
3
0101110011001100110101001110110010001011000111110111
3
0100111011001000
1
Taha
-1
Enter the text:
Text: Ahmed Kamel Taha
-- intervals --
' ' : 0.125
'A' : 0.0625
'K' : 0.0625
'T' : 0.0625
'a' : 0.1875
'd' : 0.0625
'e' : 0.125
'h' : 0.125
'l' : 0.0625
'm' : 0.125
--- Printing Codes ---
' ' : 101
'A' : 0101
'K' : 0100
'T' : 1000
'a' : 111
'd' : 1001
'e' : 001
'h' : 110
'l' : 000
'm' : 011
-- Encoding/Decoding --
Encoded Text: 0101110011001100110101001110110010001011000111110111
Decoded Text: Ahmed Kamel Taha
---- Menu ----
-- [-1] to exit
-- [1] to enter new text
-- [2] to encode a text
-- [3] to decode a text
Decision: 2
---- End of Menu ----
Enter the text to encode:
Text to Encode: Kamel
Encoded Text: 0100111011001000
---- Menu ----
-- [-1] to exit
-- [1] to enter new text
-- [2] to encode a text
-- [3] to decode a text
Decision: 3
---- End of Menu ----
Enter the text to decode:
Text to Decode: 0101110011001100110101001110110010001011000111110111
Decoded Text: Ahmed Kamel Taha
---- Menu ----
-- [-1] to exit
-- [1] to enter new text
-- [2] to encode a text
-- [3] to decode a text
Decision: 3
---- End of Menu ----
Enter the text to decode:
Text to Decode: 0100111011001000
Decoded Text: Kamel
---- Menu ----
-- [-1] to exit
-- [1] to enter new text
-- [2] to encode a text
-- [3] to decode a text
Decision: 1
---- End of Menu ----
Enter the text:
Text: Taha
-- intervals --
'T' : 0.25
'a' : 0.5
'h' : 0.25
--- Printing Codes ---
'T' : 01
'a' : 1
'h' : 00
-- Encoding/Decoding --
Encoded Text: 011001
Decoded Text: Taha
---- Menu ----
-- [-1] to exit
-- [1] to enter new text
-- [2] to encode a text
-- [3] to decode a text
Decision: -1
---- End of Menu ----
@richajain07
Copy link

It doesnot seem to work for input string containing only one character?
any inputs over it?

@lksmllr
Copy link

lksmllr commented Mar 31, 2018

I tried this with huge Data and the encoding was larger then the input

@AftabFalak
Copy link

comment ae not used. difficulty to understand

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment