In attesa dell'avvio del corso ha preparato per voi la traduzione di un altro materiale utile.
La codifica di Huffman è un algoritmo di compressione dei dati che crea la base per la 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 è chiamato codifica a lunghezza fissa, poiché ogni simbolo utilizza la stessa quantità fissa di bit per la memorizzazione.
Supponiamo di avere un testo. Come possiamo ridurre lo spazio necessario per memorizzare un simbolo?
L'idea principale è la codifica a lunghezza variabile. Possiamo sfruttare il fatto che alcuni simboli nel testo appaiono più frequentemente di altri (), per sviluppare un algoritmo che rappresenti la stessa sequenza di caratteri con un minor numero di bit. Nella codifica a lunghezza variabile, assegniamo ai caratteri un numero variabile di bit in base alla frequenza della loro apparizione nel testo. Alla fine, alcuni caratteri possono occupare solo 1 bit, mentre altri 2, 3 o più. Il problema della codifica a lunghezza variabile riguarda solo la successiva decodifica della sequenza.
Come si può decodificare in modo univoco conoscendo la sequenza di bit?
Consideriamo la stringa «aabacdab». Contiene 8 caratteri e, usando una codifica a lunghezza fissa, richiederà 64 bit per la sua memorizzazione. Notiamo che la frequenza dei caratteri «a», «b», «c» e «d» è di 4, 2, 1, 1 rispettivamente. Proviamo a rappresentare «aabacdab» con un numero minore di bit, utilizzando il fatto che «a» compare più spesso di «b», e «b» compare più spesso di «c» e «d». Iniziamo codificando «a» con un bit, pari a 0, «b» assegneremo un codice di due bit pari a 11, e utilizzeremo tre bit per codificare 100 e 011. «c» e «d».
Alla fine otterremo:
a
0
b
11
c
100
d
011
Così codificheremo la stringa «aabacdab» come 00110100011011 (0|0|11|0|100|011|0|11), utilizzando i codici presentati sopra. Tuttavia, il problema principale sarà nella decodifica. Quando proveremo a decodificare la stringa 00110100011011, otterremo un risultato ambiguo, poiché può essere rappresentato 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 un concetto chiamato regola del prefisso, il quale implica che i codici possono 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 0 – è un prefisso 011, il che viola la regola del prefisso. Quindi, se i nostri codici soddisfano la regola del prefisso, la decodifica può essere effettuata 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» sarà codificata come 00100100011010 (0|0|10|0|100|011|0|10). Ecco 00100100011010 saremo in grado di decodificare e tornare alla nostra stringa originale «aabacdab».
Codifica di Huffman
Ora che abbiamo compreso 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 sia foglia che nodo interno. Inizialmente, tutti i nodi sono considerati foglie (finali), che rappresentano il simbolo stesso e il suo peso (cioè la frequenza di occorrenza). I nodi interni contengono il peso del simbolo e fanno riferimento a due nodi figli. Per convenzione, il bit «0» rappresenta il seguito lungo il ramo sinistro, mentre «1» rappresenta il ramo destro. In un albero completo N di foglie e N-1 nodi interni. È consigliabile escludere i simboli non utilizzati durante la costruzione dell'albero di Huffman per ottenere codici di lunghezza ottimale.
Utilizzeremo una coda di priorità per costruire l'albero di Huffman, dove al nodo con la frequenza più bassa verrà assegnata la massima priorità. Di seguito sono descritti i passaggi per la costruzione:
- Crea un nodo foglia per ogni simbolo e aggiungili alla coda di priorità.
- Finché ci sono più di un foglia nella coda, procedi come segue:
- Rimuovi i due nodi con la priorità più alta (con la frequenza più bassa) dalla coda;
- Crea un nuovo nodo interno in cui questi due nodi saranno discendenti, e la frequenza di apparizione sarà pari alla somma delle frequenze di questi due nodi.
- Aggiungi un nuovo nodo alla coda di priorità.
- L'unico nodo rimanente sarà la radice, e la costruzione dell'albero sarà completata.
Immaginiamo di avere un certo testo composto solo dai caratteri «a», «b», «c», «d» e «e», e le frequenze della loro apparizione sono uguali a 15, 7, 6, 6 e 5 rispettivamente. Di seguito sono riportate delle illustrazioni che riflettono i passaggi dell'algoritmo.
Il percorso dalla radice a qualsiasi nodo finale conterrà il codice prefisso ottimale (noto anche come codice di Huffman), corrispondente al carattere associato a questo 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
{
// traversa l'albero di Huffman e memorizza i codici Huffman
// in una mappa.
public static void encode(Node root, String str,
Map huffmanCode)
{
if (root == null)
return;
// trovato un nodo foglia
if (root.sinistra == null && root.destra == null) {
huffmanCode.put(root.ch, str);
}
encode(root.sinistra, str + "0", huffmanCode);
encode(root.destra, str + "1", huffmanCode);
}
// traversa l'albero di Huffman e decodifica la stringa codificata
public static int decode(Node root, int index, StringBuilder sb)
{
if (root == null)
return index;
// trovato un nodo foglia
if (root.sinistra == null && root.destra == null)
{
System.out.print(root.ch);
return index;
}
index++;
if (sb.charAt(index) == '0')
index = decode(root.sinistra, index, sb);
else
index = decode(root.destra, index, sb);
return index;
}
// Costruisce l'albero di Huffman e huffmanCode e decodifica il testo di input fornito
public static void buildHuffmanTree(String text)
{
// conta la frequenza di apparizione di ciascun carattere
// e memorizzalo 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 vivi dell'albero di Huffman
// Nota che l'elemento di priorità più alta ha la frequenza più bassa
PriorityQueue pq = new PriorityQueue(
(l, r) -> l.freq - r.freq);
// Crea un nodo foglia per ciascun 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 priorità più alta
// (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 sum = sinistra.freq + destra.freq;
pq.add(new Node(' ', sum, sinistra, destra));
}
// root memorizza il puntatore alla radice dell'albero di Huffman
Node root = pq.peek();
// traversa l'albero di Huffman e memorizza i codici Huffman in una mappa
Map huffmanCode = new HashMap();
encode(root, "", huffmanCode);
// stampa i codici Huffman
System.out.println("I codici Huffman sono :\n");
for (Map.Entry entry : huffmanCode.entrySet()) {
System.out.println(entry.getKey() + " " + entry.getValue());
}
System.out.println("\nLa stringa originale era :\n" + 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("\nLa stringa codificata è :\n" + sb);
// traversa nuovamente l'albero di Huffman e questa volta
// decodifica la stringa codificata
int index = -1;
System.out.println("\nLa stringa decodificata è: \n");
while (index < sb.length() - 2) {
index = decode(root, index, sb);
}
}
public static void main(String[] args)
{
String text = "Il coding 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, il che significa che i dati sono compressi di circa il 48%. Nel programma C++ sopra, utilizziamo la classe string per memorizzare la stringa codificata, rendendo così il programma leggibile.
Poiché le strutture dati efficienti per le code di priorità richiedono tempo per l'inserimento O(log(N)) e in un albero binario completo con N foglie 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
