Dlaczego kodowanie Huffmana eliminuje entropię, której nie ma Lempel-Ziv?

Popularny algorytm DEFLATE wykorzystuje kodowanie Huffmana na Lempel-Ziv.

Ogólnie rzecz biorąc, jeśli mamy losowe źródło danych (= 1 bit entropii / bit), żadne kodowanie, w tym Huffman, prawdopodobnie nie skompresuje go średnio. Gdyby Lempel-Ziv był „idealny” (do którego zbliża się większość klas źródeł, ponieważ długość dochodzi do nieskończoności), kodowanie postów przy użyciu Huffmana nie pomogłoby. Oczywiście Lempel-Ziv nie jest idealny, przynajmniej o skończonej długości, więc pozostaje pewna nadmiarowość.

Jest to ta pozostająca nadmiarowość, którą kodowanie Huffmana częściowo eliminuje, a tym samym poprawia kompresję.

Moje pytanie brzmi: dlaczego ta pozostała nadmiarowość została skutecznie wyeliminowana przez kodowanie Huffmana, a nie LZ? Jakie właściwości Huffman kontra LZ sprawiają, że tak się dzieje? Czy po prostu ponowne uruchomienie LZ (to znaczy ponowne kodowanie danych skompresowanych LZ za pomocą LZ po raz drugi) osiągnęłoby coś podobnego? Jeśli nie, dlaczego nie? Podobnie, najpierw kompresowanie przy użyciu Huffmana, a następnie przy użyciu LZ, a jeśli nie, to dlaczego?

AKTUALIZACJA: Oczywiste jest, że nawet po LZ pozostanie pewna redundancja. Kilka osób już to zrobiło. Nie jest jasne: dlaczego Huffman lepiej rozwiązuje problem pozostałej nadmiarowości niż LZ? Co jest w tym wyjątkowego w porównaniu z pierwotną redundancją źródłową, w której LZ działa lepiej niż Huffman?

To był pierwotnie komentarz, ale stał się zbyt długi.

Jeśli spojrzysz na DEFLATE, Huffman kompresuje dane wyjściowe LZ77; LZ77 działa przez (gdy zajmuje to mniej bitów niż nieprzetworzone dane) wysyłając wskaźnik wcześniej do kompresowanego łańcucha i długość dopasowania, która mówi, ile symboli należy pobrać po wskaźniku. Teoria pokazuje, że nawet bez dodatkowej kompresji technika ta ostatecznie zbiega się z entropią źródłową. Jednak w przypadku kompresji danych za każdym razem, gdy masz dystrybucję, która nie jest całkowicie losowa, równie dobrze możesz ją skompresować. Nie ma powodu, aby sądzić, że dane wyjściowe LZ77 - wskaźniki i długości dopasowania - są całkowicie losowe. Muszą się zbiegać, aby osiągnąć całkowitą losowość w granicy asymptotycznej, ponieważ LZ77 jest asymptotycznie optymalny, ale w praktyce używa się tylko skończonego słownika, więc prawdopodobnie trzymają się z daleka od bycia całkowicie losowymi, aby wygrać, wykonując na nich dalszą kompresję. Oczywiście używasz jednego kodu Huffmana dla wskaźników, a drugiego dla długości dopasowania, ponieważ te dwa procesy mają różne statystyki.

Po co używać Huffmana zamiast LZ do drugiej rundy kompresji? Dużą przewagą LZ nad Huffmanem jest traktowanie zależności między symbolami. W języku angielskim, jeśli jedna litera jest literą „q”, następna najprawdopodobniej będzie literą „u” i tak dalej. Jeśli symbole są niezależnymi zdarzeniami, to Huffman jest prostszy i działa równie dobrze lub lepiej dla krótkich ciągów znaków. W przypadku wyjścia LZ77 moja intuicja jest taka, że ​​symbole powinny być dość niezależne, więc Huffman powinien działać lepiej.

Kompresja danych to tak naprawdę dwie rzeczy: modelowanie i kodowanie. Algorytmy rodziny LZ modelują tekst jako konkatenację dokładnych powtórzeń, która jest asymptotycznie optymalna dla wielu losowych źródeł i względnie dobra dla wielu prawdziwych tekstów. Jednak w przypadku niektórych danych wejściowych ten model może być dość zły. Na przykład nie można użyć LZ do bezpośredniej kompresji tablicy sufiksów, nawet jeśli tablica sufiksów jest tak samo ściśliwa jak oryginalny tekst.

