atarionline.pl Cała prawda o kompresorach - Forum Atarum

Jeśli chcesz wziąć udział w dyskusjach na forum - zaloguj się. Jeżeli nie masz loginu - poproś o członkostwo.

  • :
  • :

Vanilla 1.1.4 jest produktem Lussumo. Więcej informacji: Dokumentacja, Forum.

    • 1: CommentAuthormarok
    • CommentTime30 Jun 2023
     
    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.


    ->link<-
    • 2:
       
      CommentAuthorjhusak
    • CommentTime30 Jun 2023 zmieniony
     
    Z dokładnością do tego, że niektóre archiwujące kompresory nie kompresują struktury katalogów, i przelecenie tego kompresorem je kompresuje.

    Ale chyba to każdy, kto cokolwiek kompresował, zauważył, że kompresja mp3 czy JPG nie ma sensu (z dokładnością do metadanych).
    • 3:
       
      CommentAuthorPeri Noid
    • CommentTime30 Jun 2023
     
    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ą.
    • 4:
       
      CommentAuthorpirx
    • CommentTime30 Jun 2023
     
    ma to nawet swoją miarę "entropię teorioinformacyjną" ->link<-

    przytoczone zdanie to ciekawe "chłopskorozumowe" tłumaczenie sobie tej miary, bo wzorki nieprzyjemne, z jakimiś logarytmami itp.
    • 5: CommentAuthormarok
    • CommentTime30 Jun 2023
     
    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.

    (Może dlatego wyrażam takie a nie inne opinie.)
    • 6: CommentAuthor0xF
    • CommentTime30 Jun 2023
     
    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ą.
    • 7: CommentAuthormarok
    • CommentTime30 Jun 2023
     
    Dobrze pomyślany przykład ('samo udawadnialny').

    Bardzo szczególny przypadek kompresji 0 lub 100%.

    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).
    • 8: CommentAuthorzijacek
    • CommentTime1 Jul 2023
     
    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).
    • 9: CommentAuthormarok
    • CommentTime1 Jul 2023
     
    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
    • 10: CommentAuthorsolo/ng
    • CommentTime2 Jul 2023 zmieniony
     
    sky is blue!

    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.
    • 11:
       
      CommentAuthorPeri Noid
    • CommentTime2 Jul 2023
     
    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.
    • 12:
       
      CommentAuthorpirx
    • CommentTime2 Jul 2023
     
    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 :))))
    • 13:
       
      CommentAuthorjhusak
    • CommentTime2 Jul 2023 zmieniony
     
    @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.

    O, tu jest:
    ->link<-

    Osobiście uważam to za szalony pomysł, żeby to wcielić w życie. Bo wpaść na taki pomysł jest łatwo, jak na każdy inny, ale nie każdy się sprawdza.
    • 14: CommentAuthorzijacek
    • CommentTime2 Jul 2023
     
    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 :)
    • 15: CommentAuthorsolo/ng
    • CommentTime2 Jul 2023 zmieniony
     
    no musza. tak samo jak generowanie losowych pixeli na ekran pokaze w koncu np. screena z Zybexa;)

    a pomyslmy ile gier na 64k XL/XE, ktorych nikt nie kodowal - jeszcze nie widzielismy - tylko czekajana odkrycie :]
    • 16:
       
      CommentAuthormaly_swd
    • CommentTime3 Jul 2023
     
    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.