🥇Huffman-Kompressionsalgorithmus

Im Vorfeld des Kursstarts „Algorithmen für Entwickler“ haben für Sie die Übersetzung eines weiteren nützlichen Materials vorbereitet.

Die Huffman-Codierung ist ein Datenkomprimierungsalgorithmus, der die grundsätzliche Idee der Dateikomprimierung formuliert. In diesem Artikel werden wir über die Codierung fester und variabler Länge, eindeutig dekodierbare Codes, Präfixregeln und den Aufbau des Huffman-Baums sprechen.

Wir wissen, dass jedes Zeichen als eine Folge von 0 und 1 gespeichert wird und 8 Bit umfasst. Dies wird als Codierung fester Länge bezeichnet, da jedes Zeichen eine gleiche, feste Anzahl von Bits zur Speicherung verwendet.

Angenommen, hier ist ein Text. Wie können wir den Platz, der für die Speicherung eines Zeichens benötigt wird, verringern?

Die Grundidee besteht in der Codierung variabler Länge. Wir können die Tatsache nutzen, dass einige Zeichen im Text häufiger vorkommen als andere (siehe hier), um einen Algorithmus zu entwickeln, der dieselbe Folge von Zeichen mit weniger Bits darstellt. Bei der Codierung variabler Länge weisen wir den Zeichen eine variable Anzahl von Bits zu, abhängig von ihrer Häufigkeit in diesem Text. Letztendlich können einige Zeichen nur 1 Bit benötigen, während andere 2, 3 oder mehr Bits benötigen. Das Problem bei der Codierung variabler Länge besteht nur darin, die Folge anschließend zu dekodieren.

Wie dekodiert man die Folge eindeutig, wenn man die Bitfolge kennt?

Betrachten wir die Zeichenfolge „aabacdab“. Sie enthält 8 Zeichen, und bei der Codierung fester Länge würden 64 Bit benötigt werden, um sie zu speichern. Beachten Sie, dass die Häufigkeit der Zeichen „a“, „b“, „c“ und „d“ entsprechend 4, 2, 1, 1 beträgt. Lassen Sie uns versuchen, sie „aabacdab“ mit weniger Bits darzustellen, indem wir die Tatsache nutzen, dass „a“ häufiger vorkommt als „b“, und „b“ häufiger vorkommt als „c“ und „d“. Wir beginnen damit, dass wir „a“ mit einem Bit, das 0 entspricht, codieren, „b“ denn wir weisen den zwei-Bit-Code 11 zu, und mit drei Bits codieren wir „c“ und „d“.

Somit erhalten wir:

a
0

b
11

c
100

d
011

So wird die Zeichenfolge „aabacdab“ als 00110100011011 (0|0|11|0|100|011|0|11)codiert, wobei die oben dargestellten Codes verwendet werden. Das Hauptproblem wird jedoch das Dekodieren sein. Wenn wir versuchen, die Zeichenfolge 00110100011011zu dekodieren, erhalten wir ein mehrdeutiges Ergebnis, da sie so dargestellt werden kann:

0|011|0|100|011|0|11    adacdab
0|0|11|0|100|0|11|011   aabacabd
0|011|0|100|0|11|0|11   adacabab

…
usw.

Um diese Mehrdeutigkeit zu vermeiden, müssen wir sicherstellen, dass unsere Kodierung einem Konzept wie dem Präfixregelentspricht, was wiederum bedeutet, dass Codes auf genau eine einzigartige Weise dekodiert werden können. Die Präfixregel stellt sicher, dass kein Code ein Präfix eines anderen Codes ist. Unter einem Code verstehen wir die Bits, die zur Darstellung eines bestimmten Zeichens verwendet werden. In dem obigen Beispiel 0 ist ein Präfix 011, was die Präfixregel verletzt. Wenn unsere Codes also der Präfixregel entsprechen, kann die Dekodierung eindeutig durchgeführt werden (und umgekehrt).

