Huffmanovo kódování je bezeztrátový algoritmus komprese dat. Cílem je přiřadit vstupním znakům kódy s proměnnou délkou, délky přiřazených kódů jsou založeny na frekvencích odpovídajících znaků.
Kódy proměnné délky přiřazené vstupním znakům jsou Předponové kódy , znamená, že kódy (bitové sekvence) jsou přiřazeny tak, že kód přiřazený jednomu znaku není předponou kódu přiřazeného žádnému jinému znaku. Tímto způsobem Huffman Coding zajišťuje, že při dekódování generovaného bitového toku nedochází k nejednoznačnosti.
Pojďme pochopit předponové kódy s příkladem čítače. Nechť existují čtyři znaky a, b, c a d a jejich odpovídající kódy s proměnnou délkou jsou 00, 01, 0 a 1. Toto kódování vede k nejednoznačnosti, protože kód přiřazený c je prefixem kódů přiřazených k a a b. Pokud je komprimovaný bitový tok 0001, dekomprimovaný výstup může být cccd nebo ccb nebo acd nebo ab.
Vidět tento pro aplikace Huffmanova kódování.
Huffmanovo kódování má hlavně dvě hlavní části

1. Sestavte Huffmanův strom ze vstupních znaků.
2. Projděte Huffmanův strom a přiřaďte kódy postavám.

Algoritmus:

Zavolá se metoda, která se používá ke konstrukci optimálního prefixového kódu Huffmanovo kódování .

Tento algoritmus vytváří strom způsobem zdola nahoru. Tento strom můžeme označit pomocí T

Nechte, |c| být počet listů

|c| -1 je počet operací potřebných ke sloučení uzlů. Q je prioritní fronta, kterou lze použít při vytváření binární 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 k vybudování Huffmanova stromu
Vstupem je pole jedinečných znaků spolu s frekvencí jejich výskytů a výstupem je Huffmanův strom.

1. Vytvořte listový uzel pro každý jedinečný znak a vytvořte minimální hromadu všech listových uzlů (Min Heap se používá jako prioritní fronta. Hodnota pole frekvence se používá k porovnání dvou uzlů v minimální hromadě. Zpočátku je nejméně častý znak na vykořenit)
2. Extrahujte dva uzly s minimální frekvencí z minimální haldy.
   
3. Vytvořte nový vnitřní uzel s frekvencí rovnou součtu frekvencí dvou uzlů. Vytvořte první extrahovaný uzel jako jeho levý potomek a druhý extrahovaný uzel jako jeho pravý potomek. Přidejte tento uzel do minimální haldy.
4. Opakujte kroky #2 a #3, dokud halda nebude obsahovat pouze jeden uzel. Zbývající uzel je kořenový uzel a strom je kompletní.
   Pojďme pochopit algoritmus na příkladu:

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

Krok 1. Sestavte min haldu, která obsahuje 6 uzlů, kde každý uzel představuje kořen stromu s jedním uzlem.
Krok 2 Extrahujte dva uzly minimální frekvence z minimální haldy. Přidejte nový vnitřní uzel s frekvencí 5 + 9 = 14.

Ilustrace kroku 2

Nyní min halda obsahuje 5 uzlů, kde 4 uzly jsou kořeny stromů s jedním prvkem každý a jeden uzel haldy je kořen stromu se 3 prvky

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

Krok 3: Extrahujte dva uzly s minimální frekvencí z haldy. Přidejte nový vnitřní uzel s frekvencí 12 + 13 = 25

Ilustrace kroku 3

Nyní min halda obsahuje 4 uzly, kde 2 uzly jsou kořeny stromů s jedním prvkem každý a dva uzly haldy jsou kořen stromu s více než jedním uzly

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

Krok 4: Extrahujte dva uzly minimální frekvence. Přidejte nový vnitřní uzel s frekvencí 14 + 16 = 30

Ilustrace kroku 4

Nyní min halda obsahuje 3 uzly.

character Frequency Internal Node 25 Internal Node 30 f 45 

Krok 5: Extrahujte dva uzly minimální frekvence. Přidejte nový vnitřní uzel s frekvencí 25 + 30 = 55

Ilustrace kroku 5

Nyní min halda obsahuje 2 uzly.

character Frequency f 45 Internal Node 55 

Krok 6: Extrahujte dva uzly minimální frekvence. Přidejte nový vnitřní uzel s frekvencí 45 + 55 = 100

Ilustrace kroku 6

Nyní min halda obsahuje pouze jeden uzel.

character Frequency Internal Node 100 

Protože halda obsahuje pouze jeden uzel, algoritmus se zde zastaví.