LZ77 koduje dane wejściowe jako sekwencję krotek , po jednym na powtórzenie, gdzie jest wskaźnikiem do wcześniejszego wystąpienia, jest długością powtórzenia, a jest kolejnym znakiem. Zwykle ta sekwencja nie zawiera wielu (dość długich) dokładnych powtórzeń, więc nie możemy użyć innego algorytmu opartego na LZ do jej skompresowania. Zamiast tego musimy szukać innych modeli.p ℓ $(p, \ell, c)$$p$$\ell$$c$

Z trzech składników krotki wskaźnik może być uważany za dużą losową liczbę całkowitą, więc kodowanie go jako bitową liczbę całkowitą (dla danych wejściowych o długości ) jest dość dobrym wyborem. Z drugiej strony długości powtórzeń są zwykle małe, dlatego powinniśmy je kodować za pomocą kodów, które faworyzują małe liczby nad dużymi. Huffman jest jednym z odpowiednich schematów kodowania i są też inne. Znaki po powtórzeniach prawdopodobnie nie są równomiernie rozmieszczone, więc możemy użyć kompresora zerowego rzędu, takiego jak Huffman, aby wycisnąć najbardziej oczywistą redundancję.$\log n$$n$

Krótko mówiąc, Huffman pokonuje LZ w kompresji krotek, ponieważ jego model (stały rozkład vs. dokładne powtórzenia) lepiej pasuje do danych.

Wierzę, że odpowiedź leży w wielkości słownika odnośników.

Dane mają poczucie lokalizacji (to znaczy, jeśli użyto fragmentu danych, prawdopodobnie wkrótce zostanie ponownie użyty), a algorytm LZ wykorzystuje to w konstrukcji słownika odnośników. Generuje trie ze skończoną liczbą możliwych węzłów, aby szybko przeszukiwać . Gdy osiągnie limit rozmiaru, robi kolejną próbę, „zapominając” o poprzedniej. Musi więc ponownie zbudować tabelę wyszukiwania dla prostszych znaków, ale jeśli niektóre słowa nie są już używane, nie są już przechowywane w pamięci, więc można użyć mniejszego kodowania.

Dlatego wyjście LZ można jeszcze bardziej zmniejszyć za pomocą kodowania Huffmana, ponieważ nadmiarowość w tworzeniu prób wyszukiwania można wykryć za pomocą analizy statystycznej.

Być może jestem tutaj nie na tropie, ale kodowanie Huffmana analizuje całe dane wejściowe, aby zbudować tabelę kodowania (drzewo), podczas gdy Lempel-Ziv koduje w miarę postępów. Jest to zarówno zaletą, jak i wadą dla Huffmana. Rozczarowanie jest oczywiste, a mianowicie, że musimy zobaczyć cały wkład, zanim zaczniemy. Zaletą jest to, że Huffman weźmie pod uwagę statystyki, które występują w dowolnym miejscu na wejściu, podczas gdy Lempel-Ziv musi się do tego stopniowo rozwijać. Innymi słowy, Lempel-Ziv ma „kierunek”, którego nie ma Huffman.

Ale to wszystko jest po prostu moim naiwnym sposobem wyobrażenia sobie, jak się rzeczy mają. Potrzebowalibyśmy tutaj prawdziwego dowodu, aby zobaczyć, jak dokładnie Huffman przewyższa Lempel-Ziv.

Krótka odpowiedź brzmi: LZ jest „uniwersalnym” algorytmem, ponieważ nie musi znać dokładnego rozkładu źródła (wystarczy założyć, że źródło jest stacjonarne i ergodyczne). Ale Huffman nie jest; musi znać dokładny rozkład, z którego pobierane jest źródło (do tworzenia drzewa Huffmana). Te dodatkowe informacje sprawiają, że Huffman uzyskuje ścisłe gwarancje kompresji. Jednak w przypadku praktycznych algorytmów kompresji pliku Huffman może być mniej korzystny, ponieważ najpierw będzie musiał zebrać empiryczne statystyki pliku, a następnie dokonać faktycznej kompresji w drugiej połowie, podczas gdy LZ można zaimplementować online.

Więcej szczegółów można znaleźć w standardowych tekstach teorii informacji, np. Elementy teorii informacji autorstwa Covera i Thomasa.