Datele pot fi comprimate folosind tehnica Huffman Coding pentru a deveni mai mici, fără a pierde nicio informație. După David Huffman, cine a creat-o la început? Datele care conțin caractere repetate frecvent sunt de obicei comprimate folosind codarea Huffman.
Un algoritm Greedy bine-cunoscut este Huffman Coding. Mărimea codului alocat unui caracter se bazează pe frecvența caracterului, motiv pentru care se spune că este un algoritm lacom. Codul variabil de lungime scurtă este atribuit caracterului cu cea mai mare frecvență și invers pentru caracterele cu frecvențe mai mici. Utilizează o codificare cu lungime variabilă, ceea ce înseamnă că oferă fiecărui caracter din fluxul de date furnizat un cod diferit cu lungime variabilă.
Regula prefixului
În esență, această regulă prevede că codul care este alocat unui caracter nu trebuie să fie prefixul altui cod. Dacă această regulă este încălcată, pot apărea diverse ambiguități la decodarea arborelui Huffman care a fost creat.
Să ne uităm la o ilustrare a acestei reguli pentru a o înțelege mai bine: pentru fiecare caracter, este furnizat un cod, cum ar fi:
java arraylist sortată
a - 0 b - 1 c - 01
Presupunând că fluxul de biți produs este 001, codul poate fi exprimat după cum urmează atunci când este decodat:
0 0 1 = aab 0 01 = ac
Ce este procesul de codificare Huffman?
Codul Huffman este obținut pentru fiecare personaj distinct în principal în doi pași:
- Creați mai întâi un arbore Huffman folosind doar caracterele unice din fluxul de date furnizat.
- În al doilea rând, trebuie să trecem prin Arborele Huffman construit, să atribuim coduri personajelor și apoi să folosim acele coduri pentru a decoda textul furnizat.
Pași de urmat în codarea Huffman
Pașii utilizați pentru a construi arborele Huffman folosind caracterele furnizate
Input: string str = 'abbcdbccdaabbeeebeab'
Dacă Huffman Coding este folosit în acest caz pentru comprimarea datelor, următoarele informații trebuie determinate pentru decodare:
- Pentru fiecare personaj, Codul Huffman
- Lungimea mesajului codificat Huffman (în biți), lungimea medie a codului
- Folosind formulele prezentate mai jos, sunt descoperite ultimele două dintre ele.
Cum poate fi construit un arbore Huffman din caractere de intrare?
Frecvența fiecărui caracter din șirul furnizat trebuie mai întâi determinată.
| Caracter | Frecvență |
|---|---|
| A | 4 |
| b | 7 |
| c | 3 |
| d | 2 |
| Este | 4 |
- Sortați caracterele după frecvență, crescător. Acestea sunt păstrate într-o coadă de prioritate Q/min-heap.
- Pentru fiecare caracter distinct și frecvența acestuia în fluxul de date, creați un nod frunză.
- Îndepărtați cele două noduri cu cele două frecvențe cele mai joase din noduri și noua rădăcină a arborelui este creată folosind suma acestor frecvențe.
- Faceți din primul nod extras copilul stâng și al doilea nod extras copilul drept, în timp ce extrageți nodurile cu cea mai mică frecvență din min-heap.
- La min-heap, adăugați acest nod.
- Deoarece partea stângă a rădăcinii ar trebui să conțină întotdeauna frecvența minimă.
- Repetați pașii 3 și 4 până când rămâne un singur nod în heap sau toate caracterele sunt reprezentate prin noduri din arbore. Arborele este terminat când rămâne doar nodul rădăcină.
Exemple de codare Huffman
Să folosim o ilustrație pentru a explica algoritmul:
Algoritm pentru codarea Huffman
Pasul 1: Construiți un min-heap în care fiecare nod reprezintă rădăcina unui arbore cu un singur nod și conține 5 (numărul de caractere unice din fluxul de date furnizat).
Pasul 2: Obțineți două noduri de frecvență minimă din heap-ul min în pasul doi. Adăugați un al treilea nod intern, frecvența 2 + 3 = 5, care este creat prin unirea celor două noduri extrase.
- Acum, există 4 noduri în grămada min, dintre care 3 sunt rădăcinile copacilor cu câte un singur element fiecare și 1 este rădăcina unui copac cu două elemente.
Pasul 3: Obțineți cele două noduri de frecvență minimă din heap într-un mod similar în pasul trei. În plus, adăugați un nou nod intern format prin unirea celor două noduri extrase; frecvența sa în arbore ar trebui să fie 4 + 4 = 8.
- Acum că heap-ul minim are trei noduri, un nod servește ca rădăcină a copacilor cu un singur element și două noduri heap servesc ca rădăcină a copacilor cu mai multe noduri.
Pasul 4: Obțineți cele două noduri de frecvență minimă la pasul patru. În plus, adăugați un nou nod intern format prin unirea celor două noduri extrase; frecvența sa în arbore ar trebui să fie 5 + 7 = 12.
- Când creăm un arbore Huffman, trebuie să ne asigurăm că valoarea minimă este întotdeauna în partea stângă și că a doua valoare este întotdeauna în partea dreaptă. În prezent, imaginea de mai jos arată arborele care s-a format:
Pasul 5: Obțineți următoarele două noduri de frecvență minimă la pasul 5. În plus, adăugați un nou nod intern format prin unirea celor două noduri extrase; frecvența sa în arbore ar trebui să fie 12 + 8 = 20.
Continuați până când toate caracterele distincte au fost adăugate în arbore. Arborele Huffman creat pentru distribuția de personaje specificată este afișat în imaginea de mai sus.
sensul xdxd
Acum, pentru fiecare nod fără frunză, atribuiți 0 marginii din stânga și 1 marginii din dreapta pentru a crea codul pentru fiecare literă.
Reguli de urmat pentru determinarea greutăților muchiilor:
- Ar trebui să acordăm greutatea 1 marginilor din dreapta dacă acordați greutatea 0 marginilor din stânga.
- Dacă muchiilor din stânga li se acordă greutate 1, muchiilor din dreapta trebuie să li se acorde greutate 0.
- Oricare dintre cele două convenții menționate mai sus poate fi utilizată.
- Cu toate acestea, urmați același protocol și atunci când decodați arborele.
În urma ponderării, arborele modificat este afișat după cum urmează:
Înțelegerea Codului
- Trebuie să trecem prin arborele Huffman până ajungem la nodul frunză, unde este prezent elementul, pentru a decoda codul Huffman pentru fiecare personaj din arborele Huffman rezultat.
- Greutățile de-a lungul nodurilor trebuie înregistrate în timpul traversării și alocate elementelor situate la nodul frunză specific.
- Următorul exemplu ne va ajuta să ilustrăm în continuare ceea ce ne referim:
- Pentru a obține codul pentru fiecare personaj din imaginea de mai sus, trebuie să parcurgem întregul arbore (până când toate nodurile frunzelor sunt acoperite).
- Ca rezultat, arborele care a fost creat este folosit pentru a decoda codurile pentru fiecare nod. Mai jos este o listă a codurilor pentru fiecare personaj:
| Caracter | Frecvență/număr | Cod |
|---|---|---|
| A | 4 | 01 |
| b | 7 | unsprezece |
| c | 3 | 101 |
| d | 2 | 100 |
| Este | 4 | 00 |
Mai jos este implementarea în programarea 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; } Ieșire
f: 0 c: 100 d: 101 a: 1100 b: 1101 e: 111 …………… Process executed in 1.11 seconds Press any key to continue.
Implementarea Java a codului de mai sus:
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;> Ieșire
f: 0 c: 100 d: 101 a: 1100 b: 1101 e: 111 ………………. Process executed in 1.11 seconds Press any key to continue.
Explicaţie:
Prin traversare, Arborele Huffman este creat și decodat. Valorile adunate în timpul traversării urmează să fie apoi aplicate caracterului situat la nodul frunză. Fiecare caracter unic din fluxul de date furnizat poate fi identificat folosind Codul Huffman în acest mod. O (nlogn), unde n este numărul total de caractere, este complexitatea timpului. ExtractMin() este numit de 2*(n - 1) ori dacă există n noduri. Deoarece extractMin() apelează minHeapify(), timpul său de execuție este O (logn). Complexitatea totală este deci O (nlogn). Există un algoritm de timp liniar dacă matricea de intrare este sortată. Acest lucru va fi tratat mai detaliat în piesa noastră viitoare.
Probleme cu Huffman Coding
Să vorbim despre dezavantajele codării Huffman în această parte și de ce nu este întotdeauna cea mai bună opțiune:
- Dacă nu toate probabilitățile sau frecvențele personajelor sunt puteri negative de 2, aceasta nu este considerată ideală.
- Deși te poți apropia de ideal prin gruparea simbolurilor și extinderea alfabetului, metoda de blocare necesită manipularea unui alfabet mai mare. Prin urmare, codarea Huffman poate să nu fie întotdeauna foarte eficientă.
- Deși există multe modalități eficiente de a număra frecvența fiecărui simbol sau caracter, reconstruirea întregului arbore pentru fiecare poate fi foarte consumatoare de timp. Când alfabetul este mare și distribuțiile de probabilitate se schimbă rapid cu fiecare simbol, acesta este de obicei cazul.
Algoritmul de construcție a codului Greedy Huffman
- Huffman a dezvoltat o tehnică lacomă care generează un cod Huffman, un cod prefix ideal, pentru fiecare caracter distinct din fluxul de date de intrare.
- Abordarea folosește cele mai puține noduri de fiecare dată pentru a crea arborele Huffman de jos în sus.
- Deoarece fiecare caracter primește o lungime de cod în funcție de frecvența cu care apare în fluxul de date dat, această metodă este cunoscută ca o abordare lacomă. Este un element frecvent întâlnit în date dacă dimensiunea codului preluat este mai mică.
Utilizarea codării Huffman
- Aici, vom vorbi despre câteva utilizări practice pentru Huffman Coding:
- Formatele convenționale de compresie, cum ar fi PKZIP, GZIP etc. folosesc de obicei codarea Huffman.
- Huffman Coding este utilizat pentru transferul de date prin fax și text, deoarece reduce dimensiunea fișierului și crește viteza de transmisie.
- Codarea Huffman (în special codurile de prefix) este utilizată de mai multe formate de stocare multimedia, inclusiv JPEG, PNG și MP3, pentru a comprima fișierele.
- Codarea Huffman este folosită mai ales pentru compresia imaginii.
- Când trebuie trimis un șir de caractere adesea recurente, poate fi mai util.
Concluzie
- În general, Huffman Coding este utilă pentru comprimarea datelor care conțin caractere care apar frecvent.
- Putem vedea că caracterul care apare cel mai frecvent are cel mai scurt cod, în timp ce cel care apare cel mai puțin frecvent are cel mai mare cod.
- Tehnica de compresie Huffman Code este utilizată pentru a crea codare cu lungime variabilă, care utilizează o cantitate variată de biți pentru fiecare literă sau simbol. Această metodă este superioară codării cu lungime fixă, deoarece utilizează mai puțină memorie și transmite datele mai rapid.
- Parcurgeți acest articol pentru a cunoaște mai bine algoritmul lacom.