kompresja ma limit?

Można obliczyć entropię danych, czy coś tam, ale czy to ma tu kluczowe znaczenie?
Przecież kompresor może użyć pseudorandom, czyli jakiś tam algorytm generujący ciągi liczb,
i używając tych liczb pozmieniać dane, co przecież zmieni tę wcześniej liczoną entropię!

Jak to z tym jest - istnieje ścisła teoria, czy też jest to nierozstrzygnięte
jak wiele innych problemów, np. problem NP, o którym nie wiadomo czy nie jest on redukowalny do P,
albo analogowe metody do NP, które używając 2^n danych rozwiązują go bez problemu - liniowo?

1. Nie rozumiesz pojęcia entropii.
2. Tak, kompresja ma ograniczenie, które można wyliczyć z wzoru Shannona. Ten wzór określa ile informacji niesie dany ciąg. Nie da się tej wartości "zmniejszych" bez utraty danych i bez stosowania jakiegoś zewnętrznego źródła danych. Rozumiem że myślisz o tej drugiej ewentualności - zastosowanie zewnętrznego źródła danych które za pomocą jakiegoś algorytmu generuje dane wykorzystywane przez kompresor/dekompresor. Jest to możliwe, ale to wcale nie spowoduje obniżenie wyniku otrzymanego wzorem Shannona. Bo takie rozwiązanie ma sens tylko jeśli jakieś ciągi danych są bardziej prawdopodobne od innych, wtedy teoretycznie mógłbyś je kodować za pomocą informacji o tym który element sekwencji generowanej przez twój algorytm odpowiada temu fragmentowi danych. Tylko że wzór Shannona już to uwzględnia - bo możesz wtedy uznać taki ciąg za jeden "symbol" i nadać mu odpowiednie prawdopodobieństwo i wracasz do punktu wyjścia.
3. Jest to ściśle określona teoria ;]
4. Nie wiem co 2ⁿ danych ma wspólnego z problemami NP. Bo PSpace = NPspace...
5. Istnieje sposób na uzyskanie niemalże idealnej kompresji dowolnych danych, pisałem o nim kiedyś. Otóż liczba PI, przy założeniu że ma nieskończone nieokresowe rozwinięcie dziesiętne, musi posiadać w swoim rozwinięciu dziesiętnym każdy dowolny, dowolnie długi ciąg. To znaczy że mając informację o tym od którego elementu rozwinięcia dziesiętnego PI do którego elementu (czyli mając dwie liczby!) moglibyśmy dekodować dowolne dane o dowolnym rozmiarze, poprzez wyliczanie kolejnych wyrazów PI i składnie z nich ciągu bajtów. Oczywiście takie rozwiązanie ma dwa defekty:

• czas kodowania/dekodowania byłby niewyobrażalnie długi
• uzyskane liczby mogą okazać się bardzo bardzo duże, w praktyce do ich zapisania możemy potrzebować więcej pamięci niż do zapisania danych które kompresujemy...

Uniwersalna bezstratna kompresja nie istnieje:
http://mattmahoney.net/dc/dce.html#Section_11
http://www.faqs.org/faqs/compression-faq/part1/section-8.html

Shalom mówi o wzorze Shannona ( http://en.wikipedia.org/wiki/Shannon's_source_coding_theorem ) ale ma on zastosowanie tylko w przypadku http://en.wikipedia.org/wiki/Independent_identically-distributed_random_variables

W rzeczywistości bajty w plikach nie są niezależne, np mając plik tekstowy po ciągu "dup" litera "a" jest bardziej prawdopodobna niż po ciągu "nosoroże", dlatego wzór Shannona niewiele udowadnia.

To co ogranicza stopień kompresji to złożoność Kołmogorowa, ale jest ona niepoliczalna (w ogóle, tak samo jak w problemie stopu): http://en.wikipedia.org/wiki/Kolmogorov_complexity#Incomputability_of_Kolmogorov_complexity

Wibowit napisał(a):

W rzeczywistości bajty w plikach nie są niezależne, np mając plik tekstowy po ciągu "dup" litera "a" jest bardziej prawdopodobna niż po ciągu "nosoroże", dlatego wzór Shannona niewiele udowadnia.

Właśnie. Jemu się wydaje że ma jakiś patent na liczenie entropii, a to jest sprawa niejednoznaczna, niestety.

Chyba licząc z bajtów pliku tekstowego otrzymamy większą entropię, niż gdybyśmy obliczali ze słów, czyli pary liter,
bo one są akurat silnie skorelowane w słowach.

Niedawno gdzieś słyszałem, że ktoś wymyślił metodę rekurencyjnej kompresji, która była tak dobra, że facet całe filmy zapisywał do policzków po 8KB. :))

