Huffman kodēšana ir bezzudumu datu saspiešanas algoritms. Ideja ir piešķirt mainīga garuma kodus ievades rakstzīmēm, piešķirto kodu garumi ir balstīti uz atbilstošo rakstzīmju frekvencēm.
Mainīga garuma kodi, kas piešķirti ievades rakstzīmēm, ir Prefiksu kodi , nozīmē, ka kodi (bitu secības) ir piešķirti tā, ka vienai rakstzīmei piešķirtais kods nav nevienai citai rakstzīmei piešķirtā koda prefikss. Tādā veidā Huffman Coding nodrošina, ka, dekodējot ģenerēto bitu straumi, nav neskaidrību.
Ļaujiet mums saprast prefiksu kodus ar skaitītāja piemēru. Lai ir četras rakstzīmes a, b, c un d, un to atbilstošie mainīgā garuma kodi ir 00, 01, 0 un 1. Šī kodēšana rada neskaidrības, jo c piešķirtais kods ir a un b piešķirto kodu prefikss. Ja saspiestā bitu plūsma ir 0001, dekompresētā izvade var būt cccd vai ccb, acd vai ab.
Skat šis Huffman Coding lietojumiem.
Huffman Coding galvenokārt ir divas galvenās daļas
- Izveidojiet Hafmena koku no ievades rakstzīmēm.
- Brauciet pa Hafmena koku un piešķiriet rakstzīmēm kodus.
Algoritms:
Tiek izsaukta metode, kas tiek izmantota, lai izveidotu optimālu prefiksa kodu Hafmena kodēšana .
Šis algoritms veido koku no apakšas uz augšu. Mēs varam apzīmēt šo koku ar T
Let, |c| būt lapu skaitam
|c| -1 ir operāciju skaits, kas nepieciešams mezglu sapludināšanai. Q ir prioritārā rinda, ko var izmantot, veidojot bināro kaudzi.
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) }> Soļi, lai izveidotu Huffman Tree
Ievade ir unikālu rakstzīmju masīvs kopā ar to atgadījumu biežumu, un izvade ir Huffman Tree.
- Katrai unikālajai rakstzīmei izveidojiet lapas mezglu un izveidojiet minimālo kaudzi no visiem lapu mezgliem (Minim kaudze tiek izmantota kā prioritārā rinda. Frekvences lauka vērtību izmanto, lai salīdzinātu divus mezglus min kaudzītē. Sākotnēji retāk sastopamā rakstzīme ir plkst. sakne)
- No minimālās kaudzes izņemiet divus mezglus ar minimālo frekvenci.
- Izveidojiet jaunu iekšējo mezglu ar frekvenci, kas vienāda ar divu mezglu frekvenču summu. Padariet pirmo izvilkto mezglu par tā kreiso atvasi un otru izvilkto mezglu kā tā labo atvasi. Pievienojiet šo mezglu min kaudzītei.
- Atkārtojiet 2. un 3. darbību, līdz kaudzē ir tikai viens mezgls. Atlikušais mezgls ir saknes mezgls, un koks ir pabeigts.
Ļaujiet mums saprast algoritmu ar piemēru:
character Frequency a 5 b 9 c 12 d 13 e 16 f 45>
1. darbība. Izveidojiet minimālo kaudzi, kurā ir 6 mezgli, kur katrs mezgls ir koka sakne ar vienu mezglu.
2. darbība Izņemiet divus minimālās frekvences mezglus no minimālās kaudzes. Pievienojiet jaunu iekšējo mezglu ar frekvenci 5 + 9 = 14.
c kods abs
2. darbības ilustrācija
Tagad min kaudze satur 5 mezglus, kur 4 mezgli ir koku saknes ar vienu elementu katrā, un viens kaudzes mezgls ir koka sakne ar 3 elementiem
character Frequency c 12 d 13 Internal Node 14 e 16 f 45>
3. darbība: Izņemiet no kaudzes divus minimālās frekvences mezglus. Pievienojiet jaunu iekšējo mezglu ar frekvenci 12 + 13 = 25
3. darbības ilustrācija
Tagad min kaudze satur 4 mezglus, kur 2 mezgli ir koku saknes ar vienu elementu katrā, un divi kaudzes mezgli ir koka saknes ar vairāk nekā vienu mezglu
character Frequency Internal Node 14 e 16 Internal Node 25 f 45>
4. darbība: Izņemiet divus minimālās frekvences mezglus. Pievienojiet jaunu iekšējo mezglu ar frekvenci 14 + 16 = 30
4. darbības ilustrācija
Tagad min kaudze satur 3 mezglus.
character Frequency Internal Node 25 Internal Node 30 f 45>
5. darbība: Izņemiet divus minimālās frekvences mezglus. Pievienojiet jaunu iekšējo mezglu ar frekvenci 25 + 30 = 55
5. darbības ilustrācija
Tagad min kaudze satur 2 mezglus.
character Frequency f 45 Internal Node 55>
6. darbība: Izņemiet divus minimālās frekvences mezglus. Pievienojiet jaunu iekšējo mezglu ar frekvenci 45 + 55 = 100
6. darbības ilustrācija
Tagad min kaudze satur tikai vienu mezglu.
character Frequency Internal Node 100>
Tā kā kaudze satur tikai vienu mezglu, algoritms šeit apstājas.
Darbības, lai izdrukātu kodus no Huffman Tree:
Šķērsojiet izveidoto koku, sākot no saknes. Saglabājiet papildu masīvu. Pārejot uz kreiso bērnu, ierakstiet 0 masīvā. Pārejot uz labo bērnu, ierakstiet masīvā 1. Drukājiet masīvu, kad tiek konstatēts lapas mezgls.
Darbības, lai izdrukātu kodu no HuffmanTree
Kodi ir šādi:
character code-word f 0 c 100 d 101 a 1100 b 1101 e 111>Ieteicamā Huffman kodēšanas prakse Izmēģiniet to!
Tālāk ir aprakstīta iepriekš minētās pieejas īstenošana:
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->pa kreisi = temp->pa labi = NULL;>> 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->izmērs = 0;>> minHeap->jauda = jauda;>> minHeap->masīvs = (>struct> MinHeapNode**)>malloc>(> >minHeap->ietilpība *>>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->masīvs[pa kreisi]->frekv.> >array[smallest]->frekvence)>> > >if> (right size> >&& minHeap->masīvs[labais]->frekv.> >array[smallest]->frekvence)>> > >if> (smallest != idx) {> >swapMinHeapNode(&minHeap->masīvs[mazākais],> >&minHeap->masīvs[idx]);>> >}> }> > // A utility function to check> // if size of heap is 1 or not> int> isSizeOne(>struct> MinHeap* minHeap)> {> > >return> (minHeap->izmērs == 1);>> // A standard function to extract> // minimum value node from heap> struct> MinHeapNode* extractMin(>struct> MinHeap* minHeap)> > {> > >struct> MinHeapNode* temp = minHeap->masīvs[0];>> --minHeap->Izmērs;>> > >return> temp;> }> > // A utility function to insert> // a new node to Min Heap> void> insertMinHeap(>struct> MinHeap* minHeap,> >struct> MinHeapNode* minHeapNode)> > {> > >++minHeap->Izmērs;>> i = minHeap->izmērs - 1;>> while> (i> >&& minHeapNode->frekvence>> > >minHeap->masīvs[i] = minHeap->masīvs[(i - 1) / 2];>> >}> > >minHeap->masīvs[i] = minHeapNode;>> // A standard function to build min heap> void> buildMinHeap(>struct> MinHeap* minHeap)> > {> > >int> n = minHeap->izmērs - 1;>> i;> > >for> (i = (n - 1) / 2; i>= 0; --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->pa kreisi) && !(sakne->pa labi); } // Izveido minimālo kaudzi ar ietilpību //, kas vienāda ar lielumu, un ievieto visas // datu [] rakstzīmes minimālajā kaudzē. Sākotnēji // min kaudzes lielums ir vienāds ar kapacitāti struct MinHeap* createAndBuildMinHeap(char data[], int freq[], int size) { struct MinHeap* minHeap = createMinHeap(size); for (int i = 0; i minHeap->masīvs[i] = newNode(data[i], freq[i]); minHeap->size = izmērs; buildMinHeap(minHeap); return minHeap; } // Galvenā funkcija kas veido Huffman koku struct MinHeapNode* buildHuffmanTree(char data[], int freq[], int size) { struct MinHeapNode *pa kreisi, *labais, *augšs // 1. darbība: izveidojiet minimālo kapacitāti // vienādu ar izmēru Sākotnēji ir // režīmi, kas vienādi ar struct MinHeap* minHeap = createAndBuildMinHeap(data, freq, size) // atkārtojiet, kamēr kaudzes izmērs nekļūst par 1, kamēr (!isSizeOne(minHeap)) { // 2. darbība: izņemiet divus minimālos // freq vienumus no min kaudzes = extractMin(minHeap) = izvilkumsMin(minHeap) // 3. darbība: izveidojiet jaunu iekšējo // mezglu, kura frekvence ir vienāda ar // summu; divu mezglu frekvences // Padarīt divus izvilktos mezglus kā // šī jaunā mezgla pakārtotos // Pievienot šo mezglu min kaudzītei // '$' ir īpaša vērtība iekšējiem mezgliem, nevis //. lietots top = newNode('$', pa kreisi->freq + pa labi->frekv.); top->pa kreisi = pa kreisi; augšā->pa labi = pa labi; insertMinHeap(minHeap, top); } // 4. darbība. Atlikušais mezgls ir // saknes mezgls, un koks ir pabeigts. atgriešanās ekstraktsMin(minHeap); } // Drukā Huffman kodus no Huffman Tree saknes. // Tas izmanto arr[], lai saglabātu kodus void printCodes(struct MinHeapNode* root, int arr[], int top) { // Kreisajai malai piešķiriet 0 un atkārtojiet if (root->left) { arr[augšā] = 0 ; printCodes(root->left, arr, top + 1); } // Labajai malai piešķir 1 un atkārto, ja (root->right) { arr[augšā] = 1; printCodes(root->right, arr, top + 1); } // Ja tas ir lapas mezgls, tad // tajā ir viena no ievades // rakstzīmēm, izdrukājiet rakstzīmi // un tās kodu no arr[] if (isLeaf(root)) { printf('%c: ', sakne->dati); printArr(arr, top); } } // Galvenā funkcija, kas izveido // Huffman Tree un izdrukā kodus, šķērsojot // izveidoto Huffman Tree void HuffmanCodes(char data[], int freq[], int size) { // Konstruē Huffman Tree struct MinHeapNode* sakne = buildHuffmanTree(dati, frekvence, izmērs); // Drukāt Hafmena kodus, izmantojot // Hafmena koku, kas uzbūvēts virs int arr[MAX_TREE_HT], top = 0; printCodes(sakne, arr, augšdaļa); } // Draivera kods int main() { char arr[] = { 'a', 'b', 'c', 'd', 'e', 'f '}; int frekvence[] = {5, 9, 12, 13, 16, 45}; int izmērs = sizeof(arr) / sizeof(arr[0]); HuffmanCodes (arr, frekvence, izmērs); atgriezties 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->pa kreisi = temp->pa labi = NULL;>> 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->izmērs = 0;>> minHeap->jauda = jauda;>> minHeap->masīvs = (>struct> MinHeapNode**)>malloc>(> >minHeap->ietilpība *>>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->masīvs[pa kreisi]->frekv.> >array[smallest]->frekvence)>> > >if> (right size> >&& minHeap->masīvs[labais]->frekv.> >array[smallest]->frekvence)>> > >if> (smallest != idx) {> >swapMinHeapNode(&minHeap->masīvs[mazākais],> >&minHeap->masīvs[idx]);>> >}> }> > // A utility function to check> // if size of heap is 1 or not> int> isSizeOne(>struct> MinHeap* minHeap)> {> > >return> (minHeap->izmērs == 1);>> // A standard function to extract> // minimum value node from heap> struct> MinHeapNode* extractMin(>struct> MinHeap* minHeap)> > {> > >struct> MinHeapNode* temp = minHeap->masīvs[0];>> --minHeap->Izmērs;>> > >return> temp;> }> > // A utility function to insert> // a new node to Min Heap> void> insertMinHeap(>struct> MinHeap* minHeap,> >struct> MinHeapNode* minHeapNode)> > {> > >++minHeap->Izmērs;>> i = minHeap->izmērs - 1;>> while> (i> >&& minHeapNode->frekvence>> > >minHeap->masīvs[i] = minHeap->masīvs[(i - 1) / 2];>> >}> > >minHeap->masīvs[i] = minHeapNode;>> // A standard function to build min heap> void> buildMinHeap(>struct> MinHeap* minHeap)> > {> > >int> n = minHeap->izmērs - 1;>> i;> > >for> (i = (n - 1) / 2; i>= 0; --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->pa kreisi) && !(sakne->pa labi); } // Izveido minimālo kaudzi ar ietilpību //, kas vienāda ar lielumu, un ievieto visas // datu [] rakstzīmes minimālajā kaudzē. Sākotnēji // min kaudzes lielums ir vienāds ar kapacitāti struct MinHeap* createAndBuildMinHeap(char data[], int freq[], int size) { struct MinHeap* minHeap = createMinHeap(size); for (int i = 0; i minHeap->masīvs[i] = newNode(data[i], freq[i]); minHeap->size = izmērs; buildMinHeap(minHeap); return minHeap; } // Galvenā funkcija kas veido Huffman koku struct MinHeapNode* buildHuffmanTree(char data[], int freq[], int size) { struct MinHeapNode *pa kreisi, *labais, *augšs // 1. darbība: izveidojiet minimālo kapacitāti // vienādu ar izmēru Sākotnēji ir // režīmi, kas vienādi ar struct MinHeap* minHeap = createAndBuildMinHeap(data, freq, size) // atkārtojiet, kamēr kaudzes izmērs nekļūst par 1, kamēr (!isSizeOne(minHeap)) { // 2. darbība: izņemiet divus minimālos // freq vienumus no min kaudzes = extractMin(minHeap) = izvilkumsMin(minHeap) // 3. darbība: izveidojiet jaunu iekšējo // mezglu, kura frekvence ir vienāda ar // summu; divu mezglu frekvences // Padarīt divus izvilktos mezglus kā // šī jaunā mezgla pakārtotos // Pievienot šo mezglu min kaudzītei // '$' ir īpaša vērtība iekšējiem mezgliem, nevis //. lietots top = newNode('$', pa kreisi->freq + pa labi->freq); top->pa kreisi = pa kreisi; augšā->pa labi = pa labi; insertMinHeap(minHeap, top); } // 4. darbība. Atlikušais mezgls ir // saknes mezgls, un koks ir pabeigts. atgriešanās ekstraktsMin(minHeap); } // Drukā Huffman kodus no Huffman Tree saknes. // Tas izmanto arr[], lai saglabātu kodus void printCodes(struct MinHeapNode* root, int arr[], int top) { // Kreisajai malai piešķiriet 0 un atkārtojiet if (root->left) { arr[augšā] = 0 ; printCodes(root->left, arr, top + 1); } // Labajai malai piešķirt 1 un atkārtot, ja (root->right) { arr[augšā] = 1; printCodes(root->right, arr, top + 1); } // Ja tas ir lapas mezgls, tad // tajā ir viena no ievades // rakstzīmēm, izdrukā rakstzīmi // un tās kodu no arr[] if (isLeaf(root)) { cout ': '; printArr(arr, top); } } // Galvenā funkcija, kas izveido // Huffman Tree un izdrukā kodus, šķērsojot // izveidoto Huffman Tree void HuffmanCodes(char data[], int freq[], int size) { // Konstruē Huffman Tree struct MinHeapNode* sakne = buildHuffmanTree(dati, frekvence, izmērs); // Drukāt Hafmena kodus, izmantojot // Hafmena koku, kas uzbūvēts virs int arr[MAX_TREE_HT], top = 0; printCodes(sakne, arr, augšdaļa); } // Draivera kods int main() { char arr[] = { 'a', 'b', 'c', 'd', 'e', 'f '}; int frekvence[] = {5, 9, 12, 13, 16, 45}; int izmērs = sizeof(arr) / sizeof(arr[0]); HuffmanCodes (arr, frekvence, izmērs); atgriezties 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>->dati = dati;>> ->frekvence = frekvence;>> };> > // For comparison of> // two heap nodes (needed in min heap)> struct> compare {> > >bool> operator()(MinHeapNode* l, MinHeapNode* r)> > >{> >return> (l->frekvence> r-> frekvence);>> };> > // Prints huffman codes from> // the root of Huffman Tree.> void> printCodes(>struct> MinHeapNode* root, string str)> {> > >if> (!root)> >return>;> > >if> (root->dati !=>'$'>)> >cout ': ' << str << '
'; printCodes(root->pa kreisi, str + '0'); printCodes(sakne->pa labi, str + '1'); } // Galvenā funkcija, kas veido Huffman Tree un // drukā kodus, šķērsojot izveidoto Huffman Tree void HuffmanCodes(char data[], int freq[], int size) { struct MinHeapNode *pa kreisi, *pa labi, *augšpusē; // Izveidojiet minimālo kaudzi un ievieto visas datu rakstzīmes[] priority_queue salīdzināt> minHeap; for (int i = 0; i minHeap.push(new MinHeapNode(data[i], freq[i])); // Atkārtojiet, kamēr kaudzes lielums nekļūst par 1, kamēr (minHeap.size() != 1 ) { // Izvilkt divus minimālos vienumus no minHeap.top(); ar // frekvenci, kas ir vienāda ar // divu mezglu frekvenču summu. Padarīt // divus izvilkto mezglu kā šī jaunā mezgla // atvasināto mezglu īpaša vērtība // iekšējiem mezgliem, neizmantots top = new MinHeapNode('$', left->freq + right->freq = top->right = minHeap.push; (augšā } // Drukāt Huffman kodus, izmantojot // Huffman koku, kas izveidots virs printCodes(minHeap.top(), '') } // Draivera kods int main() { char arr[] = { '); a', 'b', 'c', 'd', 'e', 'f' } = { 5, 9, 12, 13, 16 , 45 }; int izmērs = sizeof(arr) / sizeof(arr[0]); atgriezties 0; } // Šo kodu ir sagatavojis 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) { // pirmās minūtes izraksts. HuffmanNode x = q.peek(); q.poll(); // otrā min ekstrakts. HuffmanNode y = q.peek(); q.poll(); // jauns mezgls f, kas ir vienāds HuffmanNode f = new HuffmanNode(); // uz divu mezglu frekvences summu // piešķirot vērtības f mezglam. f.data = x.data + y.data; f.c = '-'; // pirmais mezgls izvilkts kā kreisais bērns. f.pa kreisi = x; // otrais izvilktais mezgls kā pareizais bērns. f.labais = y; // atzīmējot f mezglu kā saknes mezglu. sakne = f; // pievienot šo mezglu prioritātes rindai. q.add(f); } // izdrukāt kodus, šķērsojot koku printCode(root, ''); } } // mezgla klase ir katra Huffman kokā esošā mezgla pamatstruktūra //. class HuffmanNode { int dati; char c; HuffmanNode pa kreisi; HuffmanNode pa labi; } // salīdzinājuma klase palīdz salīdzināt mezglu //, pamatojoties uz vienu no tā atribūtiem. // Šeit mūs salīdzinās //, pamatojoties uz mezglu datu vērtībām. class MyComparator implements Comparator { public int salīdzināt(HuffmanNode x, HuffmanNode y) { return x.data - y.data; } } // Šo kodu ir sagatavojis 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}') # rakstzīmes hufmena koka rakstzīmēm = ['a', 'b', 'c', 'd', 'e', 'f'] # rakstzīmju biežums freq = [5, 9, 12, 13, 16, 45] # saraksts ar neizmantotiem mezgliem mezgli = [] # pārvērš rakstzīmes un frekvences # Huffman koka mezglos x diapazonā (len(chars)): heapq .heappush(mezgli, mezgls(freq[x], rakstzīmes[x])), kamēr len(mezgli)> 1: # kārtojiet visus mezglus augošā secībā # atkarībā no to frekvences pa kreisi = heapq.heappop(nodes) right = heapq .heappop(nodes) # piešķir šiem mezgliem virziena vērtību left.huff = 0 right.huff = 1 # apvienojiet 2 mazākos mezglus, lai izveidotu # jaunu mezglu kā to vecāku newNode = node(left.freq+right.freq, left. simbols+labais.simbols, pa kreisi, pa labi) heapq.heapush(nodes, newNode) # Huffman Tree ir gatavs! printNodes(mezgli[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) { // pirmās minūtes izraksts. lai x = q[0]; q.shift(); // otrā min ekstrakts. pieņemsim, ka y = q[0]; q.shift(); // jauns mezgls f, kas ir vienāds let f = new HuffmanNode(); // uz divu mezglu frekvences summu // piešķirot vērtības f mezglam. f.data = x.data + y.data; f.c = '-'; // pirmais mezgls izvilkts kā kreisais bērns. f.pa kreisi = x; // otrais izvilktais mezgls kā pareizais bērns. f.labais = y; // atzīmējot f mezglu kā saknes mezglu. sakne = f; // pievienot šo mezglu prioritātes rindai. q.push(f); q.sort(function(a,b){return a.data-b.data;}); } // izdrukāt kodus, šķērsojot koku printCode(root, ''); // Šo kodu ir izveidojis avanitrachhadiya2155>> |
>
// 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>>atlasīt kā>Izvadef: 0 c: 100 d: 101 a: 1100 b: 1101 e: 111>Laika sarežģītība: O(nlogn), kur n ir unikālo rakstzīmju skaits. Ja mezglu ir n, ekstraktsMin() tiek izsaukts 2*(n – 1) reizes. ExtractMin() aizņem O(logn) laiku, jo tas izsauc minHeapify(). Tātad kopējā sarežģītība ir O (nlogn).
Ja ievades masīvs ir sakārtots, pastāv lineāra laika algoritms. Drīzumā mēs to apspriedīsim mūsu nākamajā ierakstā.Telpas sarežģītība: O(N)
Huffman kodēšanas pielietojumi:
- Tos izmanto faksa un teksta pārsūtīšanai.
- Tos izmanto parastie saspiešanas formāti, piemēram, PKZIP, GZIP utt.
- Multivides kodeki, piemēram, JPEG, PNG un MP3, izmanto Huffman kodējumu (precīzāk, prefiksu kodus).
Tas ir noderīgi gadījumos, kad ir vairākas bieži sastopamas rakstzīmes.
Atsauce:
http://en.wikipedia.org/wiki/Huffman_coding
Šo rakstu ir apkopojis Aashish Barnwal, un to pārskatījusi techcodeview.com komanda.