Huffman kodavimas yra duomenų glaudinimo be nuostolių algoritmas. Idėja yra priskirti kintamo ilgio kodus įvesties simboliams, priskirtų kodų ilgiai yra pagrįsti atitinkamų simbolių dažniais.
Kintamo ilgio kodai, priskirti įvesties simboliams, yra Priešdėlių kodai , reiškia, kad kodai (bitų sekos) yra priskirti taip, kad vienam simboliui priskirtas kodas nėra kodo, priskirto jokiam kitam simboliui, priešdėlis. Taip Huffman Coding užtikrina, kad dekoduojant generuojamą bitų srautą nebūtų dviprasmybių.
Supraskime priešdėlių kodus su priešingo pavyzdžio pavyzdžiu. Tegul yra keturi simboliai a, b, c ir d, o jų atitinkami kintamo ilgio kodai yra 00, 01, 0 ir 1. Šis kodavimas sukelia dviprasmiškumą, nes kodas, priskirtas c, yra kodų, priskirtų a ir b, priešdėlis. Jei suspaustas bitų srautas yra 0001, išspausta išvestis gali būti cccd arba ccb, ​​acd arba ab.
Matyti tai Huffman kodavimo programoms.
Iš esmės „Huffman Coding“ yra dvi pagrindinės dalys

1. Sukurkite Huffmano medį iš įvesties simbolių.
2. Pereikite per Huffmano medį ir priskirkite simboliams kodus.

Algoritmas:

Metodas, naudojamas optimaliam priešdėlio kodui sukurti, vadinamas Huffmano kodavimas .

Šis algoritmas sukuria medį iš apačios į viršų. Šį medį galime žymėti T

Tegu, |c| būti lapų skaičiumi

|c| -1 yra operacijų, kurių reikia norint sujungti mazgus, skaičius. Q yra prioritetinė eilė, kurią galima naudoti kuriant dvejetainę krūvą.

