Huffmanovo kodiranje je algoritem za stiskanje podatkov brez izgub. Ideja je dodeliti kode spremenljive dolžine vhodnim znakom, dolžine dodeljenih kod pa temeljijo na frekvencah ustreznih znakov.
Kode spremenljive dolžine, dodeljene vhodnim znakom, so Predponske kode , pomeni, da so kode (bitna zaporedja) dodeljene tako, da koda, dodeljena enemu znaku, ni predpona kode, dodeljene kateremu koli drugemu znaku. Tako Huffman Coding zagotavlja, da pri dekodiranju ustvarjenega bitnega toka ni dvoumnosti.
Razumejmo predponske kode s protiprimerom. Naj obstajajo štirje znaki a, b, c in d, njihove ustrezne kode spremenljive dolžine pa so 00, 01, 0 in 1. To kodiranje vodi v dvoumnost, ker je koda, dodeljena c, predpona kod, dodeljenih a in b. Če je stisnjen bitni tok 0001, je lahko dekompresiran izhod cccd ali ccb ali acd ali ab.
glej to za aplikacije Huffmanovega kodiranja.
V Huffmanovem kodiranju sta v glavnem dva glavna dela
- Iz vhodnih znakov sestavite Huffmanovo drevo.
- Prečkajte Huffmanovo drevo in dodelite kode likom.
Algoritem:
Pokliče se metoda, ki se uporablja za izdelavo optimalne kode predpone Huffmanovo kodiranje .
alternativa xampp
Ta algoritem gradi drevo od spodaj navzgor. To drevo lahko označimo z T
Naj, |c| biti število listov
|c| -1 je število operacij, potrebnih za združitev vozlišč. Q je prednostna čakalna vrsta, ki jo je mogoče uporabiti pri izdelavi binarne kopice.
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) }> Koraki za izgradnjo Huffmanovega drevesa
Vhod je niz edinstvenih znakov skupaj z njihovo pogostostjo pojavljanja, izhod pa je Huffmanovo drevo.
- Ustvarite listno vozlišče za vsak edinstven znak in zgradite najmanjšo kopico vseh listnih vozlišč (najmanjša kopica se uporablja kot prednostna čakalna vrsta. Vrednost frekvenčnega polja se uporablja za primerjavo dveh vozlišč v minimalni kopici. Na začetku je najmanj pogost znak na koren)
- Ekstrahirajte dve vozlišči z najmanjšo frekvenco iz kopice min.
- Ustvarite novo notranje vozlišče s frekvenco, ki je enaka vsoti frekvenc obeh vozlišč. Prvo izvlečeno vozlišče naj bo njegov levi podrejeni, drugo izvlečeno vozlišče pa kot desni podrejeni. Dodajte to vozlišče v najmanjšo kopico.
- Ponavljajte koraka #2 in #3, dokler kopica ne vsebuje samo enega vozlišča. Preostalo vozlišče je korensko vozlišče in drevo je dokončano.
Naj razumemo algoritem s primerom:
character Frequency a 5 b 9 c 12 d 13 e 16 f 45>
Korak 1. Zgradite najmanjšo kopico, ki vsebuje 6 vozlišč, kjer vsako vozlišče predstavlja koren drevesa z enim vozliščem.
2. korak Ekstrahirajte dve minimalni frekvenčni vozlišči iz minimalne kopice. Dodajte novo notranje vozlišče s frekvenco 5 + 9 = 14.
Ilustracija 2. koraka
Sedaj min heap vsebuje 5 vozlišč, kjer so 4 vozlišča korenine dreves z enim elementom, eno vozlišče kopice pa je koren drevesa s 3 elementi
character Frequency c 12 d 13 Internal Node 14 e 16 f 45>
3. korak: Ekstrahirajte dve minimalni frekvenčni vozlišči iz kopice. Dodajte novo notranje vozlišče s frekvenco 12 + 13 = 25
Ilustracija 3. koraka
Zdaj najmanjša kopica vsebuje 4 vozlišča, pri čemer sta 2 vozlišči korenini dreves z enim elementom, dve vozlišči kopice pa sta korenini drevesa z več kot enim vozliščem
character Frequency Internal Node 14 e 16 Internal Node 25 f 45>
4. korak: Izvlecite dve minimalni frekvenčni vozlišči. Dodajte novo notranje vozlišče s frekvenco 14 + 16 = 30
Ilustracija 4. koraka
Sedaj min kopica vsebuje 3 vozlišča.
character Frequency Internal Node 25 Internal Node 30 f 45>
5. korak: Izvlecite dve minimalni frekvenčni vozlišči. Dodajte novo notranje vozlišče s frekvenco 25 + 30 = 55
Ilustracija 5. koraka
Sedaj min kopica vsebuje 2 vozlišči.
character Frequency f 45 Internal Node 55>
6. korak: Izvlecite dve minimalni frekvenčni vozlišči. Dodajte novo notranje vozlišče s frekvenco 45 + 55 = 100
Ilustracija 6. koraka
Zdaj min heap vsebuje samo eno vozlišče.
character Frequency Internal Node 100>
Ker kopica vsebuje samo eno vozlišče, se algoritem tu ustavi.
Koraki za tiskanje kod iz Huffmanovega drevesa:
Prečkajte oblikovano drevo, začenši s korenino. Ohranite pomožni niz. Med pomikanjem na levega podrejenega elementa zapišite 0 v matriko. Medtem ko se premikate k desnemu podrejenemu elementu, zapišite 1 v matriko. Natisnite matriko, ko naletite na listno vozlišče.
Koraki za tiskanje kode iz HuffmanTree
Kode so naslednje:
character code-word f 0 c 100 d 101 a 1100 b 1101 e 111>Priporočena praksa Huffmanovo kodiranje Poskusite!
Spodaj je izvedba zgornjega pristopa:
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->levo = temp->desno = NULL;> >temp->podatki = podatki;> >temp->frekvenca = frekvenca;> > >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->velikost = 0;> > >minHeap->zmogljivost = zmogljivost;> > >minHeap->niz = (>struct> MinHeapNode**)>malloc>(> >minHeap->zmogljivost *>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->polje[levo]->freq> >array[smallest]->frekvenca)> >smallest = left;> > >if> (right size> >&& minHeap->polje [desno]->freq> >array[smallest]->frekvenca)> >smallest = right;> > >if> (smallest != idx) {> >swapMinHeapNode(&minHeap->niz[najmanjši],> >&minHeap->polje[idx]);> >minHeapify(minHeap, smallest);> >}> }> > // A utility function to check> // if size of heap is 1 or not> int> isSizeOne(>struct> MinHeap* minHeap)> {> > >return> (minHeap->velikost == 1);> }> > // A standard function to extract> // minimum value node from heap> struct> MinHeapNode* extractMin(>struct> MinHeap* minHeap)> > {> > >struct> MinHeapNode* temp = minHeap->niz [0];> >minHeap->matrika[0] = minHeap->matrika[minHeap->velikost - 1];> > >--minHeap->velikost;> >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->velikost;> >int> i = minHeap->velikost - 1;> > >while> (i> >&& minHeapNode->frekvenca>> > >minHeap->matrika[i] = minHeap->matrika[(i - 1) / 2];> >i = (i - 1) / 2;> >}> > >minHeap->polje[i] = minHeapNode;> }> > // A standard function to build min heap> void> buildMinHeap(>struct> MinHeap* minHeap)> > {> > >int> n = minHeap->velikost - 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->levo) && !(koren->desno); } // Ustvari najmanjši kup z zmogljivostjo // enake velikosti in vstavi vse znake // podatkov [] v najmanjši kup. Začetna velikost // min kopice je enaka kapaciteti 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; } // Glavna funkcija ki gradi Huffmanovo drevo struct MinHeapNode* buildHuffmanTree(char data[], int freq[], int size) { struct MinHeapNode *left, *right, *top; // 1. korak: Ustvarite najmanjšo kopico zmogljivosti // enake velikosti . Na začetku so načini enaki velikosti struct MinHeap* minHeap(data, freq, size); // Ponavljaj, dokler velikost kopice ne postane 1 (!isSizeOne(minHeap)) { // 2. korak: Ekstrahirajte dva minimalna // freq elementa iz min heap levo = extractMin(minHeap); // 3. korak: ustvarite novo interno // vozlišče s frekvenco, ki je enaka // vsoti frekvenci dveh vozlišč. // Naredi dve izvlečeni vozlišči kot // levo in desno podrejeno vozlišče // Dodajanje tega vozlišča v najmanjšo kopico // '$' je posebna vrednost za notranja vozlišča. used top = newNode('$', left->freq + right->freq); zgoraj->levo = levo; zgoraj->desno = desno; vstaviMinHeap(minHeap, vrh); } // Korak 4: Preostalo vozlišče je // korensko vozlišče in drevo je dokončano. vrni ekstraktMin(minHeap); } // Natisne huffmanove kode iz korena Huffmanovega drevesa. // Za shranjevanje kod uporablja arr[] void printCodes(struct MinHeapNode* root, int arr[], int top) { // Dodeli 0 levemu robu in se ponovi, če (root->left) { arr[top] = 0 ; printCodes(root->left, arr, top + 1); } // Dodeli 1 desnemu robu in ponovi if (root->right) { arr[top] = 1; printCodes(root->right, arr, top + 1); } // Če je to listno vozlišče, potem // vsebuje enega od vhodnih // znakov, natisnite znak // in njegovo kodo iz arr[] if (isLeaf(root)) { printf('%c: ', koren->podatki); printArr(arr, top); } } // Glavna funkcija, ki zgradi // Huffmanovo drevo in izpiše kode s prečkanjem // zgrajenega Huffmanovega drevesa void HuffmanCodes(char data[], int freq[], int size) { // Konstruiraj Huffmanovo drevo struct MinHeapNode* root = buildHuffmanTree(podatki, frekvenca, velikost); // Tiskanje Huffmanovih kod z uporabo // Huffmanovega drevesa, zgrajenega nad int arr[MAX_TREE_HT], top = 0; printCodes(root, arr, top); } // Koda gonilnika int main() { char arr[] = { 'a', 'b', 'c', 'd', 'e', 'f '}; int freq[] = { 5, 9, 12, 13, 16, 45 }; int velikost = sizeof(arr) / sizeof(arr[0]); HuffmanCodes(arr, frekvenca, velikost); vrni 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->levo = temp->desno = NULL;> >temp->podatki = podatki;> >temp->frekvenca = frekvenca;> > >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->velikost = 0;> > >minHeap->zmogljivost = zmogljivost;> > >minHeap->niz = (>struct> MinHeapNode**)>malloc>(> >minHeap->zmogljivost *>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->polje[levo]->freq> >array[smallest]->frekvenca)> >smallest = left;> > >if> (right size> >&& minHeap->polje [desno]->freq> >array[smallest]->frekvenca)> >smallest = right;> > >if> (smallest != idx) {> >swapMinHeapNode(&minHeap->niz[najmanjši],> >&minHeap->polje[idx]);> >minHeapify(minHeap, smallest);> >}> }> > // A utility function to check> // if size of heap is 1 or not> int> isSizeOne(>struct> MinHeap* minHeap)> {> > >return> (minHeap->velikost == 1);> }> > // A standard function to extract> // minimum value node from heap> struct> MinHeapNode* extractMin(>struct> MinHeap* minHeap)> > {> > >struct> MinHeapNode* temp = minHeap->niz [0];> >minHeap->matrika[0] = minHeap->matrika[minHeap->velikost - 1];> > >--minHeap->velikost;> >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->velikost;> >int> i = minHeap->velikost - 1;> > >while> (i> >&& minHeapNode->frekvenca>>> > >minHeap->matrika[i] = minHeap->matrika[(i - 1) / 2];> >i = (i - 1) / 2;> >}> > >minHeap->polje[i] = minHeapNode;> }> > // A standard function to build min heap> void> buildMinHeap(>struct> MinHeap* minHeap)> > {> > >int> n = minHeap->velikost - 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->levo) && !(koren->desno); } // Ustvari najmanjši kup z zmogljivostjo // enake velikosti in vstavi vse znake // podatkov [] v najmanjši kup. Začetna velikost // min kopice je enaka kapaciteti 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; } // Glavna funkcija ki gradi Huffmanovo drevo struct MinHeapNode* buildHuffmanTree(char data[], int freq[], int size) { struct MinHeapNode *left, *right, *top; // 1. korak: Ustvarite najmanjšo kopico zmogljivosti // enake velikosti . Na začetku so načini enaki velikosti struct MinHeap* minHeap(data, freq, size); // Ponavljaj, dokler velikost kopice ne postane 1 (!isSizeOne(minHeap)) { // 2. korak: Ekstrahirajte dva minimalna // freq elementa iz min heap levo = extractMin(minHeap); // 3. korak: ustvarite novo interno // vozlišče s frekvenco, ki je enaka // vsoti frekvenci dveh vozlišč. // Naredi dve izvlečeni vozlišči kot // levo in desno podrejeno vozlišče // Dodajanje tega vozlišča v najmanjšo kopico // '$' je posebna vrednost za notranja vozlišča. used top = newNode('$', left->freq + right->freq); zgoraj->levo = levo; zgoraj->desno = desno; vstaviMinHeap(minHeap, vrh); } // Korak 4: Preostalo vozlišče je // korensko vozlišče in drevo je dokončano. vrni ekstraktMin(minHeap); } // Natisne huffmanove kode iz korena Huffmanovega drevesa. // Za shranjevanje kod uporablja arr[] void printCodes(struct MinHeapNode* root, int arr[], int top) { // Dodeli 0 levemu robu in se ponovi, če (root->left) { arr[top] = 0 ; printCodes(root->left, arr, top + 1); } // Dodeli 1 desnemu robu in ponovi if (root->right) { arr[top] = 1; printCodes(root->right, arr, top + 1); } // Če je to listno vozlišče, // vsebuje enega od vhodnih // znakov, natisnite znak // in njegovo kodo iz arr[] if (isLeaf(root)) { cout ': '; printArr(arr, top); } } // Glavna funkcija, ki zgradi // Huffmanovo drevo in izpiše kode s prečkanjem // zgrajenega Huffmanovega drevesa void HuffmanCodes(char data[], int freq[], int size) { // Konstruiraj Huffmanovo drevo struct MinHeapNode* root = buildHuffmanTree(podatki, frekvenca, velikost); // Natisni Huffmanove kode z uporabo // Huffmanovega drevesa, zgrajenega nad int arr[MAX_TREE_HT], top = 0; printCodes(root, arr, top); } // Koda gonilnika int main() { char arr[] = { 'a', 'b', 'c', 'd', 'e', 'f '}; int freq[] = { 5, 9, 12, 13, 16, 45 }; int velikost = sizeof(arr) / sizeof(arr[0]); HuffmanCodes(arr, frekvenca, velikost); vrni 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>->podatki = podatki;> >this>->frekvenca = frekvenca;> >}> };> > // 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->podatki !=>'$'>)> >cout ': ' << str << '
'; printCodes(root->levo, str + '0'); printCodes(root->right, str + '1'); } // Glavna funkcija, ki gradi Huffmanovo drevo in // tiska kode s prečkanjem zgrajenega Huffmanovega drevesa void HuffmanCodes(char data[], int freq[], int size) { struct MinHeapNode *left, *right, *top; // Ustvari najmanjšo kopico in vstavi vse znake data[] priority_queue primerjava> minHeap; for (int i = 0; i minHeap.push(new MinHeapNode(data[i], freq[i])); // Ponavljaj, medtem ko velikost kopice ne postane 1, medtem ko (minHeap.size() != 1 ) { // Ekstrahiraj dva elementa min heap left = minHeap.pop(); // Ustvari novo notranje vozlišče // s frekvenco, ki je enaka vsoti frekvenc dveh vozlišč. Naredite // dva izvlečena vozlišča kot levega in desnega otroka // tega novega vozlišča posebna vrednost // za notranja vozlišča top = new MinHeapNode('$', left->freq + right->freq); top->left = right; minHeap.push (top); } // Natisni Huffmanovo drevo zgrajeno nad printCodes(minHeap.top(), ''); // Koda gonilnika int main() { char arr[] = { ' a', 'b', 'c', 'e', 'f' }; int freq[] = { 5, 9, 12, 13, 16 , 45 }; int size = sizeof(arr) / sizeof(arr[0]); vrni 0; } // To kodo je prispeval 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) { // prvi min izvleček. HuffmanNode x = q.peek(); q.poll(); // izvleček druge minute. HuffmanNode y = q.peek(); q.poll(); // novo vozlišče f, ki je enako HuffmanNode f = novo Huffmanovo vozlišče(); // na vsoto frekvence obeh vozlišč // dodeljevanje vrednosti vozlišču f. f.podatki = x.podatki + y.podatki; f.c = '-'; // prvo ekstrahirano vozlišče kot levi otrok. f.levo = x; // drugo ekstrahirano vozlišče kot desni otrok. f.desno = y; // označevanje vozlišča f kot korenskega vozlišča. koren = f; // dodaj to vozlišče v prednostno čakalno vrsto. q.add(f); } // tiskanje kod s prečkanjem drevesa printCode(root, ''); } } // razred vozlišča je osnovna struktura // vsakega vozlišča v Huffmanovem drevesu. class HuffmanNode { int podatki; znak c; HuffmanNode levo; HuffmanNode desno; } // razred primerjalnika pomaga primerjati vozlišče // na podlagi enega od njegovih atributov. // Tukaj bomo primerjani // na podlagi podatkovnih vrednosti vozlišč. class MyComparator implements Comparator { public int compare(HuffmanNode x, HuffmanNode y) { return x.data - y.data; } } // To kodo je prispeval 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}') # znakov za huffmanovo drevo chars = ['a', 'b', 'c', 'd', 'e', 'f'] # pogostost znakov freq = [5, 9, 12, 13, 16, 45] # seznam, ki vsebuje neuporabljena vozlišča vozlišča = [] # pretvorba znakov in frekvenc # v vozlišča huffmanovega drevesa za x v obsegu (len(chars)): heapq .heappush(nodes, node(freq[x], chars[x])) while len(nodes)> 1: # razvrsti vsa vozlišča v naraščajočem vrstnem redu # glede na njihovo frekvenco levo = heapq.heappop(vozlišča) desno = heapq .heappop(nodes) # tem vozliščem dodeli smerno vrednost left.huff = 0 right.huff = 1 # združi 2 najmanjši vozlišči, da ustvari # novo vozlišče kot njihov nadrejeni newNode = node(left.freq+right.freq, left. simbol+desno.simbol, levo, desno) heapq.heappush(nodes, newNode) # Huffmanovo drevo je pripravljeno! printNodes(vozlišča[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) { // izvleček prve minute. naj bo x = q[0]; q.shift(); // izvleček druge minute. naj bo y = q[0]; q.shift(); // novo vozlišče f, ki je enako let f = novo HuffmanNode(); // na vsoto frekvence obeh vozlišč // dodeljevanje vrednosti vozlišču f. f.podatki = x.podatki + y.podatki; f.c = '-'; // prvo ekstrahirano vozlišče kot levi otrok. f.levo = x; // drugo ekstrahirano vozlišče kot desni otrok. f.desno = y; // označevanje vozlišča f kot korenskega vozlišča. koren = f; // dodaj to vozlišče v prednostno čakalno vrsto. q.push(f); q.sort(function(a,b){return a.data-b.data;}); } // tiskanje kod s prečkanjem drevesa printCode(root, ''); // To kodo je prispeval avanitrachhadiya2155> |
>
linux free ipconfig
>
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> |
>
>Izhod
f: 0 c: 100 d: 101 a: 1100 b: 1101 e: 111>
Časovna zahtevnost: O(nlogn), kjer je n število edinstvenih znakov. Če obstaja n vozlišč, se extractMin() kliče 2*(n – 1)-krat. extractMin() potrebuje čas O(logn), ko pokliče minHeapify(). Torej je skupna kompleksnost O(nlogn).
Če je vhodna matrika razvrščena, obstaja linearni časovni algoritem. O tem bomo kmalu razpravljali v naši naslednji objavi.
Kompleksnost prostora:- O(N)
Uporaba Huffmanovega kodiranja:
- Uporabljajo se za prenos faksa in besedila.
- Uporabljajo jih običajni formati stiskanja, kot so PKZIP, GZIP itd.
- Večpredstavnostni kodeki, kot so JPEG, PNG in MP3, uporabljajo Huffmanovo kodiranje (natančneje predpone).
Uporaben je v primerih, ko obstaja niz pogosto pojavljajočih se znakov.
Referenca:
http://en.wikipedia.org/wiki/Huffman_coding
Ta članek je zbral Aashish Barnwal, pregledala pa ga je ekipa techcodeview.com.