Codage Huffman

L'encodage Huffman est un algorithme de compression de données sans perte. Dans cet algorithme, des codes de longueur variable sont attribués aux différents caractères. La longueur du code est liée à la fréquence d'utilisation du caractère. Les caractères les plus fréquents ont les plus petits codes, tandis que les codes plus longs sont utilisés pour les caractères les moins fréquents.

Il y a principalement deux parties. La première crée un arbre d'Huffman, et la seconde parcourt cet arbre pour trouver les codes.

Par exemple, considérons certaines chaînes de caractères « YYYZXXYYX », la fréquence du caractère Y est supérieure à celle de X, et la fréquence du caractère Z est la plus petite. Par conséquent, la longueur du code de Y est inférieure à celle de X, et la longueur du code de X sera inférieure à celle de Z.

• La complexité de l'allocation de codes en fonction de la fréquence de chaque caractère est de O(n log n)

Input　-Chaîne de caractères de caractères différents, par exemple « ACCEBFFFFAAXXBLKE ».
Output　-Codes de caractères différents :

Données: K, Fréquence:　1, Code: 0000
Données: L, Fréquence:　1, Code: 0001
Données: E, Fréquence:　2, Code: 001
Données: F, Fréquence:　4, Code: 01
Données: B, Fréquence:　2, Code:　100
Données: C, Fréquence:　2, Code:　101
Données: X, Fréquence:　2, Code:　110
Données: A, Fréquence:　3, Code:　111

algorithme

huffmanCoding（chaîne de caractères）

Input-Chaîne de caractères de caractères différents.

Output-Code pour chaque caractère.

Début
　　　définir un nœud avec le caractère, la fréquence, le fils gauche et le fils droit du nœud pour l'arbre d'Huffman.
　　　créer une liste 'freq' pour stocker la fréquence de chaque caractère, initialement toutes sont à 0
　　　pour chaque caractère c dans la chaîne, effectuer
　　　　　　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.

Exemple

#include<iostream>
#include<queue>
#include<string>
using namespace std;
struct node{
　　　int freq;
　　　char data;
　　　const node　*child0,　*enfant1;
　　　node(char d, int f =　-1{　//assign values in the node
　　　　　　data = d;
　　　　　　freq = f;
　　　　　　child0 = NULL;
　　　　　　enfant1　= NULL;
　　　}
　　　node(const node　*c0, const node　*c1{
　　　　　　data = 0;
　　　　　　freq = c0->freq　+　c1->freq;
　　　　　　enfant0=c0;
　　　　　　enfant1=c1;
　　　}
　　　bool opérateur< const noeud &a const {　//< opérateur effectue pour trouver la priorité dans la file
　　　　　　return freq > a.freq;
　　　}
　　　void parcourir(string code = "")const{
　　　　　　if(enfant0!=NULL){
　　　　　　　　　enfant0->parcourir(code+'0');　//ajouter 0 avec le code en tant qu'enfant gauche
　　　　　　　　　enfant1->parcourir(code+'1);　//ajouter　1　avec le code en tant qu'enfant droit
　　　　　　}else{
　　　　　　　　　cout << "Données: " << data << ", Fréquence: " << freq << ", Code: " << code << endl;
　　　　　　}
　　　}
};
void huffmanCoding(string str){
　　　filePriorité<noeud> qu;
　　　int fréquence[256];
　　　for(int i = 0; i<256;　i++)
　　　　　　fréquence[i] = 0;　//effacer toutes les fréquences
　　　for(int i = 0; i<str.size(); i++{
　　　　　　fréquence[int(str[i])]++;　//augmenter la fréquence
　　　}
　　　for(int i = 0; i<256;　i++{
　　　　　　if(fréquence[i]){
　　　　　　　　　qu.push(noeud(i, fréquence[i]));
　　　　　　}
　　　}
　　　while(qu.size() >1{
　　　　　　noeud　*c0 = new noeud(qu.top());　//obtenir l'enfant gauche et le supprimer de la file
　　　　　　qu.pop();
　　　　　　noeud　*c1　= new noeud(qu.top());　//obtenir l'enfant droit et le supprimer de la file
　　　　　　qu.pop();
　　　　　　qu.push(noeud(c0, c1));　//ajouter la fréquence des deux enfants et l'ajouter à nouveau dans la file
　　　}
　　　cout << "Le Code Huffman: " << endl;
　　　qu.top().parcourir();　//parcourir l'arbre pour obtenir le code
}
main(){
　　　string str = "ACCEBFFFFAAXXBLKE";　//Chaine arbitraire pour obtenir la fréquence
　　　huffmanCoding(str);
}

Résultat de la sortie

Le Code Huffman:
Données: K, Fréquence:　1, Code: 0000
Données: L, Fréquence:　1, Code: 0001
Données: E, Fréquence:　2, Code: 001
Données: F, Fréquence:　4, Code: 01
Données: B, Fréquence:　2, Code:　100
Données: C, Fréquence:　2, Code:　101
Données: X, Fréquence:　2, Code:　110
Données: A, Fréquence:　3, Code:　111