Podatke je mogoče stisniti s tehniko Huffmanovega kodiranja, da postanejo manjši, ne da bi pri tem izgubili podatke. Kdo ga je po Davidu Huffmanu ustvaril na začetku? Podatki, ki vsebujejo pogosto ponavljajoče se znake, so običajno stisnjeni s Huffmanovim kodiranjem.

Dobro znan algoritem Greedy je Huffmanovo kodiranje. Velikost kode, dodeljene znaku, je odvisna od frekvence znaka, zato se imenuje požrešen algoritem. Koda spremenljive kratke dolžine je dodeljena znaku z najvišjo frekvenco in obratno za znake z nižjo frekvenco. Uporablja kodiranje s spremenljivo dolžino, kar pomeni, da daje vsakemu znaku v podanem podatkovnem toku drugačno kodo s spremenljivo dolžino.

Pravilo predpone

V bistvu to pravilo določa, da koda, ki je dodeljena znaku, ne sme biti predpona druge kode. Če je to pravilo prekršeno, se lahko med dekodiranjem ustvarjenega Huffmanovega drevesa pojavijo različne dvoumnosti.

Oglejmo si ilustracijo tega pravila, da ga bomo bolje razumeli: Za vsak znak je navedena koda, kot je:

 a - 0 b - 1 c - 01 

Ob predpostavki, da je proizvedeni bitni tok 001, se lahko koda pri dekodiranju izrazi na naslednji način:

so vzorčni primeri

 0 0 1 = aab 0 01 = ac 

Kaj je postopek Huffmanovega kodiranja?

Huffmanovo kodo pridobimo za vsak ločen znak predvsem v dveh korakih:

• Najprej ustvarite Huffmanovo drevo z uporabo samo edinstvenih znakov v podanem toku podatkov.
• Drugič, nadaljevati moramo skozi zgrajeno Huffmanovo drevo, znakom dodeliti kode in te kode nato uporabiti za dekodiranje podanega besedila.

Koraki, ki jih morate narediti pri Huffmanovem kodiranju

Koraki, uporabljeni za izdelavo Huffmanovega drevesa z uporabo navedenih znakov

 Input: string str = 'abbcdbccdaabbeeebeab' 

Če se v tem primeru za stiskanje podatkov uporablja Huffmanovo kodiranje, je treba za dekodiranje določiti naslednje informacije:

• Za vsak znak Huffmanova koda
• Dolžina Huffmanovo kodiranega sporočila (v bitih), povprečna dolžina kode
• Z uporabo spodnjih formul sta odkriti zadnji dve.

Kako je mogoče sestaviti Huffmanovo drevo iz vhodnih znakov?

Najprej je treba določiti pogostost vsakega znaka v podanem nizu.

1. Razvrsti znake po pogostosti, naraščajoče. Ti se hranijo v prednostni čakalni vrsti kopice Q/min.
2. Za vsak ločen znak in njegovo frekvenco v podatkovnem toku ustvarite listno vozlišče.
3. Odstranite dve vozlišči z dvema najnižjima frekvencama iz vozlišč in nov koren drevesa se ustvari z uporabo vsote teh frekvenc.
   • Prvo izvlečeno vozlišče naredite za levega podrejenega, drugo izvlečeno vozlišče pa za desnega podrejenega, pri tem pa iz kopice min ekstrahirajte vozlišča z najnižjo frekvenco.
   • V min-heap dodajte to vozlišče.
   • Ker mora leva stran korena vedno vsebovati najmanjšo frekvenco.
4. Ponavljajte koraka 3 in 4, dokler na kupu ne ostane samo eno vozlišče ali pa so vsi znaki predstavljeni z vozlišči v drevesu. Drevo je končano, ko ostane samo korensko vozlišče.

Primeri Huffmanovega kodiranja

Za razlago algoritma uporabimo ilustracijo:

Algoritem za Huffmanovo kodiranje

Korak 1: Zgradite najmanjšo kopico, v kateri vsako vozlišče predstavlja koren drevesa z enim vozliščem in vsebuje 5 (število edinstvenih znakov iz podanega toka podatkov).