Niedawno gdzieś słyszałem, że ktoś wymyślił metodę rekurencyjnej kompresji, która była tak dobra, że facet całe filmy zapisywał do policzków po 8KB. :)

Poczytaj pierwsze dwa artykuły które zalinkowałem i zrozumiesz że to bzdura. Counting argument to matematyka na poziomie gimnazjum - liczę na to, że to ogarniesz.

Właśnie. Jemu się wydaje że ma jakiś patent na liczenie entropii, a to jest sprawa niejednoznaczna, niestety.

Sprawa jest jednoznaczna, przy założeniu że mówimy o uniwersalnym algorytmie kompresji -> takim który działa dla dowolnych danych. Jasne że kompresowanie danych o których coś wcześniej wiemy (patrz mój punkt 2.) może oznaczać że licząc entropię uwzględniamy większe "symbole" niż 1 bajt, ale wzór pozostaje ten sam. Tylko że taki algorytm wcale nie zadziała dobrze dla danych które nie pasują do rozkładu prawdopodobieństwa dla którego algorytm projektowaliśmy.

Shalom napisał(a):

Właśnie. Jemu się wydaje że ma jakiś patent na liczenie entropii, a to jest sprawa niejednoznaczna, niestety.

Sprawa jest jednoznaczna, przy założeniu że mówimy o uniwersalnym algorytmie kompresji -> takim który działa dla dowolnych danych. Jasne że kompresowanie danych o których coś wcześniej wiemy (patrz mój punkt 2.) może oznaczać że licząc entropię uwzględniamy większe "symbole" niż 1 bajt, ale wzór pozostaje ten sam. Tylko że taki algorytm wcale nie zadziała dobrze dla danych które nie pasują do rozkładu prawdopodobieństwa dla którego algorytm projektowaliśmy.

Właśnie że nie jest, i na kilka sposobów!

W systemach deterministycznych nie istnieje w ogóle pojęcie entropii - dlaczego?
Bo ona jest tam bezużyteczna, z powodu pełnej znajomości parametrów każdego z elementów systemu.

Entropia jest pojęciem statystycznym, czyli dotyczy układów, których znamy jedynie parametry grupowe - średnie, statystyczne, np. średnia prędkość, gęstość, albo liczba poszczególnych bitów, czy bajtów w danych (to też jest średnia: c/N = średnia).

A po drugie: ciąg pseudolosowy, albo plik zaszyfrowany i/lub skompresowany ma maks. entropii,
co nie jest przecież prawdą, bo ciąg random jest jednoznaczy - można go odtworzyć ze stanu początkowego generatora,
a po odszyfrowaniu/dekompresji danych entropia spadnie kilka razy.

No to właśnie piszesz o złożoności Kołmogorowa o której już wspomniałem w tym wątku. Widocznie olewasz wszelakie argumenty i ograniczasz się do własnej wyobraźni. W ten sposób nie zajdziesz daleko.

Wibowit napisał(a):

Counting argument to matematyka na poziomie gimnazjum - liczę na to, że to ogarniesz.

"No program can compress without loss all files of size >= N bits, for any given integer N >= 0."

To jest akurat kolejna bzdura.
Mogę haszować te dane (dostatecznie duże, powiedzmy > 1KB) liczbami pseudolosowymi, aż do momentu aż ta entropia spadnie z 1 promil, a wtedy kompresor zmniejszy je o kilka bajtów, bo tyle potrzeba do zapisania stanu tego random generatora + 1 bajt zysku.

Napiszę po polsku:

Załóżmy że istnieje kompresor który kompresuje bez straty wszystkie ciągi o długości co najmniej N bitów. Oznacza to, że każdy możliwy ciąg bitów o długości N zostanie skompresowany. Jednak ciągów o długości N bitów jest pow(2, N), a ciągów krótszych od N bitów jest tylko pow(2, N) - 1, więc wystąpi co najmniej jedna kolizja. A skoro będzie kolizja to kompresja nie będzie bezstratna, czyli dochodzimy do sprzeczności.

Wykaż błąd w tym rozumowaniu.

To jest akurat kolejna bzdura.
Mogę haszować te dane (dostatecznie duże, powiedzmy > 1KB) liczbami pseudolosowymi, aż do momentu aż ta entropia spadnie z 1 promil, a wtedy kompresor zmniejszy je o kilka bajtów, bo tyle potrzeba do zapisania stanu tego random generatora + 1 bajt zysku.

