TechCodeview

Huffmano kodavimo algoritmą pasiūlė David A. Huffman 1950 metais. Tai a duomenų glaudinimas be nuostolių mechanizmas. Jis taip pat žinomas kaip duomenų suspaudimo kodavimas. Jis plačiai naudojamas vaizdo (JPEG arba JPG) glaudinimui. Šiame skyriuje aptarsime Huffmano kodavimas ir dekodavimas, taip pat įdiegti jo algoritmą Java programoje.

Žinome, kad kiekvienas simbolis yra 0 ir 1 seka ir saugomas naudojant 8 bitus. Mechanizmas vadinamas fiksuoto ilgio kodavimas nes kiekvienas simbolis naudoja tiek pat fiksuoto bitų saugyklos.

bash elifas

Čia kyla klausimas, ar galima sumažinti vietos, reikalingos simboliui saugoti, kiekį?

taip, tai įmanoma naudojant kintamo ilgio kodavimas. Šiame mechanizme mes išnaudojame kai kuriuos simbolius, kurie pasitaiko dažniau, palyginti su kitais simboliais. Naudodami šią kodavimo techniką, sumažindami bitų skaičių galime pavaizduoti tą pačią teksto dalį arba eilutę.

Huffman kodavimas

Huffmano kodavimas įgyvendina šiuos veiksmus.

• Jis priskiria kintamo ilgio kodą visiems nurodytiems simboliams.
• Simbolio kodo ilgis priklauso nuo to, kaip dažnai jis pasitaiko nurodytame tekste ar eilutėje.
• Simbolis gauna mažiausią kodą, jei jis kartojasi dažnai.
• Simbolis gauna didžiausią kodą, jei jo pasitaiko mažiausiai.

Huffmano kodavimas seka a priešdėlio taisyklė kuri apsaugo nuo dviprasmybių dekoduojant. Taisyklė taip pat užtikrina, kad simboliui priskirtas kodas nebūtų traktuojamas kaip jokiam kitam simboliui priskirto kodo priešdėlis.

Yra du pagrindiniai Huffman kodavimo žingsniai:

• Pirmiausia sukurkite a Huffmano medis iš nurodytos įvesties eilutės, simbolių ar teksto.
• Kiekvienam simboliui priskirkite Huffman kodą, važiuodami per medį.

Trumpai apibūdinkime du aukščiau nurodytus veiksmus.

Huffmano medis

1 žingsnis: Kiekvienam mazgo simboliui sukurkite lapo mazgą. Simbolio lapo mazge yra šio simbolio dažnis.

2 žingsnis: Nustatykite visus mazgus surūšiuota tvarka pagal jų dažnį.

3 veiksmas: Gali būti sąlyga, kai du mazgai gali turėti tokį patį dažnį. Tokiu atveju atlikite šiuos veiksmus:

1. Sukurkite naują vidinį mazgą.
2. Mazgo dažnis bus tų dviejų mazgų, kurių dažnis yra toks pat, dažnių suma.
3. Pažymėkite pirmąjį mazgą kaip kairįjį antrinį mazgą, o kitą – kaip dešinįjį naujai sukurto vidinio mazgo antrinį mazgą.

4 veiksmas: Kartokite 2 ir 3 veiksmus, kol visas mazgas sudarys vieną medį. Taigi gauname Huffmano medį.

Huffman kodavimo pavyzdys

Tarkime, turime užkoduoti eilutę Abra Kadabra. Nustatykite šiuos dalykus:

1. Huffmano kodas visiems simboliams
2. Vidutinis nurodytos eilutės kodo ilgis
3. Užkoduotos eilutės ilgis

(i) Hafmano kodas visiems veikėjams

Norėdami nustatyti kiekvieno simbolio kodą, pirmiausia sukonstruojame a Huffmano medis.

1 žingsnis: Sudarykite simbolių poras ir jų dažnius.

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

2 žingsnis: Surūšiuodami poras pagal dažnį, gauname:

Java ne

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

3 veiksmas: Pasirinkite pirmuosius du simbolius ir sujunkite juos po pirminiu mazgu.

Pastebime, kad pirminis mazgas neturi dažnio, todėl turime jam priskirti dažnį. Pirminio mazgo dažnis bus antrinių mazgų (kairėje ir dešinėje) suma, ty 1+1= 2.

4 veiksmas: Kartokite 2 ir 3 veiksmus, kol gausime vieną medį.