2. korak: Pridobite dve minimalni frekvenčni vozlišči iz minimalne kopice v drugem koraku. Dodajte tretje notranje vozlišče, frekvenca 2 + 3 = 5, ki se ustvari z združitvijo dveh ekstrahiranih vozlišč.

• Zdaj so v kopici min 4 vozlišča, od katerih so 3 korenine dreves z enim elementom, 1 pa je koren drevesa z dvema elementoma.

3. korak: Pridobite dve minimalni frekvenčni vozlišči iz kopice na podoben način v tretjem koraku. Poleg tega dodajte novo notranje vozlišče, ki nastane z združitvijo dveh ekstrahiranih vozlišč; njegova frekvenca v drevesu bi morala biti 4 + 4 = 8.

• Zdaj, ko ima minimalna kopica tri vozlišča, eno vozlišče služi kot koren dreves z enim elementom, dve vozlišči kopice pa služita kot koren dreves z več vozlišči.

4. korak: Pridobite dve minimalni frekvenčni vozlišči v četrtem koraku. Poleg tega dodajte novo notranje vozlišče, ki nastane z združitvijo dveh ekstrahiranih vozlišč; njegova frekvenca v drevesu bi morala biti 5 + 7 = 12.

• Pri ustvarjanju Huffmanovega drevesa moramo zagotoviti, da je minimalna vrednost vedno na levi strani in da je druga vrednost vedno na desni strani. Trenutno spodnja slika prikazuje oblikovano drevo:

5. korak: Pridobite naslednji dve minimalni frekvenčni vozlišči v koraku 5. Poleg tega dodajte novo notranje vozlišče, ki nastane z združitvijo dveh ekstrahiranih vozlišč; njegova frekvenca v drevesu bi morala biti 12 + 8 = 20.

Nadaljujte, dokler v drevo niso dodani vsi različni znaki. Huffmanovo drevo, ustvarjeno za določeno zasedbo likov, je prikazano na zgornji sliki.

Zdaj za vsako vozlišče, ki ni list, dodelite 0 levemu robu in 1 desnemu robu, da ustvarite kodo za vsako črko.

Pravila, ki jih je treba upoštevati pri določanju teže robov:

• Desnim robom bi morali dati težo 1, če daš levim robom težo 0.
• Če imajo levi robovi utež 1, morajo imeti desni robovi utež 0.
• Uporabi se lahko katera koli od zgoraj navedenih konvencij.
• Vendar sledite istemu protokolu tudi pri dekodiranju drevesa.

Po tehtanju je spremenjeno drevo prikazano na naslednji način:

Razumevanje kodeksa

• Skozi Huffmanovo drevo moramo iti, dokler ne dosežemo listnega vozla, kjer je element prisoten, da dekodiramo Huffmanovo kodo za vsak znak iz nastalega Huffmanovega drevesa.
• Uteži med vozlišči je treba zabeležiti med prečkanjem in dodeliti elementom, ki se nahajajo v določenem listnem vozlišču.
• Naslednji primer vam bo pomagal še bolj ponazoriti, kaj mislimo:
• Da bi dobili kodo za vsak znak na zgornji sliki, moramo prehoditi celotno drevo (dokler niso pokriti vsi vozli listov).
• Posledično se ustvarjeno drevo uporabi za dekodiranje kod za vsako vozlišče. Spodaj je seznam kod za vsak znak:

