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?

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.