Huffman-kodning er en tabsfri datakomprimeringsalgoritme. Ideen er at tildele koder med variabel længde til inputtegn, længden af de tildelte koder er baseret på frekvenserne af tilsvarende tegn.
Koderne med variabel længde, der er tildelt inputtegn, er Præfikskoder , betyder, at koderne (bitsekvenser) er tildelt på en sådan måde, at koden, der er tildelt et tegn, ikke er præfikset for kode, der er tildelt et andet tegn. Sådan sikrer Huffman Coding, at der ikke er nogen tvetydighed, når den genererede bitstrøm afkodes.
Lad os forstå præfikskoder med et tællereksempel. Lad der være fire tegn a, b, c og d, og deres tilsvarende variable længdekoder være 00, 01, 0 og 1. Denne kodning fører til tvetydighed, fordi kode tildelt c er præfikset for koder tildelt til a og b. Hvis den komprimerede bitstrøm er 0001, kan det dekomprimerede output være cccd eller ccb eller acd eller ab.
Se det her til applikationer af Huffman Coding.
Der er hovedsageligt to hoveddele i Huffman Coding
- Byg et Huffman-træ fra input-karakterer.
- Gå gennem Huffman-træet og tildel koder til karakterer.
Algoritme:
Metoden som bruges til at konstruere optimal præfikskode kaldes Huffman kodning .
Denne algoritme bygger et træ på bottom-up måde. Vi kan betegne dette træ med T
Lad, |c| være antal blade
|c| -1 er antallet af operationer, der kræves for at flette noderne. Q være prioritetskøen, som kan bruges under konstruktion af binær heap.
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) }> Trin til at bygge Huffman Tree
Input er en række unikke karakterer sammen med deres hyppighed af forekomster, og output er Huffman Tree.
- Opret en bladknude for hvert unikt tegn, og byg en min hob af alle bladknuder (Min heap bruges som en prioritetskø. Værdien af frekvensfeltet bruges til at sammenligne to noder i min hob. I starten er det mindst hyppige tegn kl. rod)
- Udtræk to noder med minimumsfrekvensen fra min-heapen.
- Opret en ny intern knude med en frekvens svarende til summen af de to knudepunkters frekvenser. Gør den første ekstraherede node som dens venstre underordnede og den anden ekstraherede knude som dens højre underordnede. Føj denne node til min heap.
- Gentag trin #2 og #3, indtil heapen kun indeholder én node. Den resterende knude er rodknuden, og træet er komplet.
Lad os forstå algoritmen med et eksempel:
character Frequency a 5 b 9 c 12 d 13 e 16 f 45>
Trin 1. Byg en min hob, der indeholder 6 noder, hvor hver node repræsenterer roden af et træ med enkelt node.
Trin 2 Udtræk to minimumsfrekvensknuder fra min heap. Tilføj en ny intern node med frekvens 5 + 9 = 14.
Illustration af trin 2
Nu indeholder min heap 5 noder, hvor 4 noder er rødder af træer med et enkelt element hver, og en heap node er roden af træ med 3 elementer
kajal aggarwal
character Frequency c 12 d 13 Internal Node 14 e 16 f 45>
Trin 3: Udtræk to minimumsfrekvensknuder fra heap. Tilføj en ny intern node med frekvens 12 + 13 = 25
Illustration af trin 3
Nu indeholder min heap 4 noder, hvor 2 noder er rødder af træer med et enkelt element hver, og to heap noder er roden af træ med mere end én node
character Frequency Internal Node 14 e 16 Internal Node 25 f 45>
Trin 4: Udtræk to minimumsfrekvensknuder. Tilføj en ny intern node med frekvensen 14 + 16 = 30
Illustration af trin 4
Nu indeholder min heap 3 noder.
character Frequency Internal Node 25 Internal Node 30 f 45>
Trin 5: Udtræk to minimumsfrekvensknuder. Tilføj en ny intern node med frekvensen 25 + 30 = 55
Illustration af trin 5
Nu indeholder min heap 2 noder.
character Frequency f 45 Internal Node 55>
Trin 6: Udtræk to minimumsfrekvensknuder. Tilføj en ny intern node med frekvens 45 + 55 = 100
Illustration af trin 6
Nu indeholder min heap kun én node.
character Frequency Internal Node 100>
Da heapen kun indeholder én node, stopper algoritmen her.
Trin til at udskrive koder fra Huffman Tree:
Kryds det dannede træ fra roden. Vedligehold et hjælpearray. Mens du flytter til venstre barn, skriv 0 til arrayet. Mens du flytter til det rigtige barn, skal du skrive 1 til arrayet. Udskriv arrayet, når der stødes på en bladknude.
Trin til at udskrive kode fra HuffmanTree
Koderne er som følger:
character code-word f 0 c 100 d 101 a 1100 b 1101 e 111>Anbefalet praksis Huffman-kodning Prøv det!
Nedenfor er implementeringen af ovenstående tilgang:
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->venstre = temp->højre = 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->størrelse = 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[venstre]->freq> >array[smallest]->freq)> >smallest = left;> > >if> (right size> >&& minHeap->array[højre]->freq> >array[smallest]->freq)> >smallest = right;> > >if> (smallest != idx) {> >swapMinHeapNode(&minHeap->array[mindst],> >&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->størrelse == 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->størrelse - 1];> > >--minHeap->størrelse;> >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->størrelse;> >int> i = minHeap->størrelse - 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->størrelse - 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->venstre) && !(rod->højre); } // Opretter en min. bunke af kapacitet // lig med størrelse og indsætter alle karakterer af // data[] i min heap. Oprindeligt er størrelsen på // min heap lig 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->størrelse = størrelse; buildMinHeap(minHeap); return minHeap; } // Hovedfunktionen der bygger Huffman-træstruktur MinHeapNode* buildHuffmanTree(char data[], int freq[], int size) { struct MinHeapNode *venstre, *højre, *top // Trin 1: Opret en min. bunke af kapacitet // lig med størrelse . Til at begynde med er der //-tilstande lig med størrelsen struct MinHeap* minHeap = createAndBuildMinHeap(data, freq, size // Iterer mens størrelsen af heapen ikke bliver 1 mens (!isSizeOne(minHeap)) { //. Trin 2: Udtræk de to minimum // freq elementer fra min heap left = extractMin(minHeap right = extractMin(minHeap); // Trin 3: Opret en ny intern // node med frekvens lig med // summen af to noder frekvenser // Gør de to udtrukne noder som // venstre og højre underordnede af denne nye node // Tilføj denne node til min heap // '$' er en speciel værdi for interne noder, ikke //. brugt top = newNode('$', venstre->frekv + højre->frekv); top->venstre = venstre; top->højre = højre; insertMinHeap(minHeap, top); } // Trin 4: Den resterende node er //-rodknuden, og træet er komplet. returner extractMin(minHeap); } // Udskriver huffman-koder fra roden af Huffman Tree. // Det bruger arr[] til at gemme koder void printCodes(struct MinHeapNode* root, int arr[], int top) { // Tildel 0 til venstre kant og gentages hvis (root->venstre) { arr[top] = 0 ; printCodes(root->venstre, arr, top + 1); } // Tildel 1 til højre kant og gentag hvis (root->right) { arr[top] = 1; printCodes(root->right, arr, top + 1); } // Hvis dette er en bladknude, så // den indeholder et af input // tegnene, udskriv tegnet // og dets kode fra arr[] if (isLeaf(root)) { printf('%c: ', root->data); printArr(arr, top); } } // Hovedfunktionen, der bygger et // Huffman Tree og udskriver koder ved at krydse // det indbyggede Huffman Tree void HuffmanCodes(char data[], int freq[], int size) { // Construct Huffman Tree struct MinHeapNode* root = buildHuffmanTree(data, freq, size); // Udskriv Huffman-koder ved hjælp af // Huffman-træet bygget over int arr[MAX_TREE_HT], top = 0; printCodes(root, arr, top); } // Driverkode 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, freq, størrelse); retur 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->venstre = temp->højre = 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->størrelse = 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[venstre]->freq> >array[smallest]->freq)> >smallest = left;> > >if> (right size> >&& minHeap->array[højre]->freq> >array[smallest]->freq)> >smallest = right;> > >if> (smallest != idx) {> >swapMinHeapNode(&minHeap->array[mindst],> >&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->størrelse == 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->størrelse - 1];> > >--minHeap->størrelse;> >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->størrelse;> >int> i = minHeap->størrelse - 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->størrelse - 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->venstre) && !(rod->højre); } // Opretter en min. bunke af kapacitet // lig med størrelse og indsætter alle karakterer af // data[] i min heap. Oprindeligt er størrelsen på // min heap lig 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->størrelse = størrelse; buildMinHeap(minHeap); return minHeap; } // Hovedfunktionen der bygger Huffman-træstruktur MinHeapNode* buildHuffmanTree(char data[], int freq[], int size) { struct MinHeapNode *venstre, *højre, *top // Trin 1: Opret en min. bunke af kapacitet // lig med størrelse . Til at begynde med er der //-tilstande lig med størrelsen struct MinHeap* minHeap = createAndBuildMinHeap(data, freq, size // Iterer mens størrelsen af heapen ikke bliver 1 mens (!isSizeOne(minHeap)) { //. Trin 2: Udtræk de to minimum // freq elementer fra min heap left = extractMin(minHeap right = extractMin(minHeap); // Trin 3: Opret en ny intern // node med frekvens lig med // summen af to noder frekvenser // Gør de to udtrukne noder som // venstre og højre underordnede af denne nye node // Tilføj denne node til min heap // '$' er en speciel værdi for interne noder, ikke //. brugt top = newNode('$', venstre->frekv + højre->frekv); top->venstre = venstre; top->højre = højre; insertMinHeap(minHeap, top); } // Trin 4: Den resterende node er //-rodknuden, og træet er komplet. returner extractMin(minHeap); } // Udskriver huffman-koder fra roden af Huffman Tree. // Den bruger arr[] til at gemme koder void printCodes(struct MinHeapNode* root, int arr[], int top) { // Tildel 0 til venstre kant og gentages hvis (root->venstre) { arr[top] = 0 ; printCodes(root->venstre, arr, top + 1); } // Tildel 1 til højre kant og gentag hvis (root->right) { arr[top] = 1; printCodes(root->right, arr, top + 1); } // Hvis dette er en bladknude, så // den indeholder et af input // tegnene, udskriv tegnet // og dets kode fra arr[] if (isLeaf(root)) { cout ': '; printArr(arr, top); } } // Hovedfunktionen, der bygger et // Huffman Tree og udskriver koder ved at krydse // det indbyggede Huffman Tree void HuffmanCodes(char data[], int freq[], int size) { // Construct Huffman Tree struct MinHeapNode* root = buildHuffmanTree(data, frekv, størrelse); // Udskriv Huffman-koder ved hjælp af // Huffman-træet bygget over int arr[MAX_TREE_HT], top = 0; printCodes(root, arr, top); } // Driverkode 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, freq, størrelse); retur 0; }> |
>
>
C++
binær søgealgoritme
// 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->venstre, str + '0'); printCodes(root->right, str + '1'); } // Hovedfunktionen, der bygger et Huffman-træ og // udskriver koder ved at krydse det indbyggede Huffman-træ void HuffmanCodes(char data[], int freq[], int size) { struct MinHeapNode *left, *right, *top; // Opret en min heap & indsætter alle tegn i data[] priority_queue compare> minHeap; for (int i = 0; i minHeap.push(ny MinHeapNode(data[i], freq[i])); // Iterer mens størrelsen af heap ikke bliver 1 mens (minHeap.size() != 1 ) { // Uddrag de to minimum // freq-elementer fra minHeap.top(); med // frekvens lig med summen af // to noder frekvenser Gør // to ekstraherede node som venstre og højre underordnede // af denne nye node // til min bunken '$' er en speciel værdi // for interne noder, ikke brugt top = new MinHeapNode('$', venstre->freq + højre->venstre = venstre->højre = højre; (top); } // Udskriv Huffman-koder ved at bruge // Huffman-træet bygget over 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]); retur 0; } // Denne kode er bidraget af 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ørste min ekstrakt. HuffmanNode x = q.peek(); q.poll(); // sekund min ekstrakt. HuffmanNode y = q.peek(); q.poll(); // ny node f som er lig HuffmanNode f = new HuffmanNode(); // til summen af frekvensen af de to noder // tildeler værdier til f-knuden. f.data = x.data + y.data; f.c = '-'; // første udtrukne node som venstre barn. f.venstre = x; // anden ekstraheret node som det rigtige barn. f.højre = y; // markerer f-noden som rodknuden. rod = f; // tilføj denne node til prioritetskøen. q.add(f); } // udskriv koderne ved at krydse træet printCode(root, ''); } } // node klasse er den grundlæggende struktur // af hver node til stede i Huffman - træet. klasse HuffmanNode { int data; char c; HuffmanNode venstre; HuffmanNode højre; } // komparatorklassen hjælper med at sammenligne noden // på basis af en af dens attributter. // Her vil vi blive sammenlignet // på baggrund af nodernes dataværdier. klasse MyComparator implementerer Comparator { public int compare(HuffmanNode x, HuffmanNode y) { return x.data - y.data; } } // Denne kode er bidraget af Kunwar Desh Deepak Singh> |
>
>
ressourceallokeringsgraf
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}') # tegn for huffman tree chars = ['a', 'b', 'c', 'd', 'e', 'f'] # frekvens af tegn freq = [5, 9, 12, 13, 16, 45] # liste med ubrugte noder noder = [] # konvertering af tegn og frekvenser # til huffman tree noder for x i rækkevidde(len(tegn)): heapq .heappush(nodes, node(freq[x], chars[x])) mens len(nodes)> 1: # sortere alle noderne i stigende rækkefølge # baseret på deres frekvens venstre = heapq.heappop(nodes) højre = heapq .heappop(nodes) # tildel retningsbestemt værdi til disse noder left.huff = 0 right.huff = 1 # kombiner de 2 mindste noder for at skabe # ny node som deres overordnede newNode = node(left.freq+right.freq, left. symbol+højre.symbol, venstre, højre) heapq.heappush(noder, nyNode) # Huffman Tree er klar! printNodes(nodes[0])> |
>
>
Javascript
1 milliard til mio
> > // 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ørste min ekstrakt. lad x = q[0]; q.shift(); // sekund min ekstrakt. lad y = q[0]; q.shift(); // ny node f som er lig lad f = new HuffmanNode(); // til summen af frekvensen af de to noder // tildeler værdier til f-knuden. f.data = x.data + y.data; f.c = '-'; // første udtrukne knude som venstre barn. f.venstre = x; // anden ekstraheret node som det rigtige barn. f.højre = y; // markerer f-noden som rodknuden. rod = f; // tilføj denne node til prioritetskøen. q.push(f); q.sort(funktion(a,b){retur a.data-b.data;}); } // udskriv koderne ved at krydse træet printCode(root, ''); // Denne kode er bidraget af 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>
Tidskompleksitet: O(nlogn) hvor n er antallet af unikke tegn. Hvis der er n noder, kaldes extractMin() 2*(n – 1) gange. extractMin() tager O(logn) tid, da det kalder minHeapify(). Så den overordnede kompleksitet er O(nlogn).
Hvis input-arrayet er sorteret, eksisterer der en lineær tidsalgoritme. Vi vil snart diskutere dette i vores næste indlæg.
Rumkompleksitet :- O(N)
Anvendelser af Huffman Coding:
- De bruges til at sende fax og tekst.
- De bruges af konventionelle komprimeringsformater som PKZIP, GZIP osv.
- Multimedie-codecs som JPEG, PNG og MP3 bruger Huffman-kodning (for at være mere præcis, præfikskoderne).
Det er nyttigt i tilfælde, hvor der er en række hyppigt forekommende tegn.
Reference:
http://en.wikipedia.org/wiki/Huffman_coding
Denne artikel er udarbejdet af Aashish Barnwal og gennemgået af techcodeview.com-teamet.