Kroky k tisku kódů z Huffman Tree:
Projděte vytvořený strom počínaje kořenem. Udržujte pomocné pole. Při přesunu do levého potomka zapište 0 do pole. Při přesunu do pravého potomka zapište 1 do pole. Vytiskněte pole, když je nalezen listový uzel.

Kroky k tisku kódu z HuffmanTree

Kódy jsou následující:

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

Doporučený postup Kódování Huffman Vyzkoušejte to!

Níže je implementace výše uvedeného pří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->vlevo = teplota->vpravo = NULL;> > temp->data = data;> > 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->velikost = 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->array[left]->freq> > array[smallest]->frekvence)> > smallest = left;> > > if> (right size> > && minHeap->pole[vpravo]->frekvence> > array[smallest]->frekvence)> > smallest = right;> > > if> (smallest != idx) {> > swapMinHeapNode(&minHeap->pole[nejmenší],> > &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->velikost == 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->velikost - 1];> > > --minHeap->velikost;> > 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->velikost;> > int> i = minHeap->velikost - 1;> > > while> (i> > && minHeapNode->frekvence> > array[(i - 1) / 2]->frekvence) {> > > 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->velikost - 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->vlevo) && !(kořen->vpravo); } // Vytvoří minimální haldu kapacity // rovnající se velikosti a vloží všechny znaky // dat[] do minimální haldy. Na počátku je velikost // min haldy rovna kapacitě struct MinHeap* createAndBuildMinHeap(char data[], int freq[], int size) { struct MinHeap* minHeap = createMinHeap(size); for (int i = 0; i minHeap->array[i] = newNode(data[i], freq[i]); minHeap->size = velikost; buildMinHeap(minHeap); return minHeap; } // Hlavní funkce který vytvoří Huffmanův strom struct MinHeapNode* buildHuffmanTree(char data[], int freq[], int size) { struct MinHeapNode *left, *right, *top // Krok 1: Vytvořte min hromadu kapacity // rovnající se velikosti; Zpočátku existují // režimy rovné velikosti struct MinHeap* minHeap = createAndBuildMinHeap(data, freq, size // Iterujte, zatímco velikost haldy se nestane 1 while (!isSizeOne(minHeap)) { //); Krok 2: Extrahujte dvě minimální // frekv položky z min haldy left = extractMin(minHeap right = extractMin(minHeap) // Krok 3: Vytvořte nový interní // uzel s frekvencí rovnou // součtu; frekvence dvou uzlů // Udělejte ze dvou extrahovaných uzlů // levého a pravého potomka tohoto nového uzlu // Přidejte tento uzel do minimální haldy // '$' je speciální hodnota pro interní uzly, nikoli //. použitý top = newNode('$', left->freq + right->freq); nahoře->levý = vlevo; nahoře->vpravo = vpravo; insertMinHeap(minHeap, top); } // Krok 4: Zbývající uzel je // kořenový uzel a strom je kompletní. return extractMin(minHeap); } // Vytiskne huffmanovy kódy z kořene Huffmanova stromu. // K ukládání kódů používá arr[] void printCodes(struct MinHeapNode* root, int arr[], int top) { // Přiřaďte 0 levému okraji a opakujte se if (root->left) { arr[top] = 0 ; printCodes(root->left, arr, top + 1); } // Přiřaďte 1 pravému okraji a opakujte if (root->right) { arr[top] = 1; printCodes(root->right, arr, top + 1); } // Pokud se jedná o listový uzel, pak // obsahuje jeden ze vstupních // znaků, vytiskněte znak // a jeho kód z arr[] if (isLeaf(root)) { printf('%c: ', root->data); printArr(arr, top); } } // Hlavní funkce, která sestaví // Huffmanův strom a vytiskne kódy procházením // vytvořeného Huffmanova stromu void HuffmanCodes(char data[], int freq[], int size) { // Konstrukce Huffmanova stromu struct MinHeapNode* root = buildHuffmanTree(data, frekvence, velikost); // Tisk Huffmanových kódů pomocí // Huffmanova stromu vytvořeného výše int arr[MAX_TREE_HT], top = 0; printCodes(root, arr, top); } // Kód ovladače int main() { char arr[] = { 'a', 'b', 'c', 'd', 'e', 'f ' }; int frekv[] = { 5, 9, 12, 13, 16, 45 }; int velikost = sizeof(arr) / sizeof(arr[0]); HuffmanCodes(arr, frekvence, velikost); 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->vlevo = teplota->vpravo = NULL;> > temp->data = data;> > 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->velikost = 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->array[left]->freq> > array[smallest]->frekvence)> > smallest = left;> > > if> (right size> > && minHeap->pole[vpravo]->frekvence> > array[smallest]->frekvence)> > smallest = right;> > > if> (smallest != idx) {> > swapMinHeapNode(&minHeap->pole[nejmenší],> > &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->velikost == 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->velikost - 1];> > > --minHeap->velikost;> > 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->velikost;> > int> i = minHeap->velikost - 1;> > > while> (i> > && minHeapNode->frekvence> > array[(i - 1) / 2]->frekvence) {> > > 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->velikost - 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->vlevo) && !(kořen->vpravo); } // Vytvoří minimální hromadu kapacity // rovné velikosti a vloží všechny znaky // data[] do minimální hromady. Na počátku je velikost // min haldy rovna kapacitě struct MinHeap* createAndBuildMinHeap(char data[], int freq[], int size) { struct MinHeap* minHeap = createMinHeap(size); for (int i = 0; i minHeap->array[i] = newNode(data[i], freq[i]); minHeap->size = velikost; buildMinHeap(minHeap); return minHeap; } // Hlavní funkce který vytvoří Huffmanův strom struct MinHeapNode* buildHuffmanTree(char data[], int freq[], int size) { struct MinHeapNode *left, *right, *top // Krok 1: Vytvořte min hromadu kapacity // rovnající se velikosti; Zpočátku existují // režimy rovné velikosti struct MinHeap* minHeap = createAndBuildMinHeap(data, freq, size // Iterujte, zatímco velikost haldy se nestane 1 while (!isSizeOne(minHeap)) { //); Krok 2: Extrahujte dvě minimální // frekv položky z min haldy left = extractMin(minHeap right = extractMin(minHeap) // Krok 3: Vytvořte nový interní // uzel s frekvencí rovnou // součtu; frekvence dvou uzlů // Udělejte ze dvou extrahovaných uzlů // levého a pravého potomka tohoto nového uzlu // Přidejte tento uzel do minimální haldy // '$' je speciální hodnota pro interní uzly, nikoli //. použitý top = newNode('$', left->freq + right->freq); nahoře->levý = vlevo; nahoře->vpravo = vpravo; insertMinHeap(minHeap, top); } // Krok 4: Zbývající uzel je // kořenový uzel a strom je kompletní. return extractMin(minHeap); } // Vytiskne huffmanovy kódy z kořene Huffmanova stromu. // K ukládání kódů používá arr[] void printCodes(struct MinHeapNode* root, int arr[], int top) { // Přiřaďte 0 levému okraji a opakujte se if (root->left) { arr[top] = 0 ; printCodes(root->left, arr, top + 1); } // Přiřaďte 1 pravému okraji a opakujte if (root->right) { arr[top] = 1; printCodes(root->right, arr, top + 1); } // Pokud se jedná o listový uzel, pak // obsahuje jeden ze vstupních // znaků, vypíše znak // a jeho kód z arr[] if (isLeaf(kořen)) { cout ': '; printArr(arr, top); } } // Hlavní funkce, která sestaví // Huffmanův strom a vytiskne kódy procházením // vytvořeného Huffmanova stromu void HuffmanCodes(char data[], int freq[], int size) { // Konstrukce Huffmanova stromu struct MinHeapNode* root = buildHuffmanTree(data, frekvence, velikost); // Tisk Huffmanových kódů pomocí // Huffmanova stromu vytvořeného výše int arr[MAX_TREE_HT], top = 0; printCodes(root, arr, top); } // Kód ovladače int main() { char arr[] = { 'a', 'b', 'c', 'd', 'e', 'f ' }; int frekv[] = { 5, 9, 12, 13, 16, 45 }; int velikost = sizeof(arr) / sizeof(arr[0]); HuffmanCodes(arr, frekvence, velikost); 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> ->data = data;> > 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->data !=> '$'> )> > cout ': ' < < str < < ' '; printCodes(root->vlevo, str + '0'); printCodes(root->right, str + '1'); } // Hlavní funkce, která vytváří Huffmanův strom a // tiskne kódy procházením vytvořeného Huffmanova stromu void HuffmanCodes(char data[], int freq[], int size) { struct MinHeapNode *left, *right, *top; // Vytvoří minimální haldu a vloží všechny znaky dat[] priority_queue Compare> minHeap; for (int i = 0; i minHeap.push(new MinHeapNode(data[i], freq[i])); // Opakujte, dokud se velikost haldy nestane 1, zatímco (minHeap.size() != 1 ) { // Extrahujte dvě minimální // frekv položky z min hromady vlevo = minHeap.pop( vpravo = minHeap.top(); s // frekvencí rovnou součtu // frekvencí dvou uzlů Vytvořte // dva extrahované uzly // tohoto nového uzlu // Přidejte tento uzel // do minimální haldy '$' speciální hodnota // pro interní uzly, nepoužívá se top = new MinHeapNode('$', left->freq + right->freq); (top } // Tisk Huffmanových kódů pomocí // Huffmanova stromu vytvořeného výše printCodes(minHeap.top(), '' } // Kód ovladače int main() { char arr[] = { '); a', 'b', 'c', 'd', 'e', 'f' }; int frekvence[] = { 5, 9, 12, 13, 16 , 45 } int velikost = sizeof(arr) / sizeof(arr[0]); návrat 0; } // Tento kód přispěl Aditya Goel>

