Les dades es poden comprimir mitjançant la tècnica de codificació Huffman per fer-se més petites sense perdre cap informació. Després de David Huffman, qui el va crear al principi? Les dades que contenen caràcters que es repeteixen amb freqüència es comprimeixen normalment mitjançant la codificació Huffman.
Un algorisme Greedy conegut és Huffman Coding. La mida del codi assignat a un caràcter depèn de la freqüència del caràcter, per això es coneix com un algorisme cobdiciós. El codi variable de longitud curta s'assigna al caràcter amb la freqüència més alta, i viceversa per als caràcters amb freqüències més baixes. Utilitza una codificació de longitud variable, el que significa que dóna a cada caràcter del flux de dades proporcionat un codi de longitud variable diferent.
Regla del prefix
Bàsicament, aquesta regla estableix que el codi que s'assigna a un caràcter no ha de ser el prefix d'un altre codi. Si es trenca aquesta regla, poden aparèixer diverses ambigüitats en descodificar l'arbre de Huffman que s'ha creat.
Vegem una il·lustració d'aquesta regla per entendre-la millor: per a cada caràcter, es proporciona un codi, com ara:
a - 0 b - 1 c - 01
Suposant que el flux de bits produït és 001, el codi es pot expressar de la següent manera quan es descodifica:
0 0 1 = aab 0 01 = ac
Què és el procés de codificació Huffman?
El codi Huffman s'obté per a cada personatge diferent principalment en dos passos:
- Creeu primer un arbre Huffman utilitzant només els caràcters únics del flux de dades proporcionat.
- En segon lloc, hem de procedir a través de l'arbre de Huffman construït, assignar codis als personatges i després utilitzar aquests codis per descodificar el text proporcionat.
Passos a seguir en Huffman Coding
Els passos utilitzats per construir l'arbre Huffman utilitzant els personatges proporcionats
Input: string str = 'abbcdbccdaabbeeebeab'
Si s'utilitza Huffman Coding en aquest cas per a la compressió de dades, s'ha de determinar la informació següent per a la descodificació:
- Per a cada personatge, el codi Huffman
- Longitud del missatge codificat per Huffman (en bits), longitud mitjana del codi
- Utilitzant les fórmules descrites a continuació, es descobreixen les dues últimes.
Com es pot construir un arbre Huffman a partir de caràcters d'entrada?
Primer s'ha de determinar la freqüència de cada caràcter de la cadena proporcionada.
| Personatge | Freqüència |
|---|---|
| a | 4 |
| b | 7 |
| c | 3 |
| d | 2 |
| És | 4 |
- Ordena els caràcters per freqüència, ascendent. Aquests es mantenen en una cua de prioritat Q/min-heap.
- Per a cada caràcter diferent i la seva freqüència al flux de dades, creeu un node fulla.
- Traieu els dos nodes amb les dues freqüències més baixes dels nodes i es crea la nova arrel de l'arbre utilitzant la suma d'aquestes freqüències.
- Feu que el primer node extret sigui el seu fill esquerre i el segon node extret el seu fill dret mentre extreu els nodes amb la freqüència més baixa del munt min.
- Afegiu aquest node al min-heap.
- Com que el costat esquerre de l'arrel ha de contenir sempre la freqüència mínima.
- Repetiu els passos 3 i 4 fins que només quedi un node a la pila, o tots els caràcters estiguin representats per nodes a l'arbre. L'arbre s'acaba quan només queda el node arrel.
Exemples de codificació Huffman
Utilitzem una il·lustració per explicar l'algorisme:
Algorisme per a la codificació de Huffman
Pas 1: Creeu un munt mínim en què cada node representi l'arrel d'un arbre amb un sol node i en tingui 5 (el nombre de caràcters únics del flux de dades proporcionat).
Pas 2: Obteniu dos nodes de freqüència mínima del munt mínim al pas dos. Afegiu un tercer node intern, freqüència 2 + 3 = 5, que es crea unint els dos nodes extrets.
- Ara, hi ha 4 nodes al munt mínim, 3 dels quals són les arrels dels arbres amb un sol element cadascun, i 1 dels quals és l'arrel d'un arbre amb dos elements.
Pas 3: Obteniu els dos nodes de freqüència mínima del munt d'una manera similar al pas tres. Addicionalment, afegiu un nou node intern format unint els dos nodes extrets; la seva freqüència a l'arbre hauria de ser 4 + 4 = 8.
c programes
- Ara que l'emmagatzematge mínim té tres nodes, un node serveix d'arrel d'arbres amb un sol element i dos nodes de pila serveixen d'arrel d'arbres amb múltiples nodes.
Pas 4: Obteniu els dos nodes de freqüència mínima al pas quatre. Addicionalment, afegiu un nou node intern format unint els dos nodes extrets; la seva freqüència a l'arbre hauria de ser 5 + 7 = 12.
- Quan creem un arbre de Huffman, hem d'assegurar-nos que el valor mínim sempre estigui al costat esquerre i que el segon valor sempre estigui al costat dret. Actualment, la imatge següent mostra l'arbre que s'ha format:
Pas 5: Obteniu els dos nodes de freqüència mínima següents al pas 5. A més, afegiu un nou node intern format unint els dos nodes extrets; la seva freqüència a l'arbre hauria de ser 12 + 8 = 20.
Continueu fins que s'hagin afegit tots els caràcters diferents a l'arbre. L'arbre de Huffman creat per al repartiment de personatges especificat es mostra a la imatge de dalt.
Ara, per a cada node no full, assigneu 0 a la vora esquerra i 1 a la vora dreta per crear el codi per a cada lletra.
Regles a seguir per determinar els pesos de les vores:
- Hauríem de donar un pes de 1 a les vores de la dreta si doneu un pes de 0 a les vores esquerres.
- Si a les vores esquerres se'ls dóna un pes 1, s'ha de donar un pes a les vores dretes 0.
- Es pot utilitzar qualsevol de les dues convencions esmentades anteriorment.
- Tanmateix, seguiu el mateix protocol quan descodifiqueu l'arbre també.
Després de la ponderació, l'arbre modificat es mostra de la següent manera:
Comprensió del Codi
- Hem de passar per l'arbre de Huffman fins a arribar al node fulla, on hi ha l'element, per tal de descodificar el codi de Huffman per a cada caràcter de l'arbre de Huffman resultant.
- Els pesos dels nodes s'han d'enregistrar durant el recorregut i assignar-los als elements situats al node de fulla específic.
- L'exemple següent ajudarà a il·lustrar més el que volem dir:
- Per obtenir el codi de cada caràcter de la imatge de dalt, hem de caminar per tot l'arbre (fins que tots els nodes de fulla estiguin coberts).
- Com a resultat, l'arbre que s'ha creat s'utilitza per descodificar els codis de cada node. A continuació es mostra una llista dels codis de cada personatge:
| Personatge | Freqüència/compte | Codi |
|---|---|---|
| a | 4 | 01 |
| b | 7 | 11 |
| c | 3 | 101 |
| d | 2 | 100 |
| És | 4 | 00 |
A continuació es mostra la implementació en programació 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; } Sortida
f: 0 c: 100 d: 101 a: 1100 b: 1101 e: 111 …………… Process executed in 1.11 seconds Press any key to continue.
Implementació Java del codi anterior:
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 <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 = '-'; // 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, ''); } } // 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;> Sortida
f: 0 c: 100 d: 101 a: 1100 b: 1101 e: 111 ………………. Process executed in 1.11 seconds Press any key to continue.
Explicació:
En recórrer, es crea i descodifica l'arbre de Huffman. Els valors recollits durant el recorregut s'han d'aplicar després al caràcter situat al node fulla. Cada caràcter únic del flux de dades subministrat es pot identificar mitjançant el codi Huffman d'aquesta manera. O (nlogn), on n és el nombre total de caràcters, és la complexitat del temps. ExtractMin() s'anomena 2*(n - 1) vegades si hi ha n nodes. Com que extractMin() crida a minHeapify(), el seu temps d'execució és O (logn). Per tant, la complexitat total és O (nlogn). Hi ha un algorisme de temps lineal si la matriu d'entrada està ordenada. Això es tractarà amb més detall a la nostra propera peça.
Problemes amb Huffman Coding
Parlem dels inconvenients de la codificació de Huffman en aquesta part i per què no sempre és la millor opció:
- Si no totes les probabilitats o freqüències dels personatges són potències negatives de 2, no es considera ideal.
- Tot i que un pot acostar-se a l'ideal agrupant símbols i ampliant l'alfabet, el mètode de bloqueig requereix manejar un alfabet més gran. Per tant, la codificació de Huffman pot no ser sempre molt eficaç.
- Tot i que hi ha moltes maneres efectives de comptar la freqüència de cada símbol o caràcter, reconstruir l'arbre sencer per a cadascun pot ser molt llarg. Quan l'alfabet és gran i les distribucions de probabilitat canvien ràpidament amb cada símbol, aquest és normalment el cas.
Algoritme de construcció del codi Greedy Huffman
- Huffman va desenvolupar una tècnica cobdiciosa que genera un codi Huffman, un codi de prefix ideal, per a cada caràcter diferent del flux de dades d'entrada.
- L'enfocament utilitza el menor nombre de nodes cada vegada per crear l'arbre Huffman de baix a dalt.
- Com que cada caràcter rep una longitud de codi en funció de la freqüència amb què apareix en el flux de dades donat, aquest mètode es coneix com a enfocament cobdiciós. És un element que apareix habitualment a les dades si la mida del codi recuperat és menor.
L'ús de la codificació Huffman
- Aquí, parlarem d'alguns usos pràctics per a Huffman Coding:
- Els formats de compressió convencionals com PKZIP, GZIP, etc. solen emprar codificació Huffman.
- La codificació Huffman s'utilitza per a la transferència de dades per fax i text perquè minimitza la mida del fitxer i augmenta la velocitat de transmissió.
- La codificació Huffman (especialment els codis de prefix) és utilitzada per diversos formats d'emmagatzematge multimèdia, inclosos JPEG, PNG i MP3, per comprimir els fitxers.
- La codificació Huffman s'utilitza principalment per a la compressió d'imatges.
- Quan s'ha d'enviar una cadena de caràcters sovint recurrents, pot ser més útil.
Conclusió
- En general, Huffman Coding és útil per comprimir dades que contenen caràcters que apareixen amb freqüència.
- Podem veure que el caràcter que apareix amb més freqüència té el codi més curt, mentre que el que apareix amb menys freqüència té el codi més gran.
- La tècnica de compressió del codi Huffman s'utilitza per crear una codificació de longitud variable, que utilitza una quantitat variada de bits per a cada lletra o símbol. Aquest mètode és superior a la codificació de longitud fixa, ja que utilitza menys memòria i transmet dades més ràpidament.
- Consulteu aquest article per conèixer millor l'algoritme cobdiciós.