Huffmanovo kódovanie je bezstratový algoritmus kompresie údajov. Cieľom je priradiť vstupným znakom kódy s premenlivou dĺžkou, pričom dĺžky priradených kódov sú založené na frekvenciách zodpovedajúcich znakov.
Kódy s premenlivou dĺžkou priradené vstupným znakom sú Predponové kódy , znamená, že kódy (bitové sekvencie) sú priradené tak, že kód priradený k jednému znaku nie je prefixom kódu priradeným žiadnemu inému znaku. Huffman Coding sa takto stará o to, aby pri dekódovaní generovaného bitového toku nevznikali nejednoznačnosti.
Poďme pochopiť predponové kódy pomocou príkladu počítadla. Nech sú štyri znaky a, b, c a d a ich zodpovedajúce kódy s premenlivou dĺžkou sú 00, 01, 0 a 1. Toto kódovanie vedie k nejednoznačnosti, pretože kód priradený k c je predponou kódov priradených k a a b. Ak je komprimovaný bitový tok 0001, dekomprimovaný výstup môže byť cccd alebo ccb alebo acd alebo ab.
Pozri toto pre aplikácie Huffmanovho kódovania.
Huffmanovo kódovanie má hlavne dve hlavné časti

1. Zo vstupných znakov zostavte Huffmanov strom.
2. Prejdite Huffmanovým stromom a priraďte znakom kódy.

Algoritmus:

Volá sa metóda, ktorá sa používa na zostavenie optimálneho prefixového kódu Huffmanovo kódovanie .

Tento algoritmus vytvára strom zdola nahor. Tento strom môžeme označiť podľa T

Nechajte, |c| byť počet listov

|c| -1 je počet operácií potrebných na zlúčenie uzlov. Q je prioritný front, ktorý možno použiť pri vytváraní binárnej haldy.

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

Kroky na vybudovanie Huffmanovho stromu
Vstupom je pole jedinečných znakov spolu s ich frekvenciou výskytu a výstupom je Huffmanov strom.

1. Vytvorte listový uzol pre každý jedinečný znak a vytvorte minimálnu hromadu všetkých listových uzlov (Min Heap sa používa ako prioritný front. Hodnota frekvenčného poľa sa používa na porovnanie dvoch uzlov v min. hromade. Najmenej frekventovaný znak je na začiatku koreň)
2. Extrahujte dva uzly s minimálnou frekvenciou z min.
   
3. Vytvorte nový vnútorný uzol s frekvenciou rovnajúcou sa súčtu frekvencií dvoch uzlov. Vytvorte prvý extrahovaný uzol ako jeho ľavý potomok a druhý extrahovaný uzol ako jeho pravý potomok. Pridajte tento uzol do min.
4. Opakujte kroky #2 a #3, kým halda nebude obsahovať iba jeden uzol. Zostávajúci uzol je koreňový uzol a strom je kompletný.
   Poďme pochopiť algoritmus na príklade:

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

Krok 1. Vytvorte minimálnu haldu, ktorá obsahuje 6 uzlov, kde každý uzol predstavuje koreň stromu s jedným uzlom.
Krok 2 Extrahujte dva uzly s minimálnou frekvenciou z minimálnej haldy. Pridajte nový vnútorný uzol s frekvenciou 5 + 9 = 14.

Ilustrácia kroku 2

Teraz minimálna halda obsahuje 5 uzlov, kde 4 uzly sú korene stromov s jedným prvkom a jeden uzol haldy je koreň stromu s 3 prvkami

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

Krok 3: Extrahujte dva uzly s minimálnou frekvenciou z haldy. Pridajte nový vnútorný uzol s frekvenciou 12 + 13 = 25

Ilustrácia kroku 3

Teraz minimálna halda obsahuje 4 uzly, kde 2 uzly sú korene stromov s jedným prvkom každý a dva uzly haldy sú koreň stromu s viac ako jedným uzlom

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

