Data kan komprimeres ved hjelp av Huffman Coding-teknikken for å bli mindre uten å miste noe av informasjonen. Etter David Huffman, hvem skapte den i begynnelsen? Data som inneholder ofte gjentatte tegn komprimeres vanligvis ved hjelp av Huffman-koding.
En velkjent Greedy-algoritme er Huffman Coding. Størrelsen på koden som er allokert til et tegn er avhengig av frekvensen til tegnet, og det er derfor det omtales som en grådig algoritme. Den korte lengdevariabelkoden tilordnes tegnet med høyest frekvens, og omvendt for tegn med lavere frekvenser. Den bruker en koding med variabel lengde, noe som betyr at den gir hvert tegn i den angitte datastrømmen en annen kode med variabel lengde.
Prefiksregel
I hovedsak sier denne regelen at koden som er allokert til et tegn ikke skal være en annen kodes prefiks. Hvis denne regelen brytes, kan det oppstå ulike tvetydigheter ved dekoding av Huffman-treet som er opprettet.
La oss se på en illustrasjon av denne regelen for bedre å forstå den: For hvert tegn er det gitt en kode, for eksempel:
a - 0 b - 1 c - 01
Forutsatt at den produserte bitstrømmen er 001, kan koden uttrykkes som følger når den dekodes:
0 0 1 = aab 0 01 = ac
Hva er Huffman-kodingsprosessen?
Huffman-koden oppnås for hver distinkte karakter i primært to trinn:
- Opprett et Huffman-tre først ved å bruke bare de unike tegnene i datastrømmen som følger med.
- For det andre må vi gå gjennom det konstruerte Huffman-treet, tilordne koder til tegnene og deretter bruke disse kodene til å dekode den oppgitte teksten.
Trinn å ta i Huffman Coding
Trinnene som brukes til å konstruere Huffman-treet ved å bruke tegnene som følger med
natasha dalal
Input: string str = 'abbcdbccdaabbeeebeab'
Hvis Huffman Coding brukes i dette tilfellet for datakomprimering, må følgende informasjon bestemmes for dekoding:
- For hver karakter, Huffman-koden
- Huffman-kodet meldingslengde (i biter), gjennomsnittlig kodelengde
- Ved å bruke formlene nedenfor, blir de to siste av dem oppdaget.
Hvordan kan et Huffman-tre konstrueres fra inndatakarakterer?
Frekvensen av hvert tegn i den angitte strengen må først bestemmes.
| Karakter | Frekvens |
|---|---|
| en | 4 |
| b | 7 |
| c | 3 |
| d | 2 |
| Det er | 4 |
- Sorter tegnene etter frekvens, stigende. Disse holdes i en Q/min-heap-prioritetskø.
- For hvert distinkte tegn og dets frekvens i datastrømmen, lag en bladnode.
- Fjern de to nodene med de to laveste frekvensene fra nodene, og den nye roten til treet lages ved å bruke summen av disse frekvensene.
- Gjør den første ekstraherte noden til venstre barn og den andre ekstraherte noden til høyre barn mens du trekker ut nodene med lavest frekvens fra min-heapen.
- Legg til denne noden i min-haugen.
- Siden venstre side av roten alltid skal inneholde minimumsfrekvensen.
- Gjenta trinn 3 og 4 til det bare er én node igjen på haugen, eller alle tegnene er representert av noder i treet. Treet er ferdig når bare rotnoden gjenstår.
Eksempler på Huffman-koding
La oss bruke en illustrasjon for å forklare algoritmen:
Algoritme for Huffman-koding
Trinn 1: Bygg en min-heap der hver node representerer roten til et tre med en enkelt node og inneholder 5 (antall unike tegn fra den oppgitte datastrømmen).
rajesh khanna
Steg 2: Skaff to minimumsfrekvensnoder fra min-haugen i trinn to. Legg til en tredje intern node, frekvens 2 + 3 = 5, som opprettes ved å slå sammen de to ekstraherte nodene.
- Nå er det 4 noder i min-haugen, hvorav 3 er røttene til trær med et enkelt element hver, og 1 av disse er roten til et tre med to elementer.
Trinn 3: Få de to minimumsfrekvensnodene fra haugen på lignende måte i trinn tre. I tillegg, legg til en ny intern node dannet ved å slå sammen de to ekstraherte nodene; frekvensen i treet skal være 4 + 4 = 8.
- Nå som minimumshaugen har tre noder, fungerer en node som roten til trær med et enkelt element og to haugnoder fungerer som roten til trær med flere noder.
Trinn 4: Få de to minimumsfrekvensnodene i trinn fire. I tillegg, legg til en ny intern node dannet ved å slå sammen de to ekstraherte nodene; frekvensen i treet skal være 5 + 7 = 12.
- Når vi oppretter et Huffman-tre, må vi sørge for at minimumsverdien alltid er på venstre side og at den andre verdien alltid er på høyre side. For øyeblikket viser bildet nedenfor treet som har dannet seg:
Trinn 5: Få følgende to minimumsfrekvensnoder i trinn 5. Legg i tillegg til en ny intern node dannet ved å slå sammen de to ekstraherte nodene; frekvensen i treet skal være 12 + 8 = 20.
Fortsett til alle de distinkte tegnene er lagt til treet. Huffman-treet laget for den angitte rollebesetningen vises i bildet ovenfor.
Nå, for hver ikke-bladnode, tilordne 0 til venstre kant og 1 til høyre kant for å lage koden for hver bokstav.
Regler som skal følges for å bestemme kantvekter:
- Vi bør gi høyrekantene vekt 1 hvis du gir venstrekantene vekt 0.
- Hvis venstrekantene tillegges vekt 1, må høyrekantene vektes 0.
- Enhver av de to nevnte konvensjonene kan brukes.
- Følg imidlertid samme protokoll når du dekoder treet også.
Etter vektingen vises det modifiserte treet som følger:
Forstå koden
- Vi må gå gjennom Huffman-treet til vi kommer til bladnoden, der elementet er til stede, for å dekode Huffman-koden for hver karakter fra det resulterende Huffman-treet.
- Vektene på tvers av nodene må registreres under traversering og allokeres til elementene som befinner seg ved den spesifikke bladnoden.
- Følgende eksempel vil bidra til å illustrere hva vi mener:
- For å få koden for hvert tegn i bildet ovenfor, må vi gå hele treet (til alle bladnoder er dekket).
- Som et resultat blir treet som er opprettet brukt til å dekode kodene for hver node. Nedenfor er en liste over kodene for hvert tegn:
| Karakter | Frekvens/telling | Kode |
|---|---|---|
| en | 4 | 01 |
| b | 7 | elleve |
| c | 3 | 101 |
| d | 2 | 100 |
| Det er | 4 | 00 |
Nedenfor er implementering i C-programmering:
// 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; } Produksjon
f: 0 c: 100 d: 101 a: 1100 b: 1101 e: 111 …………… Process executed in 1.11 seconds Press any key to continue.
Java-implementering av koden ovenfor:
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;> Produksjon
f: 0 c: 100 d: 101 a: 1100 b: 1101 e: 111 ………………. Process executed in 1.11 seconds Press any key to continue.
Forklaring:
Ved å krysse, blir Huffman-treet opprettet og dekodet. Verdiene samlet under gjennomgangen skal deretter brukes på tegnet som ligger ved bladnoden. Hvert unike tegn i den leverte datastrømmen kan identifiseres ved hjelp av Huffman-koden på denne måten. O (nlogn), hvor n er det totale antallet tegn, er tidskompleksiteten. ExtractMin() kalles 2*(n - 1) ganger hvis det er n noder. Siden extractMin() kaller minHeapify(), er utføringstiden O (logn). Den totale kompleksiteten er derfor O (nlogn). Det er en lineær tidsalgoritme hvis inngangsmatrisen er sortert. Dette vil bli dekket mer detaljert i vårt kommende stykke.
Problemer med Huffman-koding
La oss snakke om ulempene med Huffman-koding i denne delen og hvorfor det ikke alltid er det beste alternativet:
hashbar java
- Hvis ikke alle karakterenes sannsynligheter eller frekvenser er negative potenser på 2, blir det ikke sett på som ideelt.
- Selv om man kan komme nærmere idealet ved å gruppere symboler og utvide alfabetet, krever blokkeringsmetoden å håndtere et større alfabet. Derfor kan det hende at Huffman-koding ikke alltid er veldig effektivt.
- Selv om det er mange effektive måter å telle frekvensen til hvert symbol eller tegn på, kan det være svært tidkrevende å rekonstruere hele treet for hver enkelt. Når alfabetet er stort og sannsynlighetsfordelingene endres raskt med hvert symbol, er dette typisk tilfelle.
Grådig Huffman-kodekonstruksjonsalgoritme
- Huffman utviklet en grådig teknikk som genererer en Huffman-kode, en ideell prefikskode, for hvert distinkte tegn i inndatastrømmen.
- Tilnærmingen bruker færrest noder hver gang for å lage Huffman-treet fra bunnen og opp.
- Fordi hvert tegn mottar en kodelengde basert på hvor ofte den vises i den gitte datastrømmen, er denne metoden kjent som en grådig tilnærming. Det er et ofte forekommende element i dataene hvis størrelsen på koden som hentes er mindre.
Bruken av Huffman Coding
- Her skal vi snakke om noen praktiske bruksområder for Huffman Coding:
- Konvensjonelle komprimeringsformater som PKZIP, GZIP osv. bruker vanligvis Huffman-koding.
- Huffman Coding brukes til dataoverføring via faks og tekst fordi den minimerer filstørrelsen og øker overføringshastigheten.
- Huffman-koding (spesielt prefikskodene) brukes av flere multimedielagringsformater, inkludert JPEG, PNG og MP3, for å komprimere filene.
- Huffman Coding brukes mest for bildekomprimering.
- Når en streng med ofte tilbakevendende tegn må sendes, kan det være mer nyttig.
Konklusjon
- Generelt er Huffman Coding nyttig for å komprimere data som inneholder ofte forekommende tegn.
- Vi kan se at tegnet som forekommer hyppigst har den korteste koden, mens det som forekommer minst ofte har den største koden.
- Huffman Code-komprimeringsteknikken brukes til å lage koding med variabel lengde, som bruker en variert mengde biter for hver bokstav eller symbol. Denne metoden er overlegen koding med fast lengde siden den bruker mindre minne og overfører data raskere.
- Gå gjennom denne artikkelen for å få bedre kunnskap om den grådige algoritmen.