Prima dell'inizio del corso preparato per te una traduzione di altro materiale utile.
La codifica di Huffman è un algoritmo di compressione dei dati che formula l'idea di base della compressione dei file. In questo articolo parleremo di codifica a lunghezza fissa e variabile, codici decodificabili in modo univoco, regole di prefisso e costruzione di un albero di Huffman.
Sappiamo che ogni carattere è memorizzato come una sequenza di 0 e 1 e occupa 8 bit. Questa è chiamata codifica a lunghezza fissa perché ogni carattere utilizza lo stesso numero fisso di bit da memorizzare.
Diciamo che ci viene dato del testo. Come possiamo ridurre la quantità di spazio necessaria per memorizzare un singolo carattere?
L'idea principale è la codifica a lunghezza variabile. Possiamo sfruttare il fatto che alcuni caratteri nel testo ricorrono più spesso di altri () per sviluppare un algoritmo che rappresenterà la stessa sequenza di caratteri in meno bit. Nella codifica a lunghezza variabile, assegniamo ai caratteri un numero variabile di bit, a seconda della frequenza con cui compaiono in un dato testo. Alla fine, alcuni caratteri possono richiedere solo 1 bit, mentre altri possono richiedere 2 bit, 3 o più. Il problema con la codifica a lunghezza variabile è solo la successiva decodifica della sequenza.
Come, conoscendo la sequenza di bit, decodificarla in modo univoco?
Considera la linea "abadab". Ha 8 caratteri e quando si codifica una lunghezza fissa, saranno necessari 64 bit per memorizzarlo. Si noti che la frequenza del simbolo "a", "b", "c" и "D" è uguale a 4, 2, 1, 1 rispettivamente. Proviamo a immaginare "abadab" meno bit, sfruttando il fatto che "per" si verifica più frequentemente di "B"E "B" si verifica più frequentemente di "contro" и "D". Iniziamo codificando "per" con un bit uguale a 0, "B" assegneremo un codice a due bit 11 e utilizzando tre bit 100 e 011 codificheremo "contro" и "D".
Di conseguenza, otterremo:
a
0
b
11
c
100
d
011
Quindi la linea "abadab" codificheremo come 00110100011011 (0|0|11|0|100|011|0|11)utilizzando i codici sopra. Tuttavia, il problema principale sarà nella decodifica. Quando proviamo a decodificare la stringa 00110100011011, otteniamo 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
...
eccetera
Per evitare questa ambiguità, dobbiamo assicurarci che la nostra codifica soddisfi un concetto come regola del prefisso, che a sua volta implica che i codici possono essere decodificati solo in un modo univoco. La regola del prefisso garantisce che nessun codice sia prefisso di un altro. Per codice si intendono i bit utilizzati per rappresentare un particolare carattere. Nell'esempio sopra 0 è un prefisso 011, che viola la regola del prefisso. Quindi, se i nostri codici soddisfano la regola del prefisso, allora possiamo decodificare in modo univoco (e viceversa).
Rivediamo l'esempio sopra. Questa volta assegneremo per i simboli "a", "b", "c" и "D" codici che soddisfano la regola del prefisso.
a
0
b
10
c
110
d
111
Con questa codifica, la stringa "abadab" sarà codificato come 00100100011010 (0|0|10|0|100|011|0|10). Ma l' 00100100011010 saremo già in grado di decodificare in modo univoco e tornare alla nostra stringa originale "abadab".
Codifica di Huffman
Ora che ci siamo occupati della codifica a lunghezza variabile e della regola del prefisso, parliamo della codifica di Huffman.
Il metodo si basa sulla creazione di alberi binari. In esso, il nodo può essere finale o interno. Inizialmente, tutti i nodi sono considerati foglie (terminali), che rappresentano il simbolo stesso e il suo peso (ovvero la frequenza di occorrenza). I nodi interni contengono il peso del carattere e fanno riferimento a due nodi discendenti. Di comune accordo, bit "0" rappresenta seguendo il ramo sinistro, e "1" - sulla destra. ad albero pieno N foglie e N-1 nodi interni. Si raccomanda che quando si costruisce un albero di Huffman, i simboli inutilizzati vengano scartati per ottenere codici di lunghezza ottimali.
Useremo una coda di priorità per costruire un albero di Huffman, in cui al nodo con la frequenza più bassa verrà data la priorità più alta. Le fasi di costruzione sono descritte di seguito:
- Crea un nodo foglia per ogni personaggio e aggiungili alla coda delle priorità.
- Mentre c'è più di un foglio nella coda, procedi come segue:
- Rimuovere i due nodi con la priorità più alta (frequenza più bassa) dalla coda;
- Crea un nuovo nodo interno, dove questi due nodi saranno figli, e la frequenza di occorrenza sarà uguale alla somma delle frequenze di questi due nodi.
- Aggiungi un nuovo nodo alla coda prioritaria.
- L'unico nodo rimasto sarà la radice, e questo completerà la costruzione dell'albero.
Immagina di avere un testo composto solo da caratteri "a", "b", "c", "d" и "e", e le loro frequenze di occorrenza sono rispettivamente 15, 7, 6, 6 e 5. Di seguito sono riportate illustrazioni che riflettono i passaggi dell'algoritmo.
Un percorso dalla radice a qualsiasi nodo finale memorizzerà il codice del prefisso ottimale (noto anche come codice Huffman) corrispondente al carattere associato a quel nodo finale.
Albero di Huffmann
Di seguito troverai l'implementazione dell'algoritmo di compressione di Huffman in 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;
// A Tree node
class Node
{
char ch;
int freq;
Node left = null, right = null;
Node(char ch, int freq)
{
this.ch = ch;
this.freq = freq;
}
public Node(char ch, int freq, Node left, Node right) {
this.ch = ch;
this.freq = freq;
this.left = left;
this.right = right;
}
};
class Huffman
{
// traverse the Huffman Tree and store Huffman Codes
// in a map.
public static void encode(Node root, String str,
Map<Character, String> huffmanCode)
{
if (root == null)
return;
// found a leaf node
if (root.left == null && root.right == null) {
huffmanCode.put(root.ch, str);
}
encode(root.left, str + "0", huffmanCode);
encode(root.right, str + "1", huffmanCode);
}
// traverse the Huffman Tree and decode the encoded string
public static int decode(Node root, int index, StringBuilder sb)
{
if (root == null)
return index;
// found a leaf node
if (root.left == null && root.right == null)
{
System.out.print(root.ch);
return index;
}
index++;
if (sb.charAt(index) == '0')
index = decode(root.left, index, sb);
else
index = decode(root.right, index, sb);
return index;
}
// Builds Huffman Tree and huffmanCode and decode given input text
public static void buildHuffmanTree(String text)
{
// count frequency of appearance of each character
// and store it in a map
Map<Character, Integer> 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);
}
// Create a priority queue to store live nodes of Huffman tree
// Notice that highest priority item has lowest frequency
PriorityQueue<Node> pq = new PriorityQueue<>(
(l, r) -> l.freq - r.freq);
// Create a leaf node for each character and add it
// to the priority queue.
for (Map.Entry<Character, Integer> entry : freq.entrySet()) {
pq.add(new Node(entry.getKey(), entry.getValue()));
}
// 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.poll();
Node right = pq.poll();
// 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.add(new Node('', sum, left, right));
}
// root stores pointer to root of Huffman Tree
Node root = pq.peek();
// traverse the Huffman tree and store the Huffman codes in a map
Map<Character, String> huffmanCode = new HashMap<>();
encode(root, "", huffmanCode);
// print the Huffman codes
System.out.println("Huffman Codes are :n");
for (Map.Entry<Character, String> entry : huffmanCode.entrySet()) {
System.out.println(entry.getKey() + " " + entry.getValue());
}
System.out.println("nOriginal string was :n" + text);
// print encoded string
StringBuilder sb = new StringBuilder();
for (int i = 0 ; i < text.length(); i++) {
sb.append(huffmanCode.get(text.charAt(i)));
}
System.out.println("nEncoded string is :n" + sb);
// traverse the Huffman Tree again and this time
// decode the encoded string
int index = -1;
System.out.println("nDecoded string is: n");
while (index < sb.length() - 2) {
index = decode(root, index, sb);
}
}
public static void main(String[] args)
{
String text = "Huffman coding is a data compression algorithm.";
buildHuffmanTree(text);
}
}Nota: la memoria utilizzata dalla stringa di input è 47 * 8 = 376 bit e la stringa codificata è di soli 194 bit, ovvero i dati sono compressi di circa il 48%. Nel programma C++ sopra, usiamo la classe string per memorizzare la stringa codificata per rendere leggibile il programma.
Poiché le strutture di dati della coda di priorità efficienti richiedono per inserimento O(log(N)) tempo, ma in un albero binario completo con N foglie presenti 2N-1 nodi e l'albero di Huffman è un albero binario completo, l'algoritmo viene eseguito O(Nlog(N)) tempo, dove N - Caratteri.
Fonti:
Fonte: habr.com