Daten können mit der Huffman-Codierungstechnik komprimiert werden, um kleiner zu werden, ohne dass ihre Informationen verloren gehen. Wer hat es nach David Huffman am Anfang geschaffen? Daten, die sich häufig wiederholende Zeichen enthalten, werden normalerweise mithilfe der Huffman-Codierung komprimiert.
Ein bekannter Greedy-Algorithmus ist Huffman Coding. Die einem Zeichen zugewiesene Codegröße hängt von der Häufigkeit des Zeichens ab, weshalb es sich um einen Greedy-Algorithmus handelt. Der variable Code kurzer Länge wird dem Zeichen mit der höchsten Häufigkeit zugewiesen und umgekehrt den Zeichen mit niedrigerer Häufigkeit. Es verwendet eine Codierung mit variabler Länge, was bedeutet, dass jedem Zeichen im bereitgestellten Datenstrom ein anderer Code mit variabler Länge zugewiesen wird.
Präfixregel
Im Wesentlichen besagt diese Regel, dass der einem Zeichen zugewiesene Code nicht das Präfix eines anderen Codes sein darf. Bei einem Verstoß gegen diese Regel kann es bei der Dekodierung des erstellten Huffman-Baums zu verschiedenen Unklarheiten kommen.
Schauen wir uns eine Illustration dieser Regel an, um sie besser zu verstehen: Für jedes Zeichen wird ein Code bereitgestellt, wie zum Beispiel:
Konvertieren einer Zeichenfolge in eine Ganzzahl in Java
a - 0 b - 1 c - 01
Unter der Annahme, dass der erzeugte Bitstrom 001 ist, kann der Code bei der Decodierung wie folgt ausgedrückt werden:
0 0 1 = aab 0 01 = ac
Was ist der Huffman-Codierungsprozess?
Der Huffman-Code wird für jedes einzelne Zeichen in hauptsächlich zwei Schritten ermittelt:
- Erstellen Sie zunächst einen Huffman-Baum, indem Sie nur die eindeutigen Zeichen im bereitgestellten Datenstrom verwenden.
- Zweitens müssen wir den konstruierten Huffman-Baum durchgehen, den Zeichen Codes zuweisen und diese Codes dann verwenden, um den bereitgestellten Text zu dekodieren.
Schritte zur Huffman-Codierung
Die Schritte zum Erstellen des Huffman-Baums unter Verwendung der bereitgestellten Zeichen
Input: string str = 'abbcdbccdaabbeeebeab'
Wird in diesem Fall die Huffman-Codierung zur Datenkomprimierung eingesetzt, müssen für die Decodierung folgende Informationen ermittelt werden:
Ersatz in Java
- Für jedes Zeichen der Huffman-Code
- Huffman-codierte Nachrichtenlänge (in Bits), durchschnittliche Codelänge
- Mithilfe der unten aufgeführten Formeln werden die letzten beiden ermittelt.
Wie kann ein Huffman-Baum aus Eingabezeichen erstellt werden?
Zunächst muss die Häufigkeit jedes Zeichens in der bereitgestellten Zeichenfolge ermittelt werden.
| Charakter | Frequenz |
|---|---|
| A | 4 |
| B | 7 |
| C | 3 |
| D | 2 |
| Es ist | 4 |
- Sortieren Sie die Zeichen nach Häufigkeit aufsteigend. Diese werden in einer Q/Min-Heap-Prioritätswarteschlange gehalten.
- Erstellen Sie für jedes einzelne Zeichen und seine Häufigkeit im Datenstrom einen Blattknoten.
- Entfernen Sie die beiden Knoten mit den beiden niedrigsten Häufigkeiten von den Knoten, und aus der Summe dieser Häufigkeiten wird die neue Wurzel des Baums erstellt.
- Machen Sie den ersten extrahierten Knoten zu seinem linken Kind und den zweiten extrahierten Knoten zu seinem rechten Kind, während Sie die Knoten mit der niedrigsten Häufigkeit aus dem Min-Heap extrahieren.
- Fügen Sie diesen Knoten zum Min-Heap hinzu.
- Da die linke Seite der Wurzel immer die minimale Frequenz enthalten sollte.
- Wiederholen Sie die Schritte 3 und 4, bis nur noch ein Knoten auf dem Heap übrig ist oder alle Zeichen durch Knoten im Baum dargestellt werden. Der Baum ist fertig, wenn nur noch der Wurzelknoten übrig bleibt.
Beispiele für Huffman-Codierung
Lassen Sie uns den Algorithmus anhand einer Illustration erklären:
Algorithmus für die Huffman-Codierung
Schritt 1: Erstellen Sie einen Min-Heap, in dem jeder Knoten die Wurzel eines Baums mit einem einzelnen Knoten darstellt und 5 (die Anzahl der eindeutigen Zeichen aus dem bereitgestellten Datenstrom) enthält.
Schritt 2: Erhalten Sie in Schritt zwei zwei Knoten mit minimaler Häufigkeit aus dem Min-Heap. Fügen Sie einen dritten internen Knoten mit der Frequenz 2 + 3 = 5 hinzu, der durch Verbinden der beiden extrahierten Knoten erstellt wird.
- Nun gibt es 4 Knoten im Min-Heap, von denen 3 die Wurzeln von Bäumen mit jeweils einem einzelnen Element sind und 1 davon die Wurzel eines Baums mit zwei Elementen ist.
Schritt 3: Rufen Sie in Schritt drei auf ähnliche Weise die beiden Knoten mit der minimalen Häufigkeit aus dem Heap ab. Fügen Sie außerdem einen neuen internen Knoten hinzu, der durch die Verbindung der beiden extrahierten Knoten entsteht. seine Häufigkeit im Baum sollte 4 + 4 = 8 betragen.
- Da der minimale Heap nun über drei Knoten verfügt, dient ein Knoten als Wurzel von Bäumen mit einem einzelnen Element und zwei Heap-Knoten als Wurzel von Bäumen mit mehreren Knoten.
Schritt 4: Ermitteln Sie in Schritt 4 die beiden Mindestfrequenzknoten. Fügen Sie außerdem einen neuen internen Knoten hinzu, der durch die Verbindung der beiden extrahierten Knoten entsteht. seine Häufigkeit im Baum sollte 5 + 7 = 12 betragen.
- Beim Erstellen eines Huffman-Baums müssen wir sicherstellen, dass der Mindestwert immer auf der linken Seite und der zweite Wert immer auf der rechten Seite liegt. Derzeit zeigt das Bild unten den Baum, der sich gebildet hat:
Schritt 5: Rufen Sie in Schritt 5 die folgenden zwei Knoten mit minimaler Häufigkeit ab. Fügen Sie außerdem einen neuen internen Knoten hinzu, der durch die Verbindung der beiden extrahierten Knoten gebildet wird. seine Häufigkeit im Baum sollte 12 + 8 = 20 betragen.
Fahren Sie fort, bis alle unterschiedlichen Zeichen zum Baum hinzugefügt wurden. Der für die angegebene Zeichengruppe erstellte Huffman-Baum ist im Bild oben dargestellt.
Methodenüberschreibung in Java
Weisen Sie nun für jeden Nicht-Blattknoten dem linken Rand eine 0 und dem rechten Rand eine 1 zu, um den Code für jeden Buchstaben zu erstellen.
Arrayliste in Java sortieren
Regeln zur Bestimmung der Kantengewichte:
- Wir sollten den rechten Kanten das Gewicht 1 geben, wenn Sie den linken Kanten das Gewicht 0 geben.
- Wenn die linken Kanten das Gewicht 1 erhalten, müssen die rechten Kanten das Gewicht 0 erhalten.
- Es kann jede der beiden oben genannten Konventionen verwendet werden.
- Befolgen Sie jedoch dasselbe Protokoll auch beim Dekodieren des Baums.
Nach der Gewichtung wird der geänderte Baum wie folgt angezeigt:
Den Kodex verstehen
- Wir müssen den Huffman-Baum durchlaufen, bis wir den Blattknoten erreichen, in dem das Element vorhanden ist, um den Huffman-Code für jedes Zeichen aus dem resultierenden Huffman-Baum zu dekodieren.
- Die Gewichte über die Knoten hinweg müssen während der Durchquerung aufgezeichnet und den Elementen zugeordnet werden, die sich am jeweiligen Blattknoten befinden.
- Das folgende Beispiel soll weiter veranschaulichen, was wir meinen:
- Um den Code für jedes Zeichen im Bild oben zu erhalten, müssen wir den gesamten Baum durchlaufen (bis alle Blattknoten abgedeckt sind).
- Infolgedessen wird der erstellte Baum verwendet, um die Codes für jeden Knoten zu dekodieren. Nachfolgend finden Sie eine Liste der Codes für jedes Zeichen:
| Charakter | Häufigkeit/Anzahl | Code |
|---|---|---|
| A | 4 | 01 |
| B | 7 | elf |
| C | 3 | 101 |
| D | 2 | 100 |
| Es ist | 4 | 00 |
Nachfolgend finden Sie die Implementierung in der C-Programmierung:
// 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; } Ausgabe
f: 0 c: 100 d: 101 a: 1100 b: 1101 e: 111 …………… Process executed in 1.11 seconds Press any key to continue.
Java-Implementierung des obigen Codes:
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;> Ausgabe
f: 0 c: 100 d: 101 a: 1100 b: 1101 e: 111 ………………. Process executed in 1.11 seconds Press any key to continue.
Erläuterung:
Durch das Durchlaufen wird der Huffman-Baum erstellt und dekodiert. Die während des Durchlaufs gesammelten Werte sollen dann auf das Zeichen angewendet werden, das sich am Blattknoten befindet. Auf diese Weise kann jedes eindeutige Zeichen im bereitgestellten Datenstrom mithilfe des Huffman-Codes identifiziert werden. O (nlogn), wobei n die Gesamtzahl der Zeichen ist, ist die zeitliche Komplexität. ExtractMin() wird 2*(n - 1) Mal aufgerufen, wenn es n Knoten gibt. Da extractMin() minHeapify() aufruft, beträgt seine Ausführungszeit O (logn). Die Gesamtkomplexität beträgt daher O (nlogn). Es gibt einen linearen Zeitalgorithmus, wenn das Eingabearray sortiert ist. Dies wird in unserem kommenden Artikel ausführlicher behandelt.
Probleme mit der Huffman-Codierung
Lassen Sie uns in diesem Teil über die Nachteile der Huffman-Codierung sprechen und warum sie nicht immer die beste Option ist:
- Wenn nicht alle Wahrscheinlichkeiten oder Häufigkeiten der Charaktere negative Potenzen von 2 sind, wird dies nicht als ideal angesehen.
- Obwohl man durch die Gruppierung von Symbolen und die Erweiterung des Alphabets dem Ideal näher kommen kann, erfordert die Blockierungsmethode die Handhabung eines größeren Alphabets. Daher ist die Huffman-Codierung möglicherweise nicht immer sehr effektiv.
- Obwohl es viele effektive Möglichkeiten gibt, die Häufigkeit jedes Symbols oder Zeichens zu zählen, kann die Rekonstruktion des gesamten Baums für jedes einzelne sehr zeitaufwändig sein. Wenn das Alphabet groß ist und sich die Wahrscheinlichkeitsverteilungen mit jedem Symbol schnell ändern, ist dies normalerweise der Fall.
Gieriger Huffman-Code-Konstruktionsalgorithmus
- Huffman hat eine gierige Technik entwickelt, die für jedes einzelne Zeichen im Eingabedatenstrom einen Huffman-Code, einen idealen Präfixcode, generiert.
- Der Ansatz verwendet jedes Mal die wenigsten Knoten, um den Huffman-Baum von unten nach oben zu erstellen.
- Da jedes Zeichen eine Codelänge erhält, die davon abhängt, wie häufig es im gegebenen Datenstrom vorkommt, wird diese Methode als gieriger Ansatz bezeichnet. Es handelt sich um ein häufig vorkommendes Element in den Daten, wenn die Größe des abgerufenen Codes geringer ist.
Die Verwendung der Huffman-Codierung
- Hier sprechen wir über einige praktische Anwendungen der Huffman-Codierung:
- Herkömmliche Komprimierungsformate wie PKZIP, GZIP usw. verwenden typischerweise Huffman-Codierung.
- Die Huffman-Codierung wird für die Datenübertragung per Fax und Text verwendet, da sie die Dateigröße minimiert und die Übertragungsgeschwindigkeit erhöht.
- Die Huffman-Kodierung (insbesondere die Präfixcodes) wird von mehreren Multimedia-Speicherformaten, einschließlich JPEG, PNG und MP3, zum Komprimieren der Dateien verwendet.
- Die Huffman-Codierung wird hauptsächlich zur Bildkomprimierung verwendet.
- Wenn eine Folge häufig wiederkehrender Zeichen gesendet werden muss, kann dies hilfreicher sein.
Abschluss
- Im Allgemeinen ist die Huffman-Codierung hilfreich für die Komprimierung von Daten, die häufig vorkommende Zeichen enthalten.
- Wir können sehen, dass das Zeichen, das am häufigsten vorkommt, den kürzesten Code hat, während das Zeichen, das am seltensten vorkommt, den größten Code hat.
- Die Huffman-Code-Komprimierungstechnik wird verwendet, um eine Codierung mit variabler Länge zu erstellen, die eine unterschiedliche Anzahl von Bits für jeden Buchstaben oder jedes Symbol verwendet. Diese Methode ist der Codierung mit fester Länge überlegen, da sie weniger Speicher benötigt und Daten schneller überträgt.
- Lesen Sie diesen Artikel durch, um den Greedy-Algorithmus besser kennenzulernen.