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
