---

Jeg har data AAAAAAAAAABC og vil beregne entropien
AAAAAAAAAABC

sansynlighederne er
A:10/12=0,83333333333333333333333333333333
B:1/12=0,083333333333333333333333333333333
C:1/12=0,083333333333333333333333333333333

entropi = -
0,83333333333333333333333333333333 * -0,26303440583379383358341951445843 +
0,083333333333333333333333333333333 * -3,5849625007211561814537389439478 +
0,083333333333333333333333333333333 * -3,5849625007211561814537389439478 =
0,81

Det skulle være antal bit pr "codeword". Det skal naturligvis rundes op til
en hel bit og man får een bit, men den kan da aldrig nogensinde repræsentere
tre forskellige værdier, som der er i data. Hvad går galt her?

---

Scripsit "Søren N" <soren@ni.mail.dk>

> sansynlighederne er
> A:10/12=0,83333333333333333333333333333333
> B:1/12=0,083333333333333333333333333333333
> C:1/12=0,083333333333333333333333333333333

> Det skulle være antal bit pr "codeword". Det skal naturligvis rundes op til
> en hel bit og man får een bit, men den kan da aldrig nogensinde repræsentere
> tre forskellige værdier, som der er i data. Hvad går galt her?

Informationsteoretisk entropi bliver kun til virkelige bits når du har
mange data at repræsentere. I det foreliggende tilfælde kan du kun
regne med at komme ned omkring 0,8 bits pr symbol hvis du har en hel
strøm af mange symboler at komprimere. I så tilfælde kan du fx kode
grupper på 3 symboler ad gangen som Huffman-kodning. Så vil gruppen
AAA blive represneteret med én bit, og i øvrigt får vi fordelingen

1 kombination med 3 A'er (p=1000/1728) fylder 1 bit ~ 1000
6 kombinationer med 2 A'er (p=100/1728) fylder 4 bit ~ 2400
3 kombinationer med 1 A (p=10/1728) fylder 6 bit ~ 240
9 kombinationer med 1 A (p=10/1728) fylder 7 bit ~ 630
8 kombinationer unden A (p=1/1728) fylder 10 bit ~ 80

hvor sidste kolonne angiver forventet antal bits til at kode 12³=1728
grupper a 3 symboler. I alt 4350 bits, dvs 2,517 bits pr gruppe og
0,839 bits pr underliggende symbol.

Hvis du tager større grupper end 3 symboler i hver, vil antallet af
bits pr underliggende symbol konvergere mod din beregnede
entropi på 0,817.

--
Henning Makholm "Han råber og skriger, vakler ud på kørebanen og
ind på fortorvet igen, hæver knytnæven mod en bil,
hilser overmådigt venligt på en mor med barn, bryder ud
i sang og stiller sig til sidst op og pisser i en port."

---

Scripsit Henning Makholm <henning@makholm.net>

> 3 kombinationer med 1 A (p=10/1728) fylder 6 bit ~ 240

Men spørg mig ikke om hvordan jeg fik 3*6*10 til at blive 240...

--
Henning Makholm "We can hope that this serious deficiency will be
remedied in the final version of BibTeX, 1.0, which is
expected to appear when the LaTeX 3.0 development is completed."

---

> I så tilfælde kan du fx kode
> grupper på 3 symboler ad gangen som Huffman-kodning. Så vil gruppen
> AAA blive represneteret med én bit, og i øvrigt får vi fordelingen<snip
eksempel>

Men jeg har jo i mit regnestykke defineret at mine symboler er A,B,C. Mit
tegnsæt indeholder ikke blokke af A. Entropien bliver da også beregnet ens
for AAAAAAAAAABC og for AABAACAAAAAA selvom man ikke har samme mulighed for
at lave lange A-blokke.

Ikke at jeg vil påstå at du har misforstået noget, for det virker
usansynligt, men skulle huffmann-koderne ikke repræsentere A,B og C som
selvstændige tegn i mit eksempel, og der udnytte at repræsentere A med
færrest bit og B og C med "næst-færrest", så eksempelvis A=1, B=01, C=00.

Jeg mener... selvfølgelig vil det komprimere mit eksempel mere at se det som
længere blokke, men huffmankoder laver jo kortere repræsentationer af af de
tegn som er defineret og som jeg regner på. Her er de tegn A,B og C. Det er
så der jeg ikke forstår hvordan jeg skulle komme på 0.8, da nok så mange
data hvor frekvensen af A er 10*frekvensen af B og af C, stadig ikke kan
skrives med 0.8 bit pr tegn, hvis jeg holder fast i de tre tegn...?

Dit eksempel med at tage stadig større blokke svarer jo til at jeg har 1024
bytes. Opdeler dem i kodeord af 512 bytes. Repræsenterer første kodeord med
0 og det andet med 1. Så er data komprimeret til 1 byte...

