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
- Zo vstupných znakov zostavte Huffmanov strom.
- 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
scan.nextstring java
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.
- 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ň)
- Extrahujte dva uzly s minimálnou frekvenciou z min.
- 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.
- 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
skúste catch block 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> |
>
pole pridávanie prvkov java
>
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:
- Používajú sa na prenos faxu a textu.
- Používajú ich konvenčné kompresné formáty ako PKZIP, GZIP atď.
- 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.