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:

1. Crie um novo nó interno.
2. A frequência do nó será a soma da frequência dos dois nós que possuem a mesma frequência.
3. 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:

1. Código Huffman para todos os personagens
2. Comprimento médio do código para a String fornecida
3. 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.

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 -&gt; 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&apos; 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, &apos;&apos;, huffmanCode); //print the Huffman codes for the characters System.out.println(&apos;Huffman Codes of the characters are: &apos; + huffmanCode); //prints the initial data System.out.println(&apos;The initial string is: &apos; + 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(&apos;The encoded string is: &apos; + sb); System.out.print(&apos;The decoded string is: &apos;); if (isLeaf(root)) { //special case: For input like a, aa, aaa, etc. while (root.freq-- &gt; 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 : &apos;1&apos;); } encodeData(root.left, str + &apos;0&apos;, huffmanCode); encodeData(root.right, str + &apos;1&apos;, 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) == &apos;0&apos;) ? 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 &amp;&amp; root.right == null; } //driver code public static void main(String args[]) { String text = &apos;javatpoint&apos;; //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