Czy algorytmy kompresji bezstratnej zmniejszają entropię?

Według Wikipedii :

Entropia Shannona mierzy informacje zawarte w wiadomości, a nie część wiadomości, która jest określona (lub przewidywalna). Przykłady tych ostatnich obejmują nadmiarowość w strukturze języka lub właściwości statystyczne związane z częstotliwościami występowania par liter lub słów, trojaczków itp.

Zatem entropia jest miarą ilości informacji zawartych w wiadomości. Kodery entropijne są używane do bezstratnej kompresji takiego komunikatu do minimalnej liczby bitów potrzebnej do jego przedstawienia (entropia). Dla mnie wygląda to na idealny koder entropii, który byłby potrzebny do bezstratnego kompresowania wiadomości tak bardzo, jak to możliwe.

Wiele algorytmów kompresji wykorzystuje jednak kroki przed kodowaniem entropijnym, aby rzekomo zmniejszyć entropię wiadomości.

Według niemieckiej Wikipedii

Entropiekodierer werden häufig mit anderen Kodierern kombiniert. Dabei dienen vorgeschaltete Verfahren dazu, die Entropie der Daten zu verringern.

Po angielsku:

Kodery Entropy są często łączone z innymi koderami. Poprzednie kroki służą zmniejszeniu entropii danych.

tj. bzip2 używa transformacji Burrowsa-Wheelera, a następnie transformacji Move-To-Front-Transform przed zastosowaniem kodowania entropijnego (w tym przypadku kodowania Huffmana).

Czy te kroki naprawdę zmniejszają entropię wiadomości, co oznaczałoby zmniejszenie ilości informacji zawartych w wiadomości? Wydaje mi się to sprzeczne, ponieważ oznaczałoby to utratę informacji podczas kompresji, zapobiegając bezstratnej dekompresji. A może po prostu przekształcają komunikat w celu poprawy wydajności algorytmu kodowania entropii? Czy też entropia nie odpowiada bezpośrednio ilości informacji zawartych w wiadomości?

Wiele przypadkowych opisów entropii jest w ten sposób mylące, ponieważ entropia nie jest tak schludnym i uporządkowanym środkiem, jak czasami się przedstawia. W szczególności standardowa definicja entropii Shannona stanowi, że ma ona zastosowanie tylko wtedy, gdy, jak ujęła to Wikipedia, „informacje wynikające z niezależnych zdarzeń są addytywne”.

Innymi słowy, niezależne zdarzenia muszą być statystycznie niezależne. Jeśli nie są, musisz znaleźć reprezentację danych, która definiuje zdarzenia w sposób, który czyni je naprawdę niezależnymi. W przeciwnym razie przecenisz entropię.

Innymi słowy, entropia Shannona dotyczy tylko rozkładów prawdziwego prawdopodobieństwa, a nie procesów losowych w ogóle. Dla konkretnych przykładów procesów, które nie pasują do założeń entropii Shannona, rozważ ...

Procesy Markowa

Proces Markowa generuje serię zdarzeń, w których próbkowane jest ostatnie zdarzenie z rozkładu zależnego od jednego lub większej liczby wcześniejszych zdarzeń. Oczywiście ogromna liczba zjawisk w świecie rzeczywistym jest lepiej modelowana jako procesy Markowa niż jako dyskretne, niezależne rozkłady prawdopodobieństwa. Na przykład: tekst, który teraz czytasz!

Naiwnie obliczona szybkość entropii Shannona procesu Markowa zawsze będzie większa lub równa rzeczywistej szybkości entropii procesu. Aby uzyskać prawdziwą entropię procesu, należy wziąć pod uwagę zależność statystyczną między zdarzeniami. W prostych przypadkach wzór na to wygląda następująco :

Można to również przedstawić w następujący sposób :

Ponownie cytując Wikipedię, tutaj „ $\mu_i$ jest asymptotycznym rozkładem łańcucha” - to jest ogólne prawdopodobieństwo, że dane zdarzenie nastąpi w długim horyzoncie czasowym.

Jest to wszystko skomplikowany sposób powiedzenia, że ​​nawet jeśli można obliczyć ogólne prawdopodobieństwo danego zdarzenia, pewne sekwencje zdarzeń są bardziej prawdopodobne niż inne, które zostaną wygenerowane przez proces Markowa. Na przykład następujące trzy ciągi angielskich słów są coraz mniej prawdopodobne:

• Pobiegli do drzewa
• Drzewo podbiegło do nich
• Drzewa, aby biegli

Ale entropia Shannona oceni wszystkie trzy łańcuchy jako równie prawdopodobne. Entropia procesu Markowa bierze pod uwagę różnicę, w wyniku czego przypisuje niższą szybkość entropii do procesu.

Wskaźniki entropii są zależne od modelu

Jeśli pomniejszysz wyjście, oto duży obraz: szybkość entropii danej sekwencji zdarzeń z nieznanego źródła zależy od modelu. W zależności od sposobu modelowania procesu, który je wygenerował, przypisujesz inną szybkość entropii do określonej serii zdarzeń.

