TechCodeview

Huffmanin koodausalgoritmin ehdotti David A. Huffman vuonna 1950. Se on a häviötön tietojen pakkaus mekanismi. Se tunnetaan myös nimellä tietojen pakkauskoodaus. Sitä käytetään laajasti kuvan (JPEG tai JPG) pakkaamisessa. Tässä osiossa keskustelemme Huffman koodaus ja dekoodaus, ja myös toteuttaa sen algoritmi Java-ohjelmassa.

Tiedämme, että jokainen merkki on 0:n ja 1:n sarja ja tallentaa 8-bittisinä. Mekanismia kutsutaan kiinteäpituinen koodaus koska jokainen merkki käyttää saman määrän kiinteän bitin tallennustilaa.

tyyppi javassa

Tässä herää kysymys, onko mahdollista vähentää merkin tallentamiseen tarvittavaa tilaa?

Joo, se on mahdollista käyttämällä vaihtuvapituinen koodaus. Tässä mekanismissa hyödynnämme joitain merkkejä, jotka esiintyvät useammin kuin muut merkit. Tässä koodaustekniikassa voimme esittää samaa tekstiä tai merkkijonoa vähentämällä bittien määrää.

Huffman koodaus

Huffman-koodaus toteuttaa seuraavat vaiheet.

• Se määrittää vaihtuvapituisen koodin kaikille annetuille merkeille.
• Merkin koodin pituus riippuu siitä, kuinka usein se esiintyy annetussa tekstissä tai merkkijonossa.
• Merkki saa pienimmän koodin, jos se esiintyy usein.
• Merkki saa suurimman koodin, jos sitä esiintyy vähiten.

Huffman-koodaus seuraa a etuliitteen sääntö joka estää epäselvyyden dekoodauksen aikana. Sääntö varmistaa myös, että merkille määritettyä koodia ei käsitellä millekään muulle merkille määritetyn koodin etuliitteenä.

Huffman-koodaukseen liittyy seuraavat kaksi päävaihetta:

• Rakenna ensin a Huffman puu annetusta syöttömerkkijonosta tai merkeistä tai tekstistä.
• Määritä Huffman-koodi kullekin hahmolle kulkemalla puun yli.

Tehdään lyhyesti yllä olevat kaksi vaihetta.

Huffman puu

Vaihe 1: Luo jokaiselle solmun merkille lehtisolmu. Merkin lehtisolmu sisältää kyseisen merkin taajuuden.

Vaihe 2: Aseta kaikki solmut lajiteltuun järjestykseen niiden taajuuden mukaan.

Vaihe 3: Voi olla tilanne, jossa kahdella solmulla voi olla sama taajuus. Toimi tällaisessa tapauksessa seuraavasti:

1. Luo uusi sisäinen solmu.
2. Solmun taajuus on niiden kahden solmun taajuuden summa, joilla on sama taajuus.
3. Merkitse ensimmäinen solmu äskettäin luodun sisäisen solmun vasemmaksi lapseksi ja toinen solmu oikeaksi.

Vaihe 4: Toista vaiheita 2 ja 3, kunnes kaikki solmu muodostavat yhden puun. Siten saamme Huffman-puun.

Esimerkki Huffman-koodauksesta

Oletetaan, että meidän on koodattava merkkijono Abra Cadabra. Määritä seuraavat:

1. Huffman-koodi kaikille hahmoille
2. Annetun merkkijonon keskimääräinen koodin pituus
3. Koodatun merkkijonon pituus

(i) Huffman-koodi kaikille hahmoille

Määrittääksemme koodin jokaiselle merkille muodostamme ensin a Huffman puu.

Vaihe 1: Tee hahmoparit ja niiden taajuudet.

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

java nukkua

Vaihe 2: Lajittele parit taajuuden suhteen, saamme:

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

Vaihe 3: Valitse kaksi ensimmäistä merkkiä ja liitä ne pääsolmun alle.

Huomaamme, että pääsolmulla ei ole taajuutta, joten meidän on määritettävä sille taajuus. Pääsolmun taajuus on sen alisolmujen (vasen ja oikea) summa, eli 1+1= 2.

Etsi kartalta c++

Vaihe 4: Toista vaiheita 2 ja 3, kunnes saamme yhden puun.

