// Codificação Tunstall – compressão ótima de comprimento variável para fixo
Mapeia sequências de comprimento variável para códigos de comprimento fixo.
O dicionário é construído usando a distribuição de probabilidade dos símbolos.
Códigos de comprimento fixo permitem uma decodificação simples e rápida.
A codificação Tunstall constrói um dicionário de sequências de comprimento variável que são mapeadas para códigos binários de comprimento fixo. A partir de símbolos únicos, a sequência com maior probabilidade é expandida iterativamente adicionando cada símbolo do alfabeto. Isso cria um código variável‑para‑fixo ótimo em que as sequências mais prováveis recebem seus próprios códigos.
Texto: 'aabaa' com P(a)=0.8, P(b)=0.2 Construção do dicionário (códigos de 3 bits): Inicial: a, b Expandir 'a': aa, ab Expandir 'aa': aaa, aab Expandir 'ab': aba, abb Dicionário final (8 códigos): aaa → 000 aab → 001 aba → 010 abb → 011 aa → 100 ab → 101 a → 110 b → 111 Codificação: 'aabaa' → 001 100 (aab + aa)
A codificação Tunstall é um método de codificação entrópica de comprimento variável para fixo. Diferente de Huffman (fixo para variável), Tunstall mapeia sequências de comprimento variável para palavras de código de comprimento fixo, sendo ideal para aplicações que exigem taxa de saída constante.
Huffman: entrada fixa → saída variável (por exemplo, 'a' → '0', 'b' → '10'). Tunstall: entrada variável → saída fixa (por exemplo, 'aa' → '000', 'ab' → '001'). Tunstall é melhor para hardware e sincronização, mas normalmente alcança razões de compressão ligeiramente menores.
Comece com símbolos únicos. Em seguida, repita: 1) encontre a sequência com maior probabilidade, 2) remova-a e adicione todas as extensões possíveis com um símbolo, 3) continue até atingir o tamanho desejado do dicionário (2^n para códigos de n bits).
A codificação Tunstall é usada em compressão de voz, codificação de imagens e em situações que exigem taxa de saída fixa. É especialmente útil em implementações de hardware e sistemas em tempo real, onde códigos de comprimento variável complicariam o controle de tempo.