Data kan komprimeres ved hjælp af Huffman Coding-teknikken for at blive mindre uden at miste nogen af ​​dens information. Efter David Huffman, hvem skabte det i begyndelsen? Data, der indeholder hyppigt gentagne tegn, komprimeres typisk ved hjælp af Huffman-kodning.

En velkendt Greedy algoritme er Huffman Coding. Størrelsen af ​​den kode, der er allokeret til et tegn, afhænger af karakterens frekvens, hvorfor det omtales som en grådig algoritme. Den korte længde variable kode tildeles tegnet med den højeste frekvens og omvendt for tegn med lavere frekvenser. Den anvender en kodning med variabel længde, hvilket betyder, at den giver hvert tegn i den leverede datastrøm en forskellig kode med variabel længde.

Præfiksregel

Grundlæggende siger denne regel, at den kode, der er allokeret til et tegn, ikke skal være en anden kodes præfiks. Hvis denne regel brydes, kan der forekomme forskellige tvetydigheder ved afkodning af det Huffman-træ, der er blevet oprettet.

Lad os se på en illustration af denne regel for bedre at forstå den: For hvert tegn er der angivet en kode, såsom:

 a - 0 b - 1 c - 01 

Hvis det antages, at den producerede bitstrøm er 001, kan koden udtrykkes som følger, når den er afkodet:

 0 0 1 = aab 0 01 = ac 

Hvad er Huffman-kodningsprocessen?

Huffman-koden opnås for hver særskilt karakter i primært to trin:

• Opret først et Huffman-træ ved kun at bruge de unikke tegn i den angivne datastrøm.
• For det andet skal vi fortsætte gennem det konstruerede Huffman Tree, tildele koder til tegnene og derefter bruge disse koder til at afkode den medfølgende tekst.

Trin til at tage i Huffman Coding

De trin, der bruges til at konstruere Huffman-træet ved hjælp af de medfølgende tegn

bash hvis andet

 Input: string str = 'abbcdbccdaabbeeebeab' 

Hvis Huffman Coding i dette tilfælde anvendes til datakomprimering, skal følgende information bestemmes til afkodning:

• For hver karakter, Huffman-koden
• Huffman-kodet beskedlængde (i bits), gennemsnitlig kodelængde
• Ved at bruge formlerne nedenfor, bliver de sidste to af dem opdaget.

Hvordan kan et Huffman-træ konstrueres ud fra inputtegn?

Hyppigheden af ​​hvert tegn i den medfølgende streng skal først bestemmes.

1. Sorter tegnene efter frekvens, stigende. Disse opbevares i en Q/min-heap-prioritetskø.
2. For hver enkelt karakter og dens frekvens i datastrømmen skal du oprette en bladknude.
3. Fjern de to noder med de to laveste frekvenser fra noderne, og træets nye rod skabes ved hjælp af summen af ​​disse frekvenser.
   • Gør den første ekstraherede knude til dets venstre underordnede og den anden ekstraherede knude til dets højre underordnede, mens knudepunkterne med den laveste frekvens udtages fra min-heapen.
   • Tilføj denne node til min-heapen.
   • Da venstre side af roden altid skal indeholde minimumsfrekvensen.
4. Gentag trin 3 og 4, indtil der kun er én node tilbage på heapen, eller alle tegn er repræsenteret af noder i træet. Træet er færdigt, når kun rodknuden er tilbage.

Eksempler på Huffman-kodning

Lad os bruge en illustration til at forklare algoritmen:

Algoritme til Huffman-kodning

Trin 1: Byg en min-heap, hvor hver node repræsenterer roden af ​​et træ med en enkelt node og rummer 5 (antallet af unikke tegn fra den leverede datastrøm).

romertal 1-100

Trin 2: Få to minimumsfrekvensknuder fra min-heapen i trin to. Tilføj en tredje intern node, frekvens 2 + 3 = 5, som skabes ved at forbinde de to udtrukne noder.

• Nu er der 4 noder i min-heapen, hvoraf 3 er rødderne af træer med et enkelt element hver, og 1 af dem er roden af ​​et træ med to elementer.

Trin 3: Få de to minimumsfrekvensknuder fra heapen på lignende måde i trin tre. Tilføj desuden en ny intern node dannet ved at forbinde de to ekstraherede noder; dens frekvens i træet skal være 4 + 4 = 8.

• Nu hvor minimumsbunken har tre knudepunkter, fungerer en knude som roden af ​​træer med et enkelt element, og to bunker fungerer som roden af ​​træer med flere knudepunkter.

Trin 4: Få de to minimumsfrekvensknuder i trin fire. Tilføj desuden en ny intern node dannet ved at forbinde de to ekstraherede noder; dens frekvens i træet skal være 5 + 7 = 12.

• Når vi opretter et Huffman-træ, skal vi sikre, at minimumsværdien altid er på venstre side, og at den anden værdi altid er på højre side. I øjeblikket viser billedet nedenfor det træ, der er dannet:

Trin 5: Hent følgende to minimumsfrekvensknuder i trin 5. Tilføj desuden en ny intern knude dannet ved at forbinde de to udtrukne knudepunkter; dens frekvens i træet skal være 12 + 8 = 20.