Pastebime, kad poros jau yra surūšiuotos (pagal 2 veiksmą). Vėlgi, pasirinkite pirmąsias dvi poras ir sujunkite jas.

Pastebime, kad pirminis mazgas neturi dažnio, todėl turime jam priskirti dažnį. Pirminio mazgo dažnis bus jo antrinių mazgų (kairėje ir dešinėje) suma, ty 2+2= 4.

skirtumas tarp ledo ir sniego

Vėlgi, mes patikriname, ar poros yra surūšiuotos, ar ne. Šiame etape turime surūšiuoti poras.

Pagal 3 veiksmą išsirinkite pirmąsias dvi poras ir sujunkite jas, gausime:

Pastebime, kad pirminis mazgas neturi dažnio, todėl turime jam priskirti dažnį. Pirminio mazgo dažnis bus jo antrinių mazgų (kairėje ir dešinėje) suma, ty 2+4= 6.

Vėlgi, mes patikriname, ar poros yra surūšiuotos, ar ne. Šiame etape turime surūšiuoti poras. Po rūšiavimo medis atrodo taip:

Pagal 3 veiksmą išsirinkite pirmąsias dvi poras ir sujunkite jas, gausime:

Pastebime, kad pirminis mazgas neturi dažnio, todėl turime jam priskirti dažnį. Pirminio mazgo dažnis bus antrinių mazgų (kairėje ir dešinėje) suma, ty 5+6= vienuolika.

sql duomenų tipai

Todėl gauname vieną medį.

Pagaliau kiekvieno simbolio kodą rasime aukščiau pateikto medžio pagalba. Kiekvienam kraštui priskirkite svorį. Atkreipkite dėmesį, kad kiekvienas kairiojo krašto svertinis dydis yra 0 ir svertinis dešinysis kraštas yra 1.

Pastebime, kad įvesties simboliai pateikiami tik išėjimo mazguose, o vidiniai mazgai turi nulines reikšmes. Norėdami rasti Huffman kodą kiekvienam simboliui, pereikite per Huffman medį nuo šaknies mazgo iki to konkretaus simbolio, kurio kodą norime rasti, lapo mazgo. Lentelėje aprašomas kiekvieno simbolio kodas ir kodo ilgis.

Pastebime, kad dažniausias simbolis gauna trumpiausią kodo ilgį, o retesnis simbolis – didžiausią kodo ilgį.

Dabar galime užkoduoti eilutę (Abra Cadabra) kuriuos paėmėme aukščiau.

 0 111 10 0 1100 0 1101 0 111 10 0 

(ii) Vidutinis eilutės kodo ilgis

Vidutinį Huffmano medžio kodo ilgį galima nustatyti naudojant toliau pateiktą formulę:

 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) Užkoduotos eilutės ilgis

Užkoduoto pranešimo ilgį galima nustatyti naudojant šią formulę:

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

= 11 x 2,09090909

= 23 bitai

Huffmano kodavimo algoritmas

 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) 

Huffmano algoritmas yra godus algoritmas. Kadangi kiekviename etape algoritmas ieško geriausių galimų variantų.

Huffmano kodavimo sudėtingumas yra toks O(nelogn). Kur n yra simbolių skaičius pateiktame tekste.

Huffmano dekodavimas

Huffmano dekodavimas yra metodas, kuris užkoduotus duomenis paverčia pradiniais duomenimis. Kaip matėme koduojant, Huffmano medis yra sukurtas įvesties eilutei, o simboliai iškoduojami atsižvelgiant į jų vietą medyje. Dekodavimo procesas yra toks:

dateformat.format java

• Pradėkite važiuoti per medį nuo šaknis mazgas ir ieškokite simbolio.
• Jei dvejetainiame medyje judame į kairę, pridėkite 0 prie kodo.
• Jei pereisime tiesiai į dvejetainį medį, pridėkite 1 prie kodo.

Vaikiškas mazgas turi įvesties simbolį. Jam priskiriamas kodas, kurį sudaro vėlesni 0 ir 1. Stygos iššifravimo sudėtingumas yra toks O(n), kur n yra eilutės ilgis.

Huffman kodavimo ir dekodavimo Java programa

Šioje programoje mes panaudojome duomenų struktūras, pvz., prioritetines eiles, krūvas ir medžius, kad sukurtume glaudinimo ir išskleidimo logiką. Savo komunalines paslaugas remsimės plačiai naudojama algoritmine Huffman kodavimo technika.

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

Išvestis:

 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