Szkoda że nie czytasz ze zrozumieniem moich postów. To co opisałeś to jest dokładnie to samo co opisałem z wykorzystaniem liczby PI (z tą różnicą że liczba PI jest lepsza od generatora pseudolosowego). Otóż zakładasz optymistycznie że "stan generatora" zawsze jest opisany bardzo małą liczbą, co jest bzdurą.
A zasady szufladkowej Dirichleta nie oszukasz. Jeśli mam N liczb i wkładam je do N-1 szufladek tow jednej z szufladek będą 2 liczby, cudów nie zdziałasz.
Więc jeśli kompresuje N ciagów i chce je wrzucić do N-1 szulfladek to dwa ciągi muszą mieć konflikt. Ciągów długości X jest więcej niż ciągów długości X-1.
Skoro więc kompresuje moje N ciągów i chce dla każdego z nich uzyskać krótszą reprezentację to musze mieć konflitkty.

Shalom napisał(a):

To jest akurat kolejna bzdura.
Mogę haszować te dane (dostatecznie duże, powiedzmy > 1KB) liczbami pseudolosowymi, aż do momentu aż ta entropia spadnie z 1 promil, a wtedy kompresor zmniejszy je o kilka bajtów, bo tyle potrzeba do zapisania stanu tego random generatora + 1 bajt zysku.

Szkoda że nie czytasz ze zrozumieniem moich postów. To co opisałeś to jest dokładnie to samo co opisałem z wykorzystaniem liczby PI (z tą różnicą że liczba PI jest lepsza od generatora pseudolosowego). Otóż zakładasz optymistycznie że "stan generatora" zawsze jest opisany bardzo małą liczbą, co jest bzdurą.
A zasady szufladkowej Dirichleta nie oszukasz. Jeśli mam N liczb i wkładam je do N-1 szufladek tow jednej z szufladek będą 2 liczby, cudów nie zdziałasz.
Więc jeśli kompresuje N ciagów i chce je wrzucić do N-1 szulfladek to dwa ciągi muszą mieć konflikt. Ciągów długości X jest więcej niż ciągów długości X-1.
Skoro więc kompresuje moje N ciągów i chce dla każdego z nich uzyskać krótszą reprezentację to musze mieć konflitkty.

Rzeczywiście istnieje tu pewna sprzeczność - niemożliwość, coś jak sprytny dowód infinite descent Fermata...

Po prostu generator oparty np. na 4 bajtach, znaczy inicjowany liczbą 4B, niewiele tu pomoże, choćby nawet generował wszystkie ciągi bitów większej długości np. 1024, bo wówczas musiałbym zapisać ten numer 1024 bitowy, a nie 32 tylko...

Ale to co tam napisałem też jest prawdą, bo prawdopodobieństwo wygenerowania serii, która zmniejszy entropię jest niezerowe, nawet dla 32 bitów mam 4 miliardy sekwencji, a dla danych długości np. 1KB = 1024*8 bitów mamy aż 2⁸¹⁹² możliwych serii, no ale to nie szkodzi, bo: p = 2³² / 2⁸¹⁹² > 0, czyli szansa istnieje... ale znikoma.

Działa dla dowolnych danych...

A ten sposób z Pi jest identyczny z moim:
musiałbyś zapisać numer startowy podciągu w Pi, ale niestety ten numery byłby statystycznie równy długości tego kompresowanego ciągu...

Ale przecież dokładnie o tym pisałem. Pewnie część ciągów udało by się w ten sposób "skompresować", ale pozostałe po "kompresji" byłyby większe niż przed nią ;] To jest zresztą zawsze obecne, co udowodniliśmy wcześniej za pomocą zasady szufladkowej.

Z tym że cyfry Pi raczej nie są losowe, bo to jest nawet intuicyjnie niedorzeczne - pi jest dobrze określoną liczbą, a nie losową. :)

Gdzieś kiedyś widziałem testy na losowość cyfr różnych liczby, pi, e, i kilka innych,
no i tam początkowo wyglądało to na losowe ciągnie, ale dla dłuższych obliczeń coś się zaczynało tam psuć... chyba było to okresowo losowe, czy coś tam. :)

o_O? A generator liczb pseudolosowych to co? Też nie jest losowy. Znając stan generatora można odtworzyć generowany przez niego ciąg, zresztą tak przecież chciałeś "dekodować" skompresowane ciągi. W związku z tym nie ma właściwie żadnej różnicy. To że PI jest liczbą nieokresową udowodniono już dawno temu... Dlatego jest "lepsza" od twojego generatora, bo generator może być wątpliwej jakości. Oczywiście nikt nie twierdzi że rozwinięcie PI jest zupełnie losowe i że każdy potencjalny ciąg występuje w nim z równym prawdopodobieństwem ;)