Algorithm Huffman (c) { n= |c| Q = c for i<-1 to n-1 do { temp <- get node () left (temp] Get_min (Q) right [temp] Get Min (Q) a = left [templ b = right [temp] F [temp]<- f[a] + [b] insert (Q, temp) } return Get_min (0) }>

Huffmano medžio kūrimo žingsniai
Įvestis yra unikalių simbolių masyvas kartu su jų įvykių dažniu, o išvestis yra Huffmano medis.

1. Kiekvienam unikaliam simboliui sukurkite lapo mazgą ir sukurkite min. krūvą visų lapų mazgų (Min. krūva naudojama kaip prioritetinė eilė. Dažnio lauko reikšmė naudojama norint palyginti du mazgus min. krūvoje. Iš pradžių rečiausias simbolis yra šaknis)
2. Iš min. krūvos ištraukite du mazgus mažiausiu dažniu.
   
3. Sukurkite naują vidinį mazgą, kurio dažnis lygus dviejų mazgų dažnių sumai. Pirmąjį ištrauktą mazgą padarykite kaip kairiąjį antrinį, o kitą ištrauktą mazgą kaip dešinįjį. Pridėkite šį mazgą prie min krūvos.
4. Kartokite 2 ir 3 veiksmus, kol krūvoje bus tik vienas mazgas. Likęs mazgas yra šaknies mazgas ir medis yra baigtas.
   Supraskime algoritmą su pavyzdžiu:

character Frequency a 5 b 9 c 12 d 13 e 16 f 45>

1 žingsnis. Sukurkite mažiausią krūvą, kurioje yra 6 mazgai, kur kiekvienas mazgas reiškia medžio šaknį su vienu mazgu.
2 žingsnis Ištraukite du minimalaus dažnio mazgus iš min krūvos. Pridėkite naują vidinį mazgą, kurio dažnis yra 5 + 9 = 14.

2 veiksmo iliustracija

Dabar min krūva yra 5 mazgai, iš kurių 4 mazgai yra medžių šaknys su vienu elementu, o vienas krūvos mazgas yra medžio šaknis su 3 elementais

character Frequency c 12 d 13 Internal Node 14 e 16 f 45>

3 veiksmas: Ištraukite du minimalaus dažnio mazgus iš krūvos. Pridėkite naują vidinį mazgą, kurio dažnis yra 12 + 13 = 25

3 veiksmo iliustracija

Dabar min krūva yra 4 mazgai, iš kurių 2 mazgai yra medžių šaknys su vienu elementu, o du krūvos mazgai yra medžio šaknys su daugiau nei vienu mazgu

character Frequency Internal Node 14 e 16 Internal Node 25 f 45>

4 veiksmas: Išskleiskite du minimalaus dažnio mazgus. Pridėkite naują vidinį mazgą, kurio dažnis yra 14 + 16 = 30

4 veiksmo iliustracija

Dabar min krūvoje yra 3 mazgai.

character Frequency Internal Node 25 Internal Node 30 f 45>

5 veiksmas: Išskleiskite du minimalaus dažnio mazgus. Pridėkite naują vidinį mazgą, kurio dažnis yra 25 + 30 = 55

5 veiksmo iliustracija

Dabar min krūvoje yra 2 mazgai.

character Frequency f 45 Internal Node 55>

6 veiksmas: Išskleiskite du minimalaus dažnio mazgus. Pridėkite naują vidinį mazgą, kurio dažnis yra 45 + 55 = 100

6 veiksmo iliustracija

Dabar min krūvoje yra tik vienas mazgas.

character Frequency Internal Node 100>

Kadangi krūvoje yra tik vienas mazgas, algoritmas čia sustoja.

Kodų iš Huffman Tree spausdinimo veiksmai:
Pereikite suformuotą medį, pradedant nuo šaknies. Išlaikyti pagalbinį masyvą. Pereidami prie kairiojo vaiko, į masyvą parašykite 0. Pereidami prie tinkamo vaiko, į masyvą parašykite 1. Išspausdinkite masyvą, kai aptinkamas lapo mazgas.

Kodo iš HuffmanTree spausdinimo veiksmai

Kodai yra tokie:

character code-word f 0 c 100 d 101 a 1100 b 1101 e 111>

Žemiau pateikiamas aukščiau aprašyto metodo įgyvendinimas:

C

>

>

C++

>

>

C++

> 
    
   
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 import> java.util.Comparator;> import> java.util.PriorityQueue;> import> java.util.Scanner;> > class> Huffman {> > >// recursive function to print the> >// huffman-code through the tree traversal.> >// Here s is the huffman - code generated.> >public> static> void> printCode(HuffmanNode root, String s)> >{> > >// base case; if the left and right are null> >// then its a leaf node and we print> >// the code s generated by traversing the tree.> >if> (root.left ==>null> && root.right ==>null> >&& Character.isLetter(root.c)) {> > >// c is the character in the node> >System.out.println(root.c +>':'> + s);> > >return>;> >}> > >// if we go to left then add '0' to the code.> >// if we go to the right add'1' to the code.> > >// recursive calls for left and> >// right sub-tree of the generated tree.> >printCode(root.left, s +>'0'>);> >printCode(root.right, s +>'1'>);> >}> > >// main function> >public> static> void> main(String[] args)> >{> > >Scanner s =>new> Scanner(System.in);> > >// number of characters.> >int> n =>6>;> >char>[] charArray = {>'a'>,>'b'>,>'c'>,>'d'>,>'e'>,>'f'> };> >int>[] charfreq = {>5>,>9>,>12>,>13>,>16>,>45> };> > >// creating a priority queue q.> >// makes a min-priority queue(min-heap).> >PriorityQueue q> >=>new> PriorityQueue(> >n,>new> MyComparator());> > >for> (>int> i =>0>; i     // creating a Huffman node object   // and add it to the priority queue.   HuffmanNode hn = new HuffmanNode();     hn.c = charArray[i];   hn.data = charfreq[i];     hn.left = null;   hn.right = null;     // add functions adds   // the huffman node to the queue.   q.add(hn);   }     // create a root node   HuffmanNode root = null;     // Here we will extract the two minimum value   // from the heap each time until   // its size reduces to 1, extract until   // all the nodes are extracted.   while (q.size()>1) { // pirmosios minutės ištrauka.   HuffmanNode x = q.peek();   q.poll();     // sekundės min ištrauka.   HuffmanNode y = q.peek();   q.poll();     // naujas mazgas f, kuris yra lygus HuffmanNode f = new HuffmanNode();     // į dviejų mazgų dažnių sumą // priskiriant reikšmes f mazgui.   f.duomenys = x.duomenys + y.duomenys;   f.c = '-';     // pirmasis ištrauktas mazgas kaip kairysis vaikas.   f.kairė = x;     // antrasis ištrauktas mazgas kaip tinkamas vaikas.   f.dešinė = y;     // pažymėdami f mazgą kaip šakninį mazgą.   šaknis = f;     // Pridėkite šį mazgą prie prioritetinės eilės.   q.add(f);   } // atspausdinti kodus eidami per medį printCode(root, '');   } } // mazgo klasė yra pagrindinė // kiekvieno Huffman medyje esančio mazgo struktūra.  class HuffmanNode { int duomenys;   char c;     HuffmanNode liko;   HuffmanNode dešinėje;  } // lyginamoji klasė padeda palyginti mazgą // pagal vieną iš jo atributų.  // Čia mes palyginsime // pagal mazgų duomenų reikšmes.  class MyComparator įgyvendina Comparator { public int palyginti(HuffmanNode x, HuffmanNode y) { return x.data - y.data;   } } // Šį kodą sukūrė Kunwar Desh Deepak Singh>
 
 
 
 
    
 
>
 
    
atminties keitimas
 
>
 
 
Python3
    
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 # A Huffman Tree Node> import> heapq> > > class> node:> >def> __init__(>self>, freq, symbol, left>=>None>, right>=>None>):> ># frequency of symbol> >self>.freq>=> freq> > ># symbol name (character)> >self>.symbol>=> symbol> > ># node left of current node> >self>.left>=> left> > ># node right of current node> >self>.right>=> right> > ># tree direction (0/1)> >self>.huff>=> ''> > >def> __lt__(>self>, nxt):> >return> self>.freq      # utility function to print huffman  # codes for all symbols in the newly  # created Huffman tree  def printNodes(node, val=''):     # huffman code for current node   newVal = val + str(node.huff)     # if node is not an edge node   # then traverse inside it   if(node.left):   printNodes(node.left, newVal)   if(node.right):   printNodes(node.right, newVal)     # if node is edge node then   # display its huffman code   if(not node.left and not node.right):   print(f'{node.symbol} ->{newVal}') # Huffmano medžio simbolių = ['a', 'b', 'c', 'd', 'e', 'f'] # simbolių dažnis freq = [5, 9, 12, 13, 16, 45] # sąrašas, kuriame yra nepanaudotų mazgų mazgai = [] # simbolių ir dažnių # konvertavimas į Huffmano medžio mazgus, skirtus x diapazone (len(chars)): heapq .heappush(mazgai, mazgas(dažnis[x], simboliai[x])), o len(mazgai)> 1: # rūšiuokite visus mazgus didėjimo tvarka # pagal jų dažnį kairėje = ​​heapq.heappop(nodes) right = heapq .heappop(mazgai) # priskirkite krypties reikšmę šiems mazgams left.huff = 0 right.huff = 1 # sujunkite 2 mažiausius mazgus, kad sukurtumėte # naują mazgą kaip jų pirminį newMazgas = mazgas(left.freq+right.freq, left. simbolis+dešinė.simbolis, kairysis, dešinysis) heapq.heapush(mazgai, naujas mazgas) # Huffmano medis paruoštas!  printNodes(mazgai[0])>>
 
 
 
 
    
 
> 
    
   
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 > > // node class is the basic structure> // of each node present in the Huffman - tree.> class HuffmanNode> {> >constructor()> >{> >this>.data = 0;> >this>.c =>''>;> >this>.left =>this>.right =>null>;> >}> }> > // recursive function to print the> >// huffman-code through the tree traversal.> >// Here s is the huffman - code generated.> >function> printCode(root,s)> >{> >// base case; if the left and right are null> >// then its a leaf node and we print> >// the code s generated by traversing the tree.> >if> (root.left ==>null> >&& root.right ==>null> >&& (root.c).toLowerCase() != (root.c).toUpperCase()) {> > >// c is the character in the node> >document.write(root.c +>':'> + s+>' '>);> > >return>;> >}> > >// if we go to left then add '0' to the code.> >// if we go to the right add'1' to the code.> > >// recursive calls for left and> >// right sub-tree of the generated tree.> >printCode(root.left, s +>'0'>);> >printCode(root.right, s +>'1'>);> >}> > >// main function> // number of characters.> >let n = 6;> >let charArray = [>'a'>,>'b'>,>'c'>,>'d'>,>'e'>,>'f'> ];> >let charfreq = [ 5, 9, 12, 13, 16, 45 ];> > >// creating a priority queue q.> >// makes a min-priority queue(min-heap).> >let q = [];> > >for> (let i = 0; i     // creating a Huffman node object   // and add it to the priority queue.   let hn = new HuffmanNode();     hn.c = charArray[i];   hn.data = charfreq[i];     hn.left = null;   hn.right = null;     // add functions adds   // the huffman node to the queue.   q.push(hn);   }     // create a root node   let root = null;   q.sort(function(a,b){return a.data-b.data;});     // Here we will extract the two minimum value   // from the heap each time until   // its size reduces to 1, extract until   // all the nodes are extracted.   while (q.length>1) { // pirmosios minutės ištrauka.   tegul x = q[0];   q.shift();     // antros minutės ištrauka.   tegul y = q[0];   q.shift();     // naujas mazgas f, kuris lygus tegul f = new HuffmanNode();     // į dviejų mazgų dažnių sumą // priskiriant reikšmes f mazgui.   f.duomenys = x.duomenys + y.duomenys;   f.c = '-';     // pirmasis ištrauktas mazgas kaip kairysis vaikas.   f.kairė = x;     // antrasis ištrauktas mazgas kaip tinkamas vaikas.   f.dešinė = y;     // pažymėdami f mazgą kaip šakninį mazgą.   šaknis = f;     // Pridėkite šį mazgą prie prioritetinės eilės.   q.push(f);   q.sort(function(a,b){return a.data-b.data;});   } // atspausdinti kodus eidami per medį printCode(root, '');    // Šį kodą sukūrė avanitrachhadiya2155>>
 
 
 
 
    
 
> 
    
   
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 // C# program for the above approach> > using> System;> using> System.Collections.Generic;> > // A Huffman tree node> public> class> MinHeapNode> {> >// One of the input characters> >public> char> data;> > >// Frequency of the character> >public> uint> freq;> > >// Left and right child> >public> MinHeapNode left, right;> > >public> MinHeapNode(>char> data,>uint> freq)> >{> >left = right =>null>;> >this>.data = data;> >this>.freq = freq;> >}> }> > // For comparison of two heap nodes (needed in min heap)> public> class> CompareMinHeapNode : IComparer> {> >public> int> Compare(MinHeapNode x, MinHeapNode y)> >{> >return> x.freq.CompareTo(y.freq);> >}> }> > class> Program> {> >// Prints huffman codes from the root of Huffman Tree.> >static> void> printCodes(MinHeapNode root,>string> str)> >{> >if> (root ==>null>)> >return>;> > >if> (root.data !=>'$'>)> >Console.WriteLine(root.data +>': '> + str);> > >printCodes(root.left, str +>'0'>);> >printCodes(root.right, str +>'1'>);> >}> > >// The main function that builds a Huffman Tree and> >// print codes by traversing the built Huffman Tree> >static> void> HuffmanCodes(>char>[] data,>uint>[] freq,>int> size)> >{> >MinHeapNode left, right, top;> > >// Create a min heap & inserts all characters of data[]> >var> minHeap =>new> SortedSet(>new> CompareMinHeapNode());> > >for> (>int> i = 0; i   minHeap.Add(new MinHeapNode(data[i], freq[i]));     // Iterate while size of heap doesn't become 1   while (minHeap.Count != 1)   {   // Extract the two minimum freq items from min heap   left = minHeap.Min;   minHeap.Remove(left);     right = minHeap.Min;   minHeap.Remove(right);     // Create a new internal node with frequency equal to the sum of the two nodes frequencies.   // Make the two extracted node as left and right children of this new node.   // Add this node to the min heap '$' is a special value for internal nodes, not used.   top = new MinHeapNode('$', left.freq + right.freq);     top.left = left;   top.right = right;     minHeap.Add(top);   }     // Print Huffman codes using the Huffman tree built above   printCodes(minHeap.Min, '');   }     // Driver Code   static void Main()   {   char[] arr = { 'a', 'b', 'c', 'd', 'e', 'f' };   uint[] freq = { 5, 9, 12, 13, 16, 45 };     int size = arr.Length;     HuffmanCodes(arr, freq, size);   }  }    // This code is contributed by sdeadityasharma>
 
 
 
 
    
 
>
 
    
 
>
 
  Išvestis  
 
f: 0 c: 100 d: 101 a: 1100 b: 1101 e: 111>
 
  Laiko sudėtingumas: O(nlogn) kur n yra unikalių simbolių skaičius. Jei mazgų yra n, ekstraktasMin() iškviečiamas 2*(n – 1) kartus. ExtractMin() užtrunka O(logn) laiką, nes iškviečia minHeapify(). Taigi bendras sudėtingumas yra O (nlogn). 
Jei įvesties masyvas surūšiuotas, egzistuoja tiesinis laiko algoritmas. Netrukus tai aptarsime kitame savo įraše.
 
  Erdvės sudėtingumas: O(N)  
 
Huffman kodavimo programos:
 
 
Jie naudojami faksogramoms ir tekstui perduoti.
 
Juos naudoja įprasti glaudinimo formatai, tokie kaip PKZIP, GZIP ir kt.
 
Daugialypės terpės kodekai, tokie kaip JPEG, PNG ir MP3, naudoja Huffman kodavimą (tiksliau priešdėlių kodus).
 
 
Tai naudinga tais atvejais, kai yra daugybė dažnai pasitaikančių simbolių.
 
    Nuoroda:     
  http://en.wikipedia.org/wiki/Huffman_coding   
Šį straipsnį parengė Aashish Barnwal, o jį peržiūrėjo techcodeview.com komanda.