Antes del inicio del curso preparado para usted una traducción de otro material útil.
La codificación Huffman es un algoritmo de compresión de datos que formula la idea básica de la compresión de archivos. En este artículo, hablaremos sobre la codificación de longitud fija y variable, los códigos decodificables de forma única, las reglas de prefijo y la construcción de un árbol de Huffman.
Sabemos que cada carácter se almacena como una secuencia de 0 y 1 y ocupa 8 bits. Esto se denomina codificación de longitud fija porque cada carácter utiliza el mismo número fijo de bits para almacenar.
Digamos que nos dan texto. ¿Cómo podemos reducir la cantidad de espacio requerido para almacenar un solo carácter?
La idea principal es la codificación de longitud variable. Podemos usar el hecho de que algunos caracteres en el texto aparecen con más frecuencia que otros () para desarrollar un algoritmo que represente la misma secuencia de caracteres en menos bits. En la codificación de longitud variable, asignamos a los caracteres un número variable de bits, según la frecuencia con la que aparecen en un texto determinado. Eventualmente, algunos caracteres pueden tomar tan solo 1 bit, mientras que otros pueden tomar 2 bits, 3 o más. El problema con la codificación de longitud variable es solo la posterior decodificación de la secuencia.
¿Cómo, conociendo la secuencia de bits, decodificarla sin ambigüedades?
Considere la línea "abacdab". Tiene 8 caracteres, y al codificar una longitud fija, necesitará 64 bits para almacenarlo. Tenga en cuenta que la frecuencia del símbolo "a B C" и "D" es igual a 4, 2, 1, 1 respectivamente. Tratemos de imaginar "abacdab" menos bits, utilizando el hecho de que "A" ocurre con más frecuencia que "b"Y "b" ocurre con más frecuencia que "C" и "D". Comencemos codificando "A" con un bit igual a 0, "b" asignaremos un código de dos bits 11, y usando tres bits 100 y 011 codificaremos "C" и "D".
Como resultado obtendremos:
a
0
b
11
c
100
d
011
Entonces la línea "abacdab" codificaremos como 00110100011011 (0|0|11|0|100|011|0|11)utilizando los códigos anteriores. Sin embargo, el principal problema estará en la decodificación. Cuando tratamos de decodificar la cadena 00110100011011, obtenemos un resultado ambiguo, ya que se puede 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étera
Para evitar esta ambigüedad, debemos asegurarnos de que nuestra codificación satisfaga un concepto como regla de prefijo, lo que a su vez implica que los códigos solo se pueden decodificar de una forma única. La regla del prefijo asegura que ningún código sea un prefijo de otro. Por código, nos referimos a los bits utilizados para representar un carácter en particular. En el ejemplo anterior 0 es un prefijo 011, lo que viola la regla del prefijo. Entonces, si nuestros códigos satisfacen la regla del prefijo, entonces podemos decodificar de forma única (y viceversa).
Repasemos el ejemplo anterior. Esta vez asignaremos símbolos "a B C" и "D" códigos que cumplen la regla del prefijo.
a
0
b
10
c
110
d
111
Con esta codificación, la cadena "abacdab" será codificado como 00100100011010 (0|0|10|0|100|011|0|10). Pero el 00100100011010 ya podremos decodificar sin ambigüedades y volver a nuestra cadena original "abacdab".
Codificación Huffman
Ahora que hemos tratado con la codificación de longitud variable y la regla del prefijo, hablemos de la codificación Huffman.
El método se basa en la creación de árboles binarios. En él, el nodo puede ser final o interno. Inicialmente, todos los nodos se consideran hojas (terminales), que representan el símbolo en sí y su peso (es decir, la frecuencia de aparición). Los nodos internos contienen el peso del personaje y hacen referencia a dos nodos descendientes. Por acuerdo general, bit "0" representa seguir la rama izquierda, y "1" - A la derecha. en arbol completo N hojas y N-1 nodos internos. Se recomienda que al construir un árbol de Huffman, los símbolos no utilizados se descarten para obtener códigos de longitud óptima.
Usaremos una cola de prioridad para construir un árbol de Huffman, donde el nodo con la frecuencia más baja tendrá la prioridad más alta. Los pasos de construcción se describen a continuación:
- Cree un nodo de hoja para cada personaje y agréguelos a la cola de prioridad.
- Mientras haya más de una hoja en la cola, haga lo siguiente:
- Retire los dos nodos con la prioridad más alta (frecuencia más baja) de la cola;
- Cree un nuevo nodo interno, donde estos dos nodos serán hijos, y la frecuencia de ocurrencia será igual a la suma de las frecuencias de estos dos nodos.
- Agregue un nuevo nodo a la cola de prioridad.
- El único nodo restante será la raíz, y esto completará la construcción del árbol.
Imagina que tenemos un texto que consta solo de caracteres. "a B C D" и "es", y sus frecuencias de ocurrencia son 15, 7, 6, 6 y 5, respectivamente. A continuación se muestran ilustraciones que reflejan los pasos del algoritmo.
Una ruta desde la raíz hasta cualquier nodo final almacenará el código de prefijo óptimo (también conocido como código Huffman) correspondiente al carácter asociado con ese nodo final.
árbol de huffman
A continuación encontrará la implementación del algoritmo de compresión de Huffman en C++ y 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 utilizada por la cadena de entrada es 47 * 8 = 376 bits y la cadena codificada es solo 194 bits, es decir los datos se comprimen en aproximadamente un 48 %. En el programa C++ anterior, usamos la clase de cadena para almacenar la cadena codificada para que el programa sea legible.
Debido a que las estructuras de datos de cola de prioridad eficientes requieren por inserción O (registro (N)) tiempo, pero en un árbol binario completo con N hojas presentes 2N-1 nodos, y el árbol de Huffman es un árbol binario completo, entonces el algoritmo se ejecuta en O(Nlog(N)) tiempo, donde N - Caracteres.
Fuentes:
Fuente: habr.com