Hol írnak arról, hogy egy összetömörített szöveget képviselő bitszakasz nagyon hasonlít a véletlenszerű szakaszokra?

"Azt hiszem, nem értem a problémádat."

Nekem nincs problémám. :)

Mi azt tanultuk, hogy kódolásnál a Huffman kódolás (átlagos kódszóhossz szempontjából) optimális. Ekkor valószínűség szerint egy bináris fát csinálunk az eseményekből, és ez alapján csinálunk bináris kódszavakat.

Ekkor az üzenet entrópiája határozza meg az átlagos kódszóhossz elméleti minimumát.

Az entrópia itt összefüggésben van egy üzenet információtartalmával. Például:

-ha feladsz egy lottót ötösre várva, annak 0 felé közelít az entrópiája, mivel szinte biztosan nem lesz ötösöd

-ha dobsz egy kockát egy számot várva, akkor ott a maximálishoz közelít az entrópia, mivel lényegében random bármely szám ugyanannyi eséllyel lehet kimenet.

Na, kódolásnál ugyanezt kell elképzelni, csak itt mondjuk az eseményt egy fekete dobozból érkező karakterre kell cserélni, és ezt ismert statisztika alapján kódolod.

Ennél az esetnél igazából a kódszavak hossza a megközelítés alapja, azaz a hosszú kódszót ritkán vesszük elő,a rövidet gyakran, így az átlag valahol a kettő között lesz.

Viszont megnéztem pár egyszerű huffmanos fát, és a 0/1 arány elég egyenletesen alakul. Tehát a kódban kb annyi 0 lesz, mint 1. De az is lehet, hogy ez csak véletlen, és csak a kis méretű bináris fák miatt vannak ilyen jó arányban.

Minden esetre mintázatra nem lesz összetéveszthetetlen a randommal, például nem lehet tetszőleges hosszú 000.. ÉS 11111.. sorozat a kódban egyszerre.

Tehát ha odaadnád egy szakértőnek, jó eséllyel rávágná, hogy ez nem random, mert mondjuk egy helyen sincs 20 darab 0 egymás után, pedig statisztikai alapon kéne, hogy legyen ilyen x hosszú kódban.

Vagyis bocsánat, hülyeséget mondtam. Lehet egyszerre tetszőleges hosszú 00.. és 11... sorozat. Akkor viszont holnap még gondolkozok rajta.

Igazából ha van pár órád és tudsz programozni alap szinten, akkor le lehet programozni, hogy mit dob mondjuk egy 100 karakteres angol abc ascii szöveg huffmannal kódolva, meg mondjuk 500 virtuális érmedobás.

[link]