Hafmena kodēšanas algoritmu ierosināja Deivids A. Hafmens 1950. gadā. Tas ir a datu kompresija bez zudumiem mehānisms. Tas ir pazīstams arī kā datu kompresijas kodējums. To plaši izmanto attēlu (JPEG vai JPG) saspiešanā. Šajā sadaļā mēs apspriedīsim Hafmena kodējums un dekodēšana, un arī ieviest tā algoritmu Java programmā.

Mēs zinām, ka katra rakstzīme ir 0 un 1 secība un tiek saglabāta, izmantojot 8 bitus. Mehānismu sauc fiksēta garuma kodējums jo katra rakstzīme izmanto vienādu fiksēto bitu krātuves skaitu.

c++ virknes sadalījums

Šeit paceļas jautājums, vai ir iespējams samazināt rakstzīmes uzglabāšanai nepieciešamo vietu?

Jā, tas ir iespējams, izmantojot mainīga garuma kodējums. Šajā mehānismā tiek izmantotas dažas rakstzīmes, kas parādās biežāk nekā citas rakstzīmes. Šajā kodēšanas tehnikā mēs varam attēlot vienu un to pašu teksta daļu vai virkni, samazinot bitu skaitu.

Huffman kodējums

Huffman kodēšana īsteno šādas darbības.

• Tas piešķir mainīga garuma kodu visām norādītajām rakstzīmēm.
• Rakstzīmes koda garums ir atkarīgs no tā, cik bieži tas parādās dotajā tekstā vai virknē.
• Rakstzīme saņem mazāko kodu, ja tā parādās bieži.
• Rakstzīme saņem lielāko kodu, ja tas notiek vismazāk.

Hafmena kodēšana seko a prefiksa noteikums kas novērš neskaidrības dekodēšanas laikā. Noteikums arī nodrošina, ka rakstzīmei piešķirtais kods netiek uzskatīts par jebkurai citai rakstzīmei piešķirtā koda prefiksu.

Hafmena kodēšanai ir šādi divi galvenie soļi:

• Pirmkārt, konstruējiet a Huffman koks no dotās ievades virknes vai rakstzīmēm vai teksta.
• Piešķiriet Hafmena kodu katrai rakstzīmei, šķērsojot koku.

Īsumā aprakstīsim divus iepriekš minētos soļus.

Hafmena koks

1. darbība: Katrai mezgla rakstzīmei izveidojiet lapas mezglu. Rakstzīmes lapas mezgls satur šīs rakstzīmes biežumu.

2. darbība: Iestatiet visus mezglus sakārtotā secībā atbilstoši to biežumam.

3. darbība: Var pastāvēt stāvoklis, kad diviem mezgliem var būt vienāda frekvence. Šādā gadījumā rīkojieties šādi:

1. Izveidojiet jaunu iekšējo mezglu.
2. Mezgla frekvence būs to divu mezglu frekvences summa, kuriem ir vienāda frekvence.
3. Atzīmējiet pirmo mezglu kā jaunizveidotā iekšējā mezgla kreiso atvasināto mezglu un otru mezglu kā labo bērnu.

4. darbība: Atkārtojiet 2. un 3. darbību, līdz visi mezgli veido vienu koku. Tādējādi mēs iegūstam Huffman koku.

Huffman kodēšanas piemērs

Pieņemsim, ka mums ir jākodē virkne Abra Kadabra. Nosakiet sekojošo:

1. Hafmena kods visām rakstzīmēm
2. Vidējais koda garums dotajai virknei
3. Kodētās virknes garums

(i) Hafmena kods visiem varoņiem

Lai noteiktu katras rakstzīmes kodu, vispirms mēs izveidojam a Huffman koks.

1. darbība: Izveidojiet rakstzīmju pārus un to frekvences.

koku šķērsošana

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

2. darbība: Kārtojot pārus pēc frekvences, mēs iegūstam:

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

3. darbība: Izvēlieties pirmās divas rakstzīmes un pievienojiet tās vecākmezglam.

Mēs novērojam, ka vecākajam mezglam nav frekvences, tāpēc mums tam jāpiešķir frekvence. Vecuma mezgla frekvence būs tā pakārtoto mezglu (kreisajā un labajā pusē) summa, t.i., 1+1= 2.

4. darbība: Atkārtojiet 2. un 3. darbību, līdz iegūstam vienu koku.

Mēs novērojam, ka pāri jau ir sakārtoti (pēc 2. darbības). Atkal izvēlieties pirmos divus pārus un pievienojiet tiem.

