Ou então ele bufará e soprará sua casa!
Isso foi completamente irrelevante. Esse desafio é realmente sobre a codificação de Huffman . A essência disso é que a frequência de caracteres em um determinado texto é utilizada para diminuir sua representação. Em outras palavras, digamos que nosso alfabeto é a
através do z
espaço. São 27 caracteres. Cada um deles pode ser codificado exclusivamente em apenas 5 bits, porque 5 bits têm espaço suficiente para 32 caracteres. No entanto, em muitas situações (como inglês ou idiomas em geral), alguns caracteres são mais frequentes que outros. Podemos usar menos bits para os caracteres mais frequentes e (talvez) mais bits para os caracteres menos frequentes. Feito corretamente, há uma economia geral no número de bits e o texto original ainda pode ser reconstruído exclusivamente.
Vamos pegar "esta pergunta é sobre a codificação de Huffman" como exemplo. Esse texto tem 37 caracteres, o que seria normalmente 37 * 8 = 296 bits, embora apenas 37 * 5 = 185 bits se usarmos apenas 5 bits para cada caractere. Tenha isso em mente.
Aqui está uma tabela (sorta) de cada caractere e suas frequências no texto, classificadas da mais para a menos frequente (onde _ representa um espaço):
_ 5
i 4
n 3
o 3
s 3
t 3
u 3
a 2
f 2
h 2
b 1
c 1
d 1
e 1
g 1
m 1
q 1
Uma codificação ótima associada pode ser:
_ 101
i 011
n 1100
o 1101
s 1110
t 1111
u 001
a 10011
f 0001
h 0101
b 00000
c 00001
d 01000
e 01001
g 10000
m 10001
q 10010
Deve ficar claro imediatamente que essa codificação será melhor do que usar 5 bits para cada caractere. Vamos descobrir o quão melhor, porém!
145 bits , em comparação com 185! Isso economiza 40 bits, ou pouco mais de 20%! (É claro que isso pressupõe que as informações sobre a estrutura estejam disponíveis para decodificação.) Essa codificação é ideal porque não é possível eliminar mais bits alterando a representação de qualquer caractere.
A tarefa
- Escreva um programa ou função com um parâmetro que ...
- Recebe entrada de STDIN (ou equivalente) ou como um único argumento.
- Produza uma codificação Huffman ideal, como acima, com os caracteres classificados por frequência (a ordem dentro de uma classe de frequência não importa).
- Você pode supor que os caracteres na entrada sejam restritos ao intervalo ASCII
32..126
mais uma nova linha. - Você pode supor que a entrada não tenha mais que 10.000 caracteres (idealmente, em teoria, a entrada deve ser ilimitada).
- Seu código deve terminar razoavelmente rápido. O exemplo dado acima não deve demorar mais do que um minuto, na pior das hipóteses. (Isso pretende excluir a força bruta.)
- A pontuação está em bytes.
Exemplos
x
---
x 0
xxxxxxxxx
---
x 0
xxxxxxxxy
---
x 0
y 1 (these may be swapped)
xxxxxyyyz
---
x 0
y 10
z 11
uuvvwwxxyyzz
--- (or)
u 000 000
v 001 001
w 100 010
x 101 011
y 01 10
z 11 11
this question is about huffman coding
---
101
i 011
n 1100
o 1101
s 1110
t 1111
u 001
a 10011
f 0001
h 0101
b 00000
c 00001
d 01000
e 01001
g 10000
m 10001
q 10010
Feliz codificação!
Observe que essa pergunta semelhante está intimamente relacionada, mesmo a ponto de ser uma duplicata. No entanto, o consenso até agora no Meta é que o mais antigo deve ser considerado uma duplicata deste.
fonte
this question is about huffman coding
, contei que o número de bits era 145 , não 136. #Respostas:
Pitão, 53 bytes
Demonstração
Aqui está uma versão que mostra o estado interno, para que você possa ver a codificação sendo construída:
Demonstração
Copie a saída para um ambiente com linhas mais amplas para obter uma imagem mais nítida.
fonte
Python 2, 299 bytes
Aqui está minha tentativa de resposta.
Os códigos de Huffman são diferentes dos exemplos dados, mas ainda devem ser ótimos.
fonte
Matlab, 116 bytes
tabulate
faz uma tabela de frequências.huffmandict
pega uma lista de símbolos e probabilidades para cada símbolo e calcula o código.fonte
Rubi,
189180 bytesTrabalho em progresso.
É uma função anônima; atribua a algo, por exemplo
f
, e chame-o comque retorna um hash assim:
fonte
Haskell, 227 bytes
Exemplo de uso:
Como funciona:
p
chamaf
que cria a tabela Huffman na forma de uma lista de pares (caracteres, codificação), por exemplo[ ('a',"0"), ('b',"1") ]
, classifica a tabela pelo comprimento das codificações, formata cada par para saída e junta-se às novas linhas intermediárias.f
primeiro verifica a letra maiúscula e retorna a tabela correspondente. Caso contrário, classifica a sequência de entrada e agrupa seqüências de caracteres iguais (por exemplo"ababa"
- -["aaa","bb"]
) e as mapeia em pares(sequence , [(char, "")])
(->[ ("aaa", [('a',"")]), ("bb", [('b', "")])]
. O primeiro elemento é usado para acompanhar a frequência, o segundo elemento é uma lista de pares de um caractere e é codificação (que está inicialmente vazia) .Todas as tabelas Huffman de elemento único conforme o esperadop
e são combinadas porg
eh
.g
classifica a lista de pares no comprimento do primeiro elemento, ou seja, a frequência e as chamadash
.h
combina as tabelas Huffman dos dois primeiros elementos, concatenando as frequências e colocando um0
(1
) na frente de cada elemento da primeira (segunda) tabela. Concatene ambas as tabelas. Ligueg
novamente, pare quando houver um único elemento, jogue fora a parte da frequência e retorne a tabela completa de Huffman.fonte
K (ngn / k) , 78 bytes
Experimente online!
retorna uma lista de strings para impressão
h::0#'x
cria uma lista vazia para cada caractere (tecnicamente, remodela cada caractere no comprimento 0). vamos armazenar os códigos Huffman invertidos lá. usamos em::
vez de:
atribuição para tornarh
global, para que fique visível nas sub-funções..=x
é uma lista de listas - os índices da sequência agrupada por valor de caractere(#1_)
é uma função que retorna verdade se o comprimento do argumento for> 1 (tecnicamente "comprimento de 1 gota de ...")(#1_){
...}/
significa: enquanto o argumento tiver comprimento> 1, continue aplicando a função de chavesx@<#'x
classificar o argumento por comprimento0 2_
cortá-lo em uma cabeça de 2 elementos e uma cauda{h[x],:!2;y,,,/x}
atualizarh
anexando 0 e 1 aos índices contidos no cabeçalho; devolver a cauda com a cabeça como um único elemento(?,/'x,'" ",'|'$h)(?x)?>#'=x
inverta cada umh
, ordene, coloque caracteres precedentes e adicione formatosfonte
JavaScript (ES6) 279
Essencialmente, o algoritmo básico da Wikipedia. Eu provavelmente posso fazer melhor.
Mais legível dentro do snippet abaixo
fonte