Wywód logiczny - 'smutna' prawda o wszystkich (bezstratnych) kompresorach. Zasadniczo, kogoś interesowało to, co jest w odpowiedzi napisane w ostatnim przytoczonym zdaniu (zaś sama oryginalna odpowiedź jest nieco dłuższa niż przytoczony cytat). Kluczowe do uzmysłowienia sobie 'prawdy o kompresorach' jest ostatnie zdanie pierwszego akapitu.
Suppose we have a file N bits long, and we want to compress it losslessly, so that we can recover the original file. There are 2^N possible files N bits long, and so our compression algorithm has to change one of these files to one of 2^N possible others. However, we can't express 2^N different files in less than N bits.
Therefore, if we can take some files and compress them, we have to have some files that length under compression, to balance out the ones that shorten.
This means that a compression algorithm can only compress certain files, and it actually has to lengthen some. This means that, on the average, compressing a random file can't shorten it, but might lengthen it.
Practical compression algorithms work because we don't usually use random files. Most of the files we use have some sort of structure or other properties, whether they're text or program executables or meaningful images. By using a good compression algorithm, we can dramatically shorten files of the types we normally use.
However, the compressed file is not one of those types. If the compression algorithm is good, most of the structure and redundancy have been squeezed out, and what's left looks pretty much like randomness.
No compression algorithm, as we've seen, can effectively compress a random file, and that applies to a random-looking file also. Therefore, trying to re-compress a compressed file won't shorten it significantly, and might well lengthen it some.
So, the normal number of times a compression algorithm can be profitably run is one.
To co przytoczyłeś to standardowy dowód na fakt, że nie istnieje algorytm kompresji pakujący równie skutecznie wszystko co się da. Nic wielkiego, zasada szufladkowa Dirichleta (lub z angielskiego the pigeonhole principle). Na całe szczęście nie wszystkie ciągi losowe o długości N mają sens i są wykorzystywane. Co więcej, te których używamy zwykle wykazują się jakąś wewnętrzną strukturą, dzięki czemu jednak można je upakować. I na tym te kompresory bazują.
we have to have some files that length under compression, to balance out the ones that shorten
Przyszło mi w tym punkcie na myśl, że gdyby zsumować wyniki (długości plików wynikowych) dla wszystkich możliwych 'kombinacji' o określonej długości danych plików wyjściowych, to suma ta byłaby może nawet zawsze (dla każdego algorytmu) wyższa niż suma przed pakowaniem (którą można wyrazić prosto ilorazem możliwych kombinacji a stałą - długością pliku). A więc taka 'całościowa' kompresja nie miałoby sensu (poza 'anonimizacją' danych).
Jednocześnie, wynik pakowania może dobrze odzwierciedlać "entropię" danych, co może z kolei być wyznacznikiem stopnia przypadkowości / losowości danych (czym gorszy, tym w większym stopniu dane wyjściowe 'przypominają' wartości losowe). A dobrze spakowane dane mogą być niezłym źródłem wartości losowych.
Inny wniosek jest taki, że trzeba trochę zapomnieć o uniwersalnych kompresorach do wszystkiego, bo najlepsze efekty upakowania i tak przynależeć muszą kompresorom sprofilowanym pod dany typ danych.
Przepraszam, że nie odnoszę się w żaden sposób do tych naukowych wyjaśnień z linku (czy podpowiedzi), ale zupełnie są one dla mnie nieosiągalne.
suma ta byłaby może nawet zawsze (dla każdego algorytmu)
Łatwo podać kontrprzykład obalający tę hipotezę. Załóżmy, że badamy kompresję plików N-bajtowych.
Hipotetyczny algorytm kompresuje N-bajtowy plik złożony z samych zer na pusty plik. Wynikiem kompresji każdego innego N-bajtowego pliku jest jego dokładna kopia.
Więc suma długości wszystkich skompresowanych plików N-bajtowych jest mniejsza, niż przed kompresją.
Może więc hipoteza, że suma tych i tych wartości (odnoszę się do tych sum długości plików przed i po kompresji) bilasnują się w najlepszym razie dobrze (znaczy, są do siebie mocno zbliżone, chyba że suma długości plików po kompresji znacznie przewyższa tą przed kompresją), byłaby bliższa prawdy?
Trochę się upieram z myśleniem o tym w tym kierunku, ale to moja intuicja tylko (i aż - dla mnie).
Kompresor może dysponować plikiem lub jakąś sporą tablicą wygenerowanych kiedyś losowych bitów, która może służyć jako "matryca" do szyfrowania skompresowanego pliku. Efektem takiego szyfrowania może być plik, którego struktura znowu nada się do w miarę przyzwoitej kompresji. To oczywiście tylko przemyślenia, które w rzeczywistości nie potwierdzają się (dawno temu sprawdzałem).
To jest jak dla mnie podobne zagadnienie do poszukiwania takiego algorytmu kompresji, który by działał lepiej z danymi o trudnej (lub pewnie raczej - nie oczywistej) do ustalenia strukturze (trochę jak dane losowe), niż z takimi, które normalnie się pakują dobrze (kompensacja, może nieunikniona, powodowałaby to, że te z kolei pakowałyby się źle lub wcale tym 'innym' kompresorem).
Dalsze moje wywody są raczej już tylko śmieszne, ale napisałem…
Skrajny (naiwny) przykład takiego 'algorytmu' (i struktury danych).
Powiedzmy, że mamy jakieś dane wyjściowe, które narastają o 1 (nad wyraz często) w wartościach bajta, lub o trochę więcej, z każdą kolejną pozycją w danych.
1,3,4,6,8,10,11,12,15,17,21,22,24,25, … 254, 0,2,3,5 … itd. (i będzie to solidnie długa tablica takich bardzo specyficznych danych, którą jest sens się zająć, w sensie by to jednak upakować)
przyjdzie nam na myśl to spakować czymś skutecznie (zaznaczę: nie mam pojęcia, jak taki typ danych by się pakował tym i owym) więc narzuca się pomysł na algorytm, którego podstawowym 'składnikiem' będzie uwzględnienie przyrostu wartości bajta (+1) z każdym odwołaniem do następnego po poprzednim bajcie danych
Można więc 'przelecieć' dane w jednym obiegu i odjąć odpowiednią wartość - w zależności od oddalenia od początku danych (stąd np. pozycja 256 nie uległaby żadnej przemianie po takim odjęciu, itd.) i czynić z tym dalsze operacje służące kompresji (na bardziej już uporządkowanym 'polu' do takiego działania)
tak poprawiona struktura danych (może tylko 'domyślnie' a nie faktycznie - na zawartości danych) mogłaby już podlegać metodzie RLE
to wszystko, co opisałem to skrajnie prosty przykład operacji arytmetycznych przeprowadzanych przed odczytem kolejnych danych (podlegających kompresji)
czyli to mogłoby być znacznie bardziej złożene działanie
chociaż (zdroworozsądkowo) to raczej niemożliwe, żeby znaleźć jakikolwiek algorytm, który dla faktycznie losowych wartości byłby (choć odrobinkę) skuteczny
za 5 lat jak wjada nowe CPUxGPU karty nvidii (1000x szybsze niz to co teraz puscili w produkcje) bedzie mozna pewnie do losowych 1GB danych odpowiedz w 0.001s jaki algorytm (-my) ma to zrobic i kolejne 1s - done.
wyobrazam sobie taki rok 2203, gdzie dla kazdego mozliwego (full rnd) ciagu danych np. 10000TB- jest gotowa odpowiedz po hashu (i zawsze najlepsza), a ziomeczki heheszkuja, co ci w 2023 robili (przewozili 100kg furmanką).
zakladam, ze w ta strone bedzie wszystko szlo, przez wlasnie sprzetowe mega chipy - wlatuja w produkcje pierwsze; bedzie fun nie mniejszy niz pojawienie sie pradu, a potem internetu.
Czytałem kiedyś o takiej teorii, że można zrobić taki "algorytm" kompresji: 1. Weź jakąś liczbę niewymierną typu pi, e albo coś podobnego. 2. Weź rozwinięcie dziesiętne (albo nawet lepiej binarne) tej liczby. 3. W tym rozwinięciu "znajdź" miejsce, w którym znajduje się ciąg, który chcesz skompresować. Wynikiem kompresji jest pozycja w rozwinięciu oraz jej długość. Niezwykle skuteczny sposób kompresji, zdawałoby się ;-) Tak, o ile: - jeśli tylko pozycja nie jest zbyt duża (długość wartości indeksu w porównaniu do danych wejściowych), - jesteś w stanie rozwinąć "klucz" dowolnie daleko, - i zrobisz to "natychmiast" (a przynajmniej bardzo szybko do wymaganej pozycji). Jak widać, co najmniej dwa z trzech powyższych są problematyczne dlatego ten pomysł jest tylko teoretyczny i zupełnie nieimplementowalny.
W zasadzie można się zastanowić, czy dysponując pewnym ograniczonym co do długości ciągiem nie bylibyśmy w stanie tego zrobić "na raty", czyli kompresować fragmenty wejścia wyszukiwalne w obrębie ciągu, którym dysponujemy. To wygląda trochę jak założenie z postu @marok, bo taki fragment rozwinięcia można traktować jako ciąg pseudolosowy - tylko uzyskany przez rozwinięcie liczby niewymiernej.
to lepszy jest sposób na kijek - bierzesz ciąg bitów C. Zapisujesz to jako 1/C, otrzymujesz liczbę wymierną. na kijku o długości 1 zaznaczasz miejsce 1/C :))))
@pirx, niestety, tylko matematycznie to ma sens...
Kiedyś był taki algorytm DeCSS na płytach DVD. Był prosty, ale nie wolno go było upubliczniać. Więc gość o nazwisku Johansen, co opracował ten algorytm obliczył, że jakaś tam liczba pierwsza w postaci heksadecymalnej zdekodowana na bajty daje skompresowany plik z tym programem bodajże gzipem czy innym lz cośtam.
Czyli istnieją jakieś tam liczby pierwsze, które po dekompresji dadzą konkretne gry. Wystarczy je tylko znaleźć i ciach, mamy np. takiego Bruce Lee. Więcej, można znaleźć gry, o których jeszcze nie wiemy, że mogą istnieć ;) To mi przypomina patent z wygenerowaniem wszystkich kombinacji bajtów pamięci np. 64KB. Mielibyśmy wtedy wszystkie możliwe gry, a żeby taką grę osiągnąć, wystarczyłoby tylko wskazać numer konkretnej kombinacji. Tyle tylko, że sam numer nie byłby mniejszy od wyniku :), a człowiek poszukujący działającej gry musiałby pewnie żyć dłużej niż ziemia istnieje :)
Solo: Mam wrażenie, że Wasze dema są tak robione. Napisaliście już algo który generuje te wszystkie kombinacje. Potem siadacie przy piwku i oglądacie to co się wygenerowało a potem to puszczacie na Party.
I tak za każdym razem wybieracie perełki o których nikt wcześniej nie śnił :)
* i nie mów mi że przypadkiem też jechaliście składem PKP 6502 ;) - czy jakoś tak.
