TechCodeview

Der Huffman-Codierungsalgorithmus wurde von vorgeschlagen David A. Huffman im Jahr 1950. Es ist ein verlustfreie Datenkomprimierung Mechanismus. Es ist auch bekannt als Datenkomprimierungskodierung. Es wird häufig zur Bildkomprimierung (JPEG oder JPG) verwendet. In diesem Abschnitt werden wir das besprechen Huffman-Kodierung Und Dekodierung, und seinen Algorithmus auch in einem Java-Programm implementieren.

Wir wissen, dass jedes Zeichen eine Folge von Nullen und Einsen ist und mit 8 Bits gespeichert wird. Der Mechanismus heißt Kodierung mit fester Länge weil jedes Zeichen die gleiche Anzahl an Festbitspeichern verwendet.

Java long zu int

Hier erhebt sich eine Frage: Ist es möglich, den Platzbedarf zum Speichern eines Zeichens zu reduzieren?

Ja, es ist möglich durch die Verwendung Codierung mit variabler Länge. Bei diesem Mechanismus nutzen wir einige Zeichen aus, die im Vergleich zu anderen Zeichen häufiger vorkommen. Bei dieser Codierungstechnik können wir denselben Text oder dieselbe Zeichenfolge darstellen, indem wir die Anzahl der Bits reduzieren.

Huffman-Kodierung

Die Huffman-Codierung implementiert die folgenden Schritte.

• Es weist allen angegebenen Zeichen einen Code variabler Länge zu.
• Die Codelänge eines Zeichens hängt davon ab, wie häufig es im gegebenen Text oder String vorkommt.
• Ein Zeichen erhält den kleinsten Code, wenn es häufig vorkommt.
• Ein Zeichen erhält den größten Code, wenn es am wenigsten vorkommt.

Die Huffman-Codierung folgt a Präfixregel Dies verhindert Mehrdeutigkeiten beim Dekodieren. Die Regel stellt außerdem sicher, dass der dem Zeichen zugewiesene Code nicht als Präfix des Codes behandelt wird, der einem anderen Zeichen zugewiesen ist.

Die Huffman-Codierung umfasst die folgenden zwei Hauptschritte:

• Konstruieren Sie zunächst a Huffman-Baum aus der angegebenen Eingabezeichenfolge oder den angegebenen Zeichen oder Texten.
• Weisen Sie jedem Zeichen einen Huffman-Code zu, indem Sie den Baum durchlaufen.

Lassen Sie uns die beiden oben genannten Schritte kurz zusammenfassen.

Huffman-Baum

Schritt 1: Erstellen Sie für jedes Zeichen des Knotens einen Blattknoten. Der Blattknoten eines Zeichens enthält die Häufigkeit dieses Zeichens.

Schritt 2: Ordnen Sie alle Knoten entsprechend ihrer Häufigkeit sortiert an.

Schritt 3: Es kann ein Zustand vorliegen, in dem zwei Knoten die gleiche Frequenz haben. Gehen Sie in einem solchen Fall wie folgt vor:

1. Erstellen Sie einen neuen internen Knoten.
2. Die Frequenz des Knotens ist die Summe der Frequenzen der beiden Knoten, die die gleiche Frequenz haben.
3. Markieren Sie den ersten Knoten als linken untergeordneten Knoten und einen weiteren Knoten als rechten untergeordneten Knoten des neu erstellten internen Knotens.

Schritt 4: Wiederholen Sie Schritt 2 und 3, bis alle Knoten einen einzigen Baum bilden. Somit erhalten wir einen Huffman-Baum.

Beispiel für eine Huffman-Codierung

Angenommen, wir müssen eine Zeichenfolge kodieren Abra Cadabra. Bestimmen Sie Folgendes:

1. Huffman-Code für alle Zeichen
2. Durchschnittliche Codelänge für den angegebenen String
3. Länge der codierten Zeichenfolge

(i) Huffman-Code für alle Zeichen

Um den Code für jedes Zeichen zu bestimmen, konstruieren wir zunächst a Huffman-Baum.

Schritt 1: Bilden Sie Zeichenpaare und deren Häufigkeiten.

(a, 5), (b, 2), (c, 1), (d, 1), (r, 2)

Schritt 2: Sortieren wir Paare nach der Häufigkeit, erhalten wir:

(c, 1), (d, 1), (b, 2) (r, 2), (a, 5)

boto3

Schritt 3: Wählen Sie die ersten beiden Zeichen aus und fügen Sie sie unter einem übergeordneten Knoten zusammen.

Wir stellen fest, dass ein übergeordneter Knoten keine Frequenz hat, also müssen wir ihm eine Frequenz zuweisen. Die Häufigkeit des übergeordneten Knotens ist die Summe seiner untergeordneten Knoten (links und rechts), d. h. 1+1= 2.

Schritt 4: Wiederholen Sie die Schritte 2 und 3, bis wir einen einzelnen Baum erhalten.