Jáva

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 první minuty. HuffmanNode x = q.peek(); q.poll(); // extrakt sekundy min. HuffmanNode y = q.peek(); q.poll(); // nový uzel f, který se rovná HuffmanNode f = new HuffmanNode(); // k součtu frekvence dvou uzlů // přiřazování hodnot k uzlu f. f.data = x.data + y.data; f.c = '-'; // první extrahovaný uzel jako levý potomek. f.left = x; // druhý extrahovaný uzel jako správný potomek. f.vpravo = y; // označení uzlu f jako kořenového uzlu. kořen = f; // přidejte tento uzel do fronty priority. q.add(f); } // vytiskne kódy procházením stromu printCode(root, ''); } } // třída uzlů je základní strukturou // každého uzlu přítomného v Huffmanově stromu. class HuffmanNode { int data; char c; HuffmanNode vlevo; HuffmanNode vpravo; } // třída komparátoru pomáhá porovnávat uzel // na základě jednoho z jeho atributů. // Zde budeme porovnáni // na základě datových hodnot uzlů. class MyComparator implementuje Comparator { public int Compare(HuffmanNode x, HuffmanNode y) { return x.data - y.data; } } // Tento kód přispěl 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}') # znaků pro huffman tree chars = ['a', 'b', 'c', 'd', 'e', 'f'] # frekvence znaků freq = [5, 9, 12, 13, 16, 45] # seznam obsahující nepoužité uzly nodes = [] # převod znaků a frekvencí # na uzly huffmanova stromu pro x v rozsahu(len(znaky)): heapq .heappush(nodes, node(freq[x], chars[x])) while len(nodes)> 1: # seřadit všechny uzly ve vzestupném pořadí # podle jejich frekvence left = heapq.heappop(nodes) right = heapq .heappop(nodes) # přiřadí směrovou hodnotu těmto uzlům left.huff = 0 right.huff = 1 # zkombinujte 2 nejmenší uzly a vytvořte # nový uzel jako jejich nadřazený newNode = node(left.freq+right.freq, left. symbol+right.symbol, left, right) heapq.heappush(nodes, newNode) # Huffman Tree je připraven! 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 první minuty. nechť x = q[0]; q.shift(); // extrakt sekundy min. nechť y = q[0]; q.shift(); // nový uzel f, který se rovná let f = new HuffmanNode(); // k součtu frekvence dvou uzlů // přiřazování hodnot k uzlu f. f.data = x.data + y.data; f.c = '-'; // první extrahovaný uzel jako levý potomek. f.left = x; // druhý extrahovaný uzel jako správný potomek. f.vpravo = y; // označení uzlu f jako kořenového uzlu. kořen = f; // přidejte tento uzel do fronty priority. q.push(f); q.sort(function(a,b){return a.data-b.data;}); } // vytiskne kódy procházením stromu printCode(root, ''); // Tento kód přispěl 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ýstup

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

Časová složitost: O(nlogn) kde n je počet jedinečných znaků. Pokud existuje n uzlů, je extractMin() voláno 2*(n – 1)krát. extractMin() trvá O(logn) čas, když volá minHeapify(). Celková složitost je tedy O(nlogn).
Pokud je vstupní pole tříděno, existuje lineární časový algoritmus. Brzy o tom budeme diskutovat v našem dalším příspěvku.

Prostorová složitost :- O(N)

Aplikace Huffmanova kódování:

1. Používají se pro přenos faxu a textu.
2. Používají je konvenční kompresní formáty jako PKZIP, GZIP atd.
3. Multimediální kodeky jako JPEG, PNG a MP3 používají Huffmanovo kódování (přesněji předponové kódy).

Je to užitečné v případech, kdy existuje řada často se vyskytujících znaků.

Odkaz:
http://cs.wikipedia.org/wiki/Huffman_coding
Tento článek sestavil Aashish Barnwal a zkontroloval ho tým techcodeview.com.