Lassen Sie uns das obige Beispiel erneut betrachten. Dieses Mal weisen wir den Zeichen „a“, „b“, „c“ und „d“ Codes zu, die der Präfixregel entsprechen.

a
0

b
10

c
110

d
111

Mit dieser Kodierung wird die Zeichenkette „aabacdab“ als 00100100011010 (0|0|10|0|100|011|0|10)kodiert. Und in diesem Fall 00100100011010 können wir sie dann eindeutig dekodieren und zu unserer ursprünglichen Zeichenkette zurückkehren. „aabacdab“.

Huffman-Kodierung

Jetzt, da wir die Kodierung variabler Länge und die Präfixregel verstanden haben, lassen Sie uns über die Huffman-Kodierung sprechen.

Die Methode basiert auf der Erstellung von binären Bäumen. In diesem können Knoten entweder Blätter oder innere Knoten sein. Zu Beginn werden alle Knoten als Blätter (endgültig) betrachtet, die das Zeichen selbst und sein Gewicht (d.h. die Häufigkeit des Auftretens) repräsentieren. Innere Knoten enthalten das Gewicht des Zeichens und verweisen auf zwei Nachfolgerknoten. Üblicherweise steht das Bit „0“ für das Folgen des linken Zweigs, während „1“ für den rechten steht. In einem vollständigen Baum gibt es N Blätter und N-1 innere Knoten. Es wird empfohlen, nicht verwendete Zeichen bei der Erstellung des Huffman-Baums abzulehnen, um Codes optimaler Länge zu erhalten.

Wir werden eine Prioritätswarteschlange verwenden, um den Huffman-Baum zu erstellen, wobei dem Knoten mit der niedrigsten Häufigkeit die höchste Priorität zugewiesen wird. Die Schritte zum Erstellen sind wie folgt:

Erstellen Sie ein Blattknoten für jedes Zeichen und fügen Sie sie der Prioritätswarteschlange hinzu.
Solange sich mehr als ein Blatt in der Warteschlange befindet, führen wir Folgendes durch:
- Entfernen Sie die beiden Knoten mit der höchsten Priorität (geringsten Häufigkeit) aus der Warteschlange;
- Erstellen Sie einen neuen inneren Knoten, bei dem diese beiden Knoten Nachfolger sind, und die Häufigkeit beträgt die Summe der Häufigkeiten dieser beiden Knoten.
- Fügen Sie den neuen Knoten in die Prioritätswarteschlange ein.
Der einzige verbleibende Knoten wird der Wurzelknoten sein, damit endet der Aufbau des Baumes.

Stellen wir uns vor, wir haben einen bestimmten Text, der nur aus den Zeichen „a“, „b“, „c“, „d“ und „e“, und die Häufigkeiten ihres Auftretens betragen 15, 7, 6, 6 und 5 entsprechend. Im Folgenden sind Illustrationen aufgeführt, die die Schritte des Algorithmus veranschaulichen.

Der Weg von der Wurzel zu jedem Endknoten wird den optimalen Präfixcode (auch bekannt als Huffman-Code) speichern, der dem Zeichen zugeordnet ist, das mit diesem Endknoten verbunden ist.

Huffman-Baum

Im Folgenden finden Sie eine Implementierung des Huffman-Kompressionsalgorithmus in C++ und Java:

#include <iostream>
#include <string>
#include <queue>
#include <unordered_map>
using namespace std;

// A Tree node
struct Node
{
	char ch;
	int freq;
	Node *left, *right;
};

// Function to allocate a new tree node
Node* getNode(char ch, int freq, Node* left, Node* right)
{
	Node* node = new Node();

	node->ch = ch;
	node->freq = freq;
	node->left = left;
	node->right = right;

	return node;
}

// Comparison object to be used to order the heap
struct comp
{
	bool operator()(Node* l, Node* r)
	{
		// highest priority item has lowest frequency
		return l->freq > r->freq;
	}
};

