Huffmanov algoritem kodiranja je predlagal David A. Huffman leta 1950. Je a stiskanje podatkov brez izgub mehanizem. Znan je tudi kot kodiranje stiskanja podatkov. Široko se uporablja pri stiskanju slik (JPEG ali JPG). V tem razdelku bomo razpravljali o Huffmanovo kodiranje in dekodiranje, in tudi implementira svoj algoritem v program Java.

Vemo, da je vsak znak zaporedje 0 in 1 in shranjuje z uporabo 8 bitov. Mehanizem se imenuje kodiranje s fiksno dolžino ker vsak znak uporablja enako število fiksno-bitnega pomnilnika.

shraniti iz

Tukaj se postavlja vprašanje, ali je mogoče zmanjšati količino prostora, potrebnega za shranjevanje znaka?

ja, je mogoče z uporabo kodiranje s spremenljivo dolžino. V tem mehanizmu izkoriščamo nekatere znake, ki se pojavljajo pogosteje v primerjavi z drugimi znaki. Pri tej tehniki kodiranja lahko predstavimo isti del besedila ali niza z zmanjšanjem števila bitov.

Huffmanovo kodiranje

Huffmanovo kodiranje izvaja naslednje korake.

• Vsem podanim znakom dodeli kodo spremenljive dolžine.
• Dolžina kode znaka je odvisna od tega, kako pogosto se pojavlja v danem besedilu ali nizu.
• Znak dobi najmanjšo kodo, če se pojavlja pogosto.
• Znak dobi največjo kodo, če se pojavi najmanj.

Huffmanovo kodiranje sledi a pravilo predpone ki preprečuje dvoumnost med dekodiranjem. Pravilo tudi zagotavlja, da se koda, dodeljena znaku, ne obravnava kot predpona kode, dodeljene kateremu koli drugemu znaku.

V Huffmanovo kodiranje sta vključena naslednja dva glavna koraka:

• Najprej zgradite a Huffmanovo drevo iz podanega vhodnega niza ali znakov ali besedila.
• Dodelite Huffmanovo kodo vsakemu znaku tako, da prečkate drevo.

Oglejmo si na kratko zgornja dva koraka.

Huffmanovo drevo

Korak 1: Za vsak znak vozlišča ustvarite listno vozlišče. Listno vozlišče znaka vsebuje frekvenco tega znaka.

2. korak: Vsa vozlišča nastavite v razvrščenem vrstnem redu glede na njihovo frekvenco.

primer podatkov json

3. korak: Lahko obstaja stanje, v katerem imata lahko dve vozlišči enako frekvenco. V takem primeru naredite naslednje:

1. Ustvarite novo notranje vozlišče.
2. Frekvenca vozlišča bo vsota frekvenc teh dveh vozlišč, ki imata enako frekvenco.
3. Prvo vozlišče označite kot levega podrejenega in drugo vozlišče kot desnega podrejenega novo ustvarjenega notranjega vozlišča.

4. korak: Ponavljajte 2. in 3. korak, dokler vsa vozlišča ne tvorijo enega samega drevesa. Tako dobimo Huffmanovo drevo.

Primer Huffmanovega kodiranja

Recimo, da moramo kodirati niz Abra Cadabra. Določite naslednje:

1. Huffmanova koda za vse znake
2. Povprečna dolžina kode za dani niz
3. Dolžina kodiranega niza

(i) Huffmanova koda za vse znake

Da bi določili kodo za vsak znak, najprej sestavimo a Huffmanovo drevo.

Korak 1: Sestavite pare znakov in njihove frekvence.

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

2. korak: Če razvrstimo pare glede na frekvenco, dobimo:

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

3. korak: Izberite prva dva znaka in ju združite pod nadrejenim vozliščem.

Opazimo, da nadrejeno vozlišče nima frekvence, zato mu moramo dodeliti frekvenco. Frekvenca nadrejenega vozlišča bo vsota njegovih podrejenih vozlišč (levo in desno), tj. 1+1= 2.

rosomah proti jazbecu

4. korak: Ponavljamo koraka 2 in 3, dokler ne dobimo enega samega drevesa.

