Codificação Huffman: por que não há necessidade de um separador?

17 
Char        Code
====        ====
E           0000
i           0001
y           0010
l           0011
k           0100
.           0101
space       011
e           10
r           1100
s           1101
n           1110
a           1111

Texto original:

Olhos misteriosos vistos perto do lago

Codificado:
0000101100000110011100010101101101001111101011111100011001111110100100101

Por que não há necessidade de um separador na codificação Huffman?

coding-theory encoding-scheme huffman-coding BufBills
fonte
1
Porque quando você decodifica um valor binário, pega o pedaço de bits "da esquerda para a direita", o que corresponder primeiro ao valor do texto original. Como neste caso, você vê o pedaço mais à esquerda (0000) corresponde a E. Se houvesse algum símbolo com um valor de 000 no seu código de char, você substituiria o 000 por esse símbolo e começaria a procurar novamente os bits restantes em uma maneira "da esquerda para a direita". É por isso que você não precisa de separação.
precisa saber é o seguinte
1
A questão implica que geralmente são necessários separadores. Você já sabe que não precisa de separadores Eerie eyes seen near lake(bem, exceto pelo caractere de espaço). Mas os personagens em si não precisam de separadores. Por que não é isso?
precisa saber é o seguinte
tente decodificá-lo você mesmo, nunca há ambiguidade.
Njzk2 28/04
@ MSalters: Mas geralmente são necessários separadores com palavras de comprimento variável: cat cheat for mice≠ catch eat form ice. Sua analogia é falha: cada letra é atômica; as letras são trivialmente distintas e intrinsecamente separáveis. Uma analogia melhor seria "Por que você pode ler um script cursivo (manuscrito), quando cada palavra é apenas uma linha longa, distorcida e com interseção automática?", E mesmo essa é uma analogia ruim, pois é possível olhar para uma palavra manuscrita ( ou até uma parte de uma) e discernir as letras individuais - enquanto uma string codificada por Huffman é sem sentido se você não pode ver o começo.
G-Man diz 'Reinstate Monica'
@MSalters Não vejo seu ponto. Não preciso de separadores para os caracteres porque estamos usando uma codificação de largura fixa: cada bloco sucessivo de oito bits corresponde a um caractere. Mas a codificação de Huffman não tem largura fixa, daí a questão.
David Richerby

Respostas:

50

Você não precisa de um separador porque os códigos Huffman são códigos sem prefixo (também, sem ajuda, conhecidos como "códigos de prefixo"). Isso significa que nenhuma palavra de código é um prefixo de qualquer outra palavra de código. Por exemplo, a palavra de código para "e" no seu exemplo é 10 e você pode ver que nenhuma outra palavra de código começa com os dígitos 10.

Isso significa que você pode decodificar com avidez lendo a sequência codificada da esquerda para a direita e exibindo um caractere assim que visualizar uma palavra-código. Por exemplo, 0, 00 e 000 não codificam nada, então você continua lendo bits. Quando você lê 0000, ele codifica "E" e, como o código é livre de prefixo, você sabe que não há outra palavra de código 0000x; portanto, agora você pode emitir "E" e começar a ler a próxima palavra de código. Novamente, 1 não codifica nada, mas 10 codifica "e". Nenhuma outra palavra de código começa com "10", para que você possa imprimir "e". E assim por diante.

David Richerby
fonte
1
Os códigos de prefixo também são comumente conhecidos como Códigos Instantâneos (veja, por exemplo, Elementos da Teoria da Informação por Cover & Thomas). Eu acho que o termo código de prefixo aparece muito mais frequentemente do que o código sem prefixo.
Batman
3
Também vale a pena mencionar que, para decodificar uma sequência de códigos Huffman concatenados, deve-se ter o limite correto da palavra-código para começar. Se alguém tentar decodificar a sequência em um limite incorreto da palavra de código, o processo de decodificação gerará uma sequência incorreta de símbolos de saída.
Rwong 28/04
@rwong: Se o código Huffman começar a ser sincronizado incorretamente, ele poderá continuar a emitir símbolos errados indefinidamente, mas sempre que determinar incorretamente o comprimento de um símbolo, o número de possíveis estados errados será reduzido.
Supercat
@ supercat Acho que a frase seria de uma maneira diferente: se um decodificador Huffman for inicialmente definido em um limite de palavra de código errado e iniciar o processamento, há uma possibilidade (que pode ser zero ou qualquer coisa, e pode depender do dicionário e do conteúdo de fluxo de bits) que pode atingir um limite correto de palavras de código por coincidência em tempo finito e, quando isso ocorrer, produzirá o resultado correto de decodificação para os símbolos subseqüentes. Houve alguma pesquisa sobre as propriedades (no dicionário de palavras de código e no fluxo de bits) que garantissem essa ressincronização.
Rwong 29/04/19
@rwong: se os dados originais fossem aleatórios com uma distribuição em que os bits do fluxo tivessem uma probabilidade independente de ser um ou zero, a probabilidade de permanecer fora de sincronia por mais de N símbolos decairia exponencialmente com o aumento de N. É mais provável que os dados reais contenham padrões que possam impedir a ressincronização, mas, na prática, é improvável que um erro no início de um arquivo de texto de 100 MB corrompa todos os 100 MB de texto.
Supercat 29/04
13

É útil imaginá-lo como uma árvore. Você está simplesmente percorrendo a árvore até atingir um nó folha e, em seguida, reiniciando a partir da raiz. A partir do algoritmo que codifica huffman, você pode ver que esse tipo de estrutura é criado no processo.

https://en.wikipedia.org/wiki/File:HuffmanCodeAlg.png

quietContest
fonte
6
O aspecto importante aqui é que todas as palavras de código válidas são folhas. Você precisaria de separadores se também tivesse símbolos nos nós internos.
MvG 28/04
3

Nenhum código diferente de E começa com 0000. Nenhum código além de i começa com 0001. E assim por diante. Como um caso extremo, nenhum código diferente de e começa com 01. Você não possui coisas como E = 0000, espaço = 000, nas quais você não saberia o que fazer se encontrar três zeros.

Veja sua sequência codificada: 0000101100000 ...

Você leu o primeiro zero. Você sabe que o código é E, i, y, l, k, vírgula ou espaço. O próximo zero significa que não é k, vírgula ou espaço, mas E, i, y ou l. O próximo zero significa que é E ou i. O próximo zero significa que é um E. Quando você sabe qual é o código, sabe que analisou todos os bits desse código.

Então você tem 101100000 ... O 1 significa que você tem e, r, s, n ou a. O próximo bit é 0, então o código é e. Novamente, você terminou com esse personagem.

gnasher729
fonte
-2

Não podemos usar o separador na codificação Huffman porque o equivalente binário de cada letra não corresponde ao código prefixado de qualquer letra, portanto, podemos fazer isso sem usar o separador.

Sandeep Das
fonte
3
Eu já não disse isso, apenas sem os níveis confusos de muitas negações aninhadas. (E, a propósito, não é que nós não podemos usar um separador, basta que nós não precisam para.)
David Richerby