Huffmanov algoritam kodiranja predložio je David A. Huffman godine 1950. To je a kompresija podataka bez gubitaka mehanizam. Također je poznat kao kodiranje kompresije podataka. Široko se koristi u kompresiji slika (JPEG ili JPG). U ovom odjeljku raspravljat ćemo o Huffmanovo kodiranje i dekodiranje, a također implementirati svoj algoritam u Java program.

Znamo da je svaki znak niz 0 i 1 i pohranjuje pomoću 8 bita. Mehanizam se zove kodiranje fiksne duljine jer svaki znak koristi isti broj memorije s fiksnim bitovima.

shweta tiwari

Ovdje se postavlja pitanje, je li moguće smanjiti količinu prostora potrebnog za pohranu znaka?

Da, moguće je korištenjem kodiranje promjenjive duljine. U ovom mehanizmu iskorištavamo neke znakove koji se pojavljuju češće u usporedbi s drugim znakovima. U ovoj tehnici kodiranja možemo prikazati isti dio teksta ili niza smanjenjem broja bitova.

Huffmanovo kodiranje

Huffmanovo kodiranje implementira sljedeće korake.

• Svim danim znakovima dodjeljuje kod promjenjive duljine.
• Duljina koda znaka ovisi o tome koliko se često pojavljuje u danom tekstu ili nizu.
• Znak dobiva najmanji kod ako se često pojavljuje.
• Znak dobiva najveći kod ako se najmanje pojavljuje.

Huffmanovo kodiranje slijedi a pravilo prefiksa koji sprječava dvosmislenost tijekom dekodiranja. Pravilo također osigurava da se kod dodijeljen znaku ne tretira kao prefiks koda dodijeljenog bilo kojem drugom znaku.

Postoje sljedeća dva glavna koraka uključena u Huffmanovo kodiranje:

• Prvo, konstruirajte a Huffmanovo drvo iz zadanog ulaznog niza ili znakova ili teksta.
• Dodijelite Huffmanov kod svakom znaku prelazeći preko stabla.

Ukratko ćemo opisati gornja dva koraka.

Huffmanovo drvo

Korak 1: Za svaki znak čvora kreirajte lisni čvor. Listni čvor znaka sadrži frekvenciju tog znaka.

Korak 2: Postavite sve čvorove sortiranim redoslijedom prema njihovoj učestalosti.

Korak 3: Može postojati stanje u kojem dva čvora mogu imati istu frekvenciju. U tom slučaju učinite sljedeće:

1. Stvorite novi interni čvor.
2. Frekvencija čvora bit će zbroj frekvencija ta dva čvora koja imaju istu frekvenciju.
3. Označite prvi čvor kao lijevo dijete, a drugi čvor kao desno dijete novostvorenog internog čvora.

Korak 4: Ponavljajte korake 2 i 3 dok svi čvorovi ne formiraju jedno stablo. Tako dobivamo Huffmanovo stablo.

java grah

Primjer Huffmanovog kodiranja

Pretpostavimo da moramo kodirati niz Abra Cadabra. Odredite sljedeće:

1. Huffmanov kod za sve likove
2. Prosječna duljina koda za navedeni niz
3. Duljina kodiranog niza

(i) Huffmanov kod za sve likove

Kako bismo odredili kod za svaki znak, prvo konstruiramo a Huffmanovo drvo.

Korak 1: Napravite parove znakova i njihove frekvencije.

(a, 5), (b, 2), (c, 1), (d, 1), (r, 2)

Korak 2: Poredaj parove s obzirom na frekvenciju, dobivamo:

(c, 1), (d, 1), (b, 2) (r, 2), (a, 5)

Korak 3: Odaberite prva dva znaka i pridružite im se pod nadređenim čvorom.

Primjećujemo da nadređeni čvor nema frekvenciju pa mu moramo dodijeliti frekvenciju. Frekvencija nadređenog čvora bit će zbroj njegovih podređenih čvorova (lijevo i desno), tj. 1+1= 2.

Korak 4: Ponavljajte korake 2 i 3 dok ne dobijemo jedno stablo.

Primjećujemo da su parovi već poredani (po koraku 2). Opet odaberite prva dva para i pridružite im se.

Primjećujemo da nadređeni čvor nema frekvenciju pa mu moramo dodijeliti frekvenciju. Frekvencija nadređenog čvora bit će zbroj njegovih podređenih čvorova (lijevo i desno), tj. 2+2= 4.

Opet provjeravamo jesu li parovi posloženi ili ne. U ovom koraku moramo razvrstati parove.