Krok 4: Extrahujte dva uzly minimálnej frekvencie. Pridajte nový vnútorný uzol s frekvenciou 14 + 16 = 30

Ilustrácia kroku 4

Teraz min halda obsahuje 3 uzly.

character Frequency Internal Node 25 Internal Node 30 f 45 

Krok 5: Extrahujte dva uzly minimálnej frekvencie. Pridajte nový vnútorný uzol s frekvenciou 25 + 30 = 55

Ilustrácia kroku 5

Teraz min halda obsahuje 2 uzly.

character Frequency f 45 Internal Node 55 

Krok 6: Extrahujte dva uzly minimálnej frekvencie. Pridajte nový vnútorný uzol s frekvenciou 45 + 55 = 100

Ilustrácia kroku 6

Teraz min halda obsahuje iba jeden uzol.

character Frequency Internal Node 100 

Keďže halda obsahuje iba jeden uzol, algoritmus sa tu zastaví.

Kroky na tlač kódov z Huffman Tree:
Prechádzajte vytvorený strom od koreňa. Udržujte pomocné pole. Pri presune do ľavého potomka napíšte 0 do poľa. Pri presune k pravému potomkovi napíšte 1 do poľa. Vytlačte pole, keď nájdete listový uzol.

Kroky na vytlačenie kódu z HuffmanTree

Kódy sú nasledovné:

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

Odporúčaný postup Kódovanie Huffman Vyskúšajte to!

Nižšie je uvedená implementácia vyššie uvedeného prístupu:

C