I bardzo często twój model procesu nie będzie całkiem poprawny. To nie jest prosty ani łatwy do rozwiązania problem. W rzeczywistości nie jest możliwe przypisanie prawdziwej szybkości entropii do wystarczająco długiej i złożonej sekwencji zdarzeń, jeśli nie wiesz, jaki jest prawdziwy proces leżący u podstaw. Jest to centralny wynik w algorytmicznej teorii informacji .

W praktyce oznacza to, że biorąc pod uwagę nieznane źródło sekwencji zdarzeń, różne modele przyniosą różne entropie i na dłuższą metę niemożliwe jest ustalenie, która z nich jest poprawna - chociaż ta, która przypisuje najniższą entropię, jest prawdopodobnie najlepsza.

Nie, jeśli algorytm jest bezstratny, żadne kroki w sekwencji kompresji nie mogą zmniejszyć jego entropii - w przeciwnym razie nie byłby w stanie dekompresować / zdekodować. Jednak dodatkowa entropia może być przechowywana w informacjach „poza pasmem” - takich jak lista, którą należy zachować, aby zdekodować transformację przejścia do przodu.

Zmniejszają pozorną entropię związaną ze strukturą oryginalnej wiadomości. Innymi słowy, dostrajają przekaz, aby wykorzystać moc kolejnych etapów kompresji.

Jednym prostym przykładem byłoby zastąpienie nazwy w znacznikach końcowych xml specjalnym symbolem. Możesz z tego doskonale odtworzyć oryginalny plik XML, ale kompresor nie musi ponownie umieszczać pełnej nazwy w tym miejscu.

Bardziej realnym przykładem jest kompresja png. Jego kompresorem entropijnym jest DEFLATE, który jest kombinacją Lempel-Ziff i Huffman. Oznacza to, że najlepiej działa z wartościami i wzorcami, które często się powtarzają. Większość sąsiadujących pikseli ma zwykle podobne kolory. Tak więc do każdego wiersza przypisany jest filtr, który zamienia oryginalne wartości pikseli w kodowanie różnicowe. W ten sposób wartości zakodowane przez DEFLATE są w większości bliskie 0. W skrajnym przypadku zmieni to gładki gradient ze wszystkich różnych wartości w jedną wartość w całym rzędzie, z którą część LZ lub DEFLATE wykonuje bardzo szybko.

Kodery Entropii nie kompresują komunikatu do minimalnej liczby bitów potrzebnej do jego przedstawienia. Wiem, że to kuszące, ale to nie to, co robią. Nie są magią i nie mogą tego osiągnąć.

Zamiast tego robią coś mniej magicznego - ale nadal przydatnego. Załóżmy na chwilę, że wiemy, że każda postać wiadomości została wybrana niezależnie od jakiejś dystrybucji. Wtedy byłoby możliwe zbudowanie bezstratnego algorytmu kompresji, który optymalnie kompresuje wiadomości. Algorytmy te nazywane są koderami entropijnymi.

Teraz prawdziwe wiadomości zwykle nie mają tej właściwości niezależności. Na przykład, jeśli zobaczysz pytanie Q, prawdopodobne jest, że następna litera to U. I tak dalej. Nadal możliwe jest zastosowanie algorytmu kodera entropijnego do prawdziwej wiadomości, w której każdy znak nie jest wybierany niezależnie od reszty. Algorytm nadal będzie bezstratny, nadal można go używać do kompresji, a w praktyce nadal często skraca długość wiadomości. Jednak nie skraca go do minimalnej możliwej długości. Nie kompresuje wiadomości do czegoś, którego długość jest równa entropii wiadomości; mniej go kompresuje.

Kiedy uświadomisz sobie tę właściwość enkoderów entropijnych, paradoks wyparuje.

Ogólnie rzecz biorąc, każdy bezstratny krok nigdy nie zmniejsza entropii wiadomości. Może jednak nadać komunikatowi formę, w której inny algorytm kompresji jest bardziej skuteczny, więc może być przydatny (średnio) w praktyce.

Słowo „Entropia”, często używane nieco luźno, odnosi się do dwóch różnych rzeczy:

• „Całkowita ilość informacji” w komunikacie lub systemie

• „Gęstość” informacji lub to, jak mocno informacje są zapakowane.

Cytat OP dotyczący wpisu Wikipedii dla https://en.wikipedia.org/wiki/Entropy_(information_theory) odnosi się do pierwszego:

Shannon's entropy measures the information contained in a message

Ale (przynajmniej kiedy to piszę) ten sam artykuł zaczyna się od:

Information entropy is the average rate at which information is produced by a stochastic source of data.

