Vor Kursbeginn Wir haben für Sie eine Übersetzung eines weiteren nützlichen Materials vorbereitet.
Die Huffman-Codierung ist ein Datenkomprimierungsalgorithmus, der die Grundidee der Dateikomprimierung formuliert. In diesem Artikel werden wir über die Kodierung fester und variabler Länge, eindeutig dekodierbare Codes, Präfixregeln und den Aufbau eines Huffman-Baums sprechen.
Wir wissen, dass jedes Zeichen als Folge von Nullen und Einsen gespeichert wird und 0 Bits belegt. Dies wird als Codierung mit fester Länge bezeichnet, da jedes Zeichen zum Speichern dieselbe feste Anzahl von Bits verwendet.
Nehmen wir an, wir erhalten einen Text. Wie können wir den Platzbedarf zum Speichern eines einzelnen Zeichens reduzieren?
Die Hauptidee ist die Codierung mit variabler Länge. Wir können die Tatsache nutzen, dass einige Zeichen im Text häufiger vorkommen als andere (), um einen Algorithmus zu entwickeln, der dieselbe Zeichenfolge in weniger Bits darstellt. Bei der Codierung mit variabler Länge weisen wir Zeichen eine variable Anzahl von Bits zu, je nachdem, wie oft sie in einem bestimmten Text vorkommen. Letztendlich benötigen manche Zeichen nur 1 Bit, während andere 2, 3 oder mehr Bits benötigen. Das Problem bei der Codierung mit variabler Länge besteht lediglich in der anschließenden Decodierung der Sequenz.
Wie kann man die Bitfolge eindeutig dekodieren, wenn man sie kennt?
Betrachten Sie die Linie „abacdab“. Es hat 8 Zeichen und bei der Codierung einer festen Länge werden 64 Bit zum Speichern benötigt. Beachten Sie die Symbolfrequenz „a“, „b“, „c“ и "D" entspricht 4, 2, 1 bzw. 1. Versuchen wir es uns vorzustellen „abacdab“ weniger Bits, unter Ausnutzung der Tatsache, dass "zu" kommt häufiger vor als "B"Und "B" kommt häufiger vor als "gegen" и "D". Beginnen wir mit dem Codieren "zu" mit einem Bit gleich 0, "B" Wir werden einen Zwei-Bit-Code 11 zuweisen und mit den drei Bits 100 und 011 kodieren "gegen" и "D".
Als Ergebnis erhalten wir:
a
0
b
11
c
100
d
011
Also die Zeile „abacdab“ wir werden als kodieren 00110100011011 (0|0|11|0|100|011|0|11)unter Verwendung der oben genannten Codes. Das Hauptproblem wird jedoch in der Dekodierung liegen. Wenn wir versuchen, die Zeichenfolge zu dekodieren 00110100011011erhalten wir ein mehrdeutiges Ergebnis, da es wie folgt 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 Codierung einem Konzept wie folgt Präfixregel, was wiederum bedeutet, dass die Codes nur auf eine eindeutige Weise dekodiert werden können. Die Präfixregel stellt sicher, dass kein Code ein Präfix eines anderen ist. Mit Code meinen wir die Bits, die zur Darstellung eines bestimmten Zeichens verwendet werden. Im Beispiel oben 0 ist ein Präfix 011, was gegen die Präfixregel verstößt. Wenn unsere Codes also die Präfixregel erfüllen, können wir eindeutig dekodieren (und umgekehrt).
Schauen wir uns das obige Beispiel noch einmal an. Dieses Mal werden wir Symbole zuweisen „a“, „b“, „c“ и "D" Codes, die die Präfixregel erfüllen.
a
0
b
10
c
110
d
111
Mit dieser Codierung ist die Zeichenfolge „abacdab“ wird kodiert als 00100100011010 (0|0|10|0|100|011|0|10). Aber die 00100100011010 Wir werden bereits in der Lage sein, unsere ursprüngliche Zeichenfolge eindeutig zu dekodieren und zu ihr zurückzukehren „abacdab“.
Huffman-Codierung
Nachdem wir uns nun mit der Codierung variabler Länge und der Präfixregel befasst haben, sprechen wir über die Huffman-Codierung.
Die Methode basiert auf der Erstellung binärer Bäume. Darin kann der Knoten entweder final oder intern sein. Zunächst werden alle Knoten als Blätter (Terminals) betrachtet, die das Symbol selbst und sein Gewicht (d. h. die Häufigkeit des Auftretens) darstellen. Die internen Knoten enthalten die Gewichtung des Zeichens und verweisen auf zwei untergeordnete Knoten. Nach allgemeiner Vereinbarung, Bit «0» steht für das Folgen des linken Zweigs und «1» - auf der rechten Seite. im vollen Baum N Blätter und N-1 interne Knoten. Es wird empfohlen, beim Erstellen eines Huffman-Baums nicht verwendete Symbole zu verwerfen, um Codes mit optimaler Länge zu erhalten.
Wir werden eine Prioritätswarteschlange verwenden, um einen Huffman-Baum zu erstellen, in dem der Knoten mit der niedrigsten Häufigkeit die höchste Priorität erhält. Nachfolgend werden die Bauschritte beschrieben:
- Erstellen Sie für jedes Zeichen einen Blattknoten und fügen Sie es der Prioritätswarteschlange hinzu.
- Gehen Sie wie folgt vor, solange sich mehr als ein Blatt in der Warteschlange befindet:
- Entfernen Sie die beiden Knoten mit der höchsten Priorität (niedrigste Häufigkeit) aus der Warteschlange.
- Erstellen Sie einen neuen internen Knoten, in dem diese beiden Knoten untergeordnet sind und die Häufigkeit des Auftretens der Summe der Häufigkeiten dieser beiden Knoten entspricht.
- Fügen Sie der Prioritätswarteschlange einen neuen Knoten hinzu.
- Der einzige verbleibende Knoten ist die Wurzel, und damit ist die Konstruktion des Baums abgeschlossen.
Stellen Sie sich vor, wir hätten einen Text, der nur aus Zeichen besteht "A B C D" и "und"und ihre Auftrittshäufigkeiten betragen 15, 7, 6, 6 bzw. 5. Nachfolgend finden Sie Abbildungen, die die Schritte des Algorithmus widerspiegeln.
Ein Pfad von der Wurzel zu einem beliebigen Endknoten speichert den optimalen Präfixcode (auch als Huffman-Code bekannt), der dem mit diesem Endknoten verknüpften Zeichen entspricht.
Huffman-Baum
Nachfolgend finden Sie die Implementierung des Huffman-Komprimierungsalgorithmus 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;
// A Tree node
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
{
// traverse the Huffman Tree and store Huffman Codes
// in a map.
public static void encode(Node root, String str,
Map<Character, String> huffmanCode)
{
if (root == null)
return;
// found a leaf node
if (root.left == null && root.right == null) {
huffmanCode.put(root.ch, str);
}
encode(root.left, str + "0", huffmanCode);
encode(root.right, str + "1", huffmanCode);
}
// traverse the Huffman Tree and decode the encoded string
public static int decode(Node root, int index, StringBuilder sb)
{
if (root == null)
return index;
// found a leaf node
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;
}
// Builds Huffman Tree and huffmanCode and decode given input text
public static void buildHuffmanTree(String text)
{
// count frequency of appearance of each character
// and store it in a map
Map<Character, Integer> 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);
}
// Create a priority queue to store live nodes of Huffman tree
// Notice that highest priority item has lowest frequency
PriorityQueue<Node> pq = new PriorityQueue<>(
(l, r) -> l.freq - r.freq);
// Create a leaf node for each character and add it
// to the priority queue.
for (Map.Entry<Character, Integer> entry : freq.entrySet()) {
pq.add(new Node(entry.getKey(), entry.getValue()));
}
// 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.poll();
Node right = pq.poll();
// 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.add(new Node('', sum, left, right));
}
// root stores pointer to root of Huffman Tree
Node root = pq.peek();
// traverse the Huffman tree and store the Huffman codes in a map
Map<Character, String> huffmanCode = new HashMap<>();
encode(root, "", huffmanCode);
// print the Huffman codes
System.out.println("Huffman Codes are :n");
for (Map.Entry<Character, String> entry : huffmanCode.entrySet()) {
System.out.println(entry.getKey() + " " + entry.getValue());
}
System.out.println("nOriginal string was :n" + text);
// print encoded string
StringBuilder sb = new StringBuilder();
for (int i = 0 ; i < text.length(); i++) {
sb.append(huffmanCode.get(text.charAt(i)));
}
System.out.println("nEncoded string is :n" + sb);
// traverse the Huffman Tree again and this time
// decode the encoded string
int index = -1;
System.out.println("nDecoded string is: n");
while (index < sb.length() - 2) {
index = decode(root, index, sb);
}
}
public static void main(String[] args)
{
String text = "Huffman coding is a data compression algorithm.";
buildHuffmanTree(text);
}
}Hinweis: Der von der Eingabezeichenfolge verwendete Speicher beträgt 47 * 8 = 376 Bit und die codierte Zeichenfolge umfasst nur 194 Bit, d. h. Die Daten werden um ca. 48 % komprimiert. Im obigen C++-Programm verwenden wir die String-Klasse, um den codierten String zu speichern und das Programm lesbar zu machen.
Weil effiziente Prioritätswarteschlangendatenstrukturen pro Einfügung erfordern O(log(N)) Zeit, aber in einem vollständigen Binärbaum mit N Blätter vorhanden 2N-1 Knoten und der Huffman-Baum ein vollständiger Binärbaum ist, wird der Algorithmus ausgeführt O(Nlog(N)) Zeit, wo N - Figuren.
Quellen:
Source: habr.com