Huffman-koodaus on häviötön tietojen pakkausalgoritmi. Ideana on antaa syötemerkeille vaihtuvapituisia koodeja, annettujen koodien pituudet perustuvat vastaavien merkkien taajuuksiin.
Syöttömerkeille määritetyt vaihtuvapituiset koodit ovat Etuliitekoodit , tarkoittaa, että koodit (bittisekvenssit) on määritetty siten, että yhdelle merkille määritetty koodi ei ole millekään muulle merkille määrätyn koodin etuliite. Näin Huffman Coding varmistaa, että generoitua bittivirtaa dekoodattaessa ei ole epäselvyyttä.
Ymmärrämme etuliitekoodit vastaesimerkillä. Olkoon merkkiä a, b, c ja d neljä ja niitä vastaavat muuttuvapituiset koodit 00, 01, 0 ja 1. Tämä koodaus johtaa epäselvyyteen, koska c:lle annettu koodi on a:n ja b:n koodien etuliite. Jos pakattu bittivirta on 0001, purettu lähtö voi olla cccd tai ccb tai acd tai ab.
Katso Tämä Huffman Codingin sovelluksiin.
Huffman Codingissa on pääasiassa kaksi pääosaa
- Rakenna Huffman-puu syötetyistä merkeistä.
- Kulje Huffman-puun läpi ja anna koodit hahmoille.
Algoritmi:
Menetelmää, jota käytetään optimaalisen etuliitekoodin muodostamiseen, kutsutaan Huffman koodaus .
Tämä algoritmi rakentaa puun alhaalta ylöspäin. Voimme merkitä tätä puuta T
Olkoon, |c| olla lehtien lukumäärä
|c| -1 ovat solmujen yhdistämiseen tarvittavien toimintojen lukumäärä. Q on prioriteettijono, jota voidaan käyttää binäärikeon rakentamisessa.
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) }> Huffman Treen rakentamisen vaiheet
Syöte on joukko ainutlaatuisia merkkejä ja niiden esiintymistiheys ja tulos on Huffman Tree.
- Luo lehtisolmu jokaiselle yksilölliselle merkille ja rakenna kaikista lehtisolmuista minimikeko (Minimikekoa käytetään prioriteettijonona. Taajuuskentän arvoa käytetään vertaamaan kahta min-keon solmua. Aluksi harvinaisin merkki on juuri)
- Poimi kaksi solmua minimitaajuudella minimikasasta.
- Luo uusi sisäinen solmu, jonka taajuus on yhtä suuri kuin kahden solmun taajuuksien summa. Tee ensimmäisestä puretusta solmusta sen vasen ali ja toinen purettu solmu oikeaksi. Lisää tämä solmu minimikekoon.
- Toista vaiheita 2 ja 3, kunnes kasa sisältää vain yhden solmun. Jäljellä oleva solmu on juurisolmu ja puu on valmis.
Ymmärrämme algoritmia esimerkin avulla:
character Frequency a 5 b 9 c 12 d 13 e 16 f 45>
Vaihe 1. Rakenna pieni kaso, joka sisältää 6 solmua, jossa jokainen solmu edustaa puun juuria, jossa on yksi solmu.
Vaihe 2 Poimi kaksi vähimmäistaajuussolmua min-keosta. Lisää uusi sisäinen solmu taajuudella 5 + 9 = 14.
Kuva vaiheesta 2
Nyt min kaso sisältää 5 solmua, joista 4 solmua ovat puiden juuria, joissa kussakin on yksi elementti, ja yksi kasan solmu on puun juuri, jossa on 3 elementtiä
character Frequency c 12 d 13 Internal Node 14 e 16 f 45>
Vaihe 3: Poimi kaksi minimitaajuussolmua kasasta. Lisää uusi sisäinen solmu taajuudella 12 + 13 = 25
Kuva vaiheesta 3
Nyt min kaso sisältää 4 solmua, joista 2 solmua ovat puiden juuria, joissa kussakin on yksi elementti, ja kaksi kasan solmua ovat puun juuria, joissa on useampi kuin yksi solmu
character Frequency Internal Node 14 e 16 Internal Node 25 f 45>
Vaihe 4: Pura kaksi minimitaajuussolmua. Lisää uusi sisäinen solmu taajuudella 14 + 16 = 30
Kuva vaiheesta 4
Nyt min kaso sisältää 3 solmua.
character Frequency Internal Node 25 Internal Node 30 f 45>
Vaihe 5: Pura kaksi minimitaajuussolmua. Lisää uusi sisäinen solmu taajuudella 25 + 30 = 55
Kuva vaiheesta 5
Nyt min kaso sisältää 2 solmua.
character Frequency f 45 Internal Node 55>
Vaihe 6: Pura kaksi minimitaajuussolmua. Lisää uusi sisäinen solmu taajuudella 45 + 55 = 100
Kuva vaiheesta 6
Nyt min kaso sisältää vain yhden solmun.
character Frequency Internal Node 100>
Koska kasa sisältää vain yhden solmun, algoritmi pysähtyy tähän.
usa kaupunkien nimet
Ohjeet koodien tulostamiseen Huffman Treestä:
Poikki muodostunut puu juuresta alkaen. Säilytä apujoukkoa. Kun siirryt vasemmalle lapselle, kirjoita taulukkoon 0. Kun siirryt oikeaan lapseen, kirjoita taulukkoon 1. Tulosta matriisi, kun lehtisolmu kohtaa.
Ohjeet koodin tulostamiseen HuffmanTreestä
Koodit ovat seuraavat:
character code-word f 0 c 100 d 101 a 1100 b 1101 e 111>Suositeltu Huffman-koodauksen harjoittelu Kokeile!
Alla on yllä olevan lähestymistavan toteutus:
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->vasen = temp->oikea = 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->koko = 0;>> minHeap->kapasiteetti = kapasiteetti;>> minHeap->array = (>struct> MinHeapNode**)>malloc>(> >minHeap->kapasiteetti *>>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[vasen]->taajuus>> > >if> (right size> >&& minHeap->array[right]->freq>> > >if> (smallest != idx) {> >swapMinHeapNode(&minHeap->array[pienin],> >&minHeap->array[idx]);>> >}> }> > // A utility function to check> // if size of heap is 1 or not> int> isSizeOne(>struct> MinHeap* minHeap)> {> > >return> (minHeap->koko == 1);>> // A standard function to extract> // minimum value node from heap> struct> MinHeapNode* extractMin(>struct> MinHeap* minHeap)> > {> > >struct> MinHeapNode* temp = minHeap->array[0];>> --minHeap->koko;>> > >return> temp;> }> > // A utility function to insert> // a new node to Min Heap> void> insertMinHeap(>struct> MinHeap* minHeap,> >struct> MinHeapNode* minHeapNode)> > {> > >++minHeap->koko;>> i = minHeap->koko - 1;>> while> (i> >&& minHeapNode->taaj.>> > >minHeap->taulukko[i] = minHeap->taulukko[(i - 1) / 2];>> >}> > >minHeap->array[i] = minHeapNode;>> // A standard function to build min heap> void> buildMinHeap(>struct> MinHeap* minHeap)> > {> > >int> n = minHeap->koko - 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->vasen) && !(root->right); } // Luo minimikeon, jonka kapasiteetti on // samansuuruinen kuin koko ja lisää // datan[] kaikki merkit minimikekoon. Aluksi // min-keon koko on yhtä suuri kuin kapasiteetti 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 = koko; buildMinHeap(minHeap); return minHeap; } // Pääfunktio joka rakentaa Huffman-puun struct MinHeapNode* buildHuffmanTree(char data[], int freq[], int size) { struct MinHeapNode *vasen, *oikea, *ylä // Vaihe 1: Luo pieni kapasiteetti // kokoa vastaava Aluksi on olemassa //-moodeja, jotka ovat yhtä suuria kuin koko MinHeap* minHeap = createAndBuildMinHeap(data, freq, size) // Toista, kun keon koosta ei tule 1 while (!isSizeOne(minHeap)) { // Vaihe 2: Pura kaksi vähimmäismäärää // freq -kohdetta min-kekosta vasen = extractMin(minHeap) = extractMin(minHeap) // Vaihe 3: Luo uusi sisäinen //-solmu, jonka taajuus on yhtä suuri kuin // kahden solmun taajuudet // Tee kaksi purettua solmua // tämän uuden solmun jälkeläisiksi // Lisää tämä solmu minimikekoon // '$' on erityinen arvo sisäisille solmuille, ei //. käytetty top = newNode('$', vasen->taajuus + oikea->taajuus); ylä->vasen = vasen; ylä->oikea = oikea; insertMinHeap(minHeap, top); } // Vaihe 4: Jäljellä oleva solmu on // juurisolmu ja puu on valmis. palauttaa otteenMin(minHeap); } // Tulostaa huffman-koodit Huffman Treen juuresta. // Se käyttää arr[] koodien tallentamiseen void printCodes(struct MinHeapNode* root, int arr[], int top) { // Määritä 0 vasempaan reunaan ja toista if (root->left) { arr[top] = 0 ; printCodes(juuri->vasen, arr, ylä + 1); } // Määritä 1 oikeaan reunaan ja toista, jos (juuri->oikea) { arr[ylä] = 1; printCodes(root->right, arr, top + 1); } // Jos tämä on lehtisolmu, niin // se sisältää yhden syöte //-merkeistä, tulosta merkki // ja sen koodi osoitteesta arr[] if (isLeaf(root)) { printf('%c: ', root-> data); printArr(arr, top); } } // Pääfunktio, joka rakentaa // Huffman-puun ja tulostaa koodit kulkemalla // rakennettua Huffman-puuta void HuffmanCodes(char data[], int freq[], int size) { // Muodosta Huffman Tree struct MinHeapNode* juuri = buildHuffmanTree(data, taajuus, koko); // Tulosta Huffman-koodit käyttämällä // yläpuolelle rakennettua Huffman-puuta int arr[MAX_TREE_HT], top = 0; printCodes(juuri, arr, alkuun); } // Ohjainkoodi int main() { char arr[] = { 'a', 'b', 'c', 'd', 'e', 'f '}; int taaj.[] = { 5, 9, 12, 13, 16, 45 }; int koko = sizeof(arr) / sizeof(arr[0]); HuffmanCodes(arr, taaj., koko); paluu 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->vasen = temp->oikea = 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->koko = 0;>> minHeap->kapasiteetti = kapasiteetti;>> minHeap->array = (>struct> MinHeapNode**)>malloc>(> >minHeap->kapasiteetti *>>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[vasen]->taajuus>> >smallest = left;> > >if> (right size> >&& minHeap->array[right]->freq>> > >if> (smallest != idx) {> >swapMinHeapNode(&minHeap->array[pienin],> >&minHeap->array[idx]);>> >}> }> > // A utility function to check> // if size of heap is 1 or not> int> isSizeOne(>struct> MinHeap* minHeap)> {> > >return> (minHeap->koko == 1);>> // A standard function to extract> // minimum value node from heap> struct> MinHeapNode* extractMin(>struct> MinHeap* minHeap)> > {> > >struct> MinHeapNode* temp = minHeap->array[0];>> --minHeap->koko;>> > >return> temp;> }> > // A utility function to insert> // a new node to Min Heap> void> insertMinHeap(>struct> MinHeap* minHeap,> >struct> MinHeapNode* minHeapNode)> > {> > >++minHeap->koko;>> i = minHeap->koko - 1;>> while> (i> >&& minHeapNode->taaj.>> > >minHeap->taulukko[i] = minHeap->taulukko[(i - 1) / 2];>> >}> > >minHeap->array[i] = minHeapNode;>> // A standard function to build min heap> void> buildMinHeap(>struct> MinHeap* minHeap)> > {> > >int> n = minHeap->koko - 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->vasen) && !(root->right); } // Luo vähintään kokoa vastaavan kapasiteetin keon // ja lisää // datan[] kaikki merkit minimikekoon. Aluksi // min-keon koko on yhtä suuri kuin kapasiteetti 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 = koko; buildMinHeap(minHeap); return minHeap; } // Pääfunktio joka rakentaa Huffman-puun struct MinHeapNode* buildHuffmanTree(char data[], int freq[], int size) { struct MinHeapNode *vasen, *oikea, *ylä // Vaihe 1: Luo pieni kapasiteetti // kokoa vastaava Aluksi on olemassa //-moodeja, jotka ovat yhtä suuria kuin koko MinHeap* minHeap = createAndBuildMinHeap(data, freq, size) // Toista, kun keon koosta ei tule 1 while (!isSizeOne(minHeap)) { // Vaihe 2: Pura kaksi vähimmäismäärää // freq -kohdetta min-kekosta vasen = extractMin(minHeap) = extractMin(minHeap) // Vaihe 3: Luo uusi sisäinen //-solmu, jonka taajuus on yhtä suuri kuin // kahden solmun taajuudet // Tee kaksi purettua solmua // tämän uuden solmun jälkeläisiksi // Lisää tämä solmu minimikekoon // '$' on erityinen arvo sisäisille solmuille, ei //. käytetty top = newNode('$', vasen->taajuus + oikea->taajuus); ylä->vasen = vasen; ylä->oikea = oikea; insertMinHeap(minHeap, top); } // Vaihe 4: Jäljellä oleva solmu on // juurisolmu ja puu on valmis. palauttaa otteenMin(minHeap); } // Tulostaa huffman-koodit Huffman Treen juuresta. // Se käyttää arr[] koodien tallentamiseen void printCodes(struct MinHeapNode* root, int arr[], int top) { // Määritä 0 vasempaan reunaan ja toista if (root->left) { arr[top] = 0 ; printCodes(juuri->vasen, arr, ylhäältä + 1); } // Määritä 1 oikeaan reunaan ja toista, jos (juuri->oikea) { arr[ylä] = 1; printCodes(root->right, arr, top + 1); } // Jos tämä on lehtisolmu, niin // se sisältää yhden syöte //-merkeistä, tulosta merkki // ja sen koodi osoitteesta arr[] if (isLeaf(root)) { cout ': '; printArr(arr, top); } } // Pääfunktio, joka rakentaa // Huffman-puun ja tulostaa koodit kulkemalla // rakennettua Huffman-puuta void HuffmanCodes(char data[], int freq[], int size) { // Muodosta Huffman Tree struct MinHeapNode* juuri = buildHuffmanTree(data, taajuus, koko); // Tulosta Huffman-koodit käyttämällä // yläpuolella olevaa Huffman-puuta int arr[MAX_TREE_HT], top = 0; printCodes(juuri, arr, alkuun); } // Ohjainkoodi int main() { char arr[] = { 'a', 'b', 'c', 'd', 'e', 'f '}; int taaj.[] = { 5, 9, 12, 13, 16, 45 }; int koko = sizeof(arr) / sizeof(arr[0]); HuffmanCodes(arr, taaj., koko); paluu 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>->data = data;>> ->taajuus = taajuus;>> };> > // For comparison of> // two heap nodes (needed in min heap)> struct> compare {> > >bool> operator()(MinHeapNode* l, MinHeapNode* r)> > >{> >return> (l->taajuus> r->taajuus);>> };> > // 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->vasen, str + '0'); printCodes(juuri->oikea, str + '1'); } // Pääfunktio, joka rakentaa Huffman-puun ja // tulostaa koodit kulkemalla rakennetun Huffman-puun läpi void HuffmanCodes(char data[], int freq[], int size) { struct MinHeapNode *vasen, *oikea, *ylä; // Luo minikeko ja lisää datan kaikki merkit[] priority_queue vertaa> minHeap; for (int i = 0; i minHeap.push(new MinHeapNode(data[i], freq[i])); // Toista kun keon koosta ei tule 1 while (minHeap.size() != 1 ) { // Poimi kaksi minimikekoa left = minHeap.pop(); // jonka taajuus on yhtä suuri kuin // kahden solmun taajuuksien summa. Tee // kaksi poimittua solmua // tämän uuden solmun // min kasaan erityinen arvo sisäisille solmuille, ei käytetty top = new MinHeapNode('$', vasen->taajuus + oikea->taajuus = vasen->oikea = minHeap.push; (top } // Tulosta Huffman-koodit // printCodesin yläpuolelle rakennetun Huffman-puun avulla (minHeap.top(), '') } // Ohjainkoodi int main() { char arr[] = { '); a', 'b', 'c', 'd', 'e', 'f' } = { 5, 9, 12, 13, 16 , 45 }; int koko = koko(arr) / sizeof(arr[0]); paluu 0; } // Tämän koodin tarjoaa 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) { // ensimmäisen minuutin ote. HuffmanNode x = q.peek(); q.poll(); // toisen minuutin ote. HuffmanNode y = q.peek(); q.poll(); // uusi solmu f joka on yhtä suuri HuffmanNode f = new HuffmanNode(); // kahden solmun taajuuden summaan // antaa arvot f-solmulle. f.data = x.data + y.data; f.c = '-'; // ensimmäinen purettu solmu vasemmalla lapsilla. f.vasen = x; // toinen purettu solmu oikeana lapsena. f.oikea = y; // f-solmun merkitseminen juurisolmuksi. juuri = f; // lisää tämä solmu prioriteettijonoon. q.add(f); } // tulostaa koodit kulkemalla puun läpi printCode(root, ''); } } // solmuluokka on jokaisen Huffman-puussa olevan solmun perusrakenne //. class HuffmanNode { int data; char c; HuffmanNode vasemmalle; HuffmanNode oikealla; } // vertailuluokka auttaa vertaamaan solmua // sen yhden attribuutin perusteella. // Tässä verrataan // solmujen dataarvojen perusteella. class MyComparator toteuttaa Comparator { public int vertaa(HuffmanNode x, HuffmanNode y) { return x.data - y.data; } } // Tämän koodin on antanut Kunwar Desh Deepak Singh> |
>
>
Python 3
# 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}') # merkkiä huffman-puun merkeille = ['a', 'b', 'c', 'd', 'e', 'f'] # merkkien taajuus freq = [5, 9, 12, 13, 16, 45] # lista, joka sisältää käyttämättömät solmut solmut = [] # muuntaa merkit ja taajuudet # huffman-puun solmuiksi x:lle alueella(len(merkit)): kasaq .heappush(nodes, node(freq[x], chars[x])) kun len(solmut)> 1: # lajittele kaikki solmut nousevaan järjestykseen # niiden taajuuden perusteella left = heapq.heappop(nodes) right = heapq .heappop(solmut) # määritä suunta-arvo näille solmuille left.huff = 0 right.huff = 1 # yhdistä 2 pienintä solmua luodaksesi # uusi solmu niiden yläpääksi newSolmu = solmu(vasen.taajuus+oikea.taajuus, vasen. symbol+oikea.symboli, vasen, oikea) heapq.heappush(nodes, newNode) # Huffman Tree on valmis! printNodes(nodes[0])>> |
>yleisyys javassa
>>// 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) { // ensimmäisen minuutin ote. olkoon x = q[0]; q.shift(); // toisen minuutin ote. olkoon y = q[0]; q.shift(); // uusi solmu f joka on yhtä suuri anna f = new HuffmanNode(); // kahden solmun taajuuden summaan // antaa arvot f-solmulle. f.data = x.data + y.data; f.c = '-'; // ensimmäinen purettu solmu vasemmalla lapsilla. f.vasen = x; // toinen purettu solmu oikeana lapsena. f.oikea = y; // f-solmun merkitseminen juurisolmuksi. juuri = f; // lisää tämä solmu prioriteettijonoon. q.push(f); q.sort(funktio(a,b){palauttaa a.data-b.data;}); } // tulostaa koodit kulkemalla puun läpi printCode(root, ''); // Tämän koodin tarjoaa 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>>>Lähtöf: 0 c: 100 d: 101 a: 1100 b: 1101 e: 111>Aika monimutkaisuus: O(nlogn) jossa n on yksilöllisten merkkien määrä. Jos solmuja on n, extraMin() kutsutaan 2*(n – 1) kertaa. extractMin() ottaa O(logn)-ajan, koska se kutsuu minHeapify()-funktiota. Joten yleinen monimutkaisuus on O(nlogn).
Jos syöttötaulukko on lajiteltu, on olemassa lineaarinen aikaalgoritmi. Keskustelemme tästä pian seuraavassa postauksessamme.Avaruuden monimutkaisuus: - O(N)
Huffman-koodauksen sovellukset:
- Niitä käytetään faksin ja tekstin lähettämiseen.
- Niitä käyttävät tavanomaiset pakkausmuodot, kuten PKZIP, GZIP jne.
- Multimediakoodekit, kuten JPEG, PNG ja MP3, käyttävät Huffman-koodausta (täsmällisemmin etuliitekoodeja).
Se on hyödyllinen tapauksissa, joissa on useita usein esiintyviä merkkejä.
Viite:
http://en.wikipedia.org/wiki/Huffman_coding
Tämän artikkelin on koonnut Aashish Barnwal ja arvioinut techcodeview.com-tiimi.