Huffman-kodningsalgoritmen blev foreslået af David A. Huffman i 1950. Det er en tabsfri datakomprimering mekanisme. Det er også kendt som datakomprimeringskodning. Det er meget udbredt til billedkomprimering (JPEG eller JPG). I dette afsnit vil vi diskutere Huffman-kodning og afkodning, og implementerer også dens algoritme i et Java-program.
Vi ved, at hvert tegn er en sekvens af 0'er og 1'er og lagrer ved hjælp af 8-bit. Mekanismen kaldes kodning med fast længde fordi hvert tegn bruger det samme antal fast-bit lager.
sortering array i java
Her kommer et spørgsmål op, er det muligt at reducere mængden af plads, der kræves for at gemme en karakter?
Ja, det er muligt ved at bruge kodning med variabel længde. I denne mekanisme udnytter vi nogle karakterer, der forekommer hyppigere sammenlignet med andre karakterer. I denne kodningsteknik kan vi repræsentere det samme stykke tekst eller streng ved at reducere antallet af bits.
Huffman-kodning
Huffman-kodning implementerer følgende trin.
- Den tildeler en kode med variabel længde til alle de givne tegn.
- Kodelængden af et tegn afhænger af, hvor ofte det forekommer i den givne tekst eller streng.
- Et tegn får den mindste kode, hvis det forekommer ofte.
- Et tegn får den største kode, hvis det forekommer mindst.
Huffman-kodning følger en præfiksregel der forhindrer tvetydighed under afkodning. Reglen sikrer også, at den kode, der er tildelt tegnet, ikke behandles som et præfiks for den kode, der er tildelt noget andet tegn.
Der er følgende to hovedtrin involveret i Huffman-kodning:
- Konstruer først en Huffman træ fra den givne inputstreng eller tegn eller tekst.
- Tildel en Huffman-kode til hver karakter ved at gå over træet.
Lad os kortfatte de to ovenstående trin.
Huffman træ
Trin 1: For hver karakter i noden skal du oprette en bladnode. Bladknuden på et tegn indeholder frekvensen af det pågældende tegn.
Trin 2: Indstil alle noderne i sorteret rækkefølge efter deres frekvens.
Trin 3: Der kan eksistere en tilstand, hvor to noder kan have samme frekvens. I et sådant tilfælde skal du gøre følgende:
- Opret en ny intern node.
- Frekvensen af noden vil være summen af frekvensen af de to noder, der har samme frekvens.
- Marker den første node som venstre underordnet og en anden knude som højre underordnet af den nyoprettede interne knude.
Trin 4: Gentag trin 2 og 3, indtil alle knudepunkter danner et enkelt træ. Således får vi et Huffman-træ.
Huffman-kodningseksempel
Antag, at vi skal kode streng Abra Cadabra. Bestem følgende:
- Huffman-kode for alle karaktererne
- Gennemsnitlig kodelængde for den givne streng
- Længden af den kodede streng
(i) Huffman-kode for alle karaktererne
For at bestemme koden for hvert tegn konstruerer vi først en Huffman træ.
matrix multiplikation i c
Trin 1: Lav karakterpar og deres frekvenser.
(a, 5), (b, 2), (c, 1), (d, 1), (r, 2)
Trin 2: Sorter par med hensyn til frekvens, vi får:
(c, 1), (d, 1), (b, 2) (r, 2), (a, 5)
Trin 3: Vælg de to første karakterer, og sæt dem sammen under en overordnet node.
Vi observerer, at en forældreknude ikke har en frekvens, så vi skal tildele en frekvens til den. Den overordnede nodefrekvens vil være summen af dens underordnede noder (venstre og højre), dvs. 1+1= 2.
Trin 4: Gentag trin 2 og 3, indtil vi får et enkelt træ.
Vi observerer, at parrene allerede er sorteret (efter trin 2). Igen skal du vælge de første to par og slutte dig til dem.
Vi observerer, at en forældreknude ikke har en frekvens, så vi skal tildele en frekvens til den. Overordnet node frekvens vil være summen af dens underordnede noder (venstre og højre), dvs. 2+2= 4.
fjerner sidste commit git
Igen tjekker vi, om parrene er på en sorteret måde eller ej. På dette trin skal vi sortere parrene.
Ifølge trin 3 skal du vælge de to første par og slutte dig til dem, vi får:
Vi observerer, at en forældreknude ikke har en frekvens, så vi skal tildele en frekvens til den. Den overordnede nodefrekvens vil være summen af dens underordnede noder (venstre og højre), dvs. 2+4= 6.
Igen tjekker vi, om parrene er på en sorteret måde eller ej. På dette trin skal vi sortere parrene. Efter sortering ser træet sådan ud:
Ifølge trin 3 skal du vælge de to første par og slutte dig til dem, vi får:
Vi observerer, at en forældreknude ikke har en frekvens, så vi skal tildele en frekvens til den. Overordnet node frekvens vil være summen af dens underordnede noder (venstre og højre), dvs. 5+6= elleve.
Derfor får vi et enkelt træ.
Til sidst finder vi koden for hvert tegn ved hjælp af ovenstående træ. Tildel en vægt til hver kant. Bemærk, at hver venstre kantvægtet er 0 og højre kantvægtet er 1.
Vi observerer, at input-tegn kun præsenteres i leave noder, og de interne noder har nulværdier. For at finde Huffman-koden for hvert tegn skal du gå hen over Huffman-træet fra rodknuden til bladknuden for det særlige tegn, som vi ønsker at finde kode for. Tabellen beskriver koden og kodelængden for hvert tegn.
task manager linux
| Karakter | Frekvens | Kode | Kodens længde |
|---|---|---|---|
| EN | 5 | 0 | 1 |
| B | 2 | 111 | 3 |
| C | 1 | 1100 | 4 |
| D | 1 | 1101 | 4 |
| R | 2 | 10 | 2 |
Vi observerer, at det hyppigste tegn får den korteste kodelængde, og det mindre hyppige tegn får den største kodelængde.
Nu kan vi kode strengen (Abra Cadabra) som vi har taget ovenfor.
0 111 10 0 1100 0 1101 0 111 10 0
(ii) Gennemsnitlig kodelængde for strengen
Den gennemsnitlige kodelængde af Huffman-træet kan bestemmes ved at bruge formlen nedenfor:
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 af den kodede streng
Længden af den kodede meddelelse kan bestemmes ved at bruge følgende formel:
length= Total number of characters in the text x Average code length per character
= 11 x 2,09090909
= 23 bit
Huffman-kodningsalgoritme
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 er en grådig algoritme. Da algoritmen på hvert trin leder efter de bedste tilgængelige muligheder.
Tidskompleksiteten af Huffman-kodningen er O(nlogn). Hvor n er antallet af tegn i den givne tekst.
Huffman afkodning
Huffman-afkodning er en teknik, der konverterer de kodede data til indledende data. Som vi har set i kodning, er Huffman-træet lavet til en inputstreng, og tegnene afkodes baseret på deres placering i træet. Afkodningsprocessen er som følger:
fjern sidste tegn fra streng
- Begynd at krydse over træet fra rod node og søg efter tegnet.
- Hvis vi flytter til venstre i det binære træ, tilføj 0 til koden.
- Hvis vi bevæger os til højre i det binære træ, tilføj 1 til koden.
Den underordnede node indeholder inputtegnet. Den tildeles koden dannet af efterfølgende 0'ere og 1'ere. Tidskompleksiteten ved afkodning af en streng er På), hvor n er længden af strengen.
Huffman Java-program til kodning og afkodning
I det følgende program har vi brugt datastrukturer som prioritetskøer, stakke og træer til at designe en kompressions- og dekompressionslogik. Vi vil basere vores hjælpeprogrammer på den udbredte algoritmiske teknik med 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