Huffman-Kodierung

Huffman-Kodierung ist ein verlustfreies Datenkomprimierungsverfahren. In diesem Algorithmus werden variable Längen-Codes für verschiedene Zeichen zugewiesen. Die Länge des Codes ist mit der Häufigkeit des Zeichens verbunden. Die häufigsten Zeichen haben den kürzesten Code, während längere Codes für die weniger häufigen Zeichen verwendet werden.

Es gibt hauptsächlich zwei Teile. Der erste erstellt ein Huffman-Baum, der andere das Baum durchsucht, um den Code zu finden.

Zum Beispiel, betrachten wir einige Zeichenfolgen 'YYYZXXYYX', die Häufigkeit des Zeichens Y ist größer als die des Zeichens X, die Häufigkeit des Zeichens Z ist am geringsten. Daher ist die Länge des Codes von Y kürzer als die des Zeichens X, die Länge des Codes von X wird kürzer als die des Zeichens Z.

• Die Komplexität der Zuweisung von Codes basierend auf der Häufigkeit jedes Zeichens beträgt O(n log n)

input　-Zeichenfolgen mit verschiedenen Zeichen, z.B. 'ACCEBFFFFAAXXBLKE'.
output　-Der Code verschiedener Zeichen:

Daten:　K,　Häufigkeit:　1,　Code:　0000
Daten:　L,　Häufigkeit:　1,　Code:　0001
Daten:　E,　Häufigkeit:　2,　Code:　001
Daten:　F,　Häufigkeit:　4,　Code:　01
Daten:　B,　Häufigkeit:　2,　Code:　100
Daten:　C,　Häufigkeit:　2,　Code:　101
Daten:　X,　Häufigkeit:　2,　Code:　110
Daten:　A,　Häufigkeit:　3,　Code:　111

Algorithmus

huffmanCoding（Zeichenkette）

input-Zeichenfolgen mit verschiedenen Zeichen.

output-Der Code jedes Zeichens.

Beginne
　　　Definieren Sie einen Knoten mit dem Zeichen, der Häufigkeit, linken und rechten Kindknoten des Knotens für das Huffman-Baum.
　　　Erstellen Sie eine Liste 'freq', um die Häufigkeit jedes Zeichens zu speichern, die alle initial auf 0 gesetzt sind
　　　Für jedes Zeichen c in der Zeichenkette wird ausgeführt
　　　　　　increase the frequency for character ch in freq list.
　　　done
　　　for all type of character ch do
　　　　　　if the frequency of ch is non zero then add ch and its frequency as a node of priority queue Q.
　　　done
　　　while Q is not empty do
　　　　　　remove item from Q and assign it to left child of node
　　　　　　remove item from Q and assign to the right child of node
　　　　　　traverse the node to find the assigned code
　　　done
End

traverseNode(n: node, code)

input-Huffman tree node n, and the code assigned in the last call　

output-code assigned to each character

if left child of node n ≠ φ then
　　　traverseNode(leftChild(n), code+’0’)　//traverse through the left child
　　　traverseNode(rightChild(n), code+’1’)　//traverse through the right child
else
　　　display the character and data of current node.

示例

#include<iostream>
#include<queue>
#include<string>
using namespace std;
struct node{
　　　int freq;
　　　char data;
　　　const node　*child0,　*Kind1;
　　　node(char d, int f =　-1{　//assign values in the node
　　　　　　data = d;
　　　　　　freq = f;
　　　　　　child0 = NULL;
　　　　　　Kind1　= NULL;
　　　}
　　　node(const node　*c0, const node　*c1{
　　　　　　data = 0;
　　　　　　freq = c0->freq　+　c1->freq;
　　　　　　child0=c0;
　　　　　　Kind1=c1;
　　　}
　　　bool operator<(const node &a) const {　//< Operator führt zur Priorität in der Warteschlange aus
　　　　　　return freq > a.freq;
　　　}
　　　void durchsuche(string code = "")const{
　　　　　　if(child0!=NULL){
　　　　　　　　　child0->durchsuche(code+'0');　//füge 0 hinzu, wenn der Code als linkes Kind
　　　　　　　　　Kind1->durchsuche(code+'1);　//hinzufügen　1　mit dem Code als rechtem Kind
　　　　　　}else{
　　　　　　　　　cout << "Daten: " << data << ", Häufigkeit: " << freq << ", Code: " << code << endl;
　　　　　　}
　　　}
};
void huffmanCoding(string str){
　　　priority_queue<node> qu;
　　　int frequency[256;
　　　for(int i = 0; i<256;　i++)
　　　　　　frequency[i] = 0;　//lösche alle Häufigkeiten
　　　for(int i = 0; i<str.size(); i++{
　　　　　　frequency[int(str[i])]++;　//erhöhe die Häufigkeit
　　　}
　　　for(int i = 0; i<256;　i++{
　　　　　　if(frequency[i]){
　　　　　　　　　qu.push(node(i, frequency[i]));
　　　　　　}
　　　}
　　　while(qu.size() >1{
　　　　　　node　*c0 = new node(qu.top());　//hole das linke Kind und entferne es aus der Warteschlange
　　　　　　qu.pop();
　　　　　　node　*c1　= new node(qu.top());　//hole das rechte Kind und entferne es aus der Warteschlange
　　　　　　qu.pop();
　　　　　　qu.push(node(c0, c1));　//fge die Häufigkeit beider Kinder hinzu und füge sie dann wieder in die Warteschlange hinzu
　　　}
　　　cout << "Der Huffman-Code: " << endl;
　　　qu.top().durchsuche();　//durchsuche den Baum, um den Code zu erhalten
}
main(){
　　　string str = "ACCEBFFFFAAXXBLKE";　//arbitray string to get frequency
　　　huffmanCoding(str);
}

Ausgaberesultat

Der Huffman-Code:
Daten:　K,　Häufigkeit:　1,　Code:　0000
Daten:　L,　Häufigkeit:　1,　Code:　0001
Daten:　E,　Häufigkeit:　2,　Code:　001
Daten:　F,　Häufigkeit:　4,　Code:　01
Daten:　B,　Häufigkeit:　2,　Code:　100
Daten:　C,　Häufigkeit:　2,　Code:　101
Daten:　X,　Häufigkeit:　2,　Code:　110
Daten:　A,　Häufigkeit:　3,　Code:　111