Opazimo, da so pari že razvrščeni (po 2. koraku). Spet izberite prva dva para in se jima pridružite.

Opazimo, da nadrejeno vozlišče nima frekvence, zato mu moramo dodeliti frekvenco. Frekvenca nadrejenega vozlišča bo vsota njegovih podrejenih vozlišč (levo in desno), tj. 2+2= 4.

Spet preverimo, ali so pari razvrščeni ali ne. V tem koraku moramo razvrstiti pare.

V skladu s 3. korakom izberemo prva dva para in ju združimo, dobimo:

Opazimo, da nadrejeno vozlišče nima frekvence, zato mu moramo dodeliti frekvenco. Frekvenca nadrejenega vozlišča bo vsota njegovih podrejenih vozlišč (levo in desno), tj. 2+4= 6.

Spet preverimo, ali so pari razvrščeni ali ne. V tem koraku moramo razvrstiti pare. Po razvrščanju je drevo videti takole:

V skladu s 3. korakom izberemo prva dva para in ju združimo, dobimo:

Opazimo, da nadrejeno vozlišče nima frekvence, zato mu moramo dodeliti frekvenco. Frekvenca nadrejenega vozlišča bo vsota njegovih podrejenih vozlišč (levo in desno), tj. 5+6= enajst.

Tako dobimo eno samo drevo.

Končno bomo našli kodo za vsak znak s pomočjo zgornjega drevesa. Vsakemu robu dodelite težo. Upoštevajte, da vsak ponderirano na levi rob je 0 in ponderirano na desnem robu je 1.

Opazimo, da so vhodni znaki predstavljeni samo v izhodnih vozliščih, notranja vozlišča pa imajo ničelne vrednosti. Da bi našli Huffmanovo kodo za vsak znak, prečkajte Huffmanovo drevo od korenskega vozlišča do listnega vozlišča tistega znaka, za katerega želimo najti kodo. Tabela opisuje kodo in dolžino kode za vsak znak.

Opažamo, da najpogostejši znak dobi najkrajšo dolžino kode, manj pogost znak pa največjo dolžino kode.

pretvori niz v char

Zdaj lahko kodiramo niz (Abra Cadabra) ki smo jih prevzeli zgoraj.

 0 111 10 0 1100 0 1101 0 111 10 0 

(ii) Povprečna dolžina kode za niz

Povprečno dolžino kode Huffmanovega drevesa je mogoče določiti z uporabo spodnje 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) Dolžina kodiranega niza

Dolžino kodiranega sporočila je mogoče določiti z uporabo naslednje formule:

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

= 11 x 2,09090909

= 23 bitov

Huffmanov algoritem 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 algoritem je požrešen algoritem. Ker na vsaki stopnji algoritem išče najboljše razpoložljive možnosti.

Časovna zapletenost Huffmanovega kodiranja je O(nlogn). Kjer je n število znakov v danem besedilu.

Huffmanovo dekodiranje

Huffmanovo dekodiranje je tehnika, ki pretvori kodirane podatke v začetne podatke. Kot smo videli pri kodiranju, je Huffmanovo drevo narejeno za vhodni niz in znaki so dekodirani glede na njihov položaj v drevesu. Postopek dekodiranja je naslednji:

moj živi kriket

• Začnite prečkati drevo od korenina vozlišče in poiščite znak.
• Če se premaknemo levo v binarnem drevesu, dodamo 0 na kodo.
• Če se premaknemo desno v binarnem drevesu, dodamo 1 na kodo.

Podrejeno vozlišče vsebuje vhodni znak. Dodeljena mu je koda, ki jo tvorijo naslednje 0 in 1. Časovna zahtevnost dekodiranja niza je O(n), kjer je n dolžina niza.

Huffmanov program za kodiranje in dekodiranje Java

V naslednjem programu smo za oblikovanje logike stiskanja in dekompresije uporabili podatkovne strukture, kot so prednostne čakalne vrste, skladi in drevesa. Naše pripomočke bomo zasnovali na široko uporabljeni algoritemski tehniki Huffmanovega 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()>

Izhod:

 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