Código de Huffman

El código de Huffman es un algoritmo de compresión de datos sin pérdida. En este algoritmo, se asignan códigos de longitud variable para diferentes caracteres. La longitud del código está relacionada con la frecuencia de uso del carácter. Los caracteres más frecuentes tienen los códigos más cortos, mientras que los códigos más largos se utilizan para los caracteres menos frecuentes.

Hay principalmente dos partes. La primera es crear el árbol de Huffman, y la otra es recorrer el árbol para encontrar los códigos.

por ejemplo, considera algunas cadenas 'YYYZXXYYX', la frecuencia del carácter Y es mayor que X, y la frecuencia del carácter Z es la más baja. Por lo tanto, la longitud del código de Y es menor que la de X, y la longitud del código de X será menor que la de Z.

• La complejidad de asignar códigos basados en la frecuencia de cada carácter es O(n log n)

input　-cadenas de caracteres diferentes, por ejemplo, 'ACCEBFFFFAAXXBLKE'.
output　-los códigos de caracteres diferentes:

Data:　K,　Frequency:　1,　Code:　0000
Data:　L,　Frequency:　1,　Code:　0001
Data:　E,　Frequency:　2,　Code:　001
Data:　F,　Frequency:　4,　Code:　01
Data:　B,　Frequency:　2,　Code:　100
Data:　C,　Frequency:　2,　Code:　101
Data:　X,　Frequency:　2,　Code:　110
Data:　A,　Frequency:　3,　Code:　111

algoritmo

huffmanCoding (cadena)

input-cadenas de caracteres diferentes.

output-el código de cada carácter.

comienzo
　　　definir un nodo con carácter, frecuencia, hijo izquierdo y derecho del nodo para el árbol de Huffman.
　　　crea una lista 'freq' para almacenar la frecuencia de cada carácter, inicialmente todas son 0
　　　para cada carácter c en la cadena hacer
　　　　　　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-each character assigned code

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.

ejemplo

#include<iostream>
#include<queue>
#include<string>
using namespace std;
struct node{
　　　int freq;
　　　char data;
　　　const node　*child0,　*hijo1;
　　　node(char d, int f =　-1{　//assign values in the node
　　　　　　data = d;
　　　　　　freq = f;
　　　　　　child0 = NULL;
　　　　　　hijo1　= NULL;
　　　}
　　　node(const node　*c0, const node　*c1{
　　　　　　data = 0;
　　　　　　freq = c0->freq　+　c1->freq;
　　　　　　hijo0=c0;
　　　　　　hijo1=c1;
　　　}
　　　bool operador<　(const　nodo　&a　)　const　{　//< operador realiza para encontrar la prioridad en la cola
　　　　　　return freq > a.freq;
　　　}
　　　void　recorrer(string código = "")const{
　　　　　　if(hijo0!=NULL){
　　　　　　　　　hijo0->recorrer(código+'0');　//agregar 0 con el código como hijo izquierdo
　　　　　　　　　hijo1->recorrer(código+'1);　//agregar　1　con el código como hijo derecho
　　　　　　}else{
　　　　　　　　　cout << "Datos: " << data << "，Frecuencia: " << freq << "，Código: " << code << endl;
　　　　　　}
　　　}
};
void　codificaciónHuffman(string　str){
　　　cola_de_prioridad<nodo>　qu;
　　　int　frecuencia[256];
　　　for(int　i　=　0;　i<256;　i++)
　　　　　　frecuencia[i] = 0;　//limpiar toda la frecuencia
　　　for(int　i　=　0;　i<str.tamaño();　i++{
　　　　　　frecuencia[int(str[i])]++;　//aumentar la frecuencia
　　　}
　　　for(int　i　=　0;　i<256;　i++{
　　　　　　if(frecuencia[i]){
　　　　　　　　　qu.push(nodo(i, frecuencia[i]));
　　　　　　}
　　　}
　　　while(qu.tamaño() >1{
　　　　　　nodo　*c0 = new nodo(qu.top());　//obtener el hijo izquierdo y eliminarlo de la cola
　　　　　　qu.pop();
　　　　　　nodo　*c1　= new nodo(qu.top());　//obtener el hijo derecho y eliminarlo de la cola
　　　　　　qu.pop();
　　　　　　qu.push(nodo(c0, c1));　//agregar la frecuencia de dos hijos y agregarlo nuevamente en la cola
　　　}
　　　cout << "El Código Huffman: " << endl;
　　　qu.top().recorrer();　//recorrer el árbol para obtener el código
}
main(){
　　　cadena str = "ACCEBFFFFAAXXBLKE";　//Cadena arbitraria para obtener frecuencia
　　　huffmanCoding(str);
}

Resultados de salida

El Código Huffman
Data:　K,　Frequency:　1,　Code:　0000
Data:　L,　Frequency:　1,　Code:　0001
Data:　E,　Frequency:　2,　Code:　001
Data:　F,　Frequency:　4,　Code:　01
Data:　B,　Frequency:　2,　Code:　100
Data:　C,　Frequency:　2,　Code:　101
Data:　X,　Frequency:　2,　Code:　110
Data:　A,　Frequency:　3,　Code:　111