Het Huffman-coderingsalgoritme werd voorgesteld door David A. Huffman in 1950. Het is een verliesloze datacompressie mechanisme. Het is ook bekend als codering van gegevenscompressie. Het wordt veel gebruikt bij het comprimeren van afbeeldingen (JPEG of JPG). In deze sectie bespreken we de Huffman-codering En decoderen, en implementeer ook het algoritme in een Java-programma.
We weten dat elk teken een reeks nullen en enen is en wordt opgeslagen met behulp van 8 bits. Het mechanisme wordt genoemd codering met vaste lengte omdat elk teken hetzelfde aantal vaste bitopslag gebruikt.
java elseif
Hier rijst een vraag, Is het mogelijk om de hoeveelheid ruimte die nodig is om een personage op te slaan te verminderen?
Ja, het is mogelijk door gebruik te maken van codering met variabele lengte. In dit mechanisme maken we gebruik van enkele karakters die vaker voorkomen in vergelijking met andere karakters. Bij deze coderingstechniek kunnen we hetzelfde stuk tekst of tekenreeks weergeven door het aantal bits te verminderen.
Huffman-codering
Huffman-codering implementeert de volgende stappen.
- Het wijst een code van variabele lengte toe aan alle gegeven tekens.
- De codelengte van een teken hangt af van hoe vaak het voorkomt in de gegeven tekst of string.
- Een karakter krijgt de kleinste code als het vaak voorkomt.
- Een karakter krijgt de grootste code als deze het minst voorkomt.
Huffman-codering volgt a voorvoegselregel dat voorkomt dubbelzinnigheid tijdens het decoderen. De regel zorgt er ook voor dat de code die aan het teken is toegewezen, niet wordt behandeld als een voorvoegsel van de code die aan een ander teken is toegewezen.
Er zijn de volgende twee belangrijke stappen betrokken bij Huffman-codering:
- Bouw eerst a Huffman-boom uit de gegeven invoerreeks of tekens of tekst.
- Wijs een Huffman-code toe aan elk personage door door de boom te lopen.
Laten we de bovenstaande twee stappen kort samenvatten.
Huffman Boom
Stap 1: Maak voor elk teken van het knooppunt een bladknooppunt. Het bladknooppunt van een karakter bevat de frequentie van dat karakter.
Stap 2: Zet alle knooppunten in gesorteerde volgorde op basis van hun frequentie.
Stap 3: Er kan een situatie bestaan waarin twee knooppunten dezelfde frequentie kunnen hebben. Doe in een dergelijk geval het volgende:
- Maak een nieuw intern knooppunt.
- De frequentie van het knooppunt is de som van de frequentie van de twee knooppunten die dezelfde frequentie hebben.
- Markeer het eerste knooppunt als het linkerkind en een ander knooppunt als het rechterkind van het nieuw gemaakte interne knooppunt.
Stap 4: Herhaal stap 2 en 3 totdat alle knooppunten één enkele boom vormen. We krijgen dus een Huffman-boom.
Huffman-coderingsvoorbeeld
Stel dat we een string moeten coderen Abra Cadabra. Bepaal het volgende:
- Huffman-code voor alle karakters
- Gemiddelde codelengte voor de gegeven String
- Lengte van de gecodeerde tekenreeks
(i) Huffman-code voor alle karakters
Om de code voor elk karakter te bepalen, construeren we eerst a Huffman-boom.
Stap 1: Maak paren van karakters en hun frequenties.
voorbeelden van binaire bomen
(a, 5), (b, 2), (c, 1), (d, 1), (r, 2)
Stap 2: Sorteer paren op frequentie, we krijgen:
(c, 1), (d, 1), (b, 2) (r, 2), (a, 5)
Stap 3: Kies de eerste twee tekens en voeg ze samen onder een bovenliggend knooppunt.
We zien dat een ouderknooppunt geen frequentie heeft, dus moeten we er een frequentie aan toewijzen. De frequentie van het ouderknooppunt zal de som zijn van de onderliggende knooppunten (links en rechts), d.w.z. 1+1= 2.
Stap 4: Herhaal stap 2 en 3 totdat we een enkele boom krijgen.
We zien dat de paren al gesorteerd zijn (volgens stap 2). Kies opnieuw de eerste twee paren en sluit je bij hen aan.
We zien dat een ouderknooppunt geen frequentie heeft, dus moeten we er een frequentie aan toewijzen. De frequentie van het ouderknooppunt zal de som zijn van de onderliggende knooppunten (links en rechts), d.w.z. 2+2= 4.
Opnieuw controleren we of de paren gesorteerd zijn of niet. Bij deze stap moeten we de paren sorteren.
Volgens stap 3, kies de eerste twee paren en voeg ze samen, we krijgen:
We zien dat een ouderknooppunt geen frequentie heeft, dus moeten we er een frequentie aan toewijzen. De frequentie van het ouderknooppunt zal de som zijn van de onderliggende knooppunten (links en rechts), d.w.z. 2+4= 6.
wumpus wereld
Opnieuw controleren we of de paren gesorteerd zijn of niet. Bij deze stap moeten we de paren sorteren. Na het sorteren ziet de boom er als volgt uit:
Volgens stap 3, kies de eerste twee paren en voeg ze samen, we krijgen:
We zien dat een ouderknooppunt geen frequentie heeft, dus moeten we er een frequentie aan toewijzen. De frequentie van het ouderknooppunt zal de som zijn van de onderliggende knooppunten (links en rechts), d.w.z. 5+6= elf.
Daarom krijgen we een enkele boom.
Eindelijk zullen we de code voor elk karakter vinden met behulp van de bovenstaande boom. Wijs een gewicht toe aan elke rand. Merk op dat elk linkerrandgewogen is 0 en de rechterrandgewogen is 1.
We zien dat invoertekens alleen worden weergegeven in de verlofknooppunten en dat de interne knooppunten nulwaarden hebben. Om de Huffman-code voor elk teken te vinden, doorloopt u de Huffman-boom vanaf het hoofdknooppunt naar het bladknooppunt van dat specifieke teken waarvoor we de code willen vinden. De tabel beschrijft de code en codelengte voor elk teken.
| Karakter | Frequentie | Code | Codelengte |
|---|---|---|---|
| A | 5 | 0 | 1 |
| B | 2 | 111 | 3 |
| C | 1 | 1100 | 4 |
| D | 1 | 1101 | 4 |
| R | 2 | 10 | 2 |
We zien dat het meest voorkomende teken de kortste codelengte krijgt en het minder voorkomende teken de grootste codelengte.
Nu kunnen we de string coderen (Abra Cadabra) die we hierboven hebben genomen.
verschil tussen leeuw en tijger
0 111 10 0 1100 0 1101 0 111 10 0
(ii) Gemiddelde codelengte voor de string
De gemiddelde codelengte van de Huffman-boom kan worden bepaald met behulp van de onderstaande formule:
Average Code Length = ∑ ( frequency × code length ) / ∑ ( frequency )
= { (5 x 1) + (2 x 3) + (1 x 4) + (1 x 4) + (2 x 2) } / (5+2+1+1+2)
= 2,09090909
(iii) Lengte van de gecodeerde string
De lengte van het gecodeerde bericht kan worden bepaald met behulp van de volgende formule:
length= Total number of characters in the text x Average code length per character
= 11 x 2,09090909
= 23 bits
Huffman-coderingsalgoritme
Huffman (C) n=|C| Q=C for i=1 to n-1 do z=allocate_Node() x=left[z]=Extract_Min(Q) y=right[z]=Extract_Min(Q) f[z]=f[x]+f[y] Insert(Q,z) return Extract_Min(Q)
Het Huffman-algoritme is een hebzuchtig algoritme. Omdat het algoritme in elke fase zoekt naar de best beschikbare opties.
De tijdscomplexiteit van de Huffman-codering is O(nlogn). Waarbij n het aantal tekens in de gegeven tekst is.
Huffman-decodering
Huffman-decodering is een techniek die de gecodeerde gegevens omzet in initiële gegevens. Zoals we bij het coderen hebben gezien, is de Huffman-boom gemaakt voor een invoerreeks en worden de karakters gedecodeerd op basis van hun positie in de boom. Het decoderingsproces is als volgt:
Java-collecties Java
- Begin met het doorkruisen van de boom vanaf de wortel knooppunt en zoek naar het teken.
- Als we naar links gaan in de binaire boom, optellen 0 naar de code.
- Als we naar rechts in de binaire boom gaan, optellen 1 naar de code.
Het onderliggende knooppunt bevat het invoerteken. Er wordt de code aan toegewezen die wordt gevormd door opeenvolgende nullen en enen. De tijdscomplexiteit van het decoderen van een string is: Op), waarbij n de lengte van de string is.
Huffman Java-programma coderen en decoderen
In het volgende programma hebben we datastructuren zoals prioriteitswachtrijen, stapels en bomen gebruikt om een compressie- en decompressielogica te ontwerpen. We zullen onze hulpprogramma's baseren op de veelgebruikte algoritmische techniek van Huffman-codering.
HuffmanCode.java
import java.util.Comparator; import java.util.HashMap; import java.util.Map; import java.util.PriorityQueue; //defining a class that creates nodes of the tree class Node { //storing character in ch variable of type character Character ch; //storing frequency in freq variable of type int Integer freq; //initially both child (left and right) are null Node left = null; Node right = null; //creating a constructor of the Node class Node(Character ch, Integer freq) { this.ch = ch; this.freq = freq; } //creating a constructor of the Node class public Node(Character ch, Integer freq, Node left, Node right) { this.ch = ch; this.freq = freq; this.left = left; this.right = right; } } //main class public class HuffmanCode { //function to build Huffman tree public static void createHuffmanTree(String text) { //base case: if user does not provides string if (text == null || text.length() == 0) { return; } //count the frequency of appearance of each character and store it in a map //creating an instance of the Map Map freq = new HashMap(); //loop iterates over the string and converts the text into character array for (char c: text.toCharArray()) { //storing character and their frequency into Map by invoking the put() method freq.put(c, freq.getOrDefault(c, 0) + 1); } //create a priority queue that stores current nodes of the Huffman tree. //here a point to note that the highest priority means the lowest frequency PriorityQueue pq = new PriorityQueue(Comparator.comparingInt(l -> l.freq)); //loop iterate over the Map and returns a Set view of the mappings contained in this Map for (var entry: freq.entrySet()) { //creates a leaf node and add it to the queue pq.add(new Node(entry.getKey(), entry.getValue())); } //while loop runs until there is more than one node in the queue while (pq.size() != 1) { //removing the nodes having the highest priority (the lowest frequency) from the queue Node left = pq.poll(); Node right = pq.poll(); //create a new internal node with these two nodes as children and with a frequency equal to the sum of both nodes' frequencies. Add the new node to the priority queue. //sum up the frequency of the nodes (left and right) that we have deleted int sum = left.freq + right.freq; //adding a new internal node (deleted nodes i.e. right and left) to the queue with a frequency that is equal to the sum of both nodes pq.add(new Node(null, sum, left, right)); } //root stores pointer to the root of Huffman Tree Node root = pq.peek(); //trace over the Huffman tree and store the Huffman codes in a map Map huffmanCode = new HashMap(); encodeData(root, '', huffmanCode); //print the Huffman codes for the characters System.out.println('Huffman Codes of the characters are: ' + huffmanCode); //prints the initial data System.out.println('The initial string is: ' + text); //creating an instance of the StringBuilder class StringBuilder sb = new StringBuilder(); //loop iterate over the character array for (char c: text.toCharArray()) { //prints encoded string by getting characters sb.append(huffmanCode.get(c)); } System.out.println('The encoded string is: ' + sb); System.out.print('The decoded string is: '); if (isLeaf(root)) { //special case: For input like a, aa, aaa, etc. while (root.freq-- > 0) { System.out.print(root.ch); } } else { //traverse over the Huffman tree again and this time, decode the encoded string int index = -1; while (index <sb.length() - 1) { index="decodeData(root," index, sb); } traverse the huffman tree and store codes in a map function that encodes data public static void encodedata(node root, string str, huffmancode) if (root="=" null) return; checks node is leaf or not (isleaf(root)) huffmancode.put(root.ch, str.length()> 0 ? str : '1'); } encodeData(root.left, str + '0', huffmanCode); encodeData(root.right, str + '1', huffmanCode); } //traverse the Huffman Tree and decode the encoded string function that decodes the encoded data public static int decodeData(Node root, int index, StringBuilder sb) { //checks if the root node is null or not if (root == null) { return index; } //checks if the node is a leaf node or not if (isLeaf(root)) { System.out.print(root.ch); return index; } index++; root = (sb.charAt(index) == '0') ? root.left : root.right; index = decodeData(root, index, sb); return index; } //function to check if the Huffman Tree contains a single node public static boolean isLeaf(Node root) { //returns true if both conditions return ture return root.left == null && root.right == null; } //driver code public static void main(String args[]) { String text = 'javatpoint'; //function calling createHuffmanTree(text); } } </sb.length()> Uitgang:
Huffman Codes of the characters are: {p=000, a=110, t=111, v=001, i=010, j=011, n=100, o=101} The initial string is: javatpoint The encoded string is: 011110001110111000101010100111 The decoded string is: javatpoint