// C program for Huffman Coding> #include> #include> > // This constant can be avoided by explicitly> // calculating height of Huffman Tree> #define MAX_TREE_HT 100> > // A Huffman tree node> struct> MinHeapNode {> > > // One of the input characters> > char> data;> > > // Frequency of the character> > unsigned freq;> > > // Left and right child of this node> > struct> MinHeapNode *left, *right;> };> > // A Min Heap: Collection of> // min-heap (or Huffman tree) nodes> struct> MinHeap {> > > // Current size of min heap> > unsigned size;> > > // capacity of min heap> > unsigned capacity;> > > // Array of minheap node pointers> > struct> MinHeapNode** array;> };> > // A utility function allocate a new> // min heap node with given character> // and frequency of the character> struct> MinHeapNode* newNode(> char> data, unsigned freq)> {> > struct> MinHeapNode* temp = (> struct> MinHeapNode*)> malloc> (> > sizeof> (> struct> MinHeapNode));> > > temp->vľavo = teplota->vpravo = NULL;> > temp->dáta = dáta;> > temp->frekv = frekv;> > > return> temp;> }> > // A utility function to create> // a min heap of given capacity> struct> MinHeap* createMinHeap(unsigned capacity)> > {> > > struct> MinHeap* minHeap> > = (> struct> MinHeap*)> malloc> (> sizeof> (> struct> MinHeap));> > > // current size is 0> > minHeap->veľkosť = 0;> > > minHeap->kapacita = kapacita;> > > minHeap->pole = (> struct> MinHeapNode**)> malloc> (> > minHeap->kapacita *> sizeof> (> struct> MinHeapNode*));> > return> minHeap;> }> > // A utility function to> // swap two min heap nodes> void> swapMinHeapNode(> struct> MinHeapNode** a,> > struct> MinHeapNode** b)> > {> > > struct> MinHeapNode* t = *a;> > *a = *b;> > *b = t;> }> > // The standard minHeapify function.> void> minHeapify(> struct> MinHeap* minHeap,> int> idx)> > {> > > int> smallest = idx;> > int> left = 2 * idx + 1;> > int> right = 2 * idx + 2;> > > if> (left size> > && minHeap->pole[vľavo]->frekv.> > array[smallest]->frekvencia)> > smallest = left;> > > if> (right size> > && minHeap->pole[vpravo]->frekv.> > array[smallest]->frekvencia)> > smallest = right;> > > if> (smallest != idx) {> > swapMinHeapNode(&minHeap->pole [najmenšie],> > &minHeap->pole[idx]);> > minHeapify(minHeap, smallest);> > }> }> > // A utility function to check> // if size of heap is 1 or not> int> isSizeOne(> struct> MinHeap* minHeap)> {> > > return> (minHeap->veľkosť == 1);> }> > // A standard function to extract> // minimum value node from heap> struct> MinHeapNode* extractMin(> struct> MinHeap* minHeap)> > {> > > struct> MinHeapNode* temp = minHeap->pole[0];> > minHeap->pole[0] = minHeap->pole[minHeap->veľkosť - 1];> > > --minHeap->veľkosť;> > minHeapify(minHeap, 0);> > > return> temp;> }> > // A utility function to insert> // a new node to Min Heap> void> insertMinHeap(> struct> MinHeap* minHeap,> > struct> MinHeapNode* minHeapNode)> > {> > > ++minHeap->veľkosť;> > int> i = minHeap->veľkosť - 1;> > > while> (i> > && minHeapNode->frekvencia> > array[(i - 1) / 2]->frekv.) {> > > minHeap->pole[i] = minHeap->pole[(i - 1) / 2];> > i = (i - 1) / 2;> > }> > > minHeap->pole[i] = minHeapNode;> }> > // A standard function to build min heap> void> buildMinHeap(> struct> MinHeap* minHeap)> > {> > > int> n = minHeap->veľkosť - 1;> > int> i;> > > for> (i = (n - 1) / 2; i>= 0; --i)> > minHeapify(minHeap, i);> }> > // A utility function to print an array of size n> void> printArr(> int> arr[],> int> n)> {> > int> i;> > for> (i = 0; i printf('%d', arr[i]); printf(' '); } // Utility function to check if this node is leaf int isLeaf(struct MinHeapNode* root) { return !(root->vľavo) && !(koreň->vpravo); } // Vytvorí minimálnu hromadu kapacity // rovnú veľkosti a vloží všetky znaky // dát[] do min hromady. Na začiatku sa veľkosť // min haldy rovná kapacite struct MinHeap* createAndBuildMinHeap(char data[], int freq[], int size) { struct MinHeap* minHeap = createMinHeap(size); for (int i = 0; i minHeap->pole[i] = newNode(data[i], freq[i]); minHeap->veľkosť = veľkosť; buildMinHeap(minHeap); return minHeap; } // Hlavná funkcia ktorý vytvára Huffmanov strom struct MinHeapNode* buildHuffmanTree(char data[], int freq[], int size) { struct MinHeapNode *left, *right, *top // Krok 1: Vytvorte minimálnu hromadu kapacity // rovnajúcej sa veľkosti; Na začiatku sú // režimy rovné veľkosti struct MinHeap* minHeap = createAndBuildMinHeap(data, freq, size // Iterácia, kým sa veľkosť haldy nestane 1 while (!isSizeOne(minHeap)) { //); Krok 2: Extrahujte dve minimálne // frekv položky z min haldy left = extractMin(minHeap right = extractMin(minHeap) // Krok 3: Vytvorte nový interný // uzol s frekvenciou rovnajúcou sa // súčtu; frekvencie dvoch uzlov // Urobte z dvoch extrahovaných uzlov // ľavý a pravý potomok tohto nového uzla // Pridajte tento uzol do miniatúry // '$' je špeciálna hodnota pre interné uzly, nie //. použitý top = newNode('$', left->freq + right->freq); hore->vľavo = vľavo; hore->vpravo = vpravo; insertMinHeap(minHeap, top); } // Krok 4: Zostávajúci uzol je // koreňový uzol a strom je dokončený. return extractMin(minHeap); } // Vytlačí huffmanove kódy z koreňa Huffmanovho stromu. // Používa arr[] na ukladanie kódov void printCodes(struct MinHeapNode* root, int arr[], int top) { // Priraďte 0 ľavému okraju a opakujte if (root->left) { arr[top] = 0 ; printCodes(root->left, arr, top + 1); } // Priraďte 1 pravému okraju a opakujte if (root->right) { arr[top] = 1; printCodes(root->right, arr, top + 1); } // Ak je toto listový uzol, potom // obsahuje jeden zo vstupných // znakov, vypíšte znak // a jeho kód z arr[] if (isLeaf(root)) { printf('%c: ', root->data); printArr(arr, top); } } // Hlavná funkcia, ktorá vytvára // Huffmanov strom a tlačí kódy prechádzaním // vytvoreného Huffmanovho stromu void HuffmanCodes(char data[], int freq[], int size) { // Vytvorenie štruktúry Huffmanovho stromu MinHeapNode* root = buildHuffmanTree(údaje, frekvencia, veľkosť); // Tlač Huffmanových kódov pomocou // Huffmanovho stromu vytvoreného vyššie int arr[MAX_TREE_HT], top = 0; printCodes(root, arr, top); } // Kód ovládača int main() { char arr[] = { 'a', 'b', 'c', 'd', 'e', 'f ' }; int frekv[] = { 5, 9, 12, 13, 16, 45 }; int veľkosť = sizeof(arr) / sizeof(arr[0]); HuffmanCodes(arr, frekv., veľkosť); návrat 0; }>

