Antes do comezo do curso preparou para ti unha tradución doutro material útil.
A codificación Huffman é un algoritmo de compresión de datos que formula a idea básica da compresión de ficheiros. Neste artigo, falaremos sobre a codificación de lonxitude fixa e variable, códigos decodificables de forma única, regras de prefixos e construción dunha árbore de Huffman.
Sabemos que cada carácter se almacena como unha secuencia de 0 e 1 e ocupa 8 bits. Isto chámase codificación de lonxitude fixa porque cada carácter usa o mesmo número fixo de bits para almacenar.
Digamos que nos dan un texto. Como podemos reducir a cantidade de espazo necesario para almacenar un só carácter?
A idea principal é a codificación de lonxitude variable. Podemos utilizar o feito de que algúns caracteres do texto aparecen con máis frecuencia que outros () para desenvolver un algoritmo que represente a mesma secuencia de caracteres en menos bits. Na codificación de lonxitude variable, asignamos aos caracteres un número variable de bits, dependendo da frecuencia con que aparecen nun texto determinado. Finalmente, algúns caracteres poden tardar tan só 1 bit, mentres que outros poden tardar 2 bits, 3 ou máis. O problema coa codificación de lonxitude variable é só a decodificación posterior da secuencia.
Como, coñecendo a secuencia de bits, decodificala sen ambigüidades?
Considere a liña "abacdab". Ten 8 caracteres, e ao codificar unha lonxitude fixa, necesitará 64 bits para almacenalo. Teña en conta que a frecuencia do símbolo "a", "b", "c" и "D" é igual a 4, 2, 1, 1 respectivamente. Intentemos imaxinar "abacdab" menos bits, usando o feito de que "a" ocorre con máis frecuencia que "B"E "B" ocorre con máis frecuencia que "c" и "D". Comecemos codificando "a" cun bit igual a 0, "B" asignaremos un código de dous bits 11, e usando tres bits 100 e 011 codificaremos "c" и "D".
Como resultado, obteremos:
a
0
b
11
c
100
d
011
Entón a liña "abacdab" codificaremos como 00110100011011 (0|0|11|0|100|011|0|11)usando os códigos anteriores. Non obstante, o principal problema estará na decodificación. Cando tentamos decodificar a cadea 00110100011011, obtemos un resultado ambiguo, xa que se pode representar como:
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
...
etc
Para evitar esta ambigüidade, debemos asegurarnos de que a nosa codificación satisfaga un concepto como regra do prefixo, o que á súa vez implica que os códigos só se poden decodificar dun xeito único. A regra do prefixo garante que ningún código sexa prefixo doutro. Por código, entendemos os bits utilizados para representar un determinado carácter. No exemplo anterior 0 é un prefixo 011, que infrinxe a regra do prefixo. Entón, se os nosos códigos cumpren a regra do prefixo, podemos decodificar de forma única (e viceversa).
Repasemos o exemplo anterior. Nesta ocasión asignaremos símbolos "a", "b", "c" и "D" códigos que cumpren a regra do prefixo.
a
0
b
10
c
110
d
111
Con esta codificación, a cadea "abacdab" codificarase como 00100100011010 (0|0|10|0|100|011|0|10). Pero o 00100100011010 xa poderemos decodificar sen ambigüidades e volver á nosa cadea orixinal "abacdab".
Codificación de Huffman
Agora que tratamos a codificación de lonxitude variable e a regra do prefixo, imos falar da codificación de Huffman.
O método baséase na creación de árbores binarias. Nel, o nodo pode ser final ou interno. Inicialmente, todos os nós considéranse follas (terminais), que representan o propio símbolo e o seu peso (é dicir, a frecuencia de aparición). Os nodos internos conteñen o peso do carácter e refírense a dous nodos descendentes. Por acordo xeral, pouco «0» representa seguindo a rama esquerda, e «1» - á dereita. en árbore chea N follas e N-1 nodos internos. Recoméndase que ao construír unha árbore de Huffman, descarte os símbolos non utilizados para obter códigos de lonxitude óptimos.
Usaremos unha cola de prioridades para construír unha árbore de Huffman, onde o nodo coa frecuencia máis baixa terá a máxima prioridade. Os pasos de construción descríbense a continuación:
- Crea un nodo de folla para cada personaxe e engádeos á cola de prioridades.
- Mentres hai máis dunha folla na cola, fai o seguinte:
- Elimina os dous nodos con maior prioridade (frecuencia máis baixa) da cola;
- Crea un novo nodo interno, onde estes dous nodos serán fillos, e a frecuencia de aparición será igual á suma das frecuencias destes dous nodos.
- Engade un novo nodo á cola de prioridades.
- O único nodo restante será a raíz, e isto completará a construción da árbore.
Imaxina que temos algún texto que só consta de caracteres "a", "b", "c", "d" и "e", e as súas frecuencias de aparición son 15, 7, 6, 6 e 5, respectivamente. A continuación móstranse ilustracións que reflicten os pasos do algoritmo.
Un camiño desde a raíz a calquera nodo final almacenará o código de prefixo óptimo (tamén coñecido como código Huffman) correspondente ao carácter asociado a ese nodo final.
Árbore de Huffman
A continuación atoparás a implementación do algoritmo de compresión Huffman en 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: a memoria utilizada pola cadea de entrada é de 47 * 8 = 376 bits e a cadea codificada só é de 194 bits, é dicir. os datos están comprimidos nun 48%. No programa C++ anterior, usamos a clase de cadea para almacenar a cadea codificada para que o programa sexa lexible.
Porque as estruturas de datos de filas de prioridade eficientes requiren por inserción O(log(N)) tempo, pero nunha árbore binaria completa con N follas presentes 2N-1 nodos, e a árbore de Huffman é unha árbore binaria completa, entón execútase o algoritmo O(Nlog(N)) tempo, onde N - Personaxes.
Fontes:
Fonte: www.habr.com