Tak więc jeden jest kwotą, a drugi stawką (podobną do odległości względem prędkości). Są one czasami nazywane właściwościami „ekstensywnymi” i „intensywnymi” (patrz https://en.wikipedia.org/wiki/Intensive_and_extensive_properties#Extensive_properties ).

Klasycznym przykładem tego rozróżnienia jest słynny sygnał latarni Paula Revere'a: „jeden drogą lądową, a drugi drogą morską”. 1 bit całości informacji (jeśli zignorujemy przypadek „brak, jeśli jeszcze nie dotarłem do North Church”). Gdyby Paweł dodał kolejny zestaw lampionów w każdym oknie budynku, byłoby to „zbędne”: nie ma więcej informacji, więc ta sama entropia „całkowita” lub „obszerna”; ale znacznie większa długość wiadomości, znacznie niższa „intensywna” entropia.

Jeśli zacznie w ten sposób, ale zmieni się, aby użyć tylko jednego zestawu lampionów, będzie to „bezstratna kompresja” jak w pytaniu OP. „Obszerna” entropia jest taka sama, ale „intensywna” entropia jest inna: ponieważ liczba lampionów w drugim oknie jest silnie skorelowana z liczbą wyświetlanych w pierwszym, zbędna wiadomość jest bardziej przewidywalna lub mniej losowy, więc ma znacznie niższą intensywną entropię.

Należy pamiętać o dwóch innych ważnych sprawach:

• Po pierwsze, zazwyczaj nie znamy „prawdziwej” entropii systemu w żadnym sensie. Naiwny obserwator nie wie, czy „3 latarnie” to inna wiadomość, czy też sygnały w innym oknie są zbędne. Jeśli Paul sprawi, że jego jazda stanie się nawykiem, możemy policzyć i sprawdzić, czy okna zawsze do siebie pasują. Ale może po prostu nie oglądaliśmy wystarczająco długo, aby zobaczyć rzadkie (i prawdopodobnie ważne!) Wyjątki.

• Po drugie, liczy się sposób pomiaru. Rozważ próbę oszacowania, ile jest przekazywana przez każdą kolejną literę tekstu (jest to szybkość, więc „intensywna” entropia, zwana również czasami „entropią względną”):

  • Jeśli zauważysz, że ludzie wysyłają tekst w jednostkach 8-bitowych, twoje pierwsze „oszacowanie” może wynosić 8 bitów na literę.
  • Jeśli policzysz liczbę różnych używanych liter, oszacujesz log2 (26) lub 4,7 bitów na literę (nieco więcej, jeśli weźmiesz pod uwagę spacje, wielkość liter itp.).
  • Jeśli uważasz, że „e” jest lepszym wyborem dla „następnej litery” niż „z”, zmierzysz częstotliwość liter i uzyskasz około 4,14 (patrz http://people.seas.harvard.edu/~jones/cscie129/ papers / stanford_info_paper / entropy_of_english_9.htm ).
  • Jeśli policzysz pary liter, wybierzesz wzory takie jak „qu”, „th” itp. I uzyskasz około 3,56.
  • Jeśli policzysz sekwencje składające się z około 5 liter, otrzymasz jeszcze niższe wartości, a jako bonus możesz dość niezawodnie odróżnić, w jakim języku ludzkim jest tekst).
  • Jeśli jesteś tak wymagający i sprytny jak NG Burton i JCR Licklider w „Ograniczeniach dalekiego zasięgu w statystycznej strukturze drukowanego języka angielskiego” (American Journal of Psychology 68 (1955)), możesz przejść do sekwencji 10, 0000 liter z rzędu i znajdź jeszcze jedną wartość entropii.

Ale oczywiście wiadomości mogą (i mają) wiele wzorców, które nie są modelowane takimi metodami n-gram, więc „prawdziwa” entropia jest wciąż niższa.

Jeśli modelujesz teoretyczne nieskończone źródło z idealnie losowym rozkładem tokenów Zipfiana, możesz obliczyć jego rozległą i intensywną entropię, która okazuje się zależeć tylko od liczby możliwych różnych tokenów. Wykresy tego, jak wygląda każdy typ entropii wraz ze wzrostem liczby, znajdują się w [ http://www.derose.net/steve/writings/dissertation/Diss.0.html] . Obie zachowują się zupełnie inaczej:

• ogółem (obszerne): http://www.derose.net/steve/writings/dissertation/Graph13.png
• względny (intensywny): http://www.derose.net/steve/writings/dissertation/Graph14.png

Mam nadzieję, że pomaga lub jest co najmniej interesujące ...

Podejrzewam, że sformułowanie w niemieckiej Wikipedii jest błędne. Sprężarki zwiększają entropię. To znaczy, nie ogólna entropia, ale entropia na bit : gęstość informacji. Np. Zastosowano pewne kodowanie i schemat słownikowy w celu skondensowania danych. Teraz te same informacje są pakowane w mniejszą liczbę bitów, więc każdy bit niesie więcej informacji. Kolejne kodowanie Huffmana robi trochę więcej tego samego; to tylko kolejna warstwa kompresji.