Codifica di Huffman

Huffman coding is a lossless data compression algorithm. In this algorithm, variable length codes are assigned to input different characters. The code length is related to the frequency of use of the character. The most frequently used characters have the shortest codes, and longer codes are used for the least frequently used characters.

There are mainly two parts. The first one creates the Huffman tree, and the other traverses the tree to find the codes.

For example, consider some strings “YYYZXXYYX”, the frequency of character Y is greater than X, and the frequency of character Z is the smallest. Therefore, the code length of Y is less than X, and the code length of X will be less than Z.

• The complexity of assigning codes based on the frequency of each character is O(n log n)

Input　- String of different characters, for example “ACCEBFFFFAAXXBLKE”.
Output　- Codes for different characters:

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

Algorithm

huffmanCoding（string）

Input- String of different characters.

Output- Each character's code.

Begin
　　　define a node with character, frequency, left and right child of the node for Huffman tree.
　　　create a list ‘freq’ to store frequency of each character, initially all are 0
　　　for each character c in the string do
　　　　　　increase the frequency for character ch in freq list.
　　　fatto
　　　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.
　　　fatto
　　　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
　　　fatto
Fine

traverseNode(n: nodo, codice)

Input-Il nodo n dell'albero di Huffman e il codice assegnato nell'ultima chiamata　

Output-Codice assegnato a ogni carattere

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
　　　visualizza il carattere e i dati del nodo corrente.

Esempio

#include<iostream>
#include<queue>
#include<string>
using namespace std;
struct node{
　　　int freq;
　　　char data;
　　　const node *child0, *child1;
　　　node(char d, int f = -1) { // assign values in the node
　　　　　　data = d;
　　　　　　freq = f;
　　　　　　child0 = NULL;
　　　　　　child1 = NULL;
　　　}
　　　node(const node *c0, const node *c1){
　　　　　　data = 0;
　　　　　　freq = c0->freq + c1->freq;
　　　　　　child0 = c0;
　　　　　　child1 = c1;
　　　}
　　　bool operator< (const node &a) const { // < operator performs to find priority in queue
　　　　　　return freq > a.freq;
　　　}
　　　void traverse(string code = "") const {
　　　　　　if(child0 != NULL) {
　　　　　　　　　child0->traverse(code + '0'); // aggiungi 0 con il codice come figlio sinistro
　　　　　　　　　child1->traverse(code + '1'); // aggiungi 1 con il codice come figlio destro
　　　　　　} else {
　　　　　　　　　cout << "Dati: " << data << ", Frequenza: " << freq << ", Codice: " << code << endl;
　　　　　　}
　　　}
};
void huffmanCoding(string str) {
　　　priority_queue<node> qu;
　　　int frequency[256];
　　　for(int i = 0; i < 256; i++) {
　　　　　　frequency[i] = 0; // pulisci tutte le frequenze
　　　for(int i = 0; i < str.size(); i++) {
　　　　　　frequency[int(str[i])]++;
    // aumenta la frequenza
　　　}
　　　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()); // ottieni il figlio sinistro e rimuovilo dalla coda
　　　　　　qu.pop();
　　　　　　node *c1 = new node(qu.top()); // ottieni il figlio destro e rimuovilo dalla coda
　　　　　　qu.pop();
　　　　　　qu.push(node(c0, c1)); // aggiungi la frequenza dei due figli e aggiungi di nuovo nella coda
　　　}
　　　cout << "Il codice Huffman: " << endl;
　　　qu.top().traverse(); // esplora l'albero per ottenere il codice
}
main() {
　　　string str = "ACCEBFFFFAAXXBLKE"; // string arbitraria per ottenere la frequenza
　　　huffmanCoding(str);
}

Risultato dell'output

Il Codice di Huffman:
Data: K, Frequenza: 1, Codice: 0000
Data: L, Frequenza: 1, Codice: 0001
Data: E, Frequenza: 2, Codice: 001
Data: F, Frequenza: 4, Codice: 01
Data: B, Frequenza: 2, Codice: 100
Data: C, Frequenza: 2, Codice: 101
Data: X, Frequenza: 2, Codice: 110
Data: A, Frequenza: 3, Codice: 111