Spodaj je implementacija v programiranju 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->left = temp->right = NULL; temp->data = data; temp->freq = freq; 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->size = 0; minHeap->capacity = capacity; minHeap->array = (struct MinHeapNode**)malloc( minHeap->capacity * 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[left]->freq array[smallest]->freq) smallest = left; if (right size && minHeap->array[right]->freq array[smallest]->freq) smallest = right; if (smallest != idx) { swapMinHeapNode(&minHeap->array[smallest], &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->size == 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->size - 1]; --minHeap->size; 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->size; int i = minHeap->size - 1; while (i && minHeapNode->freq 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->size - 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 left) && !(root->right); } // Creates a min heap of capacity // equal to size and inserts all character of // data[] in min heap. Initially size of // min heap is equal to capacity struct MinHeap* createAndBuildMinHeap(char data[], int freq[], int size) { struct MinHeap* minHeap = createMinHeap(size); for (int i = 0; i array[i] = newNode(data[i], freq[i]); minHeap->size = size; buildMinHeap(minHeap); return minHeap; } // The main function that builds Huffman tree struct MinHeapNode* buildHuffmanTree(char data[], int freq[], int size) { struct MinHeapNode *left, *right, *top; // Step 1: Create a min heap of capacity // equal to size. Initially, there are // modes equal to size. struct MinHeap* minHeap = createAndBuildMinHeap(data, freq, size); // Iterate while size of heap doesn't become 1 while (!isSizeOne(minHeap)) { // Step 2: Extract the two minimum // freq items from min heap left = extractMin(minHeap); right = extractMin(minHeap); // Step 3: 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 = newNode('$', left->freq + right->freq); top->left = left; top->right = right; insertMinHeap(minHeap, top); } // Step 4: The remaining node is the // root node and the tree is complete. return extractMin(minHeap); } // Prints huffman codes from the root of Huffman Tree. // It uses arr[] to store codes void printCodes(struct MinHeapNode* root, int arr[], int top) { // Assign 0 to left edge and recur if (root->left) { arr[top] = 0; printCodes(root->left, arr, top + 1); } // Assign 1 to right edge and recur if (root->right) { arr[top] = 1; printCodes(root->right, arr, top + 1); } // If this is a leaf node, then // it contains one of the input // characters, print the character // and its code from arr[] if (isLeaf(root)) { printf('%c: ', root->data); printArr(arr, top); } } // The main function that builds a // Huffman Tree and print codes by traversing // the built Huffman Tree void HuffmanCodes(char data[], int freq[], int size) { // Construct Huffman Tree struct MinHeapNode* root = buildHuffmanTree(data, freq, size); // Print Huffman codes using // the Huffman tree built above int arr[MAX_TREE_HT], top = 0; printCodes(root, arr, top); } // Driver code int main() { char arr[] = { 'a', 'b', 'c', 'd', 'e', 'f' }; int freq[] = { 5, 9, 12, 13, 16, 45 }; int size = sizeof(arr) / sizeof(arr[0]); HuffmanCodes(arr, freq, size); return 0; } 

Izhod

 f: 0 c: 100 d: 101 a: 1100 b: 1101 e: 111 …………… Process executed in 1.11 seconds Press any key to continue. 

