2.3.4 Exemplo: Árvores de Codificação de Huffman
Esta seção fornece a prática de usar listas para representar árvores, trabalhando com um exemplo de codificação Huffman—uma técnica de compressão de dados.
Codificação de Comprimento Variável
Códigos de comprimento fixo usam o mesmo número de bits para cada símbolo. Por exemplo, um alfabeto de 8 símbolos requer 3 bits por símbolo. Códigos de comprimento variável podem economizar espaço atribuindo códigos mais curtos para símbolos frequentes.
Por exemplo, código Morse usa códigos mais curtos para letras comuns (E = ".", T = "-") e códigos mais longos para letras raras.
Árvores de Huffman
Um código de Huffman é representado como uma árvore binária cujas folhas são os símbolos codificados. Cada folha tem um símbolo e um peso (frequência relativa). Nós internos contêm um conjunto de símbolos e a soma dos pesos de suas subárvores.
Carregando playground de código...
O Algoritmo de Decodificação
Para decodificar uma mensagem, começamos na raiz e seguimos os ramos de acordo com os bits: 0 significa esquerda, 1 significa direita. Ao atingir uma folha, registramos o símbolo e recomeçamos da raiz.
Carregando playground de código...
Conjuntos de Pares Ponderados
Para gerar uma árvore de Huffman, precisamos ordenar folhas e árvores por peso. Representamos isso como um conjunto de pares ponderados (árvore, peso):
Carregando playground de código...
Gerando Árvores de Huffman
O algoritmo de Huffman começa com o conjunto de folhas, e repetidamente combina as duas árvores de menor peso em uma nova árvore, até restar apenas uma:
Carregando playground de código...
Exercícios
Exercício 2.67: Defina uma árvore de codificação e uma mensagem de exemplo. Use a função decode para decodificar a mensagem e forneça o resultado.
Exercício 2.68: Escreva a função encode que recebe uma mensagem e uma árvore e produz a lista de bits codificados.
Exercício 2.69: Complete a função generate_huffman_tree implementando successive_merge.
Exercício 2.70: Gere uma árvore de Huffman para as letras da canção "Get a Job" e use-a para codificar a canção. Quantos bits são necessários? Compare com codificação de comprimento fixo.
Exercício 2.71: Suponha que temos uma árvore de Huffman para um alfabeto de n símbolos, e que as frequências relativas dos símbolos são 1, 2, 4, ..., 2^(n-1). Esboce a árvore para n=5 e n=10.
Exercício 2.72: Considere a codificação de um símbolo em relação à árvore do exercício 2.71. Qual é a ordem de crescimento do número de passos necessários para codificar um símbolo?
📝 Encontrou algo errado nesta página?
Sua ajuda é muito importante para melhorar a qualidade da tradução!
🐛 Encontrou um erro?
Se você encontrou:
- Erro de tradução (palavra incorreta, termo técnico errado)
- Erro de ortografia ou gramática
- Link quebrado
- Código de exemplo que não funciona
- Problema de formatação
❓ Tem uma dúvida?
Se você tem:
- Dúvida sobre o conteúdo desta seção
- Pergunta sobre um conceito do SICP
- Dificuldade em entender algum exemplo
- Questão sobre a tradução de algum termo
💡 Tem uma sugestão de melhoria?
Se você quer sugerir:
- Melhoria na explicação
- Exemplo adicional
- Recurso visual (diagrama, ilustração)
- Qualquer outra ideia
🌍 Quer discutir a tradução?
Se você quer debater:
- Escolha de tradução de algum termo
- Consistência de terminologia
- Nuances do português
Obrigado por ajudar a melhorar o SICP.js PT-BR! ✨