C++

// C++ program for Huffman Coding> #include> #include> using> namespace> std;> > // This constant can be avoided by explicitly> // calculating height of Huffman Tree> #define MAX_TREE_HT 100> > // A Huffman tree node> struct> MinHeapNode {> > > // One of the input characters> > char> data;> > > // Frequency of the character> > unsigned freq;> > > // Left and right child of this node> > struct> MinHeapNode *left, *right;> };> > // A Min Heap: Collection of> // min-heap (or Huffman tree) nodes> struct> MinHeap {> > > // Current size of min heap> > unsigned size;> > > // capacity of min heap> > unsigned capacity;> > > // Array of minheap node pointers> > struct> MinHeapNode** array;> };> > // A utility function allocate a new> // min heap node with given character> // and frequency of the character> struct> MinHeapNode* newNode(> char> data, unsigned freq)> {> > struct> MinHeapNode* temp = (> struct> MinHeapNode*)> malloc> (> > sizeof> (> struct> MinHeapNode));> > > temp->vľavo = teplota->vpravo = NULL;> > temp->dáta = dáta;> > temp->frekv = frekv;> > > return> temp;> }> > // A utility function to create> // a min heap of given capacity> struct> MinHeap* createMinHeap(unsigned capacity)> > {> > > struct> MinHeap* minHeap> > = (> struct> MinHeap*)> malloc> (> sizeof> (> struct> MinHeap));> > > // current size is 0> > minHeap->veľkosť = 0;> > > minHeap->kapacita = kapacita;> > > minHeap->pole = (> struct> MinHeapNode**)> malloc> (> > minHeap->kapacita *> sizeof> (> struct> MinHeapNode*));> > return> minHeap;> }> > // A utility function to> // swap two min heap nodes> void> swapMinHeapNode(> struct> MinHeapNode** a,> > struct> MinHeapNode** b)> > {> > > struct> MinHeapNode* t = *a;> > *a = *b;> > *b = t;> }> > // The standard minHeapify function.> void> minHeapify(> struct> MinHeap* minHeap,> int> idx)> > {> > > int> smallest = idx;> > int> left = 2 * idx + 1;> > int> right = 2 * idx + 2;> > > if> (left size> > && minHeap->pole[vľavo]->frekv.> > array[smallest]->frekvencia)> > smallest = left;> > > if> (right size> > && minHeap->pole[vpravo]->frekv.> > array[smallest]->frekvencia)> > smallest = right;> > > if> (smallest != idx) {> > swapMinHeapNode(&minHeap->pole [najmenšie],> > &minHeap->pole[idx]);> > minHeapify(minHeap, smallest);> > }> }> > // A utility function to check> // if size of heap is 1 or not> int> isSizeOne(> struct> MinHeap* minHeap)> {> > > return> (minHeap->veľkosť == 1);> }> > // A standard function to extract> // minimum value node from heap> struct> MinHeapNode* extractMin(> struct> MinHeap* minHeap)> > {> > > struct> MinHeapNode* temp = minHeap->pole[0];> > minHeap->pole[0] = minHeap->pole[minHeap->veľkosť - 1];> > > --minHeap->veľkosť;> > minHeapify(minHeap, 0);> > > return> temp;> }> > // A utility function to insert> // a new node to Min Heap> void> insertMinHeap(> struct> MinHeap* minHeap,> > struct> MinHeapNode* minHeapNode)> > {> > > ++minHeap->veľkosť;> > int> i = minHeap->veľkosť - 1;> > > while> (i> > && minHeapNode->frekvencia> > array[(i - 1) / 2]->frekv.) {> > > minHeap->pole[i] = minHeap->pole[(i - 1) / 2];> > i = (i - 1) / 2;> > }> > > minHeap->pole[i] = minHeapNode;> }> > // A standard function to build min heap> void> buildMinHeap(> struct> MinHeap* minHeap)> > {> > > int> n = minHeap->veľkosť - 1;> > int> i;> > > for> (i = (n - 1) / 2; i>= 0; --i)> > minHeapify(minHeap, i);> }> > // A utility function to print an array of size n> void> printArr(> int> arr[],> int> n)> {> > int> i;> > for> (i = 0; i cout < < arr[i]; cout < < ' '; } // Utility function to check if this node is leaf int isLeaf(struct MinHeapNode* root) { return !(root->vľavo) && !(koreň->vpravo); } // Vytvorí minimálnu hromadu kapacity // rovnú veľkosti a vloží všetky znaky // dát[] do min hromady. Na začiatku sa veľkosť // min haldy rovná kapacite struct MinHeap* createAndBuildMinHeap(char data[], int freq[], int size) { struct MinHeap* minHeap = createMinHeap(size); for (int i = 0; i minHeap->pole[i] = newNode(data[i], freq[i]); minHeap->veľkosť = veľkosť; buildMinHeap(minHeap); return minHeap; } // Hlavná funkcia ktorý vytvára Huffmanov strom struct MinHeapNode* buildHuffmanTree(char data[], int freq[], int size) { struct MinHeapNode *left, *right, *top // Krok 1: Vytvorte minimálnu hromadu kapacity // rovnajúcej sa veľkosti; Na začiatku sú // režimy rovné veľkosti struct MinHeap* minHeap = createAndBuildMinHeap(data, freq, size // Iterácia, kým sa veľkosť haldy nestane 1 while (!isSizeOne(minHeap)) { //); Krok 2: Extrahujte dve minimálne // frekv položky z min haldy left = extractMin(minHeap right = extractMin(minHeap) // Krok 3: Vytvorte nový interný // uzol s frekvenciou rovnajúcou sa // súčtu; frekvencie dvoch uzlov // Urobte z dvoch extrahovaných uzlov // ľavý a pravý potomok tohto nového uzla // Pridajte tento uzol do miniatúry // '$' je špeciálna hodnota pre interné uzly, nie //. použitý top = newNode('$', left->freq + right->freq); hore->vľavo = vľavo; hore->vpravo = vpravo; insertMinHeap(minHeap, top); } // Krok 4: Zostávajúci uzol je // koreňový uzol a strom je dokončený. return extractMin(minHeap); } // Vytlačí huffmanove kódy z koreňa Huffmanovho stromu. // Používa arr[] na ukladanie kódov void printCodes(struct MinHeapNode* root, int arr[], int top) { // Priraďte 0 ľavému okraju a opakujte, ak (root->left) { arr[top] = 0 ; printCodes(root->left, arr, top + 1); } // Priraďte 1 pravému okraju a opakujte if (root->right) { arr[top] = 1; printCodes(root->right, arr, top + 1); } // Ak je toto listový uzol, tak // obsahuje jeden zo vstupných // znakov, vypíše znak // a jeho kód z arr[] if (isLeaf(root)) { cout ': '; printArr(arr, top); } } // Hlavná funkcia, ktorá vytvára // Huffmanov strom a tlačí kódy prechádzaním // vytvoreného Huffmanovho stromu void HuffmanCodes(char data[], int freq[], int size) { // Vytvorenie štruktúry Huffmanovho stromu MinHeapNode* root = buildHuffmanTree(údaje, frekvencia, veľkosť); // Tlač Huffmanových kódov pomocou // Huffmanovho stromu vytvoreného vyššie int arr[MAX_TREE_HT], top = 0; printCodes(root, arr, top); } // Kód ovládača int main() { char arr[] = { 'a', 'b', 'c', 'd', 'e', 'f ' }; int frekv[] = { 5, 9, 12, 13, 16, 45 }; int veľkosť = sizeof(arr) / sizeof(arr[0]); HuffmanCodes(arr, frekv, veľkosť); návrat 0; }>