Fortsæt, indtil alle de distinkte tegn er blevet tilføjet til træet. Huffman-træet, der er oprettet til den angivne rollebesætning, er vist på billedet ovenfor.

For hver ikke-bladsknude skal du nu tildele 0 til venstre kant og 1 til højre kant for at oprette koden for hvert bogstav.

Regler, der skal følges for at bestemme kantvægte:

• Vi skal give højre kanter vægt 1, hvis du giver venstre kanter vægt 0.
• Hvis venstre kanter vægtes 1, skal højre kanter vægtes 0.
• Enhver af de to førnævnte konventioner kan bruges.
• Følg dog den samme protokol, når du også afkoder træet.

Efter vægtningen vises det ændrede træ som følger:

Forståelse af koden

• Vi skal gå gennem Huffman-træet, indtil vi når bladknuden, hvor elementet er til stede, for at afkode Huffman-koden for hver karakter fra det resulterende Huffman-træ.
• Vægtene på tværs af knudepunkterne skal registreres under traversering og tildeles de emner, der er placeret ved den specifikke bladknude.
• Følgende eksempel vil hjælpe til yderligere at illustrere, hvad vi mener:
• For at få koden for hvert tegn på billedet ovenfor, skal vi gå hele træet (indtil alle bladknuder er dækket).
• Som et resultat bliver træet, der er blevet oprettet, brugt til at afkode koderne for hver node. Nedenfor er en liste over koderne for hvert tegn:

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; } 

Produktion

 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 af ovenstående kode:

 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;>

Produktion

 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 at krydse skabes og afkodes Huffman-træet. Værdierne indsamlet under gennemkørslen skal derefter anvendes på tegnet placeret ved bladknuden. Hvert unikt tegn i den leverede datastrøm kan identificeres ved hjælp af Huffman-koden på denne måde. O (nlogn), hvor n er det samlede antal tegn, er tidskompleksiteten. ExtractMin() kaldes 2*(n - 1) gange, hvis der er n noder. Da extractMin() kalder minHeapify(), er dens udførelsestid O (logn). Den samlede kompleksitet er derfor O (nlogn). Der er en lineær tidsalgoritme, hvis input-arrayet er sorteret. Dette vil blive dækket mere detaljeret i vores kommende stykke.

Problemer med Huffman-kodning

Lad os tale om ulemperne ved Huffman-kodning i denne del, og hvorfor det ikke altid er den bedste mulighed:

hashbar java

• Hvis ikke alle karakterernes sandsynligheder eller frekvenser er negative potenser på 2, betragtes det ikke som ideelt.
• Selvom man kan komme tættere på idealet ved at gruppere symboler og udvide alfabetet, kræver blokeringsmetoden håndtering af et større alfabet. Derfor er Huffman-kodning måske ikke altid særlig effektiv.
• Selvom der er mange effektive måder at tælle frekvensen af ​​hvert symbol eller tegn på, kan det være meget tidskrævende at rekonstruere hele træet for hver enkelt. Når alfabetet er stort, og sandsynlighedsfordelingerne ændrer sig hurtigt for hvert symbol, er dette typisk tilfældet.

Greedy Huffman Code Construction Algoritme

• Huffman udviklede en grådig teknik, der genererer en Huffman-kode, en ideel præfikskode, for hvert særskilt tegn i inputdatastrømmen.
• Fremgangsmåden bruger de færreste noder hver gang til at skabe Huffman-træet fra bunden og op.
• Fordi hvert tegn modtager en længde på kode baseret på, hvor ofte det vises i den givne datastrøm, er denne metode kendt som en grådig tilgang. Det er et almindeligt forekommende element i dataene, hvis størrelsen af ​​den hentede kode er mindre.

Brugen af ​​Huffman Coding

• Her vil vi tale om nogle praktiske anvendelser af Huffman Coding:
• Konventionelle komprimeringsformater som PKZIP, GZIP osv. anvender typisk Huffman-kodning.
• Huffman Coding bruges til dataoverførsel via fax og tekst, fordi det minimerer filstørrelsen og øger transmissionshastigheden.
• Huffman-kodning (især præfikskoderne) bruges af flere multimedielagerformater, herunder JPEG, PNG og MP3, til at komprimere filerne.
• Huffman Coding bruges mest til billedkomprimering.
• Når en streng af ofte tilbagevendende tegn skal sendes, kan det være mere nyttigt.

Konklusion

• Generelt er Huffman Coding nyttig til at komprimere data, der indeholder hyppigt forekommende tegn.
• Vi kan se, at det tegn, der forekommer hyppigst, har den korteste kode, hvorimod det, der forekommer mindst hyppigt, har den største kode.
• Huffman Code komprimeringsteknikken bruges til at skabe variabel længde kodning, som bruger en varieret mængde bits for hvert bogstav eller symbol. Denne metode er bedre end kodning med fast længde, da den bruger mindre hukommelse og transmitterer data hurtigere.
• Gå gennem denne artikel for at få et bedre kendskab til den grådige algoritme.