Huffman-koding er en tapsfri datakomprimeringsalgoritme. Ideen er å tilordne koder med variabel lengde til inndatategn, lengder på de tildelte kodene er basert på frekvensene til tilsvarende tegn.
Kodene med variabel lengde tilordnet inndatategn er Prefikskoder , betyr at kodene (bitsekvenser) er tilordnet på en slik måte at koden som er tilordnet ett tegn, ikke er prefikset til kode som er tilordnet noe annet tegn. Dette er hvordan Huffman Coding sørger for at det ikke er noen tvetydighet ved dekoding av den genererte bitstrømmen.
La oss forstå prefikskoder med et telleeksempel. La det være fire tegn a, b, c og d, og deres tilsvarende koder med variabel lengde være 00, 01, 0 og 1. Denne kodingen fører til tvetydighet fordi kode tilordnet c er prefikset til koder tildelt a og b. Hvis den komprimerte bitstrømmen er 0001, kan den dekomprimerte utgangen være cccd eller ccb eller acd eller ab.
Se dette for bruk av Huffman Coding.
Det er hovedsakelig to hoveddeler i Huffman Coding
- Bygg et Huffman-tre fra inndatakarakterer.
- Gå gjennom Huffman-treet og tilordne koder til tegn.
Algoritme:
Metoden som brukes for å konstruere optimal prefikskode kalles Huffman-koding .
Denne algoritmen bygger et tre nedenfra og opp. Vi kan betegne dette treet med T
La, |c| være antall blader
|c| -1 er antall operasjoner som kreves for å slå sammen nodene. Q være prioritetskøen som kan brukes under konstruksjon av 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) }> Trinn for å bygge Huffman Tree
Input er en rekke unike karakterer sammen med deres frekvens av forekomster, og utdata er Huffman Tree.
- Lag en bladnode for hvert unike tegn og bygg en min haug av alle bladnoder (Min Heap brukes som en prioritetskø. Verdien av frekvensfeltet brukes til å sammenligne to noder i min haug. Til å begynne med er det minst hyppige tegnet på rot)
- Trekk ut to noder med minimumsfrekvensen fra min-haugen.
- Opprett en ny intern node med en frekvens lik summen av de to nodefrekvensene. Gjør den første ekstraherte noden til venstre underordnet og den andre ekstraherte noden til høyre underordnet. Legg denne noden til min haugen.
- Gjenta trinn #2 og #3 til haugen inneholder bare én node. Den gjenværende noden er rotnoden og treet er komplett.
La oss forstå algoritmen med et eksempel:
character Frequency a 5 b 9 c 12 d 13 e 16 f 45>
Trinn 1. Bygg en min haug som inneholder 6 noder der hver node representerer roten til et tre med enkelt node.
Steg 2 Trekk ut to minimumsfrekvensnoder fra min heap. Legg til en ny intern node med frekvens 5 + 9 = 14.
Illustrasjon av trinn 2
Nå inneholder min haug 5 noder der 4 noder er røtter av trær med enkeltelement hver, og en haugnode er roten av tre med 3 elementer
regissør Karan Johar
character Frequency c 12 d 13 Internal Node 14 e 16 f 45>
Trinn 3: Trekk ut to minimumsfrekvensnoder fra heap. Legg til en ny intern node med frekvens 12 + 13 = 25
Illustrasjon av trinn 3
Nå inneholder min haug 4 noder der 2 noder er røtter til trær med ett element hver, og to haugnoder er roten til treet med mer enn én node
character Frequency Internal Node 14 e 16 Internal Node 25 f 45>
Trinn 4: Trekk ut to minimumsfrekvensnoder. Legg til en ny intern node med frekvens 14 + 16 = 30
Illustrasjon av trinn 4
Nå inneholder min heap 3 noder.
character Frequency Internal Node 25 Internal Node 30 f 45>
Trinn 5: Trekk ut to minimumsfrekvensnoder. Legg til en ny intern node med frekvens 25 + 30 = 55
Illustrasjon av trinn 5
Nå inneholder min heap 2 noder.
character Frequency f 45 Internal Node 55>
Trinn 6: Trekk ut to minimumsfrekvensnoder. Legg til en ny intern node med frekvens 45 + 55 = 100
Illustrasjon av trinn 6
Nå inneholder min heap bare én node.
character Frequency Internal Node 100>
Siden heapen bare inneholder én node, stopper algoritmen her.
Trinn for å skrive ut koder fra Huffman Tree:
Gå gjennom treet som er dannet fra roten. Oppretthold en hjelpematrise. Mens du flytter til venstre barn, skriv 0 til matrisen. Mens du flytter til riktig barn, skriv 1 til matrisen. Skriv ut matrisen når en bladnode påtreffes.
Trinn for å skrive ut kode fra HuffmanTree
Kodene er som følger:
character code-word f 0 c 100 d 101 a 1100 b 1101 e 111>Anbefalt praksis Huffman-koding Prøv det!
Nedenfor er implementeringen av tilnærmingen ovenfor:
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øyre = 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->kapasitet = kapasitet;> > >minHeap->array = (>struct> MinHeapNode**)>malloc>(> >minHeap->kapasitet *>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]->frekv)> >smallest = left;> > >if> (right size> >&& minHeap->array[høyre]->freq> >array[smallest]->frekv)> >smallest = right;> > >if> (smallest != idx) {> >swapMinHeapNode(&minHeap->array[minste],> >&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]->frekv) {> > >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) && !(root->høyre); } // Oppretter en min haug med kapasitet // lik størrelse og setter inn alle tegn til // data[] i min haug. Opprinnelig er størrelsen på // min heap lik kapasitetsstruktur 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; } // Hovedfunksjonen som bygger Huffman tree struct MinHeapNode* buildHuffmanTree(char data[], int freq[], int size) { struct MinHeapNode *venstre, *høyre, *top // Trinn 1: Lag en min haug med kapasitet // lik størrelse . I utgangspunktet er det //-moduser som er lik størrelse struct MinHeap* = createAndBuildMinHeap(data, freq, size // Iterer mens størrelsen på haugen ikke blir 1 mens (!isSizeOne(minHeap)) { //. Trinn 2: Trekk ut de to minste // freq-elementene fra min haug til venstre = extractMin(minHeap); // Trinn 3: Lag en ny intern //-node med frekvens lik // summen av to noder frekvenser // Gjør de to ekstraherte nodene som // venstre og høyre underordnede av denne nye noden // Legg til denne noden til min haugen // '$' er en spesiell verdi for interne noder, ikke //. brukt topp = newNode('$', venstre->frekv + høyre->frekv); topp->venstre = venstre; topp->høyre = høyre; insertMinHeap(minHeap, topp); } // Trinn 4: Den gjenværende noden er // rotnoden og treet er komplett. return extractMin(minHeap); } // Skriver ut huffman-koder fra roten til Huffman Tree. // Den bruker arr[] for å lagre koder void printCodes(struct MinHeapNode* root, int arr[], int top) { // Tilordne 0 til venstre kant og gjenta hvis (root->venstre) { arr[top] = 0 ; printCodes(root->venstre, arr, topp + 1); } // Tilordne 1 til høyre kant og gjenta hvis (root->right) { arr[top] = 1; printCodes(root->right, arr, top + 1); } // Hvis dette er en bladnode, så // den inneholder ett av inndata //-tegnene, skriv ut tegnet // og dets kode fra arr[] if (isLeaf(root)) { printf('%c: ', root->data); printArr(arr, topp); } } // Hovedfunksjonen som bygger et // Huffman Tree og skriver ut koder ved å krysse // det bygde Huffman Tree void HuffmanCodes(char data[], int freq[], int size) { // Construct Huffman Tree struct MinHeapNode* root = buildHuffmanTree(data, frekv, størrelse); // Skriv ut Huffman-koder ved å bruke // Huffman-treet bygget over int arr[MAX_TREE_HT], topp = 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, size); returner 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øyre = 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->kapasitet = kapasitet;> > >minHeap->array = (>struct> MinHeapNode**)>malloc>(> >minHeap->kapasitet *>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]->frekv)> >smallest = left;> > >if> (right size> >&& minHeap->array[høyre]->freq> >array[smallest]->frekv)> >smallest = right;> > >if> (smallest != idx) {> >swapMinHeapNode(&minHeap->array[minste],> >&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]->frekv) {> > >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) && !(root->høyre); } // Oppretter en min haug med kapasitet // lik størrelse og setter inn alle tegn til // data[] i min haug. Opprinnelig er størrelsen på // min heap lik kapasitetsstruktur 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; } // Hovedfunksjonen som bygger Huffman tree struct MinHeapNode* buildHuffmanTree(char data[], int freq[], int size) { struct MinHeapNode *venstre, *høyre, *top // Trinn 1: Lag en min haug med kapasitet // lik størrelse . I utgangspunktet er det //-moduser som er lik størrelse struct MinHeap* = createAndBuildMinHeap(data, freq, size // Iterer mens størrelsen på haugen ikke blir 1 mens (!isSizeOne(minHeap)) { //. Trinn 2: Trekk ut de to minste // freq-elementene fra min haug til venstre = extractMin(minHeap); // Trinn 3: Lag en ny intern //-node med frekvens lik // summen av to noder frekvenser // Gjør de to ekstraherte nodene som // venstre og høyre underordnede av denne nye noden // Legg til denne noden til min haugen // '$' er en spesiell verdi for interne noder, ikke //. brukt topp = nyNode('$', venstre->frekv + høyre->frekv); topp->venstre = venstre; topp->høyre = høyre; insertMinHeap(minHeap, topp); } // Trinn 4: Den gjenværende noden er // rotnoden og treet er komplett. return extractMin(minHeap); } // Skriver ut huffman-koder fra roten til Huffman Tree. // Den bruker arr[] for å lagre koder void printCodes(struct MinHeapNode* root, int arr[], int top) { // Tilordne 0 til venstre kant og gjenta hvis (root->venstre) { arr[top] = 0 ; printCodes(root->venstre, arr, topp + 1); } // Tilordne 1 til høyre kant og gjenta hvis (root->right) { arr[top] = 1; printCodes(root->right, arr, top + 1); } // Hvis dette er en bladnode, så // den inneholder ett av inndata //-tegnene, skriv ut tegnet // og dets kode fra arr[] if (isLeaf(root)) { cout ': '; printArr(arr, topp); } } // Hovedfunksjonen som bygger et // Huffman Tree og skriver ut koder ved å krysse // det bygget Huffman Tree void HuffmanCodes(char data[], int freq[], int size) { // Construct Huffman Tree struct MinHeapNode* root = buildHuffmanTree(data, frekv, størrelse); // Skriv ut Huffman-koder ved å bruke // Huffman-treet bygget over int arr[MAX_TREE_HT], topp = 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, size); returner 0; }> |
>
>
C++
binær søkealgoritme
// 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'); } // Hovedfunksjonen som bygger et Huffman-tre og // skriver ut koder ved å krysse det bygde Huffman-treet void HuffmanCodes(char data[], int freq[], int size) { struct MinHeapNode *left, *right, *top; // Lag en min haug og setter inn alle tegnene i data[] priority_queue compare> minHeap; for (int i = 0; i minHeap.push(new MinHeapNode(data[i], freq[i])); // Iterer mens størrelsen på haugen ikke blir 1 mens (minHeap.size() != 1 ) { // Trekk ut de to minste // freq-elementene fra minHeap.top(); minHeap.pop(); med // frekvens lik summen av // to noder frekvenser Gjør // to ekstraherte node som venstre og høyre underordnede // av denne nye noden // til min haugen '$' en spesiell verdi // for interne noder, ikke brukt topp = new MinHeapNode('$', venstre->freq + høyre->venstre = venstre->høyre = høyre; (top); } // Skriv ut Huffman-koder med // Huffman-treet bygget over printCodes(minHeap.top(), ''); a', 'b', 'c', 'd', 'e', 'f' }; int freq[] = { 5, 9, 12, 13, 16 , 45 }; int size = sizeof(arr) / sizeof(arr[0]); returner 0; } // Denne koden er bidratt 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ørste min ekstrakt. HuffmanNode x = q.peek(); q.poll(); // sekund min ekstrakt. HuffmanNode y = q.peek(); q.poll(); // ny node f som er lik HuffmanNode f = new HuffmanNode(); // til summen av frekvensen til de to nodene // tildeler verdier til f-noden. f.data = x.data + y.data; f.c = '-'; // første ekstraherte node som venstre barn. f.venstre = x; // andre ekstraherte node som det rette barnet. f.høyre = y; // merker f-noden som rotnoden. rot = f; // legg til denne noden i prioritetskøen. q.add(f); } // skriv ut kodene ved å krysse treet printCode(root, ''); } } // nodeklasse er den grunnleggende strukturen // for hver node som er tilstede i Huffman - treet. klasse HuffmanNode { int data; røye c; HuffmanNode venstre; HuffmanNode høyre; } // komparatorklassen hjelper til med å sammenligne noden // på grunnlag av en av dens attributter. // Her skal vi sammenlignes // på grunnlag av dataverdier til nodene. klasse MyComparator implementerer Comparator { public int compare(HuffmanNode x, HuffmanNode y) { return x.data - y.data; } } // Denne koden er bidratt av Kunwar Desh Deepak Singh> |
>
>
java skive
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-tegn = ['a', 'b', 'c', 'd', 'e', 'f'] # frekvens av tegn freq = [5, 9, 12, 13, 16, 45] # liste som inneholder ubrukte noder noder = [] # konverterer tegn og frekvenser # til huffman tree noder for x i rekkevidde(len(tegn)): heapq .heappush(noder, node(frekv[x], tegn[x])) mens len(noder)> 1: # sorterer alle nodene i stigende rekkefølge # basert på deres frekvens venstre = heapq.heappop(noder) høyre = heapq .heappop(noder) # tilordne retningsverdi til disse nodene left.huff = 0 right.huff = 1 # kombiner de 2 minste nodene for å lage # ny node som deres overordnede newNode = node(left.freq+right.freq, left. symbol+høyre.symbol, venstre, høyre) heapq.heappush(noder, nyNode) # Huffman-treet er klart! printNodes(nodes[0])> |
>
>
Javascript
1 milliard til million
> > // 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. la x = q[0]; q.shift(); // sekund min ekstrakt. la y = q[0]; q.shift(); // ny node f som er lik la f = ny HuffmanNode(); // til summen av frekvensen til de to nodene // tildeler verdier til f-noden. f.data = x.data + y.data; f.c = '-'; // første ekstraherte node som venstre barn. f.venstre = x; // andre ekstraherte node som det rette barnet. f.høyre = y; // merker f-noden som rotnoden. rot = f; // legg til denne noden i prioritetskøen. q.trykk(f); q.sort(function(a,b){retur a.data-b.data;}); } // skriv ut kodene ved å krysse treet printCode(root, ''); // Denne koden er bidratt 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> |
>
>Produksjon
f: 0 c: 100 d: 101 a: 1100 b: 1101 e: 111>
Tidskompleksitet: O(nlogn) hvor n er antall unike tegn. Hvis det er n noder, kalles extractMin() 2*(n – 1) ganger. extractMin() tar O(logn)-tid ettersom den kaller minHeapify(). Så den generelle kompleksiteten er O(nlogn).
Hvis inngangsmatrisen er sortert, eksisterer det en lineær tidsalgoritme. Vi vil snart diskutere dette i vårt neste innlegg.
Plass kompleksitet :- O(N)
Anvendelser av Huffman Coding:
- De brukes til å sende faks og tekst.
- De brukes av konvensjonelle komprimeringsformater som PKZIP, GZIP, etc.
- Multimediekodeker som JPEG, PNG og MP3 bruker Huffman-koding (for å være mer presis prefikskodene).
Det er nyttig i tilfeller der det er en rekke ofte forekommende tegn.
Henvisning:
http://en.wikipedia.org/wiki/Huffman_coding
Denne artikkelen er kompilert av Aashish Barnwal og gjennomgått av techcodeview.com-teamet.