Mēs novērojam, ka vecākajam mezglam nav frekvences, tāpēc mums tam jāpiešķir frekvence. Vecuma mezgla frekvence būs tā pakārtoto mezglu (kreisajā un labajā pusē) summa, t.i., 2+2= 4.

Atkal mēs pārbaudām, vai pāri ir sakārtoti vai nē. Šajā posmā mums ir jāsakārto pāri.

Saskaņā ar 3. darbību, izvēlieties pirmos divus pārus un pievienojiet tiem, mēs iegūstam:

Mēs novērojam, ka vecākajam mezglam nav frekvences, tāpēc mums tam jāpiešķir frekvence. Vecuma mezgla frekvence būs tā pakārtoto mezglu (kreisajā un labajā pusē) summa, t.i., 2+4= 6.

f-string python

Atkal mēs pārbaudām, vai pāri ir sakārtoti vai nē. Šajā posmā mums ir jāsakārto pāri. Pēc šķirošanas koks izskatās šādi:

Saskaņā ar 3. darbību, izvēlieties pirmos divus pārus un pievienojiet tiem, mēs iegūstam:

Mēs novērojam, ka vecākajam mezglam nav frekvences, tāpēc mums tam jāpiešķir frekvence. Vecuma mezgla frekvence būs tā pakārtoto mezglu (kreisajā un labajā pusē) summa, t.i., 5+6= vienpadsmit.

Tāpēc mēs iegūstam vienu koku.

Beidzot mēs atradīsim katras rakstzīmes kodu, izmantojot iepriekš minēto koku. Katrai malai piešķiriet svaru. Ņemiet vērā, ka katrs Kreisās malas svērtais ir 0 un labās malas svērtais ir 1.

Mēs novērojam, ka ievades rakstzīmes tiek parādītas tikai atvaļinājuma mezglos un iekšējiem mezgliem ir nulles vērtības. Lai atrastu Hafmena kodu katrai rakstzīmei, pārejiet pa Hafmena koku no saknes mezgla līdz lapas mezglam konkrētajai rakstzīmei, kurai mēs vēlamies atrast kodu. Tabulā ir aprakstīts katras rakstzīmes kods un koda garums.

Mēs novērojam, ka visbiežāk sastopamā rakstzīme iegūst īsāko koda garumu, bet retāk sastopamā rakstzīme iegūst lielāko koda garumu.

Tagad mēs varam kodēt virkni (Abra Kadabra) ko esam pārņēmuši iepriekš.

ir modeļu piemēri

 0 111 10 0 1100 0 1101 0 111 10 0 

(ii) virknes vidējais koda garums

Hafmena koka vidējo koda garumu var noteikt, izmantojot tālāk norādīto formulu:

 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) Kodētās virknes garums

Kodētā ziņojuma garumu var noteikt, izmantojot šādu formulu:

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

= 11 x 2,09090909

= 23 biti

Hafmena kodēšanas algoritms

 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) 

Hafmena algoritms ir mantkārīgs algoritms. Tā kā katrā posmā algoritms meklē labākās pieejamās iespējas.

Huffman kodējuma laika sarežģītība ir O(nlogn). Kur n ir rakstzīmju skaits dotajā tekstā.

Hafmena dekodēšana

Huffman dekodēšana ir metode, kas pārvērš kodētos datus sākotnējos datos. Kā mēs redzējām kodēšanas laikā, Huffman koks ir izveidots ievades virknei, un rakstzīmes tiek atkodētas, pamatojoties uz to atrašanās vietu kokā. Dekodēšanas process ir šāds:

string split bash

• Sāciet braukt pāri kokam no sakne mezglu un meklējiet rakstzīmi.
• Ja mēs pārvietojamies pa kreisi binārajā kokā, pievienojiet 0 uz kodu.
• Ja mēs virzāmies tieši binārajā kokā, pievienojiet 1 uz kodu.

Bērnu mezglā ir ievades rakstzīme. Tam tiek piešķirts kods, ko veido nākamie 0 un 1. Virknes dekodēšanas laika sarežģītība ir O(n), kur n ir virknes garums.

Huffman kodēšanas un dekodēšanas Java programma

Nākamajā programmā mēs esam izmantojuši datu struktūras, piemēram, prioritārās rindas, skursteņus un kokus, lai izstrādātu saspiešanas un dekompresijas loģiku. Mēs balstīsim mūsu pakalpojumus uz plaši izmantoto Hafmena kodēšanas algoritmisko tehniku.

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

Izvade:

 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