Entropia de Shannon de 0,922, 3 valores distintos

14

Dada uma sequência de valores , a Entropia de Shannon na base de log  chega a . Pelo que entendi, na base  a Entropia de Shannon arredondada é o número mínimo de bits em binário para representar um único dos valores.AAAAAAAABC20.9222

Retirado da introdução nesta página da Wikipedia:

https://en.wikipedia.org/wiki/Entropy_%28information_theory%29

Então, como três valores podem ser representados por um bit?  pode ser  ,  pode ser  ; mas como você pode representar  ?A1B0C

Agradeço antecipadamente.

Sean C
fonte

Respostas:

16

A entropia que você calculou não é realmente para a sequência específica, mas para uma fonte aleatória de símbolos que gera com probabilidade  e e  com probabilidade  cada , sem correlação entre símbolos sucessivos. A entropia calculada para esta distribuição, significa que você não pode representar seqüências de caracteres geradas a partir dessa distribuição usando menos de bits por caractere, em média.A810BC1100.9220.922

Pode ser bastante difícil desenvolver um código que atinja essa taxa. * Por exemplo, a codificação de Huffman alocaria os códigos , e  a , e  , respectivamente, para uma média de  bits por caractere. Isso está muito longe da entropia, embora ainda seja muito melhor do que a codificação ingênua de dois bits por caractere. Qualquer tentativa de uma melhor codificação provavelmente vai explorar o fato de que mesmo um prazo de dez anos consecutivos é mais provável s (probabilidade ) do que um único  .01011ABC1.2A0.107B


* Acontece que não é difícil chegar tão perto quanto você deseja - veja as outras respostas!

David Richerby
fonte
18

Aqui está uma codificação concreta que pode representar cada símbolo em menos de 1 bit, em média:

Primeiro, divida a sequência de entrada em pares de caracteres sucessivos (por exemplo, AAAAAAAABC torna-se AA | AA | AA | AA | BC). Em seguida, codifique AA como 0, AB como 100, CA como 101, BA como 110, CA como 1110, BB como 111100, BC como 111101, CB como 111110, CC como 111111. Eu não disse o que acontece se houver um problema estranho. número de símbolos, mas você pode simplesmente codificar o último símbolo usando alguma codificação arbitrária; isso realmente não importa quando a entrada é longa.

Este é um código de Huffman para a distribuição de pares independentes de símbolos e corresponde à escolha de n=2 na resposta de Yuval. n maior levaria a códigos ainda melhores (aproximando-se da entropia de Shannon no limite, como ele mencionou).

O número médio de bits por par de símbolos para a codificação acima é

8108101+38101103+1108104+41101106=1.92
1.92/2=0.96

nomadictype
fonte
13

D{A,B,C}XDPr[X=A]=4/5Pr[X=B]=Pr[X=C]=1/10

Para cada , podemos construir códigos de prefixo modo que nCn:{A,B,C}n{0,1}

limnEX1,,XnD[Cn(X1,,Xn)]n=H(D).

Em palavras, se codificarmos um grande número de amostras independentes de , então, em média, precisamos de bits por amostra. Intuitivamente, a razão que podemos fazer com menos de um bit é que cada amostra individual é bastante provável que seja .DH(D)0.922A

Esse é o verdadeiro significado de entropia e mostra que calcular a "entropia" de uma string é um exercício inútil.A8BC

Yuval Filmus
fonte