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.

1. Classifique os caracteres por frequência, em ordem crescente. Eles são mantidos em uma fila de prioridade de heap Q/min.
2. Para cada caractere distinto e sua frequência no fluxo de dados, crie um nó folha.
3. 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.
4. 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:

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 &amp;&amp; root.right == null &amp;&amp; Character.isLetter(root.c)) { // c is the character in the node System.out.println(root.c + &apos;:&apos; + s); return; } // if we go to left then add &apos;0&apos; to the code. // if we go to the right add&apos;1&apos; to the code. // recursive calls for left and // right sub-tree of the generated tree. printCode(root.left, s + &apos;0&apos;); printCode(root.right, s + &apos;1&apos;); } // main function public static void main(String[] args) { Scanner s = new Scanner(System.in); // number of characters. int n = 6; char[] charArray = { &apos;a&apos;, &apos;b&apos;, &apos;c&apos;, &apos;d&apos;, &apos;e&apos;, &apos;f&apos; }; 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 = &apos;-&apos;; // 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, &apos;&apos;); } } // 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.