Czy dane można skompresować do rozmiaru mniejszego niż limit kompresji danych Shannona?

Czytałem o algorytmach kompresji danych i teoretycznym limicie kompresji danych. Ostatnio spotkałem metodę kompresji zwaną „kombinatorycznym kodowaniem entropii”, główną ideą tej metody jest kodowanie pliku jako znaków przedstawionych w pliku, ich częstotliwości i indeksu permutacji tych znaków reprezentowanych przez plik.

Te dokumenty mogą pomóc w wyjaśnieniu tej metody:

https://arxiv.org/pdf/1703.08127

http://www-video.eecs.berkeley.edu/papers/vdai/dcc2003.pdf

https://www.thinkmind.org/download.php?articleid=ctrq_2014_2_10_70019

Jednak w pierwszym dokumencie przeczytałem, że przy użyciu tej metody mogą skompresować część tekstu poniżej limitu Shannona (nie wzięli pod uwagę miejsca potrzebnego do zapisania częstotliwości znaków i miejsca potrzebnego do zapisania meta dane pliku). Pomyślałem o tym i stwierdziłem, że ta metoda nie będzie bardzo wydajna w przypadku bardzo małych plików, ale z drugiej strony może działać dobrze w przypadku dużych plików. Właściwie nie w pełni zrozumieć ten algorytm lub limitu Shannon bardzo dobrze, ja po prostu wiem, że to suma prawdopodobieństwa każdego znaku pomnożona przez stanowi odwrotność prawdopodobieństwa.$log_2$

Mam więc kilka pytań:

1. Czy ta metoda kompresji naprawdę kompresuje pliki do rozmiaru mniejszego niż limit Shannona?

2. Czy istnieje algorytm kompresji, który kompresuje pliki do poziomu poniżej limitu Shannona (odpowiedź na to pytanie, o ile wiem, nie jest)?

3. Czy kiedykolwiek istnieje metoda kompresji, która kompresuje pliki do rozmiaru mniejszego niż limit Shannona?

4. Jeśli kodowanie kombinatoryczne naprawdę kompresuje pliki poza limit Shannona, czy nie jest możliwe kompresowanie pliku raz za razem, dopóki nie osiągniemy pożądanego rozmiaru pliku?

Właściwie nie do końca rozumiem ten algorytm lub limit Shannona, po prostu wiem, że jest to suma prawdopodobieństwa każdego znaku pomnożona przez log2 odwrotności prawdopodobieństwa.

Na tym polega sedno. Limit Shannona nie jest jakąś uniwersalną właściwością ciągu tekstowego. Jest to właściwość ciągu tekstowego oraz modelu, który zapewnia (prawdopodobnie zależne od kontekstu) prawdopodobieństwo symboli. Mówi nam, jak dobrze ten model może skompresować tekst, przy założeniu , że model jest dokładny .

Jeśli użyjesz jednego modelu do obliczenia limitu Shannona, a następnie innego modelu do kompresji, jeśli drugi model jest dokładniejszy, możesz pokonać pierwotny limit Shannona, który obliczyłeś, ale to nie jest tak naprawdę istotne.

Łatwo jest pokazać, że możesz kompresować poniżej limitu Shannona - weź kompresję oszustów, która ma kilka wspólnych plików przypisanych do tokenów. Wymienione pliki są przechowywane jako te tokeny. (Oczywiście kompresor musi być bardzo duży lub czerpać z bardzo dużej biblioteki).

Kompresor z natury będzie mniej wydajny w radzeniu sobie z każdym plikiem, którego nie ma w bibliotece, ponieważ musi w jakiś sposób odróżniać token od normalnej kompresji.

To, czego nie możesz zrobić, to mieć kompresor, który przekracza limit Shannona dla wszystkich plików .

$1/2$$1/3$$1/6$$p$$log_2(1/p)$

Ale jeśli zastosujesz inny model, otrzymasz kolejną sekwencję prawdopodobieństw. Fe litera „u” jest raczej rzadka, więc jej prawdopodobieństwo w całym tekście może wynosić 3%, i jest to prawdopodobieństwo, że musisz przypisać tę literę za pomocą modelu Markowa rzędu 0 .

Ale w tekstach angielskich po „q” zwykle pojawia się „u”, więc stosując model rzędu 1, można przypisać znacznie większe prawdopodobieństwo „u” po „q”, poprawiając w ten sposób współczynnik kompresji.

Co więcej, niektóre modele generują mniej symboli niż te wejściowe, np. LZ77 zastępuje powtórzenia tekstu referencjami wstecznymi, więc „abababab” zamienia się w „ab [2,8]”.

Kiedy ktoś mówi o entropii Shannona niektórych danych, a nie danych skompresowanych przez konkretny model, zwykle ma na myśli entropię Shannona wytworzoną przez model rzędu 0, tj. Przypisując każdemu symbolowi jego prawdopodobieństwo w całym tekście. Oczywiście można pokonać ten margines, stosując do danych bardziej wyrafinowany model.

Inna możliwa interpretacja tekstu: dany algorytm kompresji zapewni lepszą kompresję niektórych tekstów, a gorszą kompresję w przypadku innych. Jednak użytkownicy na ogół troszczą się o niektóre rodzaje plików (strony HTML w języku angielskim, kod maszynowy 80386) bardziej niż inne (tabele liczb naprawdę losowych, szumy wybrane bez znaczenia, aby zminimalizować powtarzanie). Każdy schemat kompresji kompromisowy będzie lepszy w kompresji danych w świecie rzeczywistym, a gorszy niż bezużyteczny w kompresji niektórych innych ciągów znaków.