Huffman-kodingsalgoritmen ble foreslått av David A. Huffman i 1950. Det er en tapsfri datakomprimering mekanisme. Det er også kjent som datakomprimeringskoding. Det er mye brukt i bildekomprimering (JPEG eller JPG). I denne delen vil vi diskutere Huffman-koding og dekoding, og implementerer også algoritmen i et Java-program.
Vi vet at hvert tegn er en sekvens av 0-er og 1-er og lagres med 8-biter. Mekanismen kalles koding med fast lengde fordi hvert tegn bruker samme antall fast-bit lagring.
velg sql fra flere tabeller
Her kommer et spørsmål, er det mulig å redusere mengden plass som kreves for å lagre en karakter?
Ja, det er mulig ved å bruke koding med variabel lengde. I denne mekanismen utnytter vi noen karakterer som forekommer hyppigere sammenlignet med andre karakterer. I denne kodingsteknikken kan vi representere den samme teksten eller strengen ved å redusere antall biter.
Huffman-koding
Huffman-koding implementerer følgende trinn.
- Den tildeler en kode med variabel lengde til alle de gitte tegnene.
- Kodelengden til et tegn avhenger av hvor ofte det forekommer i den gitte teksten eller strengen.
- Et tegn får den minste koden hvis det forekommer ofte.
- Et tegn får den største koden hvis den forekommer minst.
Huffman-koding følger en prefiksregel som forhindrer tvetydighet under dekoding. Regelen sikrer også at koden som er tildelt tegnet, ikke behandles som et prefiks til koden som er tilordnet noe annet tegn.
Det er følgende to hovedtrinn involvert i Huffman-koding:
- Konstruer først en Huffman-tre fra den gitte inndatastrengen eller tegn eller tekst.
- Tildel en Huffman-kode til hver karakter ved å gå over treet.
La oss kortfatte de to ovennevnte trinnene.
Huffman-treet
Trinn 1: Lag en bladnode for hvert tegn i noden. Bladnoden til et tegn inneholder frekvensen til det tegnet.
Steg 2: Sett alle nodene i sortert rekkefølge i henhold til deres frekvens.
Trinn 3: Det kan eksistere en tilstand der to noder kan ha samme frekvens. I et slikt tilfelle, gjør følgende:
- Opprett en ny intern node.
- Frekvensen til noden vil være summen av frekvensen til de to nodene som har samme frekvens.
- Merk den første noden som venstre underordnet og en annen node som høyre underordnet til den nyopprettede interne noden.
Trinn 4: Gjenta trinn 2 og 3 til alle nodene danner et enkelt tre. Dermed får vi et Huffman-tre.
Huffman-kodingseksempel
Anta at vi må kode streng Abra Cadabra. Bestem følgende:
- Huffman-kode for Alle karakterene
- Gjennomsnittlig kodelengde for den gitte strengen
- Lengden på den kodede strengen
(i) Huffman-kode for alle karakterene
For å bestemme koden for hvert tegn, konstruerer vi først en Huffman-tre.
hva xd betyr
Trinn 1: Lag par med tegn og deres frekvenser.
(a, 5), (b, 2), (c, 1), (d, 1), (r, 2)
Steg 2: Sorter par med hensyn til frekvens, får vi:
(c, 1), (d, 1), (b, 2) (r, 2), (a, 5)
Trinn 3: Velg de to første karakterene og slå dem sammen under en overordnet node.
Vi observerer at en overordnet node ikke har en frekvens, så vi må tilordne en frekvens til den. Overordnet nodefrekvens vil være summen av dens underordnede noder (venstre og høyre), dvs. 1+1= 2.
Trinn 4: Gjenta trinn 2 og 3 til vi får et enkelt tre.
Vi observerer at parene allerede er sortert (etter trinn 2). Igjen, velg de to første parene og bli med dem.
Vi observerer at en overordnet node ikke har en frekvens, så vi må tilordne en frekvens til den. Overordnet nodefrekvens vil være summen av dens underordnede noder (venstre og høyre), dvs. 2+2= 4.
k klyngealgoritme
Igjen sjekker vi om parene er på en sortert måte eller ikke. På dette trinnet må vi sortere parene.
I henhold til trinn 3, velg de to første parene og bli med dem, får vi:
Vi observerer at en overordnet node ikke har en frekvens, så vi må tilordne en frekvens til den. Overordnet nodefrekvens vil være summen av dens underordnede noder (venstre og høyre), dvs. 2+4= 6.
Igjen sjekker vi om parene er på en sortert måte eller ikke. På dette trinnet må vi sortere parene. Etter sortering ser treet slik ut:
I henhold til trinn 3, velg de to første parene og bli med dem, får vi:
Vi observerer at en overordnet node ikke har en frekvens, så vi må tilordne en frekvens til den. Overordnet nodefrekvens vil være summen av dens underordnede noder (venstre og høyre), dvs. 5+6= elleve.
Derfor får vi et enkelt tre.
Til slutt vil vi finne koden for hvert tegn ved hjelp av treet ovenfor. Tildel en vekt til hver kant. Merk at hver venstre kantvektet er 0 og høyre kantvektet er 1.
Vi observerer at inngangstegn bare presenteres i permisjonnodene og de interne nodene har nullverdier. For å finne Huffman-koden for hvert tegn, gå over Huffman-treet fra rotnoden til bladnoden til det spesielle tegnet som vi ønsker å finne kode for. Tabellen beskriver koden og kodelengden for hvert tegn.
er tom java
| Karakter | Frekvens | Kode | Kodelengde |
|---|---|---|---|
| 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 tegnet får den korteste kodelengden og det mindre hyppige tegnet får den største kodelengden.
Nå kan vi kode strengen (Abra Cadabra) som vi har tatt ovenfor.
0 111 10 0 1100 0 1101 0 111 10 0
(ii) Gjennomsnittlig kodelengde for strengen
Den gjennomsnittlige kodelengden til Huffman-treet kan bestemmes ved å bruke formelen gitt 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) Lengden på den kodede strengen
Lengden på den kodede meldingen kan bestemmes ved å bruke følgende formel:
length= Total number of characters in the text x Average code length per character
= 11 x 2,09090909
= 23 biter
Huffman-kodingsalgoritme
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. Siden algoritmen på hvert trinn ser etter de beste tilgjengelige alternativene.
Tidskompleksiteten til Huffman-kodingen er O(nlogn). Hvor n er antall tegn i den gitte teksten.
Huffman-dekoding
Huffman-dekoding er en teknikk som konverterer de kodede dataene til innledende data. Som vi har sett i koding, er Huffman-treet laget for en inndatastreng og tegnene dekodes basert på deres plassering i treet. Dekodingsprosessen er som følger:
fjern det siste tegnet fra strengen
- Begynn å krysse over treet fra rot node og søk etter tegnet.
- Hvis vi flytter til venstre i det binære treet, legg til 0 til koden.
- Hvis vi beveger oss rett i det binære treet, legg til 1 til koden.
Barnenoden inneholder inndatategnet. Den tildeles koden som dannes av påfølgende 0-er og 1-ere. Tidskompleksiteten ved dekoding av en streng er På), hvor n er lengden på strengen.
Huffman Java-program for koding og dekoding
I det følgende programmet har vi brukt datastrukturer som prioriterte køer, stabler og trær for å designe en komprimerings- og dekompresjonslogikk. Vi vil basere verktøyene våre på den mye brukte algoritmiske teknikken til Huffman-koding.
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()> Produksjon:
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