Huffman-codering is een verliesvrij algoritme voor gegevenscompressie. Het idee is om codes van variabele lengte toe te wijzen aan invoertekens. De lengte van de toegewezen codes is gebaseerd op de frequenties van overeenkomstige tekens.
De codes met variabele lengte die zijn toegewezen aan invoertekens zijn Voorvoegselcodes , betekent dat de codes (bitreeksen) op zo'n manier worden toegewezen dat de code die aan één teken is toegewezen, niet het voorvoegsel is van een code die aan een ander teken is toegewezen. Op deze manier zorgt Huffman Coding ervoor dat er geen dubbelzinnigheid bestaat bij het decoderen van de gegenereerde bitstream.
Laten we voorvoegselcodes begrijpen met een tegenvoorbeeld. Stel dat er vier tekens a, b, c en d zijn, en hun corresponderende codes met variabele lengte zijn 00, 01, 0 en 1. Deze codering leidt tot dubbelzinnigheid omdat de code die aan c is toegewezen het voorvoegsel is van codes die aan a en b zijn toegewezen. Als de gecomprimeerde bitstroom 0001 is, kan de gedecomprimeerde uitvoer cccd of ccb of acd of ab zijn.
Zien dit voor toepassingen van Huffman-codering.
Er zijn hoofdzakelijk twee hoofdonderdelen in Huffman Coding
- Bouw een Huffman-boom op basis van ingevoerde karakters.
- Doorkruis de Huffman Tree en wijs codes toe aan personages.
Algoritme:
De methode die wordt gebruikt om de optimale prefixcode te construeren, wordt aangeroepen Huffman-codering .
Dit algoritme bouwt een boom op een bottom-up manier. We kunnen deze boom aanduiden met T
Laat, |c| aantal bladeren zijn
|c| -1 is het aantal bewerkingen dat nodig is om de knooppunten samen te voegen. Q de prioriteitswachtrij zijn die kan worden gebruikt bij het construeren van een binaire 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) }> Stappen om Huffman Tree te bouwen
Invoer is een reeks unieke karakters, samen met hun frequentie van voorkomen, en de uitvoer is Huffman Tree.
- Maak een leaf-knooppunt voor elk uniek teken en bouw een min-heap van alle leaf-knooppunten (Min Heap wordt gebruikt als prioriteitswachtrij). De waarde van het frequentieveld wordt gebruikt om twee knooppunten in de min-heap te vergelijken. In eerste instantie bevindt het minst voorkomende teken zich op wortel)
- Extraheer twee knooppunten met de minimale frequentie uit de minimale heap.
- Creëer een nieuw intern knooppunt met een frequentie die gelijk is aan de som van de frequenties van de twee knooppunten. Maak het eerste geëxtraheerde knooppunt als het linkerkind en het andere geëxtraheerde knooppunt als het rechterkind. Voeg dit knooppunt toe aan de minimale heap.
- Herhaal stap #2 en #3 totdat de heap slechts één knooppunt bevat. Het resterende knooppunt is het hoofdknooppunt en de boom is voltooid.
Laten we het algoritme begrijpen met een voorbeeld:
character Frequency a 5 b 9 c 12 d 13 e 16 f 45>
Stap 1. Bouw een minimale heap die 6 knooppunten bevat, waarbij elk knooppunt de wortel van een boom met één knooppunt vertegenwoordigt.
Stap 2 Extraheer twee knooppunten met minimale frequentie uit de minimale heap. Voeg een nieuw intern knooppunt toe met frequentie 5 + 9 = 14.
Illustratie van stap 2
Nu bevat min heap 5 knooppunten waarbij 4 knooppunten wortels zijn van bomen met elk één element, en één heapknooppunt de wortel van een boom met 3 elementen
character Frequency c 12 d 13 Internal Node 14 e 16 f 45>
Stap 3: Extraheer twee minimumfrequentieknooppunten uit de heap. Voeg een nieuw intern knooppunt toe met frequentie 12 + 13 = 25
Illustratie van stap 3
Nu bevat min heap 4 knooppunten waarbij 2 knooppunten de wortels zijn van bomen met elk één element, en twee heap-knooppunten de wortel van een boom met meer dan één knooppunt
character Frequency Internal Node 14 e 16 Internal Node 25 f 45>
Stap 4: Extraheer twee minimumfrequentieknooppunten. Voeg een nieuw intern knooppunt toe met frequentie 14 + 16 = 30
Illustratie van stap 4
Nu bevat min heap 3 knooppunten.
character Frequency Internal Node 25 Internal Node 30 f 45>
Stap 5: Extraheer twee minimumfrequentieknooppunten. Voeg een nieuw intern knooppunt toe met frequentie 25 + 30 = 55
Illustratie van stap 5
Nu bevat min heap 2 knooppunten.
character Frequency f 45 Internal Node 55>
Stap 6: Extraheer twee minimumfrequentieknooppunten. Voeg een nieuw intern knooppunt toe met frequentie 45 + 55 = 100
Illustratie van stap 6
Nu bevat min heap slechts één knooppunt.
character Frequency Internal Node 100>
Omdat de heap slechts één knooppunt bevat, stopt het algoritme hier.
Stappen om codes af te drukken vanuit Huffman Tree:
Doorkruis de gevormde boom vanaf de wortel. Onderhoud een hulparray. Terwijl u naar het linkerkind gaat, schrijft u 0 naar de array. Terwijl u naar het juiste kind gaat, schrijft u 1 naar de array. Druk de array af wanneer een leaf-knooppunt wordt aangetroffen.
Stappen om code af te drukken vanuit HuffmanTree
De codes zijn als volgt:
character code-word f 0 c 100 d 101 a 1100 b 1101 e 111>Aanbevolen praktijk Huffman-codering Probeer het!
Hieronder vindt u de implementatie van bovenstaande aanpak:
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->links = temp->rechts = NULL;> >temp->gegevens = gegevens;> >temp->frequentie = frequentie;> > >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->maat = 0;> > >minHeap->capaciteit = capaciteit;> > >minHeap->array = (>struct> MinHeapNode**)>malloc>(> >minHeap->capaciteit *>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[links]->freq> >array[smallest]->freq)> >smallest = left;> > >if> (right size> >&& minHeap->array[rechts]->freq> >array[smallest]->freq)> >smallest = right;> > >if> (smallest != idx) {> >swapMinHeapNode(&minHeap->array[kleinste],> >&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->maat == 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->grootte - 1];> > >--minHeap->maat;> >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->maat;> >int> i = minHeap->maat - 1;> > >while> (i> >&& minHeapNode->frequentie> >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->maat - 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->links) && !(wortel->rechts); } // Creëert een minimale heap aan capaciteit // gelijk aan de grootte en voegt alle karakters van // data[] in de minimale heap in. Aanvankelijk is de grootte van // min heap gelijk aan de capaciteit struct MinHeap* createAndBuildMinHeap(char data[], int freq[], int size) { struct MinHeap* minHeap = createMinHeap(size); for (int i = 0; i minHeap->array[i] = newNode(data[i], freq[i]); minHeap->size = size; buildMinHeap(minHeap); return minHeap; } // De hoofdfunctie die de Huffman-boomstructuur bouwt MinHeapNode* buildHuffmanTree(char data[], int freq[], int size) { struct MinHeapNode *left, *right, *top // Stap 1: Creëer een minimale hoop capaciteit // gelijk aan de grootte . In eerste instantie zijn er // modi gelijk aan de grootte. struct MinHeap* minHeap = createAndBuildMinHeap(data, freq, size); // Herhaal terwijl de grootte van de heap niet 1 wordt terwijl (!isSizeOne(minHeap)) {//. Stap 2: Extraheer de twee minimale // freq items uit min heap left = extractMin(minHeap); right = extractMin(minHeap); frequenties van twee knooppunten. // Maak van de twee geëxtraheerde knooppunten // linker- en rechterkinderen van dit nieuwe knooppunt // Voeg dit knooppunt toe aan de min-heap // '$' is een speciale waarde voor interne knooppunten, niet // gebruikt top = newNode('$', links->freq + rechts->freq); boven->links = links; boven->rechts = rechts; insertMinHeap(minHeap, boven); } // Stap 4: Het resterende knooppunt is het // rootknooppunt en de boom is voltooid. retourneer extractMin(minHeap); } // Drukt huffman-codes af vanuit de root van Huffman Tree. // Het gebruikt arr[] om codes op te slaan void printCodes(struct MinHeapNode* root, int arr[], int top) {// Wijs 0 toe aan de linkerrand en herhaal if (root->left) { arr[top] = 0 ; printCodes(root->links, arr, top + 1); } // Wijs 1 toe aan de rechterrand en herhaal dit als (root->right) { arr[top] = 1; printCodes(root->right, arr, top + 1); } // Als dit een leaf-knooppunt is, // dan bevat het een van de invoer // karakters, print het karakter // en zijn code uit arr[] if (isLeaf(root)) { printf('%c: ', root->gegevens); printArr(arr, boven); } } // De hoofdfunctie die een // Huffman Tree bouwt en codes afdrukt door // de ingebouwde Huffman Tree te doorlopen void HuffmanCodes(char data[], int freq[], int size) {// Construct Huffman Tree struct MinHeapNode* root = buildHuffmanTree (gegevens, freq, grootte); // Druk Huffman-codes af met // de Huffman-boom die boven int arr[MAX_TREE_HT] is gebouwd, top = 0; printCodes(root, arr, top); } // Stuurprogrammacode int main() { char arr[] = { 'a', 'b', 'c', 'd', 'e', 'f '}; int freq[] = { 5, 9, 12, 13, 16, 45 }; int grootte = groottevan(arr) / groottevan(arr[0]); HuffmanCodes(arr, freq, grootte); retour 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->links = temp->rechts = NULL;> >temp->gegevens = gegevens;> >temp->frequentie = frequentie;> > >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->maat = 0;> > >minHeap->capaciteit = capaciteit;> > >minHeap->array = (>struct> MinHeapNode**)>malloc>(> >minHeap->capaciteit *>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[links]->freq> >array[smallest]->freq)> >smallest = left;> > >if> (right size> >&& minHeap->array[rechts]->freq> >array[smallest]->freq)> >smallest = right;> > >if> (smallest != idx) {> >swapMinHeapNode(&minHeap->array[kleinste],> >&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->maat == 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->grootte - 1];> > >--minHeap->maat;> >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->maat;> >int> i = minHeap->maat - 1;> > >while> (i> >&& minHeapNode->frequentie> >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->maat - 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->links) && !(wortel->rechts); } // Creëert een minimale heap aan capaciteit // gelijk aan de grootte en voegt alle karakters van // data[] in de minimale heap in. Aanvankelijk is de grootte van // min heap gelijk aan de capaciteit struct MinHeap* createAndBuildMinHeap(char data[], int freq[], int size) { struct MinHeap* minHeap = createMinHeap(size); for (int i = 0; i minHeap->array[i] = newNode(data[i], freq[i]); minHeap->size = size; buildMinHeap(minHeap); return minHeap; } // De hoofdfunctie die de Huffman-boomstructuur bouwt MinHeapNode* buildHuffmanTree(char data[], int freq[], int size) { struct MinHeapNode *left, *right, *top // Stap 1: Creëer een minimale hoop capaciteit // gelijk aan de grootte . In eerste instantie zijn er // modi gelijk aan de grootte. struct MinHeap* minHeap = createAndBuildMinHeap(data, freq, size); // Herhaal terwijl de grootte van de heap niet 1 wordt terwijl (!isSizeOne(minHeap)) {//. Stap 2: Extraheer de twee minimale // freq items uit min heap left = extractMin(minHeap); right = extractMin(minHeap); frequenties van twee knooppunten. // Maak van de twee geëxtraheerde knooppunten // linker- en rechterkinderen van dit nieuwe knooppunt // Voeg dit knooppunt toe aan de min-heap // '$' is een speciale waarde voor interne knooppunten, niet // gebruikt top = newNode('$', links->freq + rechts->freq); boven->links = links; boven->rechts = rechts; insertMinHeap(minHeap, boven); } // Stap 4: Het resterende knooppunt is het // rootknooppunt en de boom is voltooid. retourneer extractMin(minHeap); } // Drukt huffman-codes af vanuit de root van Huffman Tree. // Het gebruikt arr[] om codes op te slaan void printCodes(struct MinHeapNode* root, int arr[], int top) {// Wijs 0 toe aan de linkerrand en herhaal if (root->left) { arr[top] = 0 ; printCodes(root->links, arr, top + 1); } // Wijs 1 toe aan de rechterrand en herhaal dit als (root->right) { arr[top] = 1; printCodes(root->right, arr, top + 1); } // Als dit een leaf-knooppunt is, // dan bevat het een van de // invoertekens, print het teken // en zijn code uit arr[] if (isLeaf(root)) { cout ': '; printArr(arr, boven); } } // De hoofdfunctie die een // Huffman Tree bouwt en codes afdrukt door // de ingebouwde Huffman Tree te doorlopen void HuffmanCodes(char data[], int freq[], int size) {// Construct Huffman Tree struct MinHeapNode* root = buildHuffmanTree (gegevens, freq, grootte); // Druk Huffman-codes af met // de Huffman-boom die boven int arr[MAX_TREE_HT] is gebouwd, top = 0; printCodes(root, arr, top); } // Stuurprogrammacode int main() { char arr[] = { 'a', 'b', 'c', 'd', 'e', 'f '}; int freq[] = { 5, 9, 12, 13, 16, 45 }; int grootte = groottevan(arr) / groottevan(arr[0]); HuffmanCodes(arr, freq, grootte); retour 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>->gegevens = gegevens;> >this>->frequentie = frequentie;> >}> };> > // 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->gegevens !=>'$'>)> >cout ': ' << str << '
'; printCodes(root->links, str + '0'); printCodes(root->right, str + '1'); } // De hoofdfunctie die een Huffman Tree bouwt en // codes afdrukt door de ingebouwde Huffman Tree te doorlopen void HuffmanCodes(char data[], int freq[], int size) { struct MinHeapNode *left, *right, *top; // Maak een min-heap en voegt alle gegevenstekens in [] prioriteit_wachtrij vergelijken> minHeap; for (int i = 0; i minHeap.push(new MinHeapNode(data[i], freq[i])); // Herhaal terwijl de grootte van de heap niet 1 wordt terwijl (minHeap.size() != 1 ) {// Extraheer de twee minimale // freq items uit min heap left = minHeap.top(); minHeap.pop(); right = minHeap.top(); met // frequentie gelijk aan de som van de // twee knooppuntfrequenties. Maak de // twee geëxtraheerde knooppunten als linker en rechter kinderen // van dit nieuwe knooppunt een speciale waarde // voor interne knooppunten, niet gebruikt top = new MinHeapNode('$', left->freq + right->freq); (top); } // Druk Huffman-codes af met // de Huffman-boom die hierboven is gebouwd printCodes(minHeap.top(), ''); a', 'b', 'c', 'd', 'e', 'f' }; , 45 }; int grootte = groottevan(arr) / groottevan(arr[0]); retour 0; } // Deze code is bijgedragen door Aditya Goel> |
>
>
f-snaar python
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) {// eerste min-extract. HuffmanNode x = q.peek(); q.poll(); // tweede min-extract. HuffmanNode y = q.peek(); q.poll(); // nieuw knooppunt f dat gelijk is HuffmanNode f = nieuw HuffmanNode(); // naar de som van de frequentie van de twee knooppunten // waarden toewijzen aan het f-knooppunt. f.data = x.data + y.data; f.c = '-'; // eerste geëxtraheerde knoop als linkerkind. f.links = x; // tweede geëxtraheerde knoop als het juiste kind. f.rechts = y; // markeer het f-knooppunt als het hoofdknooppunt. wortel = f; // voeg dit knooppunt toe aan de prioriteitswachtrij. q.toevoegen(f); } // druk de codes af door de boomstructuur te doorlopen printCode(root, ''); } } // knooppuntklasse is de basisstructuur // van elk knooppunt in de Huffman-boom. klasse HuffmanNode {int-gegevens; teken c; HuffmanNode links; HuffmanNode rechts; } // comparatorklasse helpt het knooppunt // te vergelijken op basis van een van zijn attributen. // Hier worden we vergeleken // op basis van de datawaarden van de knooppunten. klasse MyComparator implementeert Comparator { public int Compare (HuffmanNode x, HuffmanNode y) { return x.data - y.data; } } // Deze code is bijgedragen door 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}') # tekens voor huffman-boomtekens = ['a', 'b', 'c', 'd', 'e', 'f'] # frequentie van karakters freq = [5, 9, 12, 13, 16, 45] # lijst met ongebruikte knooppunten knooppunten = [] # karakters en frequenties omzetten # in huffman-boomknooppunten voor x binnen bereik (len(chars)): heapq .heappush(nodes, node(freq[x], chars[x])) while len(nodes)> 1: # sorteer alle knooppunten in oplopende volgorde # op basis van hun frequentie left = heapq.heappop(nodes) right = heapq .heappop(nodes) # wijs directionele waarde toe aan deze knooppunten left.huff = 0 right.huff = 1 # combineer de 2 kleinste knooppunten om # een nieuw knooppunt te maken als hun ouder newNode = node(left.freq+right.freq, left. symbol+right.symbol, links, rechts) heapq.heappush(nodes, newNode) # Huffman Tree is klaar! 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) {// eerste min-extract. stel dat x = q[0]; q.shift(); // tweede min-extract. stel dat y = q[0]; q.shift(); // nieuw knooppunt f dat gelijk is, laat f = new HuffmanNode(); // naar de som van de frequentie van de twee knooppunten // waarden toewijzen aan het f-knooppunt. f.data = x.data + y.data; f.c = '-'; // eerste geëxtraheerde knoop als linkerkind. f.links = x; // tweede geëxtraheerde knoop als het juiste kind. f.rechts = y; // markeer het f-knooppunt als het hoofdknooppunt. wortel = f; // voeg dit knooppunt toe aan de prioriteitswachtrij. q.push(f); q.sort(function(a,b){return a.data-b.data;}); } // druk de codes af door de boomstructuur te doorlopen printCode(root, ''); // Deze code is bijgedragen door 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> |
>
>Uitvoer
f: 0 c: 100 d: 101 a: 1100 b: 1101 e: 111>
Tijdcomplexiteit: O(nlogn) waarbij n het aantal unieke tekens is. Als er n knooppunten zijn, wordt extractMin() 2*(n – 1) keer aangeroepen. extractMin() kost O(logn) tijd terwijl het minHeapify() aanroept. De algehele complexiteit is dus O(nlogn).
Als de invoerarray is gesorteerd, bestaat er een lineair tijdalgoritme. We zullen dit binnenkort in ons volgende bericht bespreken.
Ruimtecomplexiteit: - O(N)
Toepassingen van Huffman-codering:
- Ze worden gebruikt voor het verzenden van fax- en tekstberichten.
- Ze worden gebruikt door conventionele compressieformaten zoals PKZIP, GZIP, enz.
- Multimediacodecs zoals JPEG, PNG en MP3 gebruiken Huffman-codering (om preciezer te zijn de voorvoegselcodes).
Dit is nuttig in gevallen waarin er sprake is van een reeks vaak voorkomende tekens.
Referentie:
http://en.wikipedia.org/wiki/Huffman_coding
Dit artikel is samengesteld door Aashish Barnwal en beoordeeld door het techcodeview.com-team.