O algoritmo de codificação de Huffman foi proposto por David A. Huffman em 1950. É um compactação de dados sem perdas mecanismo. Também é conhecido como codificação de compressão de dados. É amplamente utilizado na compactação de imagens (JPEG ou JPG). Nesta seção, discutiremos o Codificação Huffman e decodificação, e também implementar seu algoritmo em um programa Java.
Sabemos que cada caractere é uma sequência de 0 e 1 e é armazenado em 8 bits. O mecanismo é chamado codificação de comprimento fixo porque cada caractere usa o mesmo número de armazenamento de bits fixos.
programa python para pesquisa binária
Aqui surge uma questão, é possível reduzir a quantidade de espaço necessária para armazenar um personagem?
Sim, é possível usando codificação de comprimento variável. Neste mecanismo, exploramos alguns caracteres que ocorrem com mais frequência em comparação com outros caracteres. Nesta técnica de codificação, podemos representar o mesmo trecho de texto ou string reduzindo o número de bits.
Codificação Huffman
A codificação Huffman implementa as seguintes etapas.
- Ele atribui um código de comprimento variável a todos os caracteres fornecidos.
- O comprimento do código de um caractere depende da frequência com que ele ocorre em um determinado texto ou string.
- Um personagem obtém o menor código se ocorrer com frequência.
- Um personagem obtém o maior código se ocorrer menos.
A codificação de Huffman segue um regra de prefixo que evita ambiguidade durante a decodificação. A regra também garante que o código atribuído ao caractere não seja tratado como um prefixo do código atribuído a qualquer outro caractere.
Existem as duas etapas principais a seguir envolvidas na codificação de Huffman:
- Primeiro, construa um Árvore de Huffman da string de entrada fornecida, caracteres ou texto.
- Atribua um código Huffman a cada personagem percorrendo a árvore.
Vamos resumir as duas etapas acima.
Árvore Huffman
Passo 1: Para cada caractere do nó, crie um nó folha. O nó folha de um caractere contém a frequência desse caractere.
Passo 2: Defina todos os nós em ordem de classificação de acordo com sua frequência.
Etapa 3: Pode existir uma condição em que dois nós possam ter a mesma frequência. Nesse caso, faça o seguinte:
- Crie um novo nó interno.
- A frequência do nó será a soma da frequência dos dois nós que possuem a mesma frequência.
- Marque o primeiro nó como filho esquerdo e outro nó como filho direito do nó interno recém-criado.
Passo 4: Repita as etapas 2 e 3 até que todos os nós formem uma única árvore. Assim, obtemos uma árvore de Huffman.
Exemplo de codificação Huffman
Suponha que tenhamos que codificar string Abra Cadabra. Determine o seguinte:
- Código Huffman para todos os personagens
- Comprimento médio do código para a String fornecida
- Comprimento da string codificada
(i) Código Huffman para todos os personagens
Para determinar o código de cada caractere, primeiro, construímos um Árvore de Huffmann.
Passo 1: Faça pares de caracteres e suas frequências.
(a, 5), (b, 2), (c, 1), (d, 1), (r, 2)
decodificar javascript base64
Passo 2: Classificando os pares em relação à frequência, obtemos:
(c, 1), (d, 1), (b, 2) (r, 2), (a, 5)
Etapa 3: Escolha os dois primeiros caracteres e junte-os em um nó pai.
Observamos que um nó pai não possui frequência, portanto, devemos atribuir uma frequência a ele. A frequência do nó pai será a soma de seus nós filhos (esquerdo e direito), ou seja, 1+1= 2.
formatar a data em java
Passo 4: Repita as etapas 2 e 3 até obtermos uma única árvore.
Observamos que os pares já estão ordenados (pelo passo 2). Novamente, escolha os dois primeiros pares e junte-os.
Observamos que um nó pai não possui frequência, portanto, devemos atribuir uma frequência a ele. A frequência do nó pai será a soma de seus nós filhos (esquerdo e direito), ou seja, 2+2= 4.
Novamente, verificamos se os pares estão ordenados ou não. Nesta etapa, precisamos classificar os pares.
De acordo com o passo 3, escolha os dois primeiros pares e junte-os, obtemos:
Observamos que um nó pai não possui frequência, portanto, devemos atribuir uma frequência a ele. A frequência do nó pai será a soma de seus nós filhos (esquerdo e direito), ou seja, 2+4= 6.
Novamente, verificamos se os pares estão ordenados ou não. Nesta etapa, precisamos classificar os pares. Depois de ordenar a árvore fica assim:
De acordo com o passo 3, escolha os dois primeiros pares e junte-os, obtemos:
Observamos que um nó pai não possui frequência, portanto, devemos atribuir uma frequência a ele. A frequência do nó pai será a soma de seus nós filhos (esquerdo e direito), ou seja, 5+6= onze.
Portanto, obtemos uma única árvore.
Por fim, encontraremos o código de cada caractere com a ajuda da árvore acima. Atribua um peso a cada aresta. Observe que cada ponderada na borda esquerda é 0 e a ponderada na borda direita é 1.
Observamos que os caracteres de entrada são apresentados apenas nos nós de saída e os nós internos possuem valores nulos. Para encontrar o código de Huffman para cada caractere, percorra a árvore de Huffman do nó raiz até o nó folha daquele caractere específico para o qual queremos encontrar o código. A tabela descreve o código e o comprimento do código para cada caractere.
| Personagem | Frequência | Código | Comprimento do código |
|---|---|---|---|
| A | 5 | 0 | 1 |
| B | 2 | 111 | 3 |
| C | 1 | 1100 | 4 |
| D | 1 | 1101 | 4 |
| R | 2 | 10 | 2 |
Observamos que o caractere mais frequente obtém o menor comprimento de código e o caractere menos frequente obtém o maior comprimento de código.
Agora podemos codificar a string (Abra Cadabra) que tomamos acima.
0 111 10 0 1100 0 1101 0 111 10 0
(ii) Comprimento médio do código para a string
O comprimento médio do código da árvore Huffman pode ser determinado usando a fórmula abaixo:
Average Code Length = ∑ ( frequency × code length ) / ∑ ( frequency )
= {(5 x 1) + (2 x 3) + (1 x 4) + (1 x 4) + (2 x 2) } / (5+2+1+1+2)
alfabeto para número
= 2,09090909
(iii) Comprimento da String Codificada
O comprimento da mensagem codificada pode ser determinado usando a seguinte fórmula:
length= Total number of characters in the text x Average code length per character
= 11 x 2,09090909
= 23 bits
Algoritmo de codificação Huffman
Huffman (C) n=|C| Q=C for i=1 to n-1 do z=allocate_Node() x=left[z]=Extract_Min(Q) y=right[z]=Extract_Min(Q) f[z]=f[x]+f[y] Insert(Q,z) return Extract_Min(Q)
O algoritmo Huffman é um algoritmo ganancioso. Pois em cada etapa o algoritmo busca as melhores opções disponíveis.
A complexidade de tempo da codificação de Huffman é O(nlogn). Onde n é o número de caracteres no texto fornecido.
Decodificação de Huffman
A decodificação de Huffman é uma técnica que converte os dados codificados em dados iniciais. Como vimos na codificação, a árvore de Huffman é feita para uma string de entrada e os caracteres são decodificados com base em sua posição na árvore. O processo de decodificação é o seguinte:
cocô
- Comece a atravessar a árvore a partir do raiz nó e procure o personagem.
- Se movermos para a esquerda na árvore binária, adicione 0 ao código.
- Se movermos para a direita na árvore binária, adicione 1 ao código.
O nó filho contém o caractere de entrada. É atribuído o código formado pelos 0s e 1s subsequentes. A complexidade de tempo de decodificação de uma string é Sobre), onde n é o comprimento da string.
Programa Java de codificação e decodificação Huffman
No programa a seguir, usamos estruturas de dados como filas de prioridade, pilhas e árvores para projetar uma lógica de compactação e descompactação. Basearemos nossos utilitários na técnica algorítmica amplamente utilizada de codificação de Huffman.
HuffmanCode.java
import java.util.Comparator; import java.util.HashMap; import java.util.Map; import java.util.PriorityQueue; //defining a class that creates nodes of the tree class Node { //storing character in ch variable of type character Character ch; //storing frequency in freq variable of type int Integer freq; //initially both child (left and right) are null Node left = null; Node right = null; //creating a constructor of the Node class Node(Character ch, Integer freq) { this.ch = ch; this.freq = freq; } //creating a constructor of the Node class public Node(Character ch, Integer freq, Node left, Node right) { this.ch = ch; this.freq = freq; this.left = left; this.right = right; } } //main class public class HuffmanCode { //function to build Huffman tree public static void createHuffmanTree(String text) { //base case: if user does not provides string if (text == null || text.length() == 0) { return; } //count the frequency of appearance of each character and store it in a map //creating an instance of the Map Map freq = new HashMap(); //loop iterates over the string and converts the text into character array for (char c: text.toCharArray()) { //storing character and their frequency into Map by invoking the put() method freq.put(c, freq.getOrDefault(c, 0) + 1); } //create a priority queue that stores current nodes of the Huffman tree. //here a point to note that the highest priority means the lowest frequency PriorityQueue pq = new PriorityQueue(Comparator.comparingInt(l -> l.freq)); //loop iterate over the Map and returns a Set view of the mappings contained in this Map for (var entry: freq.entrySet()) { //creates a leaf node and add it to the queue pq.add(new Node(entry.getKey(), entry.getValue())); } //while loop runs until there is more than one node in the queue while (pq.size() != 1) { //removing the nodes having the highest priority (the 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 a frequency equal to the sum of both nodes' frequencies. Add the new node to the priority queue. //sum up the frequency of the nodes (left and right) that we have deleted int sum = left.freq + right.freq; //adding a new internal node (deleted nodes i.e. right and left) to the queue with a frequency that is equal to the sum of both nodes pq.add(new Node(null, sum, left, right)); } //root stores pointer to the root of Huffman Tree Node root = pq.peek(); //trace over the Huffman tree and store the Huffman codes in a map Map huffmanCode = new HashMap(); encodeData(root, '', huffmanCode); //print the Huffman codes for the characters System.out.println('Huffman Codes of the characters are: ' + huffmanCode); //prints the initial data System.out.println('The initial string is: ' + text); //creating an instance of the StringBuilder class StringBuilder sb = new StringBuilder(); //loop iterate over the character array for (char c: text.toCharArray()) { //prints encoded string by getting characters sb.append(huffmanCode.get(c)); } System.out.println('The encoded string is: ' + sb); System.out.print('The decoded string is: '); if (isLeaf(root)) { //special case: For input like a, aa, aaa, etc. while (root.freq-- > 0) { System.out.print(root.ch); } } else { //traverse over the Huffman tree again and this time, decode the encoded string int index = -1; while (index <sb.length() - 1) { index="decodeData(root," index, sb); } traverse the huffman tree and store codes in a map function that encodes data public static void encodedata(node root, string str, huffmancode) if (root="=" null) return; checks node is leaf or not (isleaf(root)) huffmancode.put(root.ch, str.length()> 0 ? str : '1'); } encodeData(root.left, str + '0', huffmanCode); encodeData(root.right, str + '1', huffmanCode); } //traverse the Huffman Tree and decode the encoded string function that decodes the encoded data public static int decodeData(Node root, int index, StringBuilder sb) { //checks if the root node is null or not if (root == null) { return index; } //checks if the node is a leaf node or not if (isLeaf(root)) { System.out.print(root.ch); return index; } index++; root = (sb.charAt(index) == '0') ? root.left : root.right; index = decodeData(root, index, sb); return index; } //function to check if the Huffman Tree contains a single node public static boolean isLeaf(Node root) { //returns true if both conditions return ture return root.left == null && root.right == null; } //driver code public static void main(String args[]) { String text = 'javatpoint'; //function calling createHuffmanTree(text); } } </sb.length()> Saída:
Huffman Codes of the characters are: {p=000, a=110, t=111, v=001, i=010, j=011, n=100, o=101} The initial string is: javatpoint The encoded string is: 011110001110111000101010100111 The decoded string is: javatpoint