C++

// C++(STL) program for Huffman Coding with STL> #include> using> namespace> std;> > // A Huffman tree node> struct> MinHeapNode {> > > // One of the input characters> > char> data;> > > // Frequency of the character> > unsigned freq;> > > // Left and right child> > MinHeapNode *left, *right;> > > MinHeapNode(> char> data, unsigned freq)> > > {> > > left = right = NULL;> > this> ->dáta = dáta;> > this> ->frekv = frekv;> > }> };> > // For comparison of> // two heap nodes (needed in min heap)> struct> compare {> > > bool> operator()(MinHeapNode* l, MinHeapNode* r)> > > {> > return> (l->frekv> r->frekv);> > }> };> > // Prints huffman codes from> // the root of Huffman Tree.> void> printCodes(> struct> MinHeapNode* root, string str)> {> > > if> (!root)> > return> ;> > > if> (root->údaje !=> '$'> )> > cout ': ' < < str < < ' '; printCodes(root->vľavo, str + '0'); printCodes(root->right, str + '1'); } // Hlavná funkcia, ktorá vytvára Huffmanov strom a // tlačí kódy prechádzaním vytvoreného Huffmanovho stromu void HuffmanCodes(char data[], int freq[], int size) { struct MinHeapNode *left, *right, *top; // Vytvorenie minimálnej haldy a vloženie všetkých znakov údajov[] priority_queue Compare> minHeap; for (int i = 0; i minHeap.push(new MinHeapNode(data[i], freq[i])); // Opakujte, kým sa veľkosť haldy nestane 1, zatiaľ čo (minHeap.size() != 1 ) { // Extrahujte dve minimálne // frekv položky z min hromady vľavo = minHeap.pop( vpravo = minHeap.pop(); s // frekvenciou rovnajúcou sa súčtu // frekvencií dvoch uzlov Vytvorte // dva extrahované uzly // tohto nového uzla // Pridajte tento uzol // do min haldy '$' špeciálna hodnota // pre interné uzly, nepoužíva sa top = new MinHeapNode('$', left->freq + right->freq); (top } // Tlač Huffmanových kódov pomocou // Huffmanovho stromu vytvoreného vyššie printCodes(minHeap.top(), '' } // Kód ovládača int main() { char arr[] = { '); a', 'b', 'c', 'd', 'e', 'f' }; , 45 } int veľkosť = sizeof(arr) / sizeof(arr[0]); návrat 0; } // Tento kód pridal Aditya Goel>

