Die Huffman-Codierung ist ein verlustfreier Datenkomprimierungsalgorithmus. Die Idee besteht darin, Eingabezeichen Codes variabler Länge zuzuweisen, wobei die Länge der zugewiesenen Codes auf der Häufigkeit der entsprechenden Zeichen basiert.
Die den Eingabezeichen zugewiesenen Codes variabler Länge sind Präfixcodes bedeutet, dass die Codes (Bitsequenzen) so zugewiesen werden, dass der einem Zeichen zugewiesene Code nicht das Präfix eines Codes ist, der einem anderen Zeichen zugewiesen ist. Auf diese Weise stellt Huffman Coding sicher, dass es beim Dekodieren des generierten Bitstroms keine Mehrdeutigkeiten gibt.
Lassen Sie uns Präfixcodes anhand eines Gegenbeispiels verstehen. Angenommen, es gäbe vier Zeichen a, b, c und d und ihre entsprechenden Codes variabler Länge seien 00, 01, 0 und 1. Diese Codierung führt zu Mehrdeutigkeiten, da der c zugewiesene Code das Präfix der a und b zugewiesenen Codes ist. Wenn der komprimierte Bitstrom 0001 ist, kann die dekomprimierte Ausgabe cccd oder ccb oder acd oder ab sein.
Sehen Das für Anwendungen der Huffman-Codierung.
Die Huffman-Codierung besteht hauptsächlich aus zwei Hauptteilen
- Erstellen Sie einen Huffman-Baum aus eingegebenen Zeichen.
- Durchqueren Sie den Huffman-Baum und weisen Sie Charakteren Codes zu.
Algorithmus:
Die Methode, die zum Erstellen des optimalen Präfixcodes verwendet wird, wird aufgerufen Huffman-Codierung .
Dieser Algorithmus erstellt einen Baum von unten nach oben. Wir können diesen Baum mit bezeichnen T
Sei |c| sei die Anzahl der Blätter
|c| -1 ist die Anzahl der Operationen, die zum Zusammenführen der Knoten erforderlich sind. Q sei die Prioritätswarteschlange, die beim Aufbau des binären Heaps verwendet werden kann.
Algorithm Huffman (c) { n= |c| Q = c for i<-1 to n-1 do { temp <- get node () left (temp] Get_min (Q) right [temp] Get Min (Q) a = left [templ b = right [temp] F [temp]<- f[a] + [b] insert (Q, temp) } return Get_min (0) }> Schritte zum Aufbau des Huffman-Baums
Die Eingabe ist ein Array eindeutiger Zeichen zusammen mit der Häufigkeit ihres Auftretens und die Ausgabe ist ein Huffman-Baum.
- Erstellen Sie einen Blattknoten für jedes eindeutige Zeichen und erstellen Sie einen minimalen Heap aller Blattknoten (Min. Heap wird als Prioritätswarteschlange verwendet. Der Wert des Häufigkeitsfelds wird verwendet, um zwei Knoten im minimalen Heap zu vergleichen. Anfänglich ist das am wenigsten häufige Zeichen bei Wurzel)
- Extrahieren Sie zwei Knoten mit der minimalen Häufigkeit aus dem Min-Heap.
- Erstellen Sie einen neuen internen Knoten mit einer Frequenz, die der Summe der Frequenzen der beiden Knoten entspricht. Machen Sie den ersten extrahierten Knoten zu seinem linken untergeordneten Knoten und den anderen extrahierten Knoten zu seinem rechten untergeordneten Knoten. Fügen Sie diesen Knoten zum Min-Heap hinzu.
- Wiederholen Sie die Schritte Nr. 2 und Nr. 3, bis der Heap nur noch einen Knoten enthält. Der verbleibende Knoten ist der Wurzelknoten und der Baum ist vollständig.
Lassen Sie uns den Algorithmus anhand eines Beispiels verstehen:
character Frequency a 5 b 9 c 12 d 13 e 16 f 45>
Schritt 1. Erstellen Sie einen minimalen Heap, der 6 Knoten enthält, wobei jeder Knoten die Wurzel eines Baums mit einem einzelnen Knoten darstellt.
Schritt 2 Extrahieren Sie zwei Knoten mit minimaler Häufigkeit aus dem Min-Heap. Fügen Sie einen neuen internen Knoten mit der Häufigkeit 5 + 9 = 14 hinzu.
Illustration von Schritt 2
Jetzt enthält der minimale Heap 5 Knoten, wobei 4 Knoten Wurzeln von Bäumen mit jeweils einem einzelnen Element sind und ein Heap-Knoten die Wurzel eines Baums mit 3 Elementen ist
character Frequency c 12 d 13 Internal Node 14 e 16 f 45>
Schritt 3: Extrahieren Sie zwei Knoten mit minimaler Häufigkeit aus dem Heap. Fügen Sie einen neuen internen Knoten mit der Häufigkeit 12 + 13 = 25 hinzu
Illustration von Schritt 3
Jetzt enthält der minimale Heap 4 Knoten, wobei 2 Knoten Wurzeln von Bäumen mit jeweils einem einzelnen Element sind und zwei Heap-Knoten Wurzeln von Bäumen mit mehr als einem Knoten sind
character Frequency Internal Node 14 e 16 Internal Node 25 f 45>
Schritt 4: Extrahieren Sie zwei Knoten mit minimaler Häufigkeit. Fügen Sie einen neuen internen Knoten mit der Häufigkeit 14 + 16 = 30 hinzu
Illustration von Schritt 4
Jetzt enthält der minimale Heap 3 Knoten.
c++ konvertiert int in einen String
character Frequency Internal Node 25 Internal Node 30 f 45>
Schritt 5: Extrahieren Sie zwei Knoten mit minimaler Häufigkeit. Fügen Sie einen neuen internen Knoten mit der Häufigkeit 25 + 30 = 55 hinzu
Illustration von Schritt 5
Jetzt enthält der minimale Heap 2 Knoten.
character Frequency f 45 Internal Node 55>
Schritt 6: Extrahieren Sie zwei Knoten mit minimaler Häufigkeit. Fügen Sie einen neuen internen Knoten mit der Häufigkeit 45 + 55 = 100 hinzu
Abbildung von Schritt 6
Jetzt enthält der Min-Heap nur einen Knoten.
character Frequency Internal Node 100>
Da der Heap nur einen Knoten enthält, stoppt der Algorithmus hier.
Schritte zum Drucken von Codes aus Huffman Tree:
Durchqueren Sie den entstandenen Baum ausgehend von der Wurzel. Pflegen Sie ein Hilfsarray. Schreiben Sie beim Bewegen zum linken untergeordneten Element 0 in das Array. Während Sie zum rechten untergeordneten Element wechseln, schreiben Sie 1 in das Array. Drucken Sie das Array, wenn ein Blattknoten gefunden wird.
Schritte zum Drucken von Code aus HuffmanTree
Die Codes lauten wie folgt:
character code-word f 0 c 100 d 101 a 1100 b 1101 e 111>Empfohlene Übung zur Huffman-Kodierung Probieren Sie es aus!
Nachfolgend finden Sie die Umsetzung des oben genannten Ansatzes:
C
Java-Mathe
// 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->links = temp->rechts = NULL;> >temp->Daten = Daten;> >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->Größe = 0;> > >minHeap->Kapazität = Kapazität;> > >minHeap->array = (>struct> MinHeapNode**)>malloc>(> >minHeap->Kapazität *>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[kleinste],> >&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->Größe == 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->Größe;> >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->Größe;> >int> i = minHeap->Größe - 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->Größe - 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 printf('%d', arr[i]); printf('
'); } // Utility function to check if this node is leaf int isLeaf(struct MinHeapNode* root) { return !(root->links) && !(root->right); } // Erstellt einen minimalen Heap mit Kapazität // gleich der Größe und fügt alle Zeichen von // data[] in den minimalen Heap ein. Anfänglich ist die Größe // des minimalen Heaps gleich der Kapazität struct MinHeap* createAndBuildMinHeap(char data[], int freq[], int size) { struct MinHeap* minHeap = createMinHeap(size); for (int i = 0; i minHeap->array[i] = newNode(data[i], freq[i]); minHeap->size = size; buildMinHeap(minHeap); return minHeap; } // Die Hauptfunktion das erstellt den Huffman-Baum struct MinHeapNode* buildHuffmanTree(char data[], int freq[], int size) { struct MinHeapNode *left, *right, *top; // Schritt 1: Erstellen Sie einen minimalen Heap mit Kapazität // gleich der Größe . Anfänglich gibt es // Modi, die der Größe entsprechen. struct MinHeap* minHeap = createAndBuildMinHeap(data, freq, size); Schritt 2: Extrahieren Sie die beiden minimalen // Häufigkeitselemente aus dem Min-Heap. left = extractMin(minHeap); right = extractMin(minHeap); // Die beiden extrahierten Knoten // als linke und rechte Kinder dieses neuen Knotens // hinzufügen. // '$' ist ein spezieller Wert für interne Knoten, nicht //. used top = newNode('$', left->freq + right->freq); oben->links = links; oben->rechts = rechts; insertMinHeap(minHeap, top); } // Schritt 4: Der verbleibende Knoten ist der // Wurzelknoten und der Baum ist vollständig. return extractMin(minHeap); } // Druckt Huffman-Codes aus der Wurzel des Huffman-Baums. // Es verwendet arr[], um Codes zu speichern. void printCodes(struct MinHeapNode* root, int arr[], int top) { // Weisen Sie dem linken Rand 0 zu und wiederholen Sie den Vorgang, wenn (root->left) { arr[top] = 0 ; printCodes(root->left, arr, top + 1); } // Dem rechten Rand 1 zuweisen und wiederholen if (root->right) { arr[top] = 1; printCodes(root->right, arr, top + 1); } // Wenn dies ein Blattknoten ist, // enthält er eines der Eingabezeichen //, drucken Sie das Zeichen // und seinen Code aus arr[] if (isLeaf(root)) { printf('%c: ', root->data); printArr(arr, top); } } // Die Hauptfunktion, die einen // Huffman-Baum erstellt und Codes durch Durchlaufen // des erstellten Huffman-Baums erstellt void HuffmanCodes(char data[], int freq[], int size) { // Huffman Tree struct MinHeapNode* erstellen root = buildHuffmanTree(data, freq, size); // Huffman-Codes mit // dem oben erstellten Huffman-Baum drucken int arr[MAX_TREE_HT], top = 0; printCodes(root, arr, top); } // Treibercode 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); 0 zurückgeben; }> |
>
>
C++
// C++ program for Huffman Coding> #include> #include> using> namespace> std;> > // 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->links = temp->rechts = NULL;> >temp->Daten = Daten;> >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->Größe = 0;> > >minHeap->Kapazität = Kapazität;> > >minHeap->array = (>struct> MinHeapNode**)>malloc>(> >minHeap->Kapazität *>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[kleinste],> >&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->Größe == 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->Größe;> >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->Größe;> >int> i = minHeap->Größe - 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->Größe - 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 cout << arr[i]; cout << '
'; } // Utility function to check if this node is leaf int isLeaf(struct MinHeapNode* root) { return !(root->links) && !(root->right); } // Erstellt einen minimalen Heap mit Kapazität // gleich der Größe und fügt alle Zeichen von // data[] in den minimalen Heap ein. Anfänglich ist die Größe // des minimalen Heaps gleich der Kapazität struct MinHeap* createAndBuildMinHeap(char data[], int freq[], int size) { struct MinHeap* minHeap = createMinHeap(size); for (int i = 0; i minHeap->array[i] = newNode(data[i], freq[i]); minHeap->size = size; buildMinHeap(minHeap); return minHeap; } // Die Hauptfunktion das erstellt den Huffman-Baum struct MinHeapNode* buildHuffmanTree(char data[], int freq[], int size) { struct MinHeapNode *left, *right, *top; // Schritt 1: Erstellen Sie einen minimalen Heap mit Kapazität // gleich der Größe . Anfänglich gibt es // Modi, die der Größe entsprechen. struct MinHeap* minHeap = createAndBuildMinHeap(data, freq, size); Schritt 2: Extrahieren Sie die beiden minimalen // Häufigkeitselemente aus dem Min-Heap. left = extractMin(minHeap); right = extractMin(minHeap); // Die beiden extrahierten Knoten // als linke und rechte Kinder dieses neuen Knotens // hinzufügen. // '$' ist ein spezieller Wert für interne Knoten, nicht //. used top = newNode('$', left->freq + right->freq); oben->links = links; oben->rechts = rechts; insertMinHeap(minHeap, top); } // Schritt 4: Der verbleibende Knoten ist der // Wurzelknoten und der Baum ist vollständig. return extractMin(minHeap); } // Druckt Huffman-Codes aus der Wurzel des Huffman-Baums. // Es verwendet arr[], um Codes zu speichern void printCodes(struct MinHeapNode* root, int arr[], int top) { // Weisen Sie dem linken Rand 0 zu und wiederholen Sie den Vorgang, wenn (root->left) { arr[top] = 0 ; printCodes(root->left, arr, top + 1); } // Dem rechten Rand 1 zuweisen und wiederholen if (root->right) { arr[top] = 1; printCodes(root->right, arr, top + 1); } // Wenn dies ein Blattknoten ist, // enthält er eines der Eingabezeichen //, drucke das Zeichen // und seinen Code aus arr[] if (isLeaf(root)) { cout ': '; printArr(arr, top); } } // Die Hauptfunktion, die einen // Huffman-Baum erstellt und Codes durch Durchlaufen // des erstellten Huffman-Baums erstellt void HuffmanCodes(char data[], int freq[], int size) { // Huffman-Baumstruktur erstellen MinHeapNode* root = buildHuffmanTree(data, freq, size); // Huffman-Codes mit // dem oben erstellten Huffman-Baum drucken int arr[MAX_TREE_HT], top = 0; printCodes(root, arr, top); } // Treibercode 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); 0 zurückgeben; }> |
>
>
C++
// C++(STL) program for Huffman Coding with STL> #include> using> namespace> std;> > // A Huffman tree node> struct> MinHeapNode {> > >// One of the input characters> >char> data;> > >// Frequency of the character> >unsigned freq;> > >// Left and right child> >MinHeapNode *left, *right;> > >MinHeapNode(>char> data, unsigned freq)> > >{> > >left = right = NULL;> >this>->Daten = Daten;> >this>->freq = freq;> >}> };> > // For comparison of> // two heap nodes (needed in min heap)> struct> compare {> > >bool> operator()(MinHeapNode* l, MinHeapNode* r)> > >{> >return> (l->freq> r->freq);> >}> };> > // Prints huffman codes from> // the root of Huffman Tree.> void> printCodes(>struct> MinHeapNode* root, string str)> {> > >if> (!root)> >return>;> > >if> (root->Daten !=>'$'>)> >cout ': ' << str << '
'; printCodes(root->links, str + '0'); printCodes(root->right, str + '1'); } // Die Hauptfunktion, die einen Huffman-Baum erstellt und // Codes ausgibt, indem sie den erstellten Huffman-Baum durchläuft void HuffmanCodes(char data[], int freq[], int size) { struct MinHeapNode *left, *right, *top; // Einen Min-Heap erstellen und alle Zeichen von data[] einfügen. Priority_queue Compare> MinHeap; for (int i = 0; i minHeap.push(new MinHeapNode(data[i], freq[i])); // Iterieren, während die Größe des Heaps nicht 1 wird, während (minHeap.size() != 1 ) { // Extrahieren Sie die beiden minimalen // Freq-Elemente left = minHeap.top(); right = minHeap.pop(); mit // Häufigkeit gleich der Summe der // beiden Knotenhäufigkeiten // Machen Sie die beiden extrahierten Knoten // zu linken und rechten Kindern dieses neuen Knotens ein spezieller Wert // für interne Knoten, nicht verwendet top = new MinHeapNode('$', left->freq + right->freq); (top); } // Huffman-Codes drucken mit // dem oben erstellten Huffman-Baum printCodes(minHeap.top(), '' } // Treibercode int main() { char arr[] = { ' a', 'b', 'c', 'd', 'e', 'f' }; , 45 }; int size = sizeof(arr) / sizeof(arr[0]); 0 zurückgeben; } // Dieser Code wurde von Aditya Goel beigesteuert> |
>
>
Java
Autocad-Stretch-Befehl
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 // 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; // add functions adds // the huffman node to the queue. q.add(hn); } // create a root node HuffmanNode root = null; // Here we will extract the two minimum value // from the heap each time until // its size reduces to 1, extract until // all the nodes are extracted. while (q.size()>1) { // erster Min.-Extrakt. HuffmanNode x = q.peek(); q.poll(); // Sekunden-Minuten-Extrakt. HuffmanNode y = q.peek(); q.poll(); // neuer Knoten f, der gleich ist HuffmanNode f = new HuffmanNode(); // zur Summe der Häufigkeit der beiden Knoten // Zuweisen von Werten zum f-Knoten. f.data = x.data + y.data; f.c = '-'; // Erster extrahierter Knoten als linkes Kind. f.left = x; // zweiter extrahierter Knoten als rechtes Kind. f.right = y; // Markieren des f-Knotens als Wurzelknoten. Wurzel = f; // diesen Knoten zur Prioritätswarteschlange hinzufügen. q.add(f); } // Drucke die Codes aus, indem du den Baum durchquerst printCode(root, ''); } } // Die Knotenklasse ist die Grundstruktur // jedes im Huffman-Baum vorhandenen Knotens. Klasse HuffmanNode { int data; char c; HuffmanNode links; HuffmanNode rechts; } // Die Komparatorklasse hilft, den Knoten // anhand eines seiner Attribute zu vergleichen. // Hier werden wir anhand der Datenwerte der Knoten // verglichen. Klasse MyComparator implementiert Comparator { public int Compare(HuffmanNode x, HuffmanNode y) { return x.data - y.data; } } // Dieser Code wurde von Kunwar Desh Deepak Singh beigesteuert> |
>
>
Python3
# A Huffman Tree Node> import> heapq> > > class> node:> >def> __init__(>self>, freq, symbol, left>=>None>, right>=>None>):> ># frequency of symbol> >self>.freq>=> freq> > ># symbol name (character)> >self>.symbol>=> symbol> > ># node left of current node> >self>.left>=> left> > ># node right of current node> >self>.right>=> right> > ># tree direction (0/1)> >self>.huff>=> ''> > >def> __lt__(>self>, nxt):> >return> self>.freq # utility function to print huffman # codes for all symbols in the newly # created Huffman tree def printNodes(node, val=''): # huffman code for current node newVal = val + str(node.huff) # if node is not an edge node # then traverse inside it if(node.left): printNodes(node.left, newVal) if(node.right): printNodes(node.right, newVal) # if node is edge node then # display its huffman code if(not node.left and not node.right): print(f'{node.symbol} ->{newVal}') # Zeichen für Huffman-Baum chars = ['a', 'b', 'c', 'd', 'e', 'f'] # Häufigkeit der Zeichen freq = [5, 9, 12, 13, 16, 45] # Liste mit nicht verwendeten Knoten nodes = [] # Konvertieren von Zeichen und Häufigkeiten # in Huffman-Baum-Knoten für x in range(len(chars)): heapq .heappush(nodes, node(freq[x], chars[x])) while len(nodes)> 1: # alle Knoten in aufsteigender Reihenfolge sortieren # basierend auf ihrer Häufigkeit left = heapq.heappop(nodes) right = heapq .heappop(nodes) # weist diesen Knoten einen Richtungswert zu left.huff = 0 right.huff = 1 # kombiniere die 2 kleinsten Knoten, um # neuen Knoten als ihren übergeordneten Knoten zu erstellen newNode = node(left.freq+right.freq, left. symbol+right.symbol, left, right) heapq.heappush(nodes, newNode) # Huffman Tree ist fertig! printNodes(nodes[0])> |
>
Welche Monate sind Q1?
>
Javascript
> > // node class is the basic structure> // of each node present in the Huffman - tree.> class HuffmanNode> {> >constructor()> >{> >this>.data = 0;> >this>.c =>''>;> >this>.left =>this>.right =>null>;> >}> }> > // recursive function to print the> >// huffman-code through the tree traversal.> >// Here s is the huffman - code generated.> >function> printCode(root,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> >&& (root.c).toLowerCase() != (root.c).toUpperCase()) {> > >// c is the character in the node> >document.write(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> // number of characters.> >let n = 6;> >let charArray = [>'a'>,>'b'>,>'c'>,>'d'>,>'e'>,>'f'> ];> >let charfreq = [ 5, 9, 12, 13, 16, 45 ];> > >// creating a priority queue q.> >// makes a min-priority queue(min-heap).> >let q = [];> > >for> (let i = 0; i // creating a Huffman node object // and add it to the priority queue. let hn = new HuffmanNode(); hn.c = charArray[i]; hn.data = charfreq[i]; hn.left = null; hn.right = null; // add functions adds // the huffman node to the queue. q.push(hn); } // create a root node let root = null; q.sort(function(a,b){return a.data-b.data;}); // Here we will extract the two minimum value // from the heap each time until // its size reduces to 1, extract until // all the nodes are extracted. while (q.length>1) { // erster Min.-Extrakt. sei x = q[0]; q.shift(); // Sekunden-Minuten-Extrakt. sei y = q[0]; q.shift(); // neuer Knoten f, der gleich ist let f = new HuffmanNode(); // zur Summe der Häufigkeit der beiden Knoten // Zuweisen von Werten zum f-Knoten. f.data = x.data + y.data; f.c = '-'; // Erster extrahierter Knoten als linkes Kind. f.left = x; // zweiter extrahierter Knoten als rechtes Kind. f.right = y; // Markieren des f-Knotens als Wurzelknoten. Wurzel = f; // diesen Knoten zur Prioritätswarteschlange hinzufügen. q.push(f); q.sort(function(a,b){return a.data-b.data;}); } // Drucke die Codes aus, indem du den Baum durchquerst printCode(root, ''); // Dieser Code wurde von avanitrachhadiya2155>'> beigesteuert |
>
Konvertieren Sie int in einen String Java
// C# program for the above approach>>using>System;>using>System.Collections.Generic;>>// A Huffman tree node>public>class>MinHeapNode>{>>// One of the input characters>>public>char>data;>>>// Frequency of the character>>public>uint>freq;>>>// Left and right child>>public>MinHeapNode left, right;>>>public>MinHeapNode(>char>data,>uint>freq)>>{>>left = right =>null>;>>this>.data = data;>>this>.freq = freq;>>}>}>>// For comparison of two heap nodes (needed in min heap)>public>class>CompareMinHeapNode : IComparer>{>>public>int>Compare(MinHeapNode x, MinHeapNode y)>>{>>return>x.freq.CompareTo(y.freq);>>}>}>>class>Program>{>>// Prints huffman codes from the root of Huffman Tree.>>static>void>printCodes(MinHeapNode root,>string>str)>>{>>if>(root ==>null>)>>return>;>>>if>(root.data !=>'$'>)>>Console.WriteLine(root.data +>': '>+ str);>>>printCodes(root.left, str +>'0'>);>>printCodes(root.right, str +>'1'>);>>}>>>// The main function that builds a Huffman Tree and>>// print codes by traversing the built Huffman Tree>>static>void>HuffmanCodes(>char>[] data,>uint>[] freq,>int>size)>>{>>MinHeapNode left, right, top;>>>// Create a min heap & inserts all characters of data[]>>var>minHeap =>new>SortedSet(>new>CompareMinHeapNode());>>>for>(>int>i = 0; i minHeap.Add(new MinHeapNode(data[i], freq[i])); // Iterate while size of heap doesn't become 1 while (minHeap.Count != 1) { // Extract the two minimum freq items from min heap left = minHeap.Min; minHeap.Remove(left); right = minHeap.Min; minHeap.Remove(right); // 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 = new MinHeapNode('$', left.freq + right.freq); top.left = left; top.right = right; minHeap.Add(top); } // Print Huffman codes using the Huffman tree built above printCodes(minHeap.Min, ''); } // Driver Code static void Main() { char[] arr = { 'a', 'b', 'c', 'd', 'e', 'f' }; uint[] freq = { 5, 9, 12, 13, 16, 45 }; int size = arr.Length; HuffmanCodes(arr, freq, size); } } // This code is contributed by sdeadityasharma>>>Ausgabef: 0 c: 100 d: 101 a: 1100 b: 1101 e: 111>Zeitkomplexität: O(nlogn) wobei n die Anzahl der eindeutigen Zeichen ist. Wenn es n Knoten gibt, wird extractMin() 2*(n – 1) Mal aufgerufen. extractMin() benötigt O(logn) Zeit, da es minHeapify() aufruft. Die Gesamtkomplexität beträgt also O(nlogn).
Wenn das Eingabearray sortiert ist, liegt ein linearer Zeitalgorithmus vor. Wir werden dies bald in unserem nächsten Beitrag besprechen.Raumkomplexität :- O(N)
Anwendungen der Huffman-Codierung:
- Sie dienen der Übertragung von Fax und Text.
- Sie werden von herkömmlichen Komprimierungsformaten wie PKZIP, GZIP usw. verwendet.
- Multimedia-Codecs wie JPEG, PNG und MP3 verwenden die Huffman-Kodierung (genauer gesagt die Präfixcodes).
Dies ist in Fällen nützlich, in denen eine Reihe häufig vorkommender Zeichen vorhanden sind.
Referenz:
http://en.wikipedia.org/wiki/Huffman_coding
Dieser Artikel wurde von Aashish Barnwal zusammengestellt und vom techcodeview.com-Team überprüft.