Izvedba zgornje kode v Javi:

 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 &amp;&amp; root.right == null &amp;&amp; Character.isLetter(root.c)) { // c is the character in the node System.out.println(root.c + &apos;:&apos; + s); return; } // if we go to left then add &apos;0&apos; to the code. // if we go to the right add&apos;1&apos; to the code. // recursive calls for left and // right sub-tree of the generated tree. printCode(root.left, s + &apos;0&apos;); printCode(root.right, s + &apos;1&apos;); } // main function public static void main(String[] args) { Scanner s = new Scanner(System.in); // number of characters. int n = 6; char[] charArray = { &apos;a&apos;, &apos;b&apos;, &apos;c&apos;, &apos;d&apos;, &apos;e&apos;, &apos;f&apos; }; 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 <n; 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;" functions adds q.add(hn); } create root here we will extract two minimum value from heap each time until its size reduces 1, all nodes are extracted. while (q.size()> 1) { // first min extract. HuffmanNode x = q.peek(); q.poll(); // second min extract. HuffmanNode y = q.peek(); q.poll(); // new node f which is equal HuffmanNode f = new HuffmanNode(); // to the sum of the frequency of the two nodes // assigning values to the f node. f.data = x.data + y.data; f.c = &apos;-&apos;; // first extracted node as left child. f.left = x; // second extracted node as the right child. f.right = y; // marking the f node as the root node. root = f; // add this node to the priority-queue. q.add(f); } // print the codes by traversing the tree printCode(root, &apos;&apos;); } } // node class is the basic structure // of each node present in the Huffman - tree. class HuffmanNode { int data; char c; HuffmanNode left; HuffmanNode right; } // comparator class helps to compare the node // on the basis of one of its attribute. // Here we will be compared // on the basis of data values of the nodes. class MyComparator implements Comparator { public int compare(HuffmanNode x, HuffmanNode y) { return x.data - y.data; } } </n;>

Izhod

 f: 0 c: 100 d: 101 a: 1100 b: 1101 e: 111 ………………. Process executed in 1.11 seconds Press any key to continue. 

Pojasnilo:

S prečkanjem se ustvari in dekodira Huffmanovo drevo. Vrednosti, zbrane med prečkanjem, se nato uporabijo za znak, ki se nahaja na listnem vozlišču. Na ta način je mogoče s Huffmanovo kodo identificirati vsak edinstven znak v posredovanem toku podatkov. O (nlogn), kjer je n skupno število znakov, je časovna kompleksnost. ExtractMin() se kliče 2*(n - 1)-krat, če obstaja n vozlišč. Ker extractMin() kliče minHeapify(), je njegov čas izvajanja O (logn). Skupna kompleksnost je torej O (nlogn). Obstaja linearni časovni algoritem, če je vhodna matrika razvrščena. To bo podrobneje obravnavano v našem prihodnjem delu.

Težave s Huffmanovim kodiranjem

Pogovorimo se o pomanjkljivostih Huffmanovega kodiranja v tem delu in zakaj to ni vedno najboljša možnost:

• Če niso vse verjetnosti ali frekvence znakov negativne potence 2, se ne šteje za idealno.
• Čeprav se lahko z združevanjem simbolov in razširitvijo abecede približamo idealu, metoda blokiranja zahteva uporabo večje abecede. Zato Huffmanovo kodiranje morda ni vedno zelo učinkovito.
• Čeprav obstaja veliko učinkovitih načinov za štetje pogostosti vsakega simbola ali znaka, je lahko rekonstrukcija celotnega drevesa za vsakega zelo zamudna. Če je abeceda velika in se porazdelitve verjetnosti hitro spremenijo z vsakim simbolom, je to običajno tako.

Algoritem za gradnjo pohlepne Huffmanove kode

• Huffman je razvil požrešno tehniko, ki generira Huffmanovo kodo, idealno kodo predpone, za vsak ločen znak v toku vhodnih podatkov.
• Pristop vsakič uporabi najmanj vozlišč za ustvarjanje Huffmanovega drevesa od spodaj navzgor.
• Ker vsak znak prejme dolžino kode glede na to, kako pogosto se pojavlja v danem toku podatkov, je ta metoda znana kot požrešen pristop. To je pogost element v podatkih, če je velikost pridobljene kode manjša.

Uporaba Huffmanovega kodiranja

• Tukaj bomo govorili o nekaterih praktičnih uporabah Huffmanovega kodiranja:
• Običajni formati stiskanja, kot so PKZIP, GZIP itd., običajno uporabljajo Huffmanovo kodiranje.
• Huffmanovo kodiranje se uporablja za prenos podatkov po faksu in besedilu, ker zmanjša velikost datoteke in poveča hitrost prenosa.
• Huffmanovo kodiranje (zlasti predpone) uporablja več večpredstavnostnih formatov za shranjevanje, vključno z JPEG, PNG in MP3, za stiskanje datotek.
• Huffmanovo kodiranje se večinoma uporablja za stiskanje slik.
• Ko je treba poslati niz pogosto ponavljajočih se znakov, je to lahko bolj koristno.

Zaključek

• Na splošno je Huffmanovo kodiranje koristno za stiskanje podatkov, ki vsebujejo znake, ki se pogosto pojavljajo.
• Vidimo lahko, da ima znak, ki se najpogosteje pojavlja, najkrajšo kodo, medtem ko ima znak, ki se pojavlja najredkeje, največjo kodo.
• Tehnika stiskanja Huffmanove kode se uporablja za ustvarjanje kodiranja s spremenljivo dolžino, ki uporablja različno količino bitov za vsako črko ali simbol. Ta metoda je boljša od kodiranja s fiksno dolžino, saj uporablja manj pomnilnika in hitreje prenaša podatke.
• Preberite ta članek, da boste bolje spoznali pohlepni algoritem.