Java

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) { // extrakt prvej minúty. HuffmanNode x = q.peek(); q.poll(); // extrakt z druhej minúty. HuffmanNode y = q.peek(); q.poll(); // nový uzol f, ktorý sa rovná HuffmanNode f = new HuffmanNode(); // k súčtu frekvencií dvoch uzlov // priraďujúcich hodnoty k uzlu f. f.data = x.data + y.data; f.c = '-'; // prvý extrahovaný uzol ako ľavé dieťa. f.vľavo = x; // druhý extrahovaný uzol ako správne dieťa. f.vpravo = y; // označenie uzla f ako koreňového uzla. koreň = f; // pridajte tento uzol do fronty priorít. q.add(f); } // vytlačíte kódy prechodom cez strom printCode(root, ''); } } // trieda uzla je základná štruktúra // každého uzla prítomného v Huffmanovom strome. class HuffmanNode { int data; char c; HuffmanNode odišiel; HuffmanNode vpravo; } // trieda komparátora pomáha porovnávať uzol // na základe jedného z jeho atribútov. // Tu budeme porovnávaní // na základe údajových hodnôt uzlov. class MyComparator implementuje Comparator { public int porovnanie(HuffmanNode x, HuffmanNode y) { return x.data - y.data; } } // Tento kód pridal Kunwar Desh Deepak Singh>

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}') # znakov pre huffman tree chars = ['a', 'b', 'c', 'd', 'e', 'f'] # frekvencia znakov freq = [5, 9, 12, 13, 16, 45] # zoznam obsahujúci nepoužité uzly uzly = [] # konverzia znakov a frekvencií # na uzly huffmanovho stromu pre x v rozsahu(len(znaky)): heapq .heappush(nodes, node(freq[x], chars[x])) while len(nodes)> 1: # zoraď všetky uzly vo vzostupnom poradí # na základe ich frekvencie left = heapq.heappop(nodes) right = heapq .heappop(nodes) # priradí smerovú hodnotu týmto uzlom left.huff = 0 right.huff = 1 # skombinujte 2 najmenšie uzly a vytvorte # nový uzol ako ich rodičov newNode = node(left.freq+right.freq, left. symbol+right.symbol, left, right) heapq.heappush(nodes, newNode) # Huffman Tree je pripravený! printNodes(nodes[0])>