Måske jeg blander to ting sammen... entropiens værdi og gennemsnitligt antal
bit pr kodeord?

---

Søren N wrote:

> Ikke at jeg vil påstå at du har misforstået noget, for det virker
> usansynligt, men skulle huffmann-koderne ikke repræsentere A,B og C som
> selvstændige tegn i mit eksempel, og der udnytte at repræsentere A med
> færrest bit og B og C med "næst-færrest", så eksempelvis A=1, B=01, C=00.

Korrekt.

> Det er så der jeg ikke forstår hvordan jeg skulle komme på 0.8, da nok så
> mange data hvor frekvensen af A er 10*frekvensen af B og af C, stadig ikke
> kan skrives med 0.8 bit pr tegn, hvis jeg holder fast i de tre tegn...?

Det kan du heller ikke. Entropien er rigtig nok 0.8. Og som du siger, kan
man ikke med huffman komme ned under 1 bit pr. tegn. Problemet ligger i at
din "ordbog" kun indeholder 3 forskellige tegn. Prov i stedet med et
"rigtigt" eksempel, med fx. 256 forskellige tegn.

> Måske jeg blander to ting sammen... entropiens værdi og gennemsnitligt
> antal bit pr kodeord?

De kan sagtens blandes sammen (selv om man ikke altid kommer ned og rammer
entropien), dit eksempel var blot for simpelt.

--
/Jesper

---

Scripsit "Søren N" <soren@ni.mail.dk>

> > I så tilfælde kan du fx kode
> > grupper på 3 symboler ad gangen som Huffman-kodning. Så vil gruppen
> > AAA blive represneteret med én bit, og i øvrigt får vi fordelingen

> Men jeg har jo i mit regnestykke defineret at mine symboler er A,B,C.

Den informationsteoretiske entropi angiver en undergrænse for den
gennemsnitlige omkostning pr. symbol når du repræsenterer en strøm af
mange symboler på én gang.

> Mit tegnsæt indeholder ikke blokke af A.

Informationsteorien er ligeglad med om dens brugere er for
snæversynede til at finde smarte måder at repræsentere data på.
Sådanne snæversynede brugere kan bare ikke altid nå tæt på
undergrænsen.

> Entropien bliver da også beregnet ens for AAAAAAAAAABC og for
> AABAACAAAAAA

Det giver ikke meningsfulde resultater at tale om entropi af et enkelt
konkret datapunkt. Entropi er først relevant når man ser på hele
sandsynlighedsfeltet på en gang.

> Ikke at jeg vil påstå at du har misforstået noget, for det virker
> usansynligt, men skulle huffmann-koderne ikke repræsentere A,B og C som
> selvstændige tegn i mit eksempel, og der udnytte at repræsentere A med
> færrest bit og B og C med "næst-færrest", så eksempelvis A=1, B=01, C=00.

Sådan er man nødt til at gøre hvis man Huffman-koder et enkelt symbol
ad gangen. Det er der ikke noget galt i, hvis man accepterer at det
gennemsnitlige bitforbrug kan være betydeligt større end den
informationsteoretiske entropi.

> Jeg mener... selvfølgelig vil det komprimere mit eksempel mere at se det som
> længere blokke, men huffmankoder laver jo kortere repræsentationer af af de
> tegn som er defineret og som jeg regner på.

Informationsteorien ved ikke at du kunstigt begrænser dig til at
repræsentere hvert tegn uafhængigt.

> Det er så der jeg ikke forstår hvordan jeg skulle komme på 0.8,

Det har jeg forklaret hvordan du gør. Det er ikke teoriens problem at
du bagefter stiller kunstige begrænsninger op der gør at du ikke vil
anerkende løsninger.

> Dit eksempel med at tage stadig større blokke svarer jo til at jeg har 1024
> bytes. Opdeler dem i kodeord af 512 bytes. Repræsenterer første kodeord med
> 0 og det andet med 1. Så er data komprimeret til 1 byte...

Hvis din sandsynlighedsfordeling siger at der kun er to af de 2^512
muligheder der forekommer i praksis, er entropien af såden en blok
ganske rigtigt højst 1 bit. (Hvis de to mulige 512-bits-følger har
forskellige sandsynligheder, er entropien mindre end 1 bit).

> Måske jeg blander to ting sammen... entropiens værdi og gennemsnitligt antal
> bit pr kodeord?

Entropien er undergrænsen for det gennemsnitlige antal bits pr kodeord
man kan opnå ved nogensomhelst kodning.

--
Henning Makholm "En tapper tinsoldat. En dame i
spagat. Du er en lykkelig mand ..."