# Introduction to Huffman Coding Huffman Coding is a data compression algorithm created by [David A. Huffman](https://en.wikipedia.org/wiki/David_A._Huffman) in 1952. It is an **entropy-based** algorithm that uses a *greedy approach* to generate a prefix-free code for a given set of symbols and associated probability/frequency of occurrence. The generated code is optimal in the sense that it minimizes the expected length of the encoded message. Huffman coding works by assigning a unique binary string to each character in a given dataset. The codes are assigned in such a way that the length of the code is inversely proportional to the frequency of occurrence of the character. Characters that occur more often in the dataset are assigned shorter codes than those that occur less frequently. The resulting string of 0s and 1s, when combined with a Huffman tree, can be used to decode the encoded message. Huffman coding is widely used in many applications, such as data compression, data transmission and image processing. It is also used in many communication protocols, such as GSM, JPEG and MPEG.

Huffman Coding is a Greedy Algorithm used for compressing data. It works by assigning variable length codes to characters, which allows for a more efficient representation of the data. The algorithm works by creating a binary tree, with the least frequent characters at the deepest level of the tree. We then traverse the tree, creating a code for each character based on the path from the root of the tree to the character's node. ## Sample Code ``` // Create a HashMap to store character frequencies Map frequencies = new HashMap<>(); // Populate the HashMap with character frequencies frequencies.put('a', 5); frequencies.put('b', 9); frequencies.put('c', 12); frequencies.put('d', 13); frequencies.put('e', 16); frequencies.put('f', 45); // Create a Priority Queue to store nodes of the Huffman tree PriorityQueue pq = new PriorityQueue(); // Create Huffman tree nodes for each character and add them to the Priority Queue for (Map.Entry entry : frequencies.entrySet()) { Node node = new Node(entry.getKey(), entry.getValue()); pq.add(node); } // Build the Huffman tree while (pq.size() > 1) { // Extract two nodes with the lowest frequency Node left = pq.poll(); Node right = pq.poll(); // Create a new internal node with the frequency of the two nodes int sum = left.frequency + right.frequency; Node parent = new Node(null, sum); // Set the two extracted nodes as children of the new internal node parent.left = left; parent.right = right; // Add the new internal node to the Priority Queue pq.add(parent); } // Traverse the tree to extract the Huffman codes Map codes = new HashMap<>(); extractCodes(pq.poll(), "", codes); // Print the Huffman codes System.out.println(codes); // Recursive function to traverse the tree and extract the codes public void extractCodes(Node node, String code, Map codes) { if (node == null) { return; } if (node.character != null) { codes.put(node.character, code); } extractCodes(node.left, code + "0", codes); extractCodes(node.right, code + "1", codes); } ```