// traverse the Huffman Tree and store Huffman Codes
// in a map.
void encode(Node* root, string str,
			unordered_map<char, string> &huffmanCode)
{
	if (root == nullptr)
		return;

	// found a leaf node
	if (!root->left && !root->right) {
		huffmanCode[root->ch] = str;
	}

	encode(root->left, str + "0", huffmanCode);
	encode(root->right, str + "1", huffmanCode);
}

// traverse the Huffman Tree and decode the encoded string
void decode(Node* root, int &index, string str)
{
	if (root == nullptr) {
		return;
	}

	// found a leaf node
	if (!root->left && !root->right)
	{
		cout << root->ch;
		return;
	}

	index++;

	if (str[index] =='0')
		decode(root->left, index, str);
	else
		decode(root->right, index, str);
}

// Builds Huffman Tree and decode given input text
void buildHuffmanTree(string text)
{
	// count frequency of appearance of each character
	// and store it in a map
	unordered_map<char, int> freq;
	for (char ch: text) {
		freq[ch]++;
	}

	// Create a priority queue to store live nodes of
	// Huffman tree;
	priority_queue<Node*, vector<Node*>, comp> pq;

	// Create a leaf node for each character and add it
	// to the priority queue.
	for (auto pair: freq) {
		pq.push(getNode(pair.first, pair.second, nullptr, nullptr));
	}

	// do till there is more than one node in the queue
	while (pq.size() != 1)
	{
		// Remove the two nodes of highest priority
		// (lowest frequency) from the queue
		Node *left = pq.top(); pq.pop();
		Node *right = pq.top();	pq.pop();

		// Create a new internal node with these two nodes
		// as children and with frequency equal to the sum
		// of the two nodes' frequencies. Add the new node
		// to the priority queue.
		int sum = left->freq + right->freq;
		pq.push(getNode(' ', sum, left, right));
	}

	// root stores pointer to root of Huffman Tree
	Node* root = pq.top();

	// traverse the Huffman Tree and store Huffman Codes
	// in a map. Also prints them
	unordered_map<char, string> huffmanCode;
	encode(root, "", huffmanCode);

	cout << "Huffman Codes are :n" << 'n';
	for (auto pair: huffmanCode) {
		cout << pair.first << " " << pair.second << 'n';
	}

	cout << "nOriginal string was :n" << text << 'n';

	// print encoded string
	string str = "";
	for (char ch: text) {
		str += huffmanCode[ch];
	}

	cout << "nEncoded string is :n" << str << 'n';

	// traverse the Huffman Tree again and this time
	// decode the encoded string
	int index = -1;
	cout << "nDecoded string is: n";
	while (index < (int)str.size() - 2) {
		decode(root, index, str);
	}
}

// Huffman coding algorithm
int main()
{
	string text = "Huffman coding is a data compression algorithm.";

	buildHuffmanTree(text);

	return 0;
}

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

// Ein Baumknoten
class Node
{
	char ch;
	int freq;
	Node left = null, right = null;

	Node(char ch, int freq)
	{
		this.ch = ch;
		this.freq = freq;
	}

	public Node(char ch, int freq, Node left, Node right) {
		this.ch = ch;
		this.freq = freq;
		this.left = left;
		this.right = right;
	}
};

class Huffman
{
	// Durchlaufen des Huffman-Baumes und Speichern der Huffman-Codes
	// in einer Map.
	public static void encode(Node root, String str,
							  Map huffmanCode)
	{
		if (root == null)
			return;

		// Ein Blattknoten gefunden
		if (root.left == null && root.right == null) {
			huffmanCode.put(root.ch, str);
		}


		encode(root.left, str + "0", huffmanCode);
		encode(root.right, str + "1", huffmanCode);
	}

	// Durchlaufen des Huffman-Baumes und Dekodieren des kodierten Strings
	public static int decode(Node root, int index, StringBuilder sb)
	{
		if (root == null)
			return index;

		// Ein Blattknoten gefunden
		if (root.left == null && root.right == null)
		{
			System.out.print(root.ch);
			return index;
		}

		index++;

		if (sb.charAt(index) == '0')
			index = decode(root.left, index, sb);
		else
			index = decode(root.right, index, sb);

		return index;
	}