Prema koraku 3, odaberite prva dva para i spojite ih, dobivamo:

Primjećujemo da nadređeni čvor nema frekvenciju pa mu moramo dodijeliti frekvenciju. Frekvencija nadređenog čvora bit će zbroj njegovih podređenih čvorova (lijevo i desno), tj. 2+4= 6.

glumac ranbir kapoor dob

Opet provjeravamo jesu li parovi posloženi ili ne. U ovom koraku moramo razvrstati parove. Nakon sortiranja stablo izgleda ovako:

Prema koraku 3, odaberite prva dva para i spojite ih, dobivamo:

SIM kartica je umetnuta, ali nema usluge android

Primjećujemo da nadređeni čvor nema frekvenciju pa mu moramo dodijeliti frekvenciju. Frekvencija nadređenog čvora bit će zbroj njegovih podređenih čvorova (lijevo i desno), tj. 5+6= jedanaest.

Stoga dobivamo jedno stablo.

Napokon ćemo pronaći kod za svaki znak uz pomoć gornjeg stabla. Dodijelite težinu svakom rubu. Imajte na umu da svaki ponderirano lijevom rubu je 0 i ponderirano na desnom rubu je 1.

Primjećujemo da su ulazni znakovi prikazani samo u izlaznim čvorovima, a unutarnji čvorovi imaju nulte vrijednosti. Kako bismo pronašli Huffmanov kod za svaki znak, prijeđimo Huffmanovim stablom od korijenskog čvora do lisnog čvora tog određenog znaka za koji želimo pronaći kod. Tablica opisuje kod i duljinu koda za svaki znak.

Primjećujemo da najčešći znak dobiva najkraću duljinu koda, a rjeđi znak dobiva najveću duljinu koda.

Sada možemo kodirati niz (Abra Cadabra) koje smo uzeli gore.

 0 111 10 0 1100 0 1101 0 111 10 0 

(ii) Prosječna duljina koda za niz

Prosječna duljina koda Huffmanovog stabla može se odrediti korištenjem formule dane u nastavku:

 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) Duljina kodiranog niza

Duljina kodirane poruke može se odrediti pomoću sljedeće formule:

 length= Total number of characters in the text x Average code length per character 

= 11 x 2,09090909

= 23 bita

Huffmanov algoritam kodiranja

 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) 

Huffmanov algoritam je pohlepan algoritam. Budući da u svakoj fazi algoritam traži najbolje dostupne opcije.

Vremenska složenost Huffmanovog kodiranja je O(nlogn). Gdje je n broj znakova u datom tekstu.

Huffmanovo dekodiranje

Huffmanovo dekodiranje je tehnika koja pretvara kodirane podatke u početne podatke. Kao što smo vidjeli u kodiranju, Huffmanovo stablo napravljeno je za ulazni niz i znakovi se dekodiraju na temelju njihovog položaja u stablu. Proces dekodiranja je sljedeći:

binarno pretraživanje python

• Počnite prelaziti preko stabla od korijen čvor i potražite znak.
• Ako se pomaknemo lijevo u binarnom stablu, dodajte 0 na kod.
• Ako se pomaknemo desno u binarnom stablu, dodajte 1 na kod.

Čvor dijete sadrži ulazni znak. Dodjeljuje mu se kod formiran od sljedećih 0 i 1. Vremenska složenost dekodiranja niza je Na), gdje je n duljina niza.

Huffman Java program za kodiranje i dekodiranje

U sljedećem programu upotrijebili smo strukture podataka kao što su prioritetni redovi, hrpe i stabla za dizajn logike kompresije i dekompresije. Temeljit ćemo naše pomoćne programe na široko korištenoj algoritamskoj tehnici Huffmanovog kodiranja.

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 -&gt; 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&apos; 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, &apos;&apos;, huffmanCode); //print the Huffman codes for the characters System.out.println(&apos;Huffman Codes of the characters are: &apos; + huffmanCode); //prints the initial data System.out.println(&apos;The initial string is: &apos; + 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(&apos;The encoded string is: &apos; + sb); System.out.print(&apos;The decoded string is: &apos;); if (isLeaf(root)) { //special case: For input like a, aa, aaa, etc. while (root.freq-- &gt; 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 : &apos;1&apos;); } encodeData(root.left, str + &apos;0&apos;, huffmanCode); encodeData(root.right, str + &apos;1&apos;, 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) == &apos;0&apos;) ? 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 &amp;&amp; root.right == null; } //driver code public static void main(String args[]) { String text = &apos;javatpoint&apos;; //function calling createHuffmanTree(text); } } </sb.length()>

Izlaz:

 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