Prima dell'inizio del corso hanno preparato per voi la traduzione di un altro utile materiale.
La codifica di Huffman è un algoritmo di compressione dei dati che formula l'idea principale della compressione dei file. In questo articolo parleremo di codifica a lunghezza fissa e variabile, codici univocamente decodificabili, regole di prefisso e costruzione dell'albero di Huffman.
Sappiamo che ogni simbolo è memorizzato come una sequenza di 0 e 1 e occupa 8 bit. Questo è conosciuto come codifica a lunghezza fissa, poiché ogni simbolo utilizza lo stesso numero fisso di bit per la memorizzazione.
Supponiamo di avere un testo. In che modo possiamo ridurre la quantità di spazio richiesta per memorizzare un singolo simbolo?
L'idea principale è nella codifica a lunghezza variabile. Possiamo sfruttare il fatto che alcuni simboli nel testo compaiono più frequentemente di altri (), per sviluppare un algoritmo che rappresenti la stessa sequenza di simboli con un minor numero di bit. Nella codifica a lunghezza variabile, attribuiamo ai simboli un numero variabile di bit in base alla frequenza della loro comparsa nel testo. Alla fine, alcuni simboli possono occupare solo 1 bit, mentre altri 2 bit, 3 o più. Il problema della codifica a lunghezza variabile riguarda solamente la successiva decodifica della sequenza.
Come fare per decodificare univocamente una sequenza di bit conosciuta?
Consideriamo la stringa «aabacdab». Contiene 8 simboli e, con codifica a lunghezza fissa, richiederebbe 64 bit per la sua memorizzazione. Notiamo che la frequenza dei simboli «a», «b», «c» e «d» è rispettivamente 4, 2, 1, 1. Proviamo a rappresentarla «aabacdab» con un numero minore di bit, sfruttando il fatto che «a» compare più frequentemente di «b», ma «b» compare più frequentemente di «c» e «d». Iniziamo codificando «a» con un bit, pari a 0, «b» attribuendo un codice di due bit pari a 11 e codificando con tre bit «c» e «d».
Alla fine otteniamo:
a
0
b
11
c
100
d
011
Così la stringa «aabacdab» la codificheremo come 00110100011011 (0|0|11|0|100|011|0|11), usando i codici indicati sopra. Tuttavia, il problema principale sarà nella decodifica. Quando proveremo a decodificare la stringa 00110100011011, otterremo un risultato ambivalente, poiché può essere rappresentata come:
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
…
ecc.
Per evitare questa ambiguità, dobbiamo garantire che la nostra codifica soddisfi il concetto di regola del prefisso, che implica che i codici possano essere decodificati in un modo unico. La regola del prefisso garantisce che nessun codice sia un prefisso di un altro. Con codice intendiamo i bit utilizzati per rappresentare un simbolo specifico. Nell'esempio sopra riportato, 0 è un prefisso 011, il che viola la regola del prefisso. Quindi, se i nostri codici soddisfano la regola del prefisso, la decodifica può avvenire in modo univoco (e viceversa).
Rivediamo l'esempio sopra. Questa volta assegneremo ai simboli «a», «b», «c» e «d» codici che soddisfano la regola del prefisso.
a
0
b
10
c
110
d
111
Utilizzando tale codifica, la stringa «aabacdab» verrà codificata come 00100100011010 (0|0|10|0|100|011|0|10). Ecco la 00100100011010 potremo già decodificare in modo univoco e tornare alla nostra stringa originale. «aabacdab».
Codifica di Huffman
Ora che abbiamo capito la codifica a lunghezza variabile e la regola del prefisso, parliamo della codifica di Huffman.
Il metodo si basa sulla creazione di alberi binari. In esso, un nodo può essere terminale o interno. Inizialmente, tutti i nodi sono considerati foglie (terminali), che rappresentano il simbolo stesso e il suo peso (cioè la frequenza di occorrenza). I nodi interni contengono il peso del simbolo e puntano a due nodi discendenti. Per convenzione, il bit "0" rappresenta il seguire il ramo sinistro, mentre "1" rappresenta il ramo destro. In un albero completo ci sono N fogli e N-1 nodi interni. Si consiglia di scartare i simboli non utilizzati durante la costruzione dell'albero di Huffman per ottenere codici di lunghezza ottimale.
Useremo una coda di priorità per costruire l'albero di Huffman, dove al nodo con la frequenza più bassa viene assegnata la priorità più alta. Di seguito sono descritti i passi per la costruzione:
- Creare un nodo foglia per ogni simbolo e aggiungerli alla coda di priorità.
- Finché nella coda ci sono più di una foglia, fare quanto segue:
- Rimuovere i due nodi con la priorità più alta (la frequenza più bassa) dalla coda;
- Creare un nuovo nodo interno, in cui questi due nodi saranno discendenti e la frequenza di occorrenza sarà la somma delle frequenze di questi due nodi.
- Aggiungere il nuovo nodo alla coda di priorità.
- L'unico nodo rimasto sarà la radice, e su questo la costruzione dell'albero si concluderà.
Immaginiamo di avere un certo testo, che consiste solo in caratteri «a», «b», «c», «d» e «e», e le frequenze di comparsa sono rispettivamente 15, 7, 6, 6 e 5. Di seguito sono riportate illustrazioni che riflettono i passi dell'algoritmo.
Il percorso dalla radice a qualsiasi nodo finale conterrà il codice ottimale del prefisso (noto anche come codice di Huffman), corrispondente al carattere associato a quel nodo finale.
Albero di Huffman
Di seguito troverai l'implementazione dell'algoritmo di compressione di Huffman nei linguaggi C++ e 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;
// Un nodo dell'albero
class Node
{
char ch;
int freq;
Node sinistra = null, destra = null;
Node(char ch, int freq)
{
this.ch = ch;
this.freq = freq;
}
public Node(char ch, int freq, Node sinistra, Node destra) {
this.ch = ch;
this.freq = freq;
this.sinistra = sinistra;
this.destra = destra;
}
};
class Huffman
{
// attraversa l'albero di Huffman e memorizza i codici di Huffman
// in una mappa.
public static void encode(Node radice, String str,
Map huffmanCode)
{
if (radice == null)
return;
// trovato un nodo foglia
if (radice.sinistra == null && radice.destra == null) {
huffmanCode.put(radice.ch, str);
}
encode(radice.sinistra, str + "0", huffmanCode);
encode(radice.destra, str + "1", huffmanCode);
}
// attraversa l'albero di Huffman e decodifica la stringa codificata
public static int decode(Node radice, int index, StringBuilder sb)
{
if (radice == null)
return index;
// trovato un nodo foglia
if (radice.sinistra == null && radice.destra == null)
{
System.out.print(radice.ch);
return index;
}
index++;
if (sb.charAt(index) == '0')
index = decode(radice.sinistra, index, sb);
else
index = decode(radice.destra, index, sb);
return index;
}
// Crea l'albero di Huffman e huffmanCode e decodifica il testo di input dato
public static void buildHuffmanTree(String text)
{
// conta la frequenza di apparizione di ogni carattere
// e memorizzala in una mappa
Map 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);
}
// Crea una coda di priorità per memorizzare i nodi attivi dell'albero di Huffman
// Nota che l'elemento con priorità più alta ha la frequenza più bassa
PriorityQueue pq = new PriorityQueue(
(l, r) -> l.freq - r.freq);
// Crea un nodo foglia per ogni carattere e aggiungilo
// alla coda di priorità.
for (Map.Entry entry : freq.entrySet()) {
pq.add(new Node(entry.getKey(), entry.getValue()));
}
// continua finché ci sono più di un nodo nella coda
while (pq.size() != 1)
{
// Rimuovi i due nodi di massima priorità
// (frequenza più bassa) dalla coda
Node sinistra = pq.poll();
Node destra = pq.poll();
// Crea un nuovo nodo interno con questi due nodi come figli
// e con frequenza uguale alla somma delle frequenze dei due nodi
// Aggiungi il nuovo nodo alla coda di priorità.
int somma = sinistra.freq + destra.freq;
pq.add(new Node(' ', somma, sinistra, destra));
}
// radice memorizza il puntatore alla radice dell'albero di Huffman
Node radice = pq.peek();
// percorre l'albero di Huffman e memorizza i codici di Huffman in una mappa
Map huffmanCode = new HashMap();
encode(radice, "", huffmanCode);
// stampa i codici di Huffman
System.out.println("I codici di Huffman sono :");
for (Map.Entry entry : huffmanCode.entrySet()) {
System.out.println(entry.getKey() + " " + entry.getValue());
}
System.out.println("La stringa originale era :" + text);
// stampa la stringa codificata
StringBuilder sb = new StringBuilder();
for (int i = 0 ; i < text.length(); i++) {
sb.append(huffmanCode.get(text.charAt(i)));
}
System.out.println("La stringa codificata è :" + sb);
// attraversa di nuovo l'albero di Huffman e questa volta
// decodifica la stringa codificata
int index = -1;
System.out.println("La stringa decodificata è: ");
while (index < sb.length() - 2) {
index = decode(radice, index, sb);
}
}
public static void main(String[] args)
{
String text = "La codifica di Huffman è un algoritmo di compressione dei dati.";
buildHuffmanTree(text);
}
}Nota: La memoria utilizzata dalla stringa di input è di 47 * 8 = 376 bit, mentre la stringa codificata occupa solo 194 bit, ovvero i dati vengono compressi di circa il 48%. Nel programma in C++ sopra, utilizziamo la classe string per memorizzare la stringa codificata, rendendo il programma più leggibile.
Poiché le strutture dati efficienti delle code di priorità richiedono un tempo di inserimento O(log(N)) e in un albero binario completo con N fogli ci sono 2N-1 nodi, e l'albero di Huffman è un albero binario completo, l'algoritmo funziona in O(Nlog(N)) tempo, dove N è il numero di simboli.
Fonti:
Fonte: habr.com
