Huffman-kodning är en förlustfri datakomprimeringsalgoritm. Tanken är att tilldela koder med variabel längd till inmatningstecken, längden på de tilldelade koderna baseras på frekvenserna för motsvarande tecken.
Koderna med variabel längd som tilldelas indatatecken är Prefixkoder , betyder att koderna (bitsekvenserna) är tilldelade på ett sådant sätt att koden som tilldelas ett tecken inte är prefixet för kod som tilldelats något annat tecken. Detta är hur Huffman Coding säkerställer att det inte finns någon tvetydighet vid avkodning av den genererade bitströmmen.
Låt oss förstå prefixkoder med ett motexempel. Låt det finnas fyra tecken a, b, c och d, och deras motsvarande koder med variabel längd vara 00, 01, 0 och 1. Denna kodning leder till tvetydighet eftersom kod som tilldelas c är prefixet för koder som tilldelats a och b. Om den komprimerade bitströmmen är 0001, kan den dekomprimerade utsignalen vara cccd eller ccb eller acd eller ab.
Ser detta för tillämpningar av Huffman Coding.
Det finns huvudsakligen två huvuddelar i Huffman Coding
- Bygg ett Huffman-träd från ingående karaktärer.
- Gå igenom Huffman-trädet och tilldela koder till karaktärer.
Algoritm:
Metoden som används för att konstruera optimal prefixkod kallas Huffman kodning .
Denna algoritm bygger ett träd nedifrån och upp. Vi kan beteckna detta träd med T
Låt, |c| vara antal blad
|c| -1 är antalet operationer som krävs för att slå samman noderna. Q är prioritetskön som kan användas vid konstruktion av binär hög.
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) }> Steg för att bygga Huffman Tree
Indata är en rad unika karaktärer tillsammans med deras frekvens av händelser och utdata är Huffman Tree.
- Skapa en lövnod för varje unik karaktär och bygg en min-hög av alla lövnoder (Min-hög används som en prioritetskö. Värdet på frekvensfältet används för att jämföra två noder i min-hög. Inledningsvis är det minst frekventa tecknet vid rot)
- Extrahera två noder med lägsta frekvens från min-högen.
- Skapa en ny intern nod med en frekvens lika med summan av de två nodernas frekvenser. Gör den första extraherade noden som dess vänstra underordnade och den andra extraherade noden som dess högra underordnade. Lägg till denna nod till min-högen.
- Upprepa steg #2 och #3 tills högen bara innehåller en nod. Den återstående noden är rotnoden och trädet är komplett.
Låt oss förstå algoritmen med ett exempel:
character Frequency a 5 b 9 c 12 d 13 e 16 f 45>
Steg 1. Bygg en min-hög som innehåller 6 noder där varje nod representerar roten av ett träd med en enda nod.
Steg 2 Extrahera två lägsta frekvensnoder från min heap. Lägg till en ny intern nod med frekvens 5 + 9 = 14.
Illustration av steg 2
Nu innehåller min heap 5 noder där 4 noder är rötter till träd med ett enda element var och en heap nod är roten till träd med 3 element
character Frequency c 12 d 13 Internal Node 14 e 16 f 45>
Steg 3: Extrahera två lägsta frekvensnoder från heap. Lägg till en ny intern nod med frekvensen 12 + 13 = 25
Illustration av steg 3
Nu innehåller min heap 4 noder där 2 noder är rötter till träd med ett enda element vardera, och två heapnoder är roten till träd med mer än en nod
character Frequency Internal Node 14 e 16 Internal Node 25 f 45>
Steg 4: Extrahera två lägsta frekvensnoder. Lägg till en ny intern nod med frekvensen 14 + 16 = 30
Illustration av steg 4
Nu innehåller min heap 3 noder.
character Frequency Internal Node 25 Internal Node 30 f 45>
Steg 5: Extrahera två lägsta frekvensnoder. Lägg till en ny intern nod med frekvensen 25 + 30 = 55
Illustration av steg 5
Nu innehåller min heap 2 noder.
character Frequency f 45 Internal Node 55>
Steg 6: Extrahera två lägsta frekvensnoder. Lägg till en ny intern nod med frekvensen 45 + 55 = 100
Illustration av steg 6
Nu innehåller min heap bara en nod.
character Frequency Internal Node 100>
Eftersom högen bara innehåller en nod, stannar algoritmen här.
Steg för att skriva ut koder från Huffman Tree:
Traversera det bildade trädet med början från roten. Underhåll en extra array. När du flyttar till vänster barn skriver du 0 till arrayen. När du flyttar till rätt barn, skriv 1 till arrayen. Skriv ut arrayen när en lövnod påträffas.
Steg för att skriva ut kod från HuffmanTree
Koderna är följande:
character code-word f 0 c 100 d 101 a 1100 b 1101 e 111>Rekommenderad övning Huffman-kodning Prova!
Nedan är implementeringen av ovanstående tillvägagångssätt:
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änster = temp->höger = 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->storlek = 0;> > >minHeap->kapacitet = kapacitet;> > >minHeap->array = (>struct> MinHeapNode**)>malloc>(> >minHeap->kapacitet *>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[vänster]->frekv> >array[smallest]->frekv)> >smallest = left;> > >if> (right size> >&& minHeap->array[höger]->freq> >array[smallest]->frekv)> >smallest = right;> > >if> (smallest != idx) {> >swapMinHeapNode(&minHeap->array[minst],> >&minHeap->array[idx]);> >minHeapify(minHeap, smallest);> >}> }> > // A utility function to check> // if size of heap is 1 or not> int> isSizeOne(>struct> MinHeap* minHeap)> {> > >return> (minHeap->storlek == 1);> }> > // A standard function to extract> // minimum value node from heap> struct> MinHeapNode* extractMin(>struct> MinHeap* minHeap)> > {> > >struct> MinHeapNode* temp = minHeap->array[0];> >minHeap->array[0] = minHeap->array[minHeap->storlek - 1];> > >--minHeap->storlek;> >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->storlek;> >int> i = minHeap->storlek - 1;> > >while> (i> >&& minHeapNode->frekv> >array[(i - 1) / 2]->freq) {> > >minHeap->array[i] = minHeap->array[(i - 1) / 2];> >i = (i - 1) / 2;> >}> > >minHeap->array[i] = minHeapNode;> }> > // A standard function to build min heap> void> buildMinHeap(>struct> MinHeap* minHeap)> > {> > >int> n = minHeap->storlek - 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änster) && !(root->höger); } // Skapar en min hög med kapacitet // lika med storlek och infogar alla tecken på // data[] i min hög. Initialt är storleken på // min heap lika med kapacitetsstruktur 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 = size; buildMinHeap(minHeap); return minHeap; } // Huvudfunktionen som bygger Huffman-trädstrukturen MinHeapNode* buildHuffmanTree(char data[], int freq[], int size) { struct MinHeapNode *vänster, *höger, *top // Steg 1: Skapa en minhög med kapacitet // lika med storlek . Inledningsvis finns det //-lägen som är lika med storleken MinHeap* minHeap = createAndBuildMinHeap(data, freq, size // Iterera medan storleken på högen inte blir 1 while (!isSizeOne(minHeap)) { //; Steg 2: Extrahera de två minsta // freq objekten från min heap left = extractMin(minHeap right = extractMin(minHeap); // Steg 3: Skapa en ny intern // nod med frekvensen lika med // summan av två noder frekvenser // Gör de två extraherade noderna som // vänster och höger underordnade av denna nya nod // Lägg till denna nod till min högen // '$' är ett speciellt värde för interna noder, inte //. använd top = newNode('$', vänster->frekv + höger->frekv); topp->vänster = vänster; topp->höger = höger; insertMinHeap(minHeap, topp); } // Steg 4: Den återstående noden är // rotnoden och trädet är komplett. returnera extraktMin(minHeap); } // Skriver ut huffman-koder från roten av Huffman Tree. // Den använder arr[] för att lagra koder void printCodes(struct MinHeapNode* root, int arr[], int top) { // Tilldela 0 till vänster kant och återkommer om (root->left) { arr[top] = 0 ; printCodes(root->vänster, arr, topp + 1); } // Tilldela 1 till höger kant och upprepas om (root->right) { arr[top] = 1; printCodes(root->right, arr, top + 1); } // Om detta är en lövnod, då // den innehåller ett av de ingående //-tecknen, skriv ut tecknet // och dess kod från arr[] if (isLeaf(root)) { printf('%c: ', root->data); printArr(arr, topp); } } // Huvudfunktionen som bygger ett // Huffman Tree och skriver ut koder genom att korsa // det byggda Huffman Tree void HuffmanCodes(char data[], int freq[], int size) { // Construct Huffman Tree struct MinHeapNode* root = buildHuffmanTree(data, frekv, storlek); // Skriv ut Huffman-koder med // Huffman-trädet byggt ovanför int arr[MAX_TREE_HT], top = 0; printCodes(root, arr, top); } // Drivrutinskod int main() { char arr[] = { 'a', 'b', 'c', 'd', 'e', 'f ' }; int freq[] = {5, 9, 12, 13, 16, 45}; int size = sizeof(arr) / sizeof(arr[0]); HuffmanCodes(arr, frekv, storlek); returnera 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änster = temp->höger = 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->storlek = 0;> > >minHeap->kapacitet = kapacitet;> > >minHeap->array = (>struct> MinHeapNode**)>malloc>(> >minHeap->kapacitet *>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[vänster]->frekv> >array[smallest]->frekv)> >smallest = left;> > >if> (right size> >&& minHeap->array[höger]->freq> >array[smallest]->frekv)> >smallest = right;> > >if> (smallest != idx) {> >swapMinHeapNode(&minHeap->array[minst],> >&minHeap->array[idx]);> >minHeapify(minHeap, smallest);> >}> }> > // A utility function to check> // if size of heap is 1 or not> int> isSizeOne(>struct> MinHeap* minHeap)> {> > >return> (minHeap->storlek == 1);> }> > // A standard function to extract> // minimum value node from heap> struct> MinHeapNode* extractMin(>struct> MinHeap* minHeap)> > {> > >struct> MinHeapNode* temp = minHeap->array[0];> >minHeap->array[0] = minHeap->array[minHeap->storlek - 1];> > >--minHeap->storlek;> >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->storlek;> >int> i = minHeap->storlek - 1;> > >while> (i> >&& minHeapNode->frekv> >array[(i - 1) / 2]->freq) {> > >minHeap->array[i] = minHeap->array[(i - 1) / 2];> >i = (i - 1) / 2;> >}> > >minHeap->array[i] = minHeapNode;> }> > // A standard function to build min heap> void> buildMinHeap(>struct> MinHeap* minHeap)> > {> > >int> n = minHeap->storlek - 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änster) && !(root->höger); } // Skapar en min hög med kapacitet // lika med storlek och infogar alla tecken på // data[] i min hög. Initialt är storleken på // min heap lika med kapacitetsstruktur 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 = size; buildMinHeap(minHeap); return minHeap; } // Huvudfunktionen som bygger Huffman-trädstrukturen MinHeapNode* buildHuffmanTree(char data[], int freq[], int size) { struct MinHeapNode *vänster, *höger, *top // Steg 1: Skapa en minhög med kapacitet // lika med storlek . Inledningsvis finns det //-lägen som är lika med storleken MinHeap* minHeap = createAndBuildMinHeap(data, freq, size // Iterera medan storleken på högen inte blir 1 while (!isSizeOne(minHeap)) { //; Steg 2: Extrahera de två minsta // freq objekten från min heap left = extractMin(minHeap right = extractMin(minHeap); // Steg 3: Skapa en ny intern // nod med frekvensen lika med // summan av två noder frekvenser // Gör de två extraherade noderna som // vänster och höger underordnade av denna nya nod // Lägg till denna nod till min högen // '$' är ett speciellt värde för interna noder, inte //. använd top = newNode('$', vänster->frekv + höger->frekv); topp->vänster = vänster; topp->höger = höger; insertMinHeap(minHeap, topp); } // Steg 4: Den återstående noden är // rotnoden och trädet är komplett. returnera extraktMin(minHeap); } // Skriver ut huffman-koder från roten av Huffman Tree. // Den använder arr[] för att lagra koder void printCodes(struct MinHeapNode* root, int arr[], int top) { // Tilldela 0 till vänster kant och återkommer om (root->left) { arr[top] = 0 ; printCodes(root->vänster, arr, topp + 1); } // Tilldela 1 till höger kant och upprepas om (root->right) { arr[top] = 1; printCodes(root->right, arr, top + 1); } // Om detta är en lövnod, då // den innehåller ett av de ingående //-tecknen, skriv ut tecknet // och dess kod från arr[] if (isLeaf(root)) { cout ': '; printArr(arr, topp); } } // Huvudfunktionen som bygger ett // Huffman Tree och skriver ut koder genom att korsa // det byggda Huffman Tree void HuffmanCodes(char data[], int freq[], int size) { // Construct Huffman Tree struct MinHeapNode* root = buildHuffmanTree(data, frekv, storlek); // Skriv ut Huffman-koder med // Huffman-trädet byggt ovanför int arr[MAX_TREE_HT], top = 0; printCodes(root, arr, top); } // Drivrutinskod int main() { char arr[] = { 'a', 'b', 'c', 'd', 'e', 'f ' }; int freq[] = {5, 9, 12, 13, 16, 45}; int size = sizeof(arr) / sizeof(arr[0]); HuffmanCodes(arr, frekv, storlek); returnera 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->freq> r->freq);> >}> };> > // 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->vänster, str + '0'); printCodes(root->right, str + '1'); } // Huvudfunktionen som bygger ett Huffman-träd och // skriver ut koder genom att korsa det byggda Huffman-trädet void HuffmanCodes(char data[], int freq[], int size) { struct MinHeapNode *left, *right, *top; // Skapa en min heap & infogar alla tecken i data[] priority_queue compare> minHeap; for (int i = 0; i minHeap.push(new MinHeapNode(data[i], freq[i])); // Iterera medan storleken på heapen inte blir 1 while (minHeap.size() != 1 ) { // Extrahera de två minsta // freq objekten från min heap left = minHeap.pop(); med // frekvens lika med summan av // två noder frekvenser Gör // två extraherade noden som vänster och höger underordnade // av denna nya nod // till min högen '$' ett speciellt värde // för interna noder, används inte top = new MinHeapNode('$', left->freq + right->left = left = minHeap.push; (top); } // Skriv ut Huffman-koder med // Huffman-trädet byggt ovanför printCodes(minHeap.top(), '' } // Driver Code int main() { char arr[] = { '); a', 'b', 'c', 'd', 'e', 'f' }; int freq[] = { 5, 9, 12, 13, 16 , 45 }; int size = sizeof(arr) / sizeof(arr[0]); returnera 0; } // Denna kod är bidragit av 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) { // första min extrakt. HuffmanNode x = q.peek(); q.poll(); // sekund min extrakt. HuffmanNode y = q.peek(); q.poll(); // ny nod f som är lika med HuffmanNode f = new HuffmanNode(); // till summan av frekvensen för de två noderna // tilldelar värden till f-noden. f.data = x.data + y.data; f.c = '-'; // första extraherade noden som vänster barn. f.vänster = x; // andra extraherade noden som rätt barn. f.höger = y; // markerar f-noden som rotnoden. rot = f; // lägg till denna nod i prioritetskön. q.add(f); } // skriv ut koderna genom att gå igenom trädet printCode(root, ''); } } // nodklass är den grundläggande strukturen // för varje nod som finns i Huffman - trädet. klass HuffmanNode { int data; kol c; HuffmanNode vänster; HuffmanNode höger; } // komparatorklassen hjälper till att jämföra noden // på basis av ett av dess attribut. // Här kommer vi att jämföras // på basis av datavärden för noderna. class MyComparator implementerar Comparator { public int compare(HuffmanNode x, HuffmanNode y) { return x.data - y.data; } } // Denna kod är bidragit av 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}') # tecken för huffman tree chars = ['a', 'b', 'c', 'd', 'e', 'f'] # frekvens av tecken freq = [5, 9, 12, 13, 16, 45] # lista som innehåller oanvända noder noder = [] # konverterar tecken och frekvenser # till huffman tree noder för x i intervallet(len(tecken)): heapq .heappush(noder, nod(frekv[x], tecken[x])) medan len(noder)> 1: # sortera alla noder i stigande ordning # baserat på deras frekvens vänster = heapq.heappop(noder) höger = heapq .heappop(noder) # tilldela riktningsvärden till dessa noder left.huff = 0 right.huff = 1 # kombinera de 2 minsta noderna för att skapa # ny nod som deras överordnade newNode = node(left.freq+right.freq, left. symbol+höger.symbol, vänster, höger) heapq.heappush(noder, newNode) # Huffman Tree är redo! printNodes(noder[0])> |
>
>
vad är mac os
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) { // första min extrakt. låt x = q[0]; q.shift(); // sekund min extrakt. låt y = q[0]; q.shift(); // ny nod f som är lika låt f = new HuffmanNode(); // till summan av frekvensen för de två noderna // tilldelar värden till f-noden. f.data = x.data + y.data; f.c = '-'; // första extraherade noden som vänster barn. f.vänster = x; // andra extraherade noden som rätt barn. f.höger = y; // markerar f-noden som rotnoden. rot = f; // lägg till denna nod i prioritetskön. q.push(f); q.sort(function(a,b){retur a.data-b.data;}); } // skriv ut koderna genom att gå igenom trädet printCode(root, ''); // Denna kod är bidragit av 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> |
>
>Produktion
f: 0 c: 100 d: 101 a: 1100 b: 1101 e: 111>
Tidskomplexitet: O(nlogn) där n är antalet unika tecken. Om det finns n noder kallas extractMin() 2*(n – 1) gånger. extractMin() tar O(logn)-tid eftersom det anropar minHeapify(). Så den övergripande komplexiteten är O(nlogn).
Om inmatningsmatrisen är sorterad, finns det en linjär tidsalgoritm. Vi kommer snart att diskutera detta i vårt nästa inlägg.
Rymdkomplexitet :- O(N)
Tillämpningar av Huffman Coding:
- De används för att överföra fax och text.
- De används av konventionella komprimeringsformat som PKZIP, GZIP, etc.
- Multimedia-codecs som JPEG, PNG och MP3 använder Huffman-kodning (för att vara mer exakt prefixkoderna).
Det är användbart i fall där det finns en serie ofta förekommande karaktärer.
Referens:
http://en.wikipedia.org/wiki/Huffman_coding
Den här artikeln är sammanställd av Aashish Barnwal och granskad av techcodeview.com-teamet.