Wir stellen fest, dass die Paare bereits (nach Schritt 2) sortiert sind. Wählen Sie erneut die ersten beiden Paare aus und verbinden Sie sie.

Wir stellen fest, dass ein übergeordneter Knoten keine Frequenz hat, also müssen wir ihm eine Frequenz zuweisen. Die Häufigkeit des übergeordneten Knotens ist die Summe seiner untergeordneten Knoten (links und rechts), d. h. 2+2= 4.

Auch hier prüfen wir, ob die Paare sortiert sind oder nicht. In diesem Schritt müssen wir die Paare sortieren.

Wählen Sie gemäß Schritt 3 die ersten beiden Paare aus und verbinden Sie sie. Wir erhalten:

Wir stellen fest, dass ein übergeordneter Knoten keine Frequenz hat, also müssen wir ihm eine Frequenz zuweisen. Die Häufigkeit des übergeordneten Knotens ist die Summe seiner untergeordneten Knoten (links und rechts), d. h. 2+4= 6.

setzt in Java

Auch hier prüfen wir, ob die Paare sortiert sind oder nicht. In diesem Schritt müssen wir die Paare sortieren. Nach dem Sortieren sieht der Baum wie folgt aus:

Wählen Sie gemäß Schritt 3 die ersten beiden Paare aus und verbinden Sie sie. Wir erhalten:

Wir stellen fest, dass ein übergeordneter Knoten keine Frequenz hat, also müssen wir ihm eine Frequenz zuweisen. Die Häufigkeit des übergeordneten Knotens ist die Summe seiner untergeordneten Knoten (links und rechts), d. h. 5+6= elf.

Daher erhalten wir einen einzelnen Baum.

Schließlich finden wir mit Hilfe des obigen Baums den Code für jedes Zeichen. Weisen Sie jeder Kante ein Gewicht zu. Beachten Sie, dass jeder linkskantengewichtet ist 0 und das rechtskantengewichtet ist 1.

Java-Switch-Gehäuse

Wir beobachten, dass Eingabezeichen nur in den Leave-Knoten dargestellt werden und die internen Knoten Nullwerte haben. Um den Huffman-Code für jedes Zeichen zu finden, durchlaufen Sie den Huffman-Baum vom Wurzelknoten zum Blattknoten des bestimmten Zeichens, für das wir den Code finden möchten. Die Tabelle beschreibt den Code und die Codelänge für jedes Zeichen.

Wir beobachten, dass das häufigste Zeichen die kürzeste Codelänge und das weniger häufige Zeichen die größte Codelänge erhält.

Jetzt können wir die Zeichenfolge kodieren (Abra Cadabra) das haben wir oben genommen.

 0 111 10 0 1100 0 1101 0 111 10 0 

(ii) Durchschnittliche Codelänge für die Zeichenfolge

Die durchschnittliche Codelänge des Huffman-Baums kann mithilfe der folgenden Formel ermittelt werden:

 Average Code Length = ∑ ( frequency × code length ) / ∑ ( frequency ) 

= { (5 x 1) + (2 x 3) + (1 x 4) + (1 x 4) + (2 x 2) } / (5+2+1+1+2)

= 2,09090909

(iii) Länge der codierten Zeichenfolge

Die Länge der codierten Nachricht kann mithilfe der folgenden Formel ermittelt werden:

 length= Total number of characters in the text x Average code length per character 

= 11 x 2,09090909

= 23 Bit

Huffman-Kodierungsalgorithmus

 Huffman (C) n=|C| Q=C for i=1 to n-1 do z=allocate_Node() x=left[z]=Extract_Min(Q) y=right[z]=Extract_Min(Q) f[z]=f[x]+f[y] Insert(Q,z) return Extract_Min(Q) 

Der Huffman-Algorithmus ist ein Greedy-Algorithmus. Denn in jeder Phase sucht der Algorithmus nach den besten verfügbaren Optionen.

Die zeitliche Komplexität der Huffman-Kodierung beträgt O(nlogn). Wobei n die Anzahl der Zeichen im angegebenen Text ist.

Huffman-Dekodierung

Die Huffman-Dekodierung ist eine Technik, die die kodierten Daten in Ausgangsdaten umwandelt. Wie wir bei der Kodierung gesehen haben, wird der Huffman-Baum für eine Eingabezeichenfolge erstellt und die Zeichen werden basierend auf ihrer Position im Baum dekodiert. Der Dekodierungsprozess ist wie folgt:

int parseint

• Beginnen Sie mit der Überquerung des Baumes Wurzel Knoten und suchen Sie nach dem Zeichen.
• Wenn wir uns im Binärbaum nach links bewegen, fügen wir hinzu 0 zum Code.
• Wenn wir uns im Binärbaum nach rechts bewegen, fügen Sie hinzu 1 zum Code.

Der untergeordnete Knoten enthält das Eingabezeichen. Ihm wird der aus aufeinanderfolgenden Nullen und Einsen gebildete Code zugewiesen. Die zeitliche Komplexität der Dekodierung einer Zeichenfolge beträgt An), wobei n die Länge der Zeichenfolge ist.

Huffman-Kodierungs- und Dekodierungs-Java-Programm

Im folgenden Programm haben wir Datenstrukturen wie Prioritätswarteschlangen, Stapel und Bäume verwendet, um eine Komprimierungs- und Dekomprimierungslogik zu entwerfen. Wir werden unsere Dienstprogramme auf der weit verbreiteten algorithmischen Technik der Huffman-Codierung basieren.

HuffmanCode.java

 import java.util.Comparator; import java.util.HashMap; import java.util.Map; import java.util.PriorityQueue; //defining a class that creates nodes of the tree class Node { //storing character in ch variable of type character Character ch; //storing frequency in freq variable of type int Integer freq; //initially both child (left and right) are null Node left = null; Node right = null; //creating a constructor of the Node class Node(Character ch, Integer freq) { this.ch = ch; this.freq = freq; } //creating a constructor of the Node class public Node(Character ch, Integer freq, Node left, Node right) { this.ch = ch; this.freq = freq; this.left = left; this.right = right; } } //main class public class HuffmanCode { //function to build Huffman tree public static void createHuffmanTree(String text) { //base case: if user does not provides string if (text == null || text.length() == 0) { return; } //count the frequency of appearance of each character and store it in a map //creating an instance of the Map Map freq = new HashMap(); //loop iterates over the string and converts the text into character array for (char c: text.toCharArray()) { //storing character and their frequency into Map by invoking the put() method freq.put(c, freq.getOrDefault(c, 0) + 1); } //create a priority queue that stores current nodes of the Huffman tree. //here a point to note that the highest priority means the lowest frequency PriorityQueue pq = new PriorityQueue(Comparator.comparingInt(l -&gt; l.freq)); //loop iterate over the Map and returns a Set view of the mappings contained in this Map for (var entry: freq.entrySet()) { //creates a leaf node and add it to the queue pq.add(new Node(entry.getKey(), entry.getValue())); } //while loop runs until there is more than one node in the queue while (pq.size() != 1) { //removing the nodes having the highest priority (the lowest frequency) from the queue Node left = pq.poll(); Node right = pq.poll(); //create a new internal node with these two nodes as children and with a frequency equal to the sum of both nodes&apos; frequencies. Add the new node to the priority queue. //sum up the frequency of the nodes (left and right) that we have deleted int sum = left.freq + right.freq; //adding a new internal node (deleted nodes i.e. right and left) to the queue with a frequency that is equal to the sum of both nodes pq.add(new Node(null, sum, left, right)); } //root stores pointer to the root of Huffman Tree Node root = pq.peek(); //trace over the Huffman tree and store the Huffman codes in a map Map huffmanCode = new HashMap(); encodeData(root, &apos;&apos;, huffmanCode); //print the Huffman codes for the characters System.out.println(&apos;Huffman Codes of the characters are: &apos; + huffmanCode); //prints the initial data System.out.println(&apos;The initial string is: &apos; + text); //creating an instance of the StringBuilder class StringBuilder sb = new StringBuilder(); //loop iterate over the character array for (char c: text.toCharArray()) { //prints encoded string by getting characters sb.append(huffmanCode.get(c)); } System.out.println(&apos;The encoded string is: &apos; + sb); System.out.print(&apos;The decoded string is: &apos;); if (isLeaf(root)) { //special case: For input like a, aa, aaa, etc. while (root.freq-- &gt; 0) { System.out.print(root.ch); } } else { //traverse over the Huffman tree again and this time, decode the encoded string int index = -1; while (index <sb.length() - 1) { index="decodeData(root," index, sb); } traverse the huffman tree and store codes in a map function that encodes data public static void encodedata(node root, string str, huffmancode) if (root="=" null) return; checks node is leaf or not (isleaf(root)) huffmancode.put(root.ch, str.length()> 0 ? str : &apos;1&apos;); } encodeData(root.left, str + &apos;0&apos;, huffmanCode); encodeData(root.right, str + &apos;1&apos;, huffmanCode); } //traverse the Huffman Tree and decode the encoded string function that decodes the encoded data public static int decodeData(Node root, int index, StringBuilder sb) { //checks if the root node is null or not if (root == null) { return index; } //checks if the node is a leaf node or not if (isLeaf(root)) { System.out.print(root.ch); return index; } index++; root = (sb.charAt(index) == &apos;0&apos;) ? root.left : root.right; index = decodeData(root, index, sb); return index; } //function to check if the Huffman Tree contains a single node public static boolean isLeaf(Node root) { //returns true if both conditions return ture return root.left == null &amp;&amp; root.right == null; } //driver code public static void main(String args[]) { String text = &apos;javatpoint&apos;; //function calling createHuffmanTree(text); } } </sb.length()>

Ausgabe:

 Huffman Codes of the characters are: {p=000, a=110, t=111, v=001, i=010, j=011, n=100, o=101} The initial string is: javatpoint The encoded string is: 011110001110111000101010100111 The decoded string is: javatpoint