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

17

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.losol2)

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?

HTG
źródło
26
Shannon udowodnił, że nie można kompresować poniżej limitu Shannon.
Yuval Filmus
11
Możesz zejść poniżej limitu Shannona dzięki kompresji stratnej . Shannon pokazał tylko, że nie można kompresować poniżej limitu bez utraty informacji . @YuvalFilmus. Podobnie jak na obrazie RGB, możesz wyrzucić bity niskiego rzędu komponentów R, G, B.
smci,
6
@smci Jest to w dużej mierze nieistotne w żadnej dyskusji na temat teorii kompresji. Oczywiście mogę wyrzucić wszystko i nazwać to kompresją.
rura
1
Powiedzmy, że mam duży plik jak obraz. Teraz w modelu odwzorowuję cały obraz na „1” ha. Skompresowałem poniżej limitu Shannona, ponieważ cały obraz jest skompresowany do „1” ......
Pieter B

Odpowiedzi:

34

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.

orlp
źródło
4
Dla praktycznego przykładu, jeśli wiesz, że twoje dane składają się z jednej litery powtarzanej N razy, możesz osiągnąć arbitralnie duże stopnie kompresji (tj. Przechodząc od 10 miliardów „a” do krotki („a”, 10000000))
Ant
12

Ł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 .

Loren Pechtel
źródło
11

1/2)1/3)1/6plosol2)(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.

Bulat
źródło
3

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.

Davislor
źródło