Havaitsemme, että parit ovat jo lajiteltuina (vaiheen 2 mukaan). Valitse jälleen kaksi ensimmäistä paria ja liitä ne.

Huomaamme, että pääsolmulla ei ole taajuutta, joten meidän on määritettävä sille taajuus. Pääsolmun taajuus on sen alisolmujen (vasen ja oikea) summa, eli 2+2= 4.

Tarkistamme jälleen, ovatko parit lajiteltu vai eivät. Tässä vaiheessa meidän on lajiteltava parit.

Valitse vaiheen 3 mukaisesti kaksi ensimmäistä paria ja yhdistä ne, saamme:

Huomaamme, että pääsolmulla ei ole taajuutta, joten meidän on määritettävä sille taajuus. Pääsolmun taajuus on sen alisolmujen (vasen ja oikea) summa, eli 2+4= 6.

Tarkistamme jälleen, ovatko parit lajiteltu vai eivät. Tässä vaiheessa meidän on lajiteltava parit. Lajittelun jälkeen puu näyttää tältä:

Valitse vaiheen 3 mukaisesti kaksi ensimmäistä paria ja yhdistä ne, saamme:

Huomaamme, että pääsolmulla ei ole taajuutta, joten meidän on määritettävä sille taajuus. Pääsolmun taajuus on sen alisolmujen (vasen ja oikea) summa, eli 5+6= yksitoista.

Siksi saamme yhden puun.

Viimeinkin löydämme kunkin merkin koodin yllä olevan puun avulla. Määritä paino jokaiselle reunalle. Huomaa, että jokainen vasemmalla reunalla painotettu on 0 ja oikean reunan painotettu on 1.

Huomaamme, että syöttömerkit esitetään vain poistumissolmuissa ja sisäisillä solmuilla on nolla-arvot. Löytääksesi kunkin merkin Huffman-koodin, kulje Huffman-puun yli juurisolmusta sen merkin lehtisolmuun, jolle haluamme löytää koodin. Taulukossa kuvataan kunkin merkin koodi ja koodin pituus.

Huomaamme, että yleisin merkki saa lyhimmän koodin pituuden ja harvempi merkki saa suurimman koodin pituuden.

Nyt voimme koodata merkkijonon (Abra Cadabra) jonka olemme ottaneet edellä.

 0 111 10 0 1100 0 1101 0 111 10 0 

(ii) Merkkijonon keskimääräinen koodin pituus

Huffman-puun keskimääräinen koodin pituus voidaan määrittää käyttämällä alla olevaa kaavaa:

 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)

rohit shetty näyttelijä

= 2,09090909

(iii) Koodatun merkkijonon pituus

Koodatun viestin pituus voidaan määrittää seuraavalla kaavalla:

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

= 11 x 2,09090909

= 23 bittiä

Huffman-koodausalgoritmi

 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-algoritmi on ahne algoritmi. Koska jokaisessa vaiheessa algoritmi etsii parhaita saatavilla olevia vaihtoehtoja.

Huffman-koodauksen aika monimutkaisuus on O(nlogn). Missä n on annetussa tekstissä olevien merkkien määrä.

Huffmanin dekoodaus

Huffman-dekoodaus on tekniikka, joka muuntaa koodatun datan alkutiedoksi. Kuten olemme nähneet koodauksessa, Huffman-puu on tehty syötemerkkijonolle ja merkit puretaan niiden sijainnin perusteella. Dekoodausprosessi on seuraava:

matematiikka satunnainen java

• Aloita kulkeminen puun yli kohdasta juuri solmu ja etsi hahmo.
• Jos siirrymme vasemmalle binääripuussa, lisää 0 koodiin.
• Jos siirrymme oikealle binääripuussa, lisää 1 koodiin.

Lapsisolmu pitää syöttömerkin. Sille annetaan koodi, jonka muodostavat seuraavat 0:t ja 1:t. Merkkijonon dekoodauksen aika monimutkaisuus on Päällä), missä n on merkkijonon pituus.

Huffmanin koodaus ja dekoodaus Java-ohjelma

Seuraavassa ohjelmassa olemme käyttäneet tietorakenteita, kuten prioriteettijonoja, pinoja ja puita pakkaus- ja purkulogiikan suunnitteluun. Perustamme apuohjelmamme laajalti käytettyyn Huffman-koodauksen algoritmitekniikkaan.

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

Lähtö:

 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