Będę pisał

Paczor, Ty żyjesz?

Mam do Ciebie pytanie odnośnie entropii. Uwaga, skup się:

Wyobraź sobie jakiś plik z danymi. Teraz wyobraź sobie że ten plik

kompresujesz. Może to być zip, gzip, bzip, xz, lha albo nawet divx

jeśli plik wejściowy to był obraz.

No i teraz pytanie:

Która wersja pliku ma większą entropię? Przed czy po skompresowaniu?

Odpowiedzi należy nadsyłać drogą mailową do mnie (reply a nie reply to

all) wraz z uzasadnieniem do wtorku, 20.08.

Po tym terminie opublikuję odpowiedzi a najciekawsze omówimy w drodze

dyskusji mailowej.

p.s. prawidłowa odpowiedź jest tylko jedna.

--

Mariusz Wołoszyn

Obstawiłem, że maleje a nawet wynosi zero. Zobaczymy.

[edit]

A tu niestety jest dokładnie odwrotnie.

Potwierdza to to, co podejrzewałem od dawna, a co wychodziło mi w

poprzednich naszych dyskusjach: na poziomie Wikipedii wszystko kumasz

ale kiedy dochodzi do wysnuwania wniosków to masz całkowicie błędne

zrozumienie entropii. Pewnie trudność stwarza Ci fakt, że entropia

jest zdefiniowana przez negację, czyli miara NIE-porządku.

W pliku bez kompresji występuje pewien porządek. Tym porządkiem jest

chociażby to, że są to same literki w pliku tekstowym albo wyrazy albo

ciągi bajtów o tej samej wartości odpowiadające powierzchniom w tym

samym kolorze w pliku z obrazem albo jest jakas struktura pliku z

danymi, kolumny, wiersze, zbiory, drzewa, cokolwiek... Po kompresji

ten porządek znika. Idealna kompresja wypluwałaby plik z maksymalną

entropią, którego już nie da się niczym skompresować: plik, w którym

entropia jest maksymalna. Co ważne, istnieje wiele różnych plików

danej długości o maksymalnej entropii. Gdyby był tylko jeden można by

go oznaczyć jako M i podać długość pliku w efekcie zapisując go w

znacznie krótszej postaci co jest sprzeczne z założeniem, że nie da

się go skompresować bardziej. [Ta konstrukcja logiczna to się nazywa

dowód nie wprost. Dowodzi prawdziwości tezy poprzez zaprzeczenie

(sprowadzenie do sprzeczności) tezy przeciwnej.]

Kompresja więc zwiększa entropię, bo burzy struktury obecne w pliku i

zamienia je na chaos, w którym nie da się wyróżnić struktur a to

właśnie struktury i regularność daje się kompresować (jak w

najprostszym przypadku jeśli widzisz AAAAAAA to możesz napisać 7*A i

mieć tą samą informację ale w krótszym zapisie; zauważ, że 7*A to

trzy, na pozór, przypadkowe znaki, podczas gdy AAAAA... na przypadkowe

nie wyglądają.).

p.s. tu jest fajna książka Information Theory, Inference, and Learning

Algorithms (http://www.inference.phy.cam.ac.uk/itprnn/book.pdf)

p.p.s: z tym Shanonem to jest niezły lol bo się okazuje, ze w

informatyce w wielu procesach mamy do czynienia w praktyce z inną

entropią, niż ta którą on opisał i sam ten fakt można wykorzystać np.

do łamania zabezpieczeń kryptograficznych.

Ja: No bo stopień nieuporządkowania odnoszę do jakiegoś, teraz to pominę, stopnia pełnego uporządkowania i jego odwrotności. Definicja z Wikipedii skupia się, być może to błąd w wytłumaczeniu, na próbie przewidzenia następnego bitu.

Nie kojarzę akurat tej definicji ale na pewno nie chodzi o

przewidzenie ale prawdopodobieństwa wystąpienia (niby to samo ale

inaczej sformułowane). Jeśli prawdopodobieństwo wystąpienia N-tego

bitu 0 jak i 1 jest takie samo, nie zależy od tego, co już było,

pozycji, ilości zer wcześniej, czy to co 8 bit (jak było w przykładzie

z tekstem, gdzie co 8 bit był 0) itd. to mamy do czynienia z

dystrybucją jednorodną. Tak jest na przykład z cyframi dziesiętnego

rozwinięcia liczby PI. Nie na żadnej regularności, jeśli weźmiesz

dowolnie duży kawałek to będzie w nim taka sama liczba cyfr 8, 7 jak i

2, 3 itd. Jeśli nie ma żadnej reguły co to teraz ma być za cyfra to

znaczy, że mamy idealny bałagan, większego się nie da, czyli

maksymalna entropia.

Ja: Wyobraziłem sobie zatem algorytm, który analizując plik pierwotny dokonuje statystycznego doboru rodzaju kompresji, tak to jest opisane w Wiki, czyli niejako "uczy się" struktury takiego pliku. Następnie zmniejsza jego chaos, czyli nieprzewidywalność następnego bitu, uzyskując coś bliskie zeru entropii bo w procesie dekodowania każdy następny bit jest przecież przewidywalny.

No jest dokładnie odwrotnie :) Po pierwsze kompresja (czy też

szyfrowanie bo działa podobnie jeśli chodzi o entropię w pliku) rzadko

się "uczy" pliku (w sensie takim jak uczenie maszyn, chyba ze chodzi

Ci o rozpoznawanie charakterystyki pliku), po drugie właśnie w pliku

źródłowym (jeśli daje się kompresować a zakładam że tak :) rzadko jest

chaos (przecież nie zapis z /dev/urandom) tylko jakieś dane, które

właśnie mają strukturę.

Ja: Zatem entropia dla AAAA jest większa bo jest iloczynem entropii dla każdego A, a mniejsza w przypadku 4*A bo tylko pierwszy bit ma jakąś entropię (jest nieznany), a pozostałe mają zero bo są jak najbardziej przewidywalne.

Nie wiem czy zrozumiale dla was to opisałem.

Może i zrozumiale ale całkowicie błędnie :) Dla AAAA

prawdopodobieństwo wystąpienia A na dowolnej pozycji wynosi 1. W

drugim wypadku tylko 1/3.

Tutaj znalazłem fajny opis, tylko jest używane trochę inny opis, bo

sumowane jest prawdopodobieństwo dla dowolnego bajtu (bajt ma 8 bitów

więc wartości może mieć od 0 do 255 i liczona jest suma iloczynu

prawdopodobieństwa wystąpienia każdego bajtu i jego logarytmu) więc

wartości są z przedziału 0-8 (gdzie 8 pełny random):

http://www.forensickb.com/2013/03/file-entropy-explained.html