Huffman Coding Algorithm föreslogs av David A. Huffman år 1950. Det är en förlustfri datakomprimering mekanism. Det är också känt som datakomprimeringskodning. Det används ofta i bild (JPEG eller JPG) komprimering. I det här avsnittet kommer vi att diskutera Huffman-kodning och avkodning, och även implementera dess algoritm i ett Java-program.
Vi vet att varje tecken är en sekvens av 0:or och 1:or och lagras med 8-bitar. Mekanismen kallas kodning med fast längd eftersom varje tecken använder samma antal fasta bitars lagring.
strängen för lång
Här kommer en fråga, är det möjligt att minska mängden utrymme som krävs för att lagra en karaktär?
Ja, det är möjligt genom att använda kodning med variabel längd. I den här mekanismen utnyttjar vi vissa karaktärer som förekommer oftare jämfört med andra karaktärer. I denna kodningsteknik kan vi representera samma text eller sträng genom att minska antalet bitar.
Huffman-kodning
Huffman-kodning implementerar följande steg.
- Den tilldelar en kod med variabel längd till alla givna tecken.
- Kodlängden för ett tecken beror på hur ofta det förekommer i den givna texten eller strängen.
- Ett tecken får den minsta koden om den förekommer ofta.
- Ett tecken får den största koden om den förekommer minst.
Huffman-kodning följer en prefixregel som förhindrar tvetydighet vid avkodning. Regeln säkerställer också att koden som tilldelats tecknet inte behandlas som ett prefix till koden som tilldelats något annat tecken.
Det finns följande två huvudsteg involverade i Huffman-kodning:
- Konstruera först en Huffman träd från den givna inmatningssträngen eller tecken eller text.
- Tilldela en Huffman-kod till varje karaktär genom att gå över trädet.
Låt oss kortfatta ovanstående två steg.
Huffman träd
Steg 1: Skapa en lövnod för varje tecken i noden. Bladnoden för ett tecken innehåller frekvensen för det tecknet.
Steg 2: Ställ in alla noder i sorterad ordning efter deras frekvens.
Steg 3: Det kan finnas ett tillstånd där två noder kan ha samma frekvens. Gör i så fall följande:
- Skapa en ny intern nod.
- Nodens frekvens kommer att vara summan av frekvensen för de två noder som har samma frekvens.
- Markera den första noden som vänster underordnad och en annan nod som höger underordnad till den nyskapade interna noden.
Steg 4: Upprepa steg 2 och 3 tills alla noder bildar ett enda träd. Därmed får vi ett Huffman-träd.
Huffman-kodningsexempel
Anta att vi måste koda strängen Abra Cadabra. Bestäm följande:
- Huffman-kod för Alla karaktärer
- Genomsnittlig kodlängd för den givna strängen
- Längden på den kodade strängen
(i) Huffman-koden för alla karaktärer
För att bestämma koden för varje tecken, först konstruerar vi en Huffman träd.
Steg 1: Gör par av tecken och deras frekvenser.
(a, 5), (b, 2), (c, 1), (d, 1), (r, 2)
Steg 2: Sortera par med avseende på frekvens, vi får:
är proteinfett
(c, 1), (d, 1), (b, 2) (r, 2), (a, 5)
Steg 3: Välj de två första tecknen och slå ihop dem under en överordnad nod.
Vi observerar att en föräldernod inte har en frekvens så vi måste tilldela en frekvens till den. Föräldernodfrekvensen kommer att vara summan av dess underordnade noder (vänster och höger), dvs. 1+1= 2.
Steg 4: Upprepa steg 2 och 3 tills vi får ett enda träd.
Vi observerar att paren redan är sorterade (efter steg 2). Återigen, välj de två första paren och gå med dem.
Vi observerar att en föräldernod inte har en frekvens så vi måste tilldela en frekvens till den. Föräldernodfrekvensen kommer att vara summan av dess underordnade noder (vänster och höger), dvs. 2+2= 4.
en rad objekt java
Återigen kontrollerar vi om paren är på ett sorterat sätt eller inte. I det här steget måste vi sortera paren.
Enligt steg 3, välj de två första paren och gå med dem, vi får:
Vi observerar att en föräldernod inte har en frekvens så vi måste tilldela en frekvens till den. Föräldernodfrekvensen kommer att vara summan av dess underordnade noder (vänster och höger), dvs. 2+4= 6.
Återigen kontrollerar vi om paren är på ett sorterat sätt eller inte. I det här steget måste vi sortera paren. Efter sortering ser trädet ut så här:
Enligt steg 3, välj de två första paren och gå med dem, vi får:
Vi observerar att en föräldernod inte har en frekvens så vi måste tilldela en frekvens till den. Föräldernodfrekvensen kommer att vara summan av dess underordnade noder (vänster och höger), dvs. 5+6= elva.
java cast sträng till int
Därför får vi ett enda träd.
Äntligen hittar vi koden för varje tecken med hjälp av ovanstående träd. Tilldela en vikt till varje kant. Observera att varje vänster kantvikt är 0 och den högerkantviktad är 1.
Vi observerar att indatatecken endast presenteras i leave noderna och de interna noderna har nollvärden. För att hitta Huffman-koden för varje tecken, gå över Huffman-trädet från rotnoden till lövnoden för det speciella tecknet som vi vill hitta kod för. Tabellen beskriver koden och kodlängden för varje tecken.
| Karaktär | Frekvens | Koda | Kodlängd |
|---|---|---|---|
| A | 5 | 0 | 1 |
| B | 2 | 111 | 3 |
| C | 1 | 1100 | 4 |
| D | 1 | 1101 | 4 |
| R | 2 | 10 | 2 |
Vi observerar att det vanligaste tecknet får den kortaste kodlängden och det mindre frekventa tecknet får den största kodlängden.
Nu kan vi koda strängen (Abra Cadabra) som vi har tagit ovan.
0 111 10 0 1100 0 1101 0 111 10 0
(ii) Genomsnittlig kodlängd för strängen
Den genomsnittliga kodlängden för Huffman-trädet kan bestämmas genom att använda formeln nedan:
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) Längden på den kodade strängen
Längden på det kodade meddelandet kan bestämmas genom att använda följande formel:
length= Total number of characters in the text x Average code length per character
= 11 x 2,09090909
= 23 bitar
Huffman kodningsalgoritm
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)
Huffman-algoritmen är en girig algoritm. Eftersom algoritmen i varje skede letar efter de bästa tillgängliga alternativen.
Tidskomplexiteten för Huffman-kodningen är O(nlogn). Där n är antalet tecken i den givna texten.
Huffman-avkodning
Huffman-avkodning är en teknik som omvandlar kodad data till initial data. Som vi har sett i kodning är Huffman-trädet gjort för en inmatningssträng och tecknen avkodas baserat på deras position i trädet. Avkodningsprocessen är som följer:
lista sträng java
- Börja korsa över trädet från rot nod och sök efter karaktären.
- Om vi flyttar till vänster i det binära trädet, lägg till 0 till koden.
- Om vi flyttar till höger i det binära trädet, lägg till 1 till koden.
Den underordnade noden innehåller inmatningstecknet. Den tilldelas koden som bildas av efterföljande 0:or och 1:or. Tidskomplexiteten för att avkoda en sträng är På), där n är strängens längd.
Huffman Java-program för kodning och avkodning
I följande program har vi använt datastrukturer som prioritetsköer, stackar och träd för att designa en komprimerings- och dekompressionslogik. Vi kommer att basera våra verktyg på den mycket använda algoritmiska tekniken för Huffman-kodning.
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()> Produktion:
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