Im Vorfeld des Starts des Kurses haben für Sie die Übersetzung eines weiteren nützlichen Materials vorbereitet.
Das Huffman-Coding ist ein Datenkompressionsalgorithmus, der das grundlegende Konzept der Dateikompression formuliert. In diesem Artikel sprechen wir über Codierung fester und variabler Länge, eindeutig decodierbare Codes, Präfixregeln und den Aufbau des Huffman-Baums.
Wir wissen, dass jedes Zeichen als Folge von 0 und 1 gespeichert wird und 8 Bit benötigt. Dies wird als Codierung fester Länge bezeichnet, da jedes Zeichen die gleiche feste Anzahl von Bits zur Speicherung verwendet.
Nehmen wir an, es gibt einen Text. Wie können wir den Platzbedarf zur Speicherung eines Zeichens verringern?
Die grundlegende Idee besteht darin, die Codierung variabler Länge zu verwenden. Wir können den Umstand nutzen, dass einige Zeichen im Text häufiger vorkommen als andere (), um einen Algorithmus zu entwickeln, der dieselbe Zeichenfolge mit weniger Bits darstellt. Bei der variablen Längencodierung weisen wir Zeichen je nach Häufigkeit ihres Auftretens im Text eine unterschiedliche Anzahl von Bits zu. Letztendlich können einige Zeichen nur 1 Bit, andere 2, 3 oder mehr benötigen. Das Problem bei der variablen Längencodierung liegt einzig im späteren Dekodieren der Folge.
Wie kann man die Bitfolge eindeutig dekodieren, wenn man sie kennt?
Betrachten wir die Zeichenfolge «aabacdab». Sie besteht aus 8 Zeichen, und bei der festen Längencodierung wären dafür 64 Bits erforderlich. Es fällt auf, dass die Häufigkeit der Zeichen «a», «b», «c» und «d» jeweils 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, kodieren, «b» wir weisen den zwei-Bit-Code 11 zu, und mit drei Bits kodieren wir 100 und 011 «c» und «d».
Am Ende haben wir:
a
0
b
11
c
100
d
011
Somit kodieren wir die Zeichenfolge «aabacdab» als 00110100011011 (0|0|11|0|100|011|0|11), indem Sie die oben angegebenen Codes verwenden. Allerdings liegt das Hauptproblem im Decodieren. Wenn wir versuchen, die Zeile zu decodieren, 00110100011011, erhalten wir ein mehrdeutiges Ergebnis, da sie dargestellt werden kann als:
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 dem Konzept des Präfixregeln, welches wiederum bedeutet, dass Codes auf genau eine einzigartige Weise decodiert werden können. Die Präfixregel gewährleistet, dass kein Code ein Präfix eines anderen ist. Unter einem Code verstehen wir die Bits, die zur Darstellung eines bestimmten Symbols verwendet werden. Im 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 erfolgen (und umgekehrt).
Lassen Sie uns das obige Beispiel erneut betrachten. Dieses Mal weisen wir für die Symbole «a», «b», «c» und «d» Codes zu, die der Präfixregel entsprechen.
a
0
b
10
c
110
d
111
Mit einer solchen Kodierung wird die Zeile «aabacdab» als kodiert 00100100011010 (0|0|10|0|100|011|0|10). Und hier ist 00100100011010 Wir können nun eindeutig decodieren und zu unserem ursprünglichen String zurückkehren. «aabacdab».
Huffman-Codierung
Jetzt, da wir die variable Längen-Codierung und die Präfixregel verstanden haben, lassen Sie uns über die Huffman-Codierung sprechen.
Die Methode basiert auf der Erstellung binärer Bäume. Ein Knoten kann entweder ein Blatt oder ein innerer Knoten sein. Anfangs werden alle Knoten als Blätter (Endknoten) betrachtet, die das Symbol selbst und dessen Gewicht (d.h. die Häufigkeit des Auftretens) darstellen. Innere Knoten enthalten das Gewicht des Symbols und verweisen auf zwei Nachfolgerknoten. Üblicherweise steht das Bit "0" für das Durchlaufen des linken Zweigs, während "1" für den rechten Zweig steht. In einem vollständigen Baum gibt es N Blätter und N-1 innere Knoten. Es wird empfohlen, bei der Konstruktion des Huffman-Baums nicht verwendete Symbole zu verwerfen, um Codes optimaler Länge zu erhalten.
Wir werden eine Prioritätswarteschlange verwenden, um den Huffman-Baum zu erstellen, wobei dem Knoten mit der geringsten Frequenz die höchste Priorität zugewiesen wird. Die folgenden Schritte beschreiben den Aufbau:
- Erstellen Sie einen Blattknoten für jedes Symbol und fügen Sie ihn in die Prioritätswarteschlange ein.
- Solange mehr als ein Blatt in der Warteschlange ist, führen Sie Folgendes durch:
- Entfernen Sie die beiden Knoten mit der höchsten Priorität (mit der niedrigsten Frequenz) aus der Warteschlange;
- Erstellen Sie einen neuen inneren Knoten, bei dem diese beiden Knoten Nachfolger sind, und die Auftretensfrequenz beträgt die Summe der Frequenzen dieser beiden Knoten.
- Fügen Sie einen neuen Knoten in die Prioritätswarteschlange ein.
- Der einzige verbleibende Knoten wird die Wurzel sein, damit endet der Bau des Baums.
Stellen wir uns vor, wir haben einen bestimmten Text, der nur aus den Zeichen „a“, „b“, „c“, „d“ und „e“, und ihre Frequenzen sind 15, 7, 6, 6 und 5. Im Folgenden sind Illustrationen dargestellt, die die Schritte des Algorithmus verdeutlichen.
Der Weg von der Wurzel zu jedem Endknoten speichert den optimalen Präfixcode (auch bekannt als Huffman-Code), der dem Zeichen entspricht, das mit diesem Endknoten verbunden ist.
Huffman-Baum
Nachfolgend 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
{
// Durchqueren des Huffman-Baums und Speichern der Huffman-Codes
// in einer Map.
public static void encode(Node root, String str,
Map huffmanCode)
{
if (root == null)
return;
// 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);
}
// Durchqueren des Huffman-Baums und Dekodieren des kodierten Strings
public static int decode(Node root, int index, StringBuilder sb)
{
if (root == null)
return index;
// 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 den Huffman-Code und dekodiert den gegebenen Eingabetext
public static void buildHuffmanTree(String text)
{
// Häufigkeit des Vorkommens jedes Zeichens zählen
// und in einer Map speichern
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, um lebende Knoten des Huffman-Baums zu speichern
// 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 ihn
// 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
// (geringste 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-Baums
Node root = pq.peek();
// Durchqueren des Huffman-Baums und Speichern der Huffman-Codes in einer Map
Map huffmanCode = new HashMap();
encode(root, "", huffmanCode);
// Gebe die Huffman-Codes aus
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);
// Gebe den kodierten String aus
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);
// Durchqueren des Huffman-Baums erneut und diesmal
// 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 Eingabestring verwendete Speicher beträgt 47 * 8 = 376 Bit, während die kodierte Zeichenfolge nur 194 Bit benötigt. Das bedeutet, dass die Daten um etwa 48 % komprimiert werden. In dem oben stehenden C++-Programm verwenden wir die Klasse string zur Speicherung der kodierten Zeichenfolge, um das Programm leserlich zu machen.
Da effiziente Datenstrukturen für Prioritätswarteschlangen für das Einfügen O(log(N)) Zeit benötigen, und in einem vollständigen Binärbaum mit N Blättern vorhanden sind 2N-1 Knoten, und der Huffman-Baum ein vollständiger Binärbaum ist, läuft der Algorithmus in O(Nlog(N)) Zeit, wobei N die Anzahl der Symbole ist.
Quellen:
Quelle: habr.com
