Antes do início do curso preparou para você uma tradução de outro material útil.
A codificação Huffman é um algoritmo de compactação de dados que formula a ideia básica de compactação de arquivos. Neste artigo, falaremos sobre codificação de comprimento fixo e variável, códigos exclusivamente decodificáveis, regras de prefixo e construção de uma árvore de Huffman.
Sabemos que cada caractere é armazenado como uma sequência de 0s e 1s e ocupa 8 bits. Isso é chamado de codificação de comprimento fixo porque cada caractere usa o mesmo número fixo de bits para armazenar.
Digamos que recebemos um texto. Como podemos reduzir a quantidade de espaço necessária para armazenar um único caractere?
A ideia principal é a codificação de comprimento variável. Podemos usar o fato de que alguns caracteres no texto ocorrem com mais frequência do que outros () para desenvolver um algoritmo que representará a mesma sequência de caracteres em menos bits. Na codificação de comprimento variável, atribuímos aos caracteres um número variável de bits, dependendo da frequência com que aparecem em um determinado texto. Eventualmente, alguns caracteres podem levar apenas 1 bit, enquanto outros podem levar 2 bits, 3 ou mais. O problema com a codificação de comprimento variável é apenas a decodificação subsequente da sequência.
Como, conhecendo a sequência de bits, decodificá-la sem ambiguidade?
Considere a linha "abacdab". Possui 8 caracteres e, ao codificar um comprimento fixo, precisará de 64 bits para armazená-lo. Note que a frequência do símbolo "um", "b", "c" и "D" é igual a 4, 2, 1, 1, respectivamente. Vamos tentar imaginar "abacdab" menos bits, usando o fato de que "para" ocorre com mais frequência do que "B"E "B" ocorre com mais frequência do que "vs" и "D". Vamos começar codificando "para" com um bit igual a 0, "B" atribuiremos um código 11 de dois bits e, usando três bits 100 e 011, codificaremos "vs" и "D".
Como resultado, obteremos:
a
0
b
11
c
100
d
011
Então a linha "abacdab" vamos codificar como 00110100011011 (0|0|11|0|100|011|0|11)usando os códigos acima. No entanto, o principal problema estará na decodificação. Quando tentamos decodificar a string 00110100011011, obteremos um resultado ambíguo, pois pode ser representado 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
...
и т.д.
Para evitar essa ambigüidade, devemos garantir que nossa codificação satisfaça um conceito como regra de prefixo, o que, por sua vez, implica que os códigos só podem ser decodificados de uma maneira única. A regra do prefixo garante que nenhum código seja um prefixo de outro. Por código, queremos dizer os bits usados para representar um caractere específico. No exemplo acima 0 é um prefixo 011, que viola a regra do prefixo. Portanto, se nossos códigos satisfizerem a regra do prefixo, podemos decodificar exclusivamente (e vice-versa).
Vamos revisitar o exemplo acima. Desta vez vamos atribuir para símbolos "um", "b", "c" и "D" códigos que satisfazem a regra do prefixo.
a
0
b
10
c
110
d
111
Com esta codificação, a string "abacdab" será codificado como 00100100011010 (0|0|10|0|100|011|0|10). Mas o 00100100011010 já seremos capazes de decodificar inequivocamente e retornar à nossa string original "abacdab".
Codificação de Huffman
Agora que lidamos com a codificação de comprimento variável e a regra do prefixo, vamos falar sobre a codificação de Huffman.
O método é baseado na criação de árvores binárias. Nela, o nó pode ser final ou interno. Inicialmente, todos os nós são considerados folhas (terminais), que representam o próprio símbolo e seu peso (ou seja, a frequência de ocorrência). Os nós internos contêm o peso do personagem e referem-se a dois nós descendentes. Por acordo geral, pouco «0» representa seguindo o ramo esquerdo, e «1» - à direita. em árvore cheia N folhas e N-1 nós internos. Recomenda-se que, ao construir uma árvore de Huffman, os símbolos não utilizados sejam descartados para obter códigos de comprimento ideal.
Usaremos uma fila de prioridade para construir uma árvore de Huffman, onde o nó com a menor frequência terá a maior prioridade. As etapas de construção são descritas a seguir:
- Crie um nó folha para cada personagem e adicione-os à fila de prioridade.
- Enquanto houver mais de uma folha na fila, faça o seguinte:
- Remova os dois nós com maior prioridade (menor frequência) da fila;
- Crie um novo nó interno, onde esses dois nós serão filhos, e a frequência de ocorrência será igual à soma das frequências desses dois nós.
- Adicione um novo nó à fila de prioridade.
- O único nó restante será a raiz, e isso completará a construção da árvore.
Imagine que temos algum texto que consiste apenas em caracteres "a", "b", "c", "d" и "e", e suas frequências de ocorrência são 15, 7, 6, 6 e 5, respectivamente. Abaixo estão as ilustrações que refletem as etapas do algoritmo.
Um caminho da raiz para qualquer nó final armazenará o código de prefixo ideal (também conhecido como código Huffman) correspondente ao caractere associado a esse nó final.
árvore Huffman
Abaixo você encontrará a implementação do algoritmo de compressão Huffman em 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 memória usada pela string de entrada é de 47 * 8 = 376 bits e a string codificada é de apenas 194 bits, ou seja, os dados são compactados em cerca de 48%. No programa C++ acima, usamos a classe string para armazenar a string codificada para tornar o programa legível.
Porque as estruturas de dados de fila de prioridade eficientes exigem por inserção O(log(N)) tempo, mas em uma árvore binária completa com N deixa presente 2N-1 nós, e a árvore de Huffman é uma árvore binária completa, então o algoritmo é executado em O(Nlog(N)) tempo, onde N - Personagens.
Fontes:
Fonte: habr.com