Os dados podem ser compactados usando a técnica de codificação Huffman para ficarem menores sem perder nenhuma informação. Depois de David Huffman, quem o criou no começo? Os dados que contêm caracteres repetidos com frequência são normalmente compactados usando a codificação Huffman.
Um algoritmo Greedy bem conhecido é a codificação Huffman. O tamanho do código alocado para um caractere depende da frequência do caractere, por isso é considerado um algoritmo ganancioso. O código variável de comprimento curto é atribuído ao caractere com frequência mais alta e vice-versa para caracteres com frequências mais baixas. Ele emprega uma codificação de comprimento variável, o que significa que dá a cada caractere no fluxo de dados fornecido um código de comprimento variável diferente.
Regra de prefixo
Essencialmente, esta regra estabelece que o código atribuído a um carácter não deve ser o prefixo de outro código. Se esta regra for quebrada, várias ambigüidades podem aparecer ao decodificar a árvore Huffman que foi criada.
Vejamos uma ilustração desta regra para melhor compreendê-la: Para cada caractere é fornecido um código, como:
a - 0 b - 1 c - 01
Supondo que o fluxo de bits produzido seja 001, o código pode ser expresso da seguinte forma quando decodificado:
0 0 1 = aab 0 01 = ac
Qual é o processo de codificação Huffman?
O Código Huffman é obtido para cada caractere distinto basicamente em duas etapas:
- Crie primeiro uma árvore Huffman usando apenas os caracteres exclusivos no fluxo de dados fornecido.
- Segundo, devemos prosseguir através da Árvore de Huffman construída, atribuir códigos aos caracteres e então usar esses códigos para decodificar o texto fornecido.
Passos a seguir na codificação Huffman
As etapas usadas para construir a árvore Huffman usando os caracteres fornecidos
Input: string str = 'abbcdbccdaabbeeebeab'
Se a Codificação Huffman for empregada neste caso para compactação de dados, as seguintes informações deverão ser determinadas para decodificação:
- Para cada personagem, o Código Huffman
- Comprimento da mensagem codificada por Huffman (em bits), comprimento médio do código
- Utilizando as fórmulas abordadas abaixo, as duas últimas são descobertas.
Como uma árvore Huffman pode ser construída a partir de caracteres de entrada?
A frequência de cada caractere na string fornecida deve primeiro ser determinada.
| Personagem | Frequência |
|---|---|
| a | 4 |
| b | 7 |
| c | 3 |
| d | 2 |
| e | 4 |
- Classifique os caracteres por frequência, em ordem crescente. Eles são mantidos em uma fila de prioridade de heap Q/min.
- Para cada caractere distinto e sua frequência no fluxo de dados, crie um nó folha.
- Remova os dois nós com as duas frequências mais baixas dos nós e a nova raiz da árvore é criada usando a soma dessas frequências.
- Faça do primeiro nó extraído seu filho esquerdo e o segundo nó extraído seu filho direito enquanto extrai os nós com a frequência mais baixa do heap mínimo.
- Ao min-heap, adicione este nó.
- Já o lado esquerdo da raiz deve sempre conter a frequência mínima.
- Repita as etapas 3 e 4 até que reste apenas um nó no heap ou todos os caracteres sejam representados por nós na árvore. A árvore termina quando resta apenas o nó raiz.
Exemplos de codificação Huffman
Vamos usar uma ilustração para explicar o algoritmo:
Algoritmo para codificação Huffman
Passo 1: Construa um heap mínimo no qual cada nó representa a raiz de uma árvore com um único nó e contém 5 (o número de caracteres exclusivos do fluxo de dados fornecido).
Passo 2: Obtenha dois nós de frequência mínima do heap mínimo na etapa dois. Adicione um terceiro nó interno, frequência 2 + 3 = 5, que é criado pela união dos dois nós extraídos.
- Agora, existem 4 nós no min-heap, 3 dos quais são raízes de árvores com um único elemento cada e 1 dos quais é a raiz de uma árvore com dois elementos.
Etapa 3: Obtenha os dois nós de frequência mínima do heap de maneira semelhante na etapa três. Além disso, adicione um novo nó interno formado pela união dos dois nós extraídos; sua frequência na árvore deve ser 4 + 4 = 8.
- Agora que o heap mínimo tem três nós, um nó serve como raiz de árvores com um único elemento e dois nós de heap servem como raiz de árvores com vários nós.
Passo 4: Obtenha os dois nós de frequência mínima na etapa quatro. Além disso, adicione um novo nó interno formado pela união dos dois nós extraídos; sua frequência na árvore deve ser 5 + 7 = 12.
- Ao criar uma árvore de Huffman, devemos garantir que o valor mínimo esteja sempre no lado esquerdo e que o segundo valor esteja sempre no lado direito. Atualmente, a imagem abaixo mostra a árvore que se formou:
Etapa 5: Obtenha os dois nós de frequência mínima a seguir na etapa 5. Além disso, adicione um novo nó interno formado pela união dos dois nós extraídos; sua frequência na árvore deve ser 12 + 8 = 20.
Continue até que todos os caracteres distintos tenham sido adicionados à árvore. A árvore Huffman criada para o elenco de personagens especificado é mostrada na imagem acima.
Agora, para cada nó não folha, atribua 0 à borda esquerda e 1 à borda direita para criar o código para cada letra.
Regras a seguir para determinar os pesos das arestas:
idade de hrithik roshan
- Devemos atribuir peso 1 às bordas direitas se você atribuir peso 0 às bordas esquerdas.
- Se as arestas esquerdas receberem peso 1, as arestas direitas deverão receber peso 0.
- Qualquer uma das duas convenções acima mencionadas pode ser usada.
- No entanto, siga também o mesmo protocolo ao decodificar a árvore.
Após a ponderação, a árvore modificada é exibida da seguinte forma:
Compreendendo o Código
- Devemos percorrer a árvore de Huffman até chegar ao nó folha, onde o elemento está presente, para decodificar o código de Huffman para cada caractere da árvore de Huffman resultante.
- Os pesos entre os nós devem ser registrados durante o percurso e alocados aos itens localizados no nó folha específico.
- O exemplo a seguir ajudará a ilustrar melhor o que queremos dizer:
- Para obter o código de cada caractere da imagem acima, devemos percorrer toda a árvore (até que todos os nós das folhas sejam cobertos).
- Como resultado, a árvore criada é usada para decodificar os códigos de cada nó. Abaixo está uma lista dos códigos para cada personagem:
| Personagem | Frequência/contagem | Código |
|---|---|---|
| a | 4 | 01 |
| b | 7 | onze |
| c | 3 | 101 |
| d | 2 | 100 |
| e | 4 | 00 |
Abaixo está a implementação na programação C:
// C program for Huffman Coding #include #include // This constant can be avoided by explicitly // calculating height of Huffman Tree #define MAX_TREE_HT 100 // A Huffman tree node struct MinHeapNode { // One of the input characters char data; // Frequency of the character unsigned freq; // Left and right child of this node struct MinHeapNode *left, *right; }; // A Min Heap: Collection of // min-heap (or Huffman tree) nodes struct MinHeap { // Current size of min heap unsigned size; // capacity of min heap unsigned capacity; // Array of minheap node pointers struct MinHeapNode** array; }; // A utility function allocate a new // min heap node with given character // and frequency of the character struct MinHeapNode* newNode(char data, unsigned freq) { struct MinHeapNode* temp = (struct MinHeapNode*)malloc( sizeof(struct MinHeapNode)); temp->left = temp->right = NULL; temp->data = data; temp->freq = freq; return temp; } // A utility function to create // a min heap of given capacity struct MinHeap* createMinHeap(unsigned capacity) { struct MinHeap* minHeap = (struct MinHeap*)malloc(sizeof(struct MinHeap)); // current size is 0 minHeap->size = 0; minHeap->capacity = capacity; minHeap->array = (struct MinHeapNode**)malloc( minHeap->capacity * sizeof(struct MinHeapNode*)); return minHeap; } // A utility function to // swap two min heap nodes void swapMinHeapNode(struct MinHeapNode** a, struct MinHeapNode** b) { struct MinHeapNode* t = *a; *a = *b; *b = t; } // The standard minHeapify function. void minHeapify(struct MinHeap* minHeap, int idx) { int smallest = idx; int left = 2 * idx + 1; int right = 2 * idx + 2; if (left size && minHeap->array[left]->freq array[smallest]->freq) smallest = left; if (right size && minHeap->array[right]->freq array[smallest]->freq) smallest = right; if (smallest != idx) { swapMinHeapNode(&minHeap->array[smallest], &minHeap->array[idx]); minHeapify(minHeap, smallest); } } // A utility function to check // if size of heap is 1 or not int isSizeOne(struct MinHeap* minHeap) { return (minHeap->size == 1); } // A standard function to extract // minimum value node from heap struct MinHeapNode* extractMin(struct MinHeap* minHeap) { struct MinHeapNode* temp = minHeap->array[0]; minHeap->array[0] = minHeap->array[minHeap->size - 1]; --minHeap->size; minHeapify(minHeap, 0); return temp; } // A utility function to insert // a new node to Min Heap void insertMinHeap(struct MinHeap* minHeap, struct MinHeapNode* minHeapNode) { ++minHeap->size; int i = minHeap->size - 1; while (i && minHeapNode->freq array[(i - 1) / 2]->freq) { minHeap->array[i] = minHeap->array[(i - 1) / 2]; i = (i - 1) / 2; } minHeap->array[i] = minHeapNode; } // A standard function to build min heap void buildMinHeap(struct MinHeap* minHeap) { int n = minHeap->size - 1; int i; for (i = (n - 1) / 2; i >= 0; --i) minHeapify(minHeap, i); } // A utility function to print an array of size n void printArr(int arr[], int n) { int i; for (i = 0; i left) && !(root->right); } // Creates a min heap of capacity // equal to size and inserts all character of // data[] in min heap. Initially size of // min heap is equal to capacity struct MinHeap* createAndBuildMinHeap(char data[], int freq[], int size) { struct MinHeap* minHeap = createMinHeap(size); for (int i = 0; i array[i] = newNode(data[i], freq[i]); minHeap->size = size; buildMinHeap(minHeap); return minHeap; } // The main function that builds Huffman tree struct MinHeapNode* buildHuffmanTree(char data[], int freq[], int size) { struct MinHeapNode *left, *right, *top; // Step 1: Create a min heap of capacity // equal to size. Initially, there are // modes equal to size. struct MinHeap* minHeap = createAndBuildMinHeap(data, freq, size); // Iterate while size of heap doesn't become 1 while (!isSizeOne(minHeap)) { // Step 2: Extract the two minimum // freq items from min heap left = extractMin(minHeap); right = extractMin(minHeap); // Step 3: Create a new internal // node with frequency equal to the // sum of the two nodes frequencies. // Make the two extracted node as // left and right children of this new node. // Add this node to the min heap // '$' is a special value for internal nodes, not // used top = newNode('$', left->freq + right->freq); top->left = left; top->right = right; insertMinHeap(minHeap, top); } // Step 4: The remaining node is the // root node and the tree is complete. return extractMin(minHeap); } // Prints huffman codes from the root of Huffman Tree. // It uses arr[] to store codes void printCodes(struct MinHeapNode* root, int arr[], int top) { // Assign 0 to left edge and recur if (root->left) { arr[top] = 0; printCodes(root->left, arr, top + 1); } // Assign 1 to right edge and recur if (root->right) { arr[top] = 1; printCodes(root->right, arr, top + 1); } // If this is a leaf node, then // it contains one of the input // characters, print the character // and its code from arr[] if (isLeaf(root)) { printf('%c: ', root->data); printArr(arr, top); } } // The main function that builds a // Huffman Tree and print codes by traversing // the built Huffman Tree void HuffmanCodes(char data[], int freq[], int size) { // Construct Huffman Tree struct MinHeapNode* root = buildHuffmanTree(data, freq, size); // Print Huffman codes using // the Huffman tree built above int arr[MAX_TREE_HT], top = 0; printCodes(root, arr, top); } // Driver code int main() { char arr[] = { 'a', 'b', 'c', 'd', 'e', 'f' }; int freq[] = { 5, 9, 12, 13, 16, 45 }; int size = sizeof(arr) / sizeof(arr[0]); HuffmanCodes(arr, freq, size); return 0; } Saída
f: 0 c: 100 d: 101 a: 1100 b: 1101 e: 111 …………… Process executed in 1.11 seconds Press any key to continue.
Implementação Java do código acima:
import java.util.Comparator; import java.util.PriorityQueue; import java.util.Scanner; class Huffman { // recursive function to print the // huffman-code through the tree traversal. // Here s is the huffman - code generated. public static void printCode(HuffmanNode root, String s) { // base case; if the left and right are null // then its a leaf node and we print // the code s generated by traversing the tree. if (root.left == null && root.right == null && Character.isLetter(root.c)) { // c is the character in the node System.out.println(root.c + ':' + s); return; } // if we go to left then add '0' to the code. // if we go to the right add'1' to the code. // recursive calls for left and // right sub-tree of the generated tree. printCode(root.left, s + '0'); printCode(root.right, s + '1'); } // main function public static void main(String[] args) { Scanner s = new Scanner(System.in); // number of characters. int n = 6; char[] charArray = { 'a', 'b', 'c', 'd', 'e', 'f' }; int[] charfreq = { 5, 9, 12, 13, 16, 45 }; // creating a priority queue q. // makes a min-priority queue(min-heap). PriorityQueue q = new PriorityQueue( n, new MyComparator()); for (int i = 0; i <n; i++) { creating a huffman node object and add it to the priority queue. huffmannode hn="new" huffmannode(); hn.c="charArray[i];" hn.data="charfreq[i];" hn.left="null;" hn.right="null;" functions adds q.add(hn); } create root here we will extract two minimum value from heap each time until its size reduces 1, all nodes are extracted. while (q.size()> 1) { // first min extract. HuffmanNode x = q.peek(); q.poll(); // second min extract. HuffmanNode y = q.peek(); q.poll(); // new node f which is equal HuffmanNode f = new HuffmanNode(); // to the sum of the frequency of the two nodes // assigning values to the f node. f.data = x.data + y.data; f.c = '-'; // first extracted node as left child. f.left = x; // second extracted node as the right child. f.right = y; // marking the f node as the root node. root = f; // add this node to the priority-queue. q.add(f); } // print the codes by traversing the tree printCode(root, ''); } } // node class is the basic structure // of each node present in the Huffman - tree. class HuffmanNode { int data; char c; HuffmanNode left; HuffmanNode right; } // comparator class helps to compare the node // on the basis of one of its attribute. // Here we will be compared // on the basis of data values of the nodes. class MyComparator implements Comparator { public int compare(HuffmanNode x, HuffmanNode y) { return x.data - y.data; } } </n;> Saída
f: 0 c: 100 d: 101 a: 1100 b: 1101 e: 111 ………………. Process executed in 1.11 seconds Press any key to continue.
Explicação:
Ao percorrer, a Árvore Huffman é criada e decodificada. Os valores coletados durante o percurso devem então ser aplicados ao caracter localizado no nó folha. Cada caractere único no fluxo de dados fornecido pode ser identificado usando o Código Huffman desta maneira. O (nlogn), onde n é o número total de caracteres, é a complexidade do tempo. ExtractMin() é chamado 2*(n - 1) vezes se houver n nós. Como extractMin() chama minHeapify(), seu tempo de execução é O (logn). A complexidade total é, portanto, O (nlogn). Existe um algoritmo de tempo linear se a matriz de entrada for classificada. Isso será abordado com mais detalhes em nosso próximo artigo.
Problemas com codificação Huffman
Vamos falar sobre as desvantagens da codificação Huffman nesta parte e por que nem sempre é a melhor opção:
- Se nem todas as probabilidades ou frequências dos caracteres forem potências negativas de 2, isso não é considerado ideal.
- Embora seja possível chegar mais perto do ideal agrupando símbolos e expandindo o alfabeto, o método de bloqueio exige o manuseio de um alfabeto maior. Portanto, a codificação de Huffman nem sempre é muito eficaz.
- Embora existam muitas maneiras eficazes de contar a frequência de cada símbolo ou caractere, reconstruir a árvore inteira para cada um deles pode consumir muito tempo. Quando o alfabeto é grande e as distribuições de probabilidade mudam rapidamente com cada símbolo, normalmente é esse o caso.
Algoritmo de construção de código ganancioso de Huffman
- Huffman desenvolveu uma técnica gananciosa que gera um Código Huffman, um código de prefixo ideal, para cada caractere distinto no fluxo de dados de entrada.
- A abordagem usa o menor número de nós de cada vez para criar a árvore Huffman de baixo para cima.
- Como cada caractere recebe um comprimento de código com base na frequência com que aparece em um determinado fluxo de dados, esse método é conhecido como abordagem gananciosa. É um elemento que ocorre comumente nos dados se o tamanho do código recuperado for menor.
O uso da codificação Huffman
- Aqui, falaremos sobre alguns usos práticos da codificação Huffman:
- Formatos de compactação convencionais como PKZIP, GZIP, etc. normalmente empregam codificação Huffman.
- A codificação Huffman é usada para transferência de dados por fax e texto porque minimiza o tamanho do arquivo e aumenta a velocidade de transmissão.
- A codificação Huffman (particularmente os códigos de prefixo) é usada por vários formatos de armazenamento multimídia, incluindo JPEG, PNG e MP3, para compactar os arquivos.
- A codificação Huffman é usada principalmente para compactação de imagens.
- Quando uma sequência de caracteres frequentemente recorrentes precisa ser enviada, isso pode ser mais útil.
Conclusão
- Em geral, a codificação Huffman é útil para compactar dados que contêm caracteres que ocorrem com frequência.
- Podemos ver que o caractere que ocorre com mais frequência possui o código mais curto, enquanto aquele que ocorre com menos frequência possui o código maior.
- A técnica de compressão do Código Huffman é usada para criar codificação de comprimento variável, que utiliza uma quantidade variada de bits para cada letra ou símbolo. Este método é superior à codificação de comprimento fixo, pois utiliza menos memória e transmite dados mais rapidamente.
- Leia este artigo para ter um melhor conhecimento do algoritmo ganancioso.