Jak praktycznie zmierzyć entropię pliku?

Próbuję teraz zmierzyć wiele niepotrzebnych (rzeczywistych) informacji, które zawiera mój plik. Niektórzy nazywają to wielkością entropii.

Oczywiście istnieje standardowy p (x) log {p (x)}, ale myślę, że Shannon rozważał go tylko z punktu widzenia transmisji przez kanał. Dlatego formuła wymaga rozmiaru bloku (powiedzmy w bitach, zazwyczaj 8). W przypadku dużego pliku obliczenia te są dość bezużyteczne, ignorując korelacje między symbolami na krótkich i długich dystansach.

Istnieją drzewa binarne i metody Ziv-Lempel, ale mają one charakter wysoce akademicki.

Ściśliwość jest również uważana za miarę entropii, ale wydaje się, że nie ma dolnej granicy co do stopnia ściskania. Dla mojego pliku hiss.wav

oryginalny hiss.wav = 5,2 MB
entropia za pomocą wzoru Shannona = 4,6 MB
hiss.zip = 4,6 MB
syk. 7z = 4,2 MB
hiss.wav.fp8 = 3,3 MB

Czy istnieje jakaś praktyczna metoda pomiaru ilości entropii w obrębie hiss.wav?

entropy

— Paweł Uszak
źródło

Nie rozumiem, co rozumiesz przez „wysoce naukowy”.

— David Richerby,

Dead 'ard. Pomyślałbym, że skala globalnych wydatków na badania wydanych na maksymalizację transmisji i przechowywania danych byłaby bardziej rozwinięta w sposobie szacowania, ile naprawdę masz do czynienia z cholernymi rzeczami. Nie pomyślałbym, że poza sferą możliwości istnieje narzędzie do przekazywania plików, które przesyłasz niektóre dane, które generują teoretyczną ocenę entropii. Tylko w co grają producenci telefonów i dysków?

— Paul Uszak

Entropia jest cechą zmiennej losowej . Dany plik ma zerową entropię, ponieważ jest stały. Entropia ma sens w wielu sytuacjach, w których nie ma kanału i można go zastosować do losowego zestawu, powiedzmy, plików WAV, generowanych z danego źródła. W tym przypadku jest całym plikiem WAV. $x$

Rzeczywisty plik WAV (z wyłączeniem nagłówka) można uznać za wygenerowany przez jakieś źródło Markovian. To źródło wytwarza amplitudy dźwięków („próbek”) w sekwencji, z których każda zależy od poprzedniej. Po bardzo długim uruchomieniu procesu entropia każdej próbki (a dokładniej entropia warunkowa przy poprzednich próbach) zbliża się bardzo do pewnej wartości granicznej, którą określamy jako entropia źródła. Entropia próbek jest razy większa od tej liczby (w granicy; ponownie, dokładniej, mierzymy entropię warunkową). Lempel i Ziv wykazali, że jeśli entropia próbki to bitów, to ich algorytm kompresuje próbek do $N$ $N$ $H$ $N$ $HN + o(N)$ bity, z dużym prawdopodobieństwem (prawdopodobieństwo jest większe niż próbki). Kompresja Lempel – Ziv jest dość popularna w praktyce, stosowana np. W popularnym gzipformacie.

Z powodu tego wyniku Lempela i Ziva entropię źródła można aproksymować, kompresując długą sekwencję próbek przy użyciu algorytmu Lempel – Ziv. Nie szacuje to entropii określonych próbek, co nie jest dobrze zdefiniowaną koncepcją (stała sekwencja ma entropię zerową), ale raczej entropię źródła, które ją generuje.

Pokrewną koncepcją jest entropia algorytmiczna , znana również jako złożoność Kołmogorowa . Jest to długość najkrótszego programu generującego plik. Ta ilość ma sens dla pojedynczego pliku. W przypadku pliku wygenerowanego z losowego źródła twierdzenie Lempela – Ziva pokazuje, że entropia algorytmiczna pliku jest z dużym prawdopodobieństwem ograniczona entropią Shannona. Niestety, entropia algorytmiczna nie jest obliczalna, więc jest to raczej koncepcja teoretyczna.

Aby uzupełnić obraz, proponuję przeczytać artykuł Shannona o Prognozowaniu i entropii drukowanego angielskiego, aby poznać inne podejście do szacowania entropii źródła.

— Yuval Filmus
źródło

Mam. I papier Schurmann & Grassberger. Na podstawie ich szacunkowych entropii dla języka angielskiego wydaje się, że najlepszą oceną entropii, jaką możemy uzyskać, jest kompresja z wariantem PAQ8, takim jak fp8. Są i moje wyniki całkiem dobrze poślubiają prozę Szekspira.

— Paul Uszak

Problem wydaje się jednak taki, że myślałem, że musi istnieć ograniczająca teoretyczna wartość entropii źródła. Określenie przez kompresję odzwierciedla tylko efektywność algorytmu kompresji. Empirycznie twój gzip jest dobry, ale 7z jest lepszy. A FP8 jest o wiele lepszy, jak pokazano w moim pytaniu. Czy mogę znaleźć, że hiss.wav zawiera tylko 10 bajtów całkowitej entropii, gdy będę używać fp12000 w dalekiej przyszłości?

— Paul Uszak,

Entropia nie jest własnością pliku; każdy pojedynczy plik ma zerową entropię. Entropia jest raczej własnością losowego źródła. Miarą losowości, która jest właściwa dla określonych plików, jest złożoność Kołmogorowa (znana również jako entropia algorytmiczna), ale niestety ta miara nie jest obliczalna.

— Yuval Filmus

Podczas kompresji pliku w celu oszacowania entropii źródła używasz twierdzenia, które gwarantuje, że szybkość kompresji danych generowanych przez źródło zbliża się do entropii źródła. Jednak w rzeczywistych narzędziach do kompresji nie stosuje się waniliowego algorytmu Lempel – Ziv, ale jego bardziej praktyczna wersja. Jeśli chcesz oszacować entropię, być może powinieneś ponownie wdrożyć algorytm mając na uwadze ten cel.

— Yuval Filmus,

Usunąłem niekonstruktywną dyskusję; komentarze nie dotyczą długich dyskusji, z wyjątkiem ulepszenia dostępnego postu. Jeśli chcesz szczerze omawiać sprawy związane z entropią, utwórz pokój czatu. Pamiętaj, aby zachować cywilność.

— Raphael