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
- Sestavte Huffmanův strom ze vstupních znaků.
- 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.
- 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)
- Extrahujte dva uzly s minimální frekvencí z minimální haldy.
- 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.
- 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
prázdný seznam java
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í:
- Používají se pro přenos faxu a textu.
- Používají je konvenční kompresní formáty jako PKZIP, GZIP atd.
- 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.