Javascript

> > // 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) { // extrakt prvej minúty. nech x = q[0]; q.shift(); // extrakt z druhej minúty. nech y = q[0]; q.shift(); // nový uzol f, ktorý sa rovná nech f = new HuffmanNode(); // k súčtu frekvencií dvoch uzlov // priraďujúcich hodnoty k uzlu f. f.data = x.data + y.data; f.c = '-'; // prvý extrahovaný uzol ako ľavé dieťa. f.vľavo = x; // druhý extrahovaný uzol ako správne dieťa. f.vpravo = y; // označenie uzla f ako koreňového uzla. koreň = f; // pridajte tento uzol do fronty priorít. q.push(f); q.sort(function(a,b){return a.data-b.data;}); } // vytlačíte kódy prechodom cez strom printCode(root, ''); // Tento kód prispel avanitrachhadiya2155>

C#

// 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>

Výkon

f: 0 c: 100 d: 101 a: 1100 b: 1101 e: 111 

Časová zložitosť: O(nlogn) kde n je počet jedinečných znakov. Ak existuje n uzlov, extraktMin() sa volá 2*(n – 1) krát. extractMin() trvá O(logn) čas, keď volá minHeapify(). Celková zložitosť je teda O(nlogn).
Ak je vstupné pole triedené, existuje lineárny časový algoritmus. Čoskoro o tom budeme diskutovať v našom ďalšom príspevku.

Priestorová zložitosť :- O(N)

Aplikácie Huffmanovho kódovania:

1. Používajú sa na prenos faxu a textu.
2. Používajú ich konvenčné kompresné formáty ako PKZIP, GZIP atď.
3. Multimediálne kodeky ako JPEG, PNG a MP3 používajú Huffmanovo kódovanie (presnejšie predponové kódy).

Je to užitočné v prípadoch, keď existuje séria často sa vyskytujúcich znakov.

Referencia:
http://en.wikipedia.org/wiki/Huffman_coding
Tento článok zostavil Aashish Barnwal a preskúmal ho tím techcodeview.com.