	// Baut den Huffman-Baum und huffmanCode und dekodiert den gegebenen Eingabetext
	public static void buildHuffmanTree(String text)
	{
		// Zählt die Frequenz des Auftretens jedes Zeichens
		// und speichert es in einer Map
		Map freq = new HashMap();
		for (int i = 0 ; i < text.length(); i++) {
			if (!freq.containsKey(text.charAt(i))) {
				freq.put(text.charAt(i), 0);
			}
			freq.put(text.charAt(i), freq.get(text.charAt(i)) + 1);
		}

		// Erstelle eine Prioritätswarteschlange zum Speichern lebender Knoten des Huffman-Baumes
		// Beachte, dass das Element mit der höchsten Priorität die niedrigste Frequenz hat
		PriorityQueue pq = new PriorityQueue (
										(l, r) -> l.freq - r.freq);

		// Erstelle einen Blattknoten für jedes Zeichen und füge es
		// zur Prioritätswarteschlange hinzu.
		for (Map.Entry entry : freq.entrySet()) {
			pq.add(new Node(entry.getKey(), entry.getValue()));
		}

		// mache weiter, bis mehr als ein Knoten in der Warteschlange ist
		while (pq.size() != 1)
		{
			// Entferne die beiden Knoten mit der höchsten Priorität
			// (niedrigste Frequenz) aus der Warteschlange
			Node left = pq.poll();
			Node right = pq.poll();

			// Erstelle einen neuen internen Knoten mit diesen beiden Knoten als Kinder
			// und mit einer Frequenz, die der Summe der Frequenzen der beiden Knoten entspricht.
			// Füge den neuen Knoten zur Prioritätswarteschlange hinzu.
			int sum = left.freq + right.freq;
			pq.add(new Node(' ', sum, left, right));
		}

		// root speichert den Zeiger auf die Wurzel des Huffman-Baumes
		Node root = pq.peek();

		// Durchlaufe den Huffman-Baum und speichere die Huffman-Codes in einer Map
		Map huffmanCode = new HashMap();
		encode(root, "", huffmanCode);

		// Drucke die Huffman-Codes
		System.out.println("Huffman-Codes sind :\n");
		for (Map.Entry entry : huffmanCode.entrySet()) {
			System.out.println(entry.getKey() + " " + entry.getValue());
		}

		System.out.println("\nDer ursprüngliche String war :\n" + text);

		// Drucke den kodierten String
		StringBuilder sb = new StringBuilder();
		for (int i = 0 ; i < text.length(); i++) {
			sb.append(huffmanCode.get(text.charAt(i)));
		}

		System.out.println("\nDer kodierte String ist :\n" + sb);

		// Durchlaufe den Huffman-Baum erneut und dekodiere den kodierten String
		int index = -1;
		System.out.println("\nDer dekodierte String ist: \n");
		while (index < sb.length() - 2) {
			index = decode(root, index, sb);
		}
	}

	public static void main(String[] args)
	{
		String text = "Huffman-Codierung ist ein Algorithmus zur Datenkompression.";

		buildHuffmanTree(text);
	}
}

Hinweis: Der von der Eingabezeichenfolge verwendete Speicher beträgt 47 * 8 = 376 Bit, während die kodierte Zeichenfolge nur 194 Bit benötigt, d.h. die Daten werden um etwa 48 % komprimiert. In dem oben dargestellten C++-Programm verwenden wir die Klasse string zur Speicherung der kodierten Zeichenfolge, um das Programm lesbar zu machen.

Da effektive Datenstrukturen für Prioritätswarteschlangen beim Einfügen O(log(N)) Zeit erfordern und in einem vollständigen binären Baum mit N Blättern 2N-1 Knoten vorhanden sind, und der Huffman-Baum ein vollständiger binärer Baum ist, funktioniert der Algorithmus in O(Nlog(N)) Zeit, wobei N die Anzahl der Zeichen ist.