TechCodeview

Huffmanov kódovací algoritmus navrhol David A. Huffman v roku 1950. Ide o a bezstratová kompresia dát mechanizmus. Je tiež známy ako kódovanie kompresie údajov. Je široko používaný pri kompresii obrázkov (JPEG alebo JPG). V tejto časti budeme diskutovať o Huffmanovo kódovanie a dekódovanie, a tiež implementovať svoj algoritmus v programe Java.

Vieme, že každý znak je sekvencia 0 a 1 a ukladá sa pomocou 8-bitov. Mechanizmus je tzv kódovanie s pevnou dĺžkou pretože každý znak používa rovnaký počet pevného bitového úložiska.

homogénna zmes

Tu vyvstáva otázka, je možné znížiť množstvo miesta potrebného na uloženie postavy?

Áno, je to možné pomocou kódovanie s premennou dĺžkou. V tomto mechanizme využívame niektoré znaky, ktoré sa vyskytujú častejšie v porovnaní s inými znakmi. V tejto technike kódovania môžeme reprezentovať rovnaký kus textu alebo reťazec znížením počtu bitov.

Huffmanovo kódovanie

Huffmanovo kódovanie implementuje nasledujúce kroky.

• Všetkým daným znakom priradí kód s premenlivou dĺžkou.
• Dĺžka kódu znaku závisí od toho, ako často sa vyskytuje v danom texte alebo reťazci.
• Znak dostane najmenší kód, ak sa vyskytuje často.
• Znak dostane najväčší kód, ak sa vyskytne najmenej.

Huffmanovo kódovanie nasleduje a pravidlo predpony čo zabraňuje nejednoznačnosti pri dekódovaní. Pravidlo tiež zaisťuje, že kód priradený znaku sa nepovažuje za predponu kódu priradeného k akémukoľvek inému znaku.

Huffmanovo kódovanie zahŕňa nasledujúce dva hlavné kroky:

• Najprv postavte a Huffmanov strom z daného vstupného reťazca alebo znakov alebo textu.
• Priraďte Huffmanov kód každej postave prechádzaním cez strom.

Stručne si povedzme dva vyššie uvedené kroky.

Huffmanov strom

Krok 1: Pre každý znak uzla vytvorte listový uzol. Listový uzol znaku obsahuje frekvenciu tohto znaku.

Krok 2: Nastavte všetky uzly v zoradenom poradí podľa ich frekvencie.

Krok 3: Môže existovať stav, v ktorom môžu mať dva uzly rovnakú frekvenciu. V takom prípade postupujte takto:

1. Vytvorte nový interný uzol.
2. Frekvencia uzla bude súčtom frekvencie týchto dvoch uzlov, ktoré majú rovnakú frekvenciu.
3. Označte prvý uzol ako ľavý potomok a ďalší uzol ako pravý potomok novovytvoreného interného uzla.

Krok 4: Opakujte kroky 2 a 3, kým všetky uzly nevytvoria jeden strom. Tak dostaneme Huffmanov strom.

Príklad Huffmanovho kódovania

Predpokladajme, že musíme zakódovať reťazec Abra Cadabra. Určte nasledovné:

1. Huffmanov kód pre všetky postavy
2. Priemerná dĺžka kódu pre daný reťazec
3. Dĺžka zakódovaného reťazca

(i) Huffmanov kód pre všetky postavy

Aby sme určili kód pre každý znak, najprv zostrojíme a Huffmanov strom.

Krok 1: Vytvorte dvojice znakov a ich frekvencie.

xor cpp

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

Krok 2: Zoraďte páry podľa frekvencie, dostaneme:

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

Krok 3: Vyberte prvé dva znaky a pripojte ich pod nadradený uzol.

Všimli sme si, že nadradený uzol nemá frekvenciu, takže mu musíme frekvenciu priradiť. Frekvencia rodičovského uzla bude súčtom jeho dcérskych uzlov (ľavý a pravý), t.j. 1+1= 2.

Krok 4: Opakujte kroky 2 a 3, kým nezískame jeden strom.

Pozorujeme, že páry sú už zoradené (podľa kroku 2). Opäť vyberte prvé dva páry a spojte ich.

Všimli sme si, že nadradený uzol nemá frekvenciu, takže mu musíme frekvenciu priradiť. Frekvencia rodičovského uzla bude súčtom jeho dcérskych uzlov (ľavý a pravý), t.j. 2+2= 4.

Opäť skontrolujeme, či sú dvojice zoradené alebo nie. V tomto kroku musíme zoradiť dvojice.

Podľa kroku 3 vyberte prvé dva páry a spojte ich, získame:

Všimli sme si, že nadradený uzol nemá frekvenciu, takže mu musíme frekvenciu priradiť. Frekvencia rodičovského uzla bude súčtom jeho dcérskych uzlov (ľavý a pravý), t.j. 2+4= 6.

reťazec v c

Opäť skontrolujeme, či sú dvojice zoradené alebo nie. V tomto kroku musíme zoradiť dvojice. Po zoradení strom vyzerá takto:

Podľa kroku 3 vyberte prvé dva páry a spojte ich, získame:

Všimli sme si, že nadradený uzol nemá frekvenciu, takže mu musíme frekvenciu priradiť. Frekvencia rodičovského uzla bude súčtom jeho dcérskych uzlov (ľavý a pravý), t.j. 5+6= jedenásť.

Preto dostaneme jediný strom.

Nakoniec nájdeme kód pre každý znak pomocou vyššie uvedeného stromu. Každému okraju priraďte váhu. Všimnite si, že každý so zvážením ľavej hrany je 0 a vážený pravý okraj je 1.

Všimli sme si, že vstupné znaky sú prezentované iba v opúšťacích uzloch a interné uzly majú nulové hodnoty. Aby ste našli Huffmanov kód pre každý znak, prejdite cez Huffmanov strom z koreňového uzla do listového uzla konkrétneho znaku, pre ktorý chceme nájsť kód. Tabuľka popisuje kód a dĺžku kódu pre každý znak.

Pozorujeme, že najčastejší znak má najkratšiu dĺžku kódu a menej častý znak má najväčšiu dĺžku kódu.

Teraz môžeme zakódovať reťazec (Abra Cadabra) ktoré sme prevzali vyššie.

gimp ako zrušiť výber

 0 111 10 0 1100 0 1101 0 111 10 0 

(ii) Priemerná dĺžka kódu pre reťazec

Priemernú dĺžku kódu Huffmanovho stromu možno určiť pomocou vzorca uvedeného nižšie:

 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) Dĺžka kódovaného reťazca

Dĺžku zakódovanej správy je možné určiť pomocou nasledujúceho vzorca:

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

= 11 x 2,09090909

= 23 bitov

Huffmanov kódovací algoritmus

 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 algoritmus je chamtivý algoritmus. Pretože v každej fáze algoritmus hľadá najlepšie dostupné možnosti.

Časová zložitosť Huffmanovho kódovania je O(nlogn). Kde n je počet znakov v danom texte.

Huffmanovo dekódovanie

Huffmanovo dekódovanie je technika, ktorá konvertuje zakódované dáta na počiatočné dáta. Ako sme videli pri kódovaní, Huffmanov strom je vytvorený pre vstupný reťazec a znaky sú dekódované na základe ich pozície v strome. Proces dekódovania je nasledujúci:

java rovná sa

• Začnite prechádzať cez strom z koreň uzol a vyhľadajte znak.
• Ak sa v binárnom strome posunieme doľava, pridajte 0 ku kódu.
• Ak sa pohybujeme priamo v binárnom strome, pridajte 1 ku kódu.

Podradený uzol obsahuje vstupný znak. Je mu priradený kód tvorený nasledujúcimi 0 a 1. Časová zložitosť dekódovania reťazca je O(n), kde n je dĺžka reťazca.

Program Java na kódovanie a dekódovanie Huffman

V nasledujúcom programe sme použili dátové štruktúry, ako sú prioritné fronty, zásobníky a stromy, aby sme navrhli logiku kompresie a dekompresie. Naše nástroje založíme na široko používanej algoritmickej technike Huffmanovho kódovania.

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()>

Výkon:

 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