Pomysł na kolejny system kompresji plików?

Z nieznanych przyczyn przyśniło mi się, iż napisałem rewolucyjny system kompresji plików (kliknij i skompresuj 10 GB danych do 2 MB - hasło reklamowe :-) ). O dziwo, zapamiętałem na czym on polegał.

Podczas kompresji program zapisywał strukturę plików - standard. Inaczej było w przypadku kompresji samych danych. Do każdego pliku aplikacja obliczała sumę kontrolną i badała, za którym razem plik wygenerowany (?) na podstawie tej sumy kontrolnej będzie identyczny z oryginalnym plikiem (jestem ciekaw, jak długo by taka kompresja trwała). Liczba ta była zapisywana w archiwum.

Co do dekompresji, wystarczy wygenerować plik z sumy kontrolnej na podstawie obliczonej liczby.

Zastanawiam się i... czy takie coś jest w praktyce w ogóle możliwe?

offtopic : mam obraz Visty skompresowany to 1,5 MB

Made in China napisał(a)

Zastanawiam się i... czy takie coś jest w praktyce w ogóle możliwe?
Wątpię. Chociażby dlatego że ilość sum kontrolnych jest ograniczona i powstawałyby konflikty.

Chłopcy, poznajcie pojęcie entropii.

Istnieje inne podejście, pozwalające obejść wspomnianą granicę - zamiast redukować zbędne rzeczy można zacząć bezpośrednio generować dane. Póki co nie istnieje jednak nawet koncepcja algorytmu pozwalającego w sensowny sposób wyznaczyć jakiś wielomian, przy pomocy którego możnaby wyliczyć zawartość kompresowanego pliku. Cała zabawa sprowadzałaby się do wyprowadzenia z danych odpowiedniego wielomianu, dane po 'kompresji' zajmowałyby tyle ile zapis wielomianu.

lukasz1235 napisał(a)

Made in China napisał(a)

Zastanawiam się i... czy takie coś jest w praktyce w ogóle możliwe?
Wątpię. Chociażby dlatego że ilość sum kontrolnych jest ograniczona i powstawałyby konflikty.

Nawet gdyby skompresowane pliki miałyby tę samą sumę kontrolną to przecież:

Pierwszy plik byłby poprawnie generowany dopiero za np. 99810 razem (myśli optymistyczne)
Drugi za 99811.

Skoro te liczby są zapisywane to jakie mogłyby wtedy powstać konflikty?

A jak wyznaczysz algorytm generowania n-tego pliku dającego taką samą sumę kontrolną? Przecież to tak samo nierealne jak Twoje pomysły z pierwszego postu w tym wątku.

Może rozmiar sumy kontrolnej proporcjonalny do rozmiaru pliku?

//Ale nadal może być inny plik o identycznej sumie kontrolnej...

I co to da?

Suma kontrolna nie będzie jednakowej długości. Skoro w grę wchodzą duże pliki suma kontrolna może osiągnąć rozmiar x razy mniejszy od oryginalnego pliku. Jeśli jednak nadal będzie ta sama suma to przecież kompresor łatwo to wykryje i doda dodatkowy ciąg do sumy kontrolnej.

Dobra, tylko gdzie Ty widzisz kompresję? Proponujesz bruteforce'a, funkcję jednokierunkową zamiast spojrzeć na to z drugiej strony. Były eksperymenty, próby stworzenia zabawek do wspomnianego tworzenia równań/wtf opisujących zawartość pliku, to działa, tylko ma tak cholerną złożoność obliczeniową, że jest bezużyteczne. Oczywiście robiono to 'dla zabawy', nie jako poważne zamienniki normalnej kompresji.

Tak, przekroczenie entropii jest możliwe tylko w dwie strony - albo szybka funkcja 'kompresująca' i niesamowicie kosztowne odtwarzanie albo vice versa.

Każda kompresja musi być co najmniej injekcją - tzn różne dane wejściowe muszą dawać różne dane wyjściowe. Najefektywniejsze injekcje to bijekcje bo każde dane wyjściowe są osiągalne i jednoznaczne z dokładnie jednymi danymi wejściowymi.

Najefektywniejszą metodą kompresji, biorąc pod uwagę wszystkie możliwe dane wejściowe, jest zwykłe kopiowanie. Daje ono oczekiwaną kompresję rzędu dokładnie 1.

Jeśli jakaś metoda kompresji skraca jakiś jeden ciąg n-bitowy o 1 bit, to musi także wydłużać co najmniej 2 ciągi n-bitowe o 1 bit. (Dowód możecie sami zrobić). Dla ułatwienia polecam popatrzeć na konstrukcję kodów Huffmana.

Kompresja danych działa tylko dzięki temu, że znakomita większość danych ma dużą dozę nadmiarowości, pewną strukturę etc. Niemożliwe jest na przykład kompresowanie plików całkowicie losowych.

Świętowit napisał(a)

Były eksperymenty, próby stworzenia zabawek do wspomnianego tworzenia równań/wtf opisujących zawartość pliku, to działa, tylko ma tak cholerną złożoność obliczeniową, że jest bezużyteczne. Oczywiście robiono to 'dla zabawy', nie jako poważne zamienniki normalnej kompresji.

O powyższym nie słyszałem, ale ideowo podobne jest to do kompresji fraktalnej. Której to niespecjalnie jest gdzie użyć (+ wiki wspomina o problemie patentowym).

Bierzemy strumień bajtów, który chcemy skompresować, zapisujemy go w postaci cyfr, np dla "abcde" będzie to: "097098099100101". Następnie przyjmujemy, że nasza liczba jest częścią ułamkową innej liczby, której część całkowita to 1, czyli mamy: "1.097098099100101". Teraz bierzemy drewniany patyk o długości 1m i dzielimy go nacięciem na dwa odcinki w proporcji 1:1.097098099100101.
Jak łatwo zauważyć taki sam patyk wystarczy nam do bezstratnej kompresji dowolnej ilości danych.

Na tej samej zasadzie Bóg skompresował świat w liczbie pi.

Youngster napisał(a)

Na tej samej zasadzie Bóg skompresował świat w liczbie pi.

A nieprawda bo w 42, pi to tylko składowa.

Czasami braki w teorii się mocno czkawką odbijają. Dawno temu postanowiłem zaimplementować zwykłe kodowanie Huffmana, a potem zrobiłem malutki programik który generował losowe pliki testowe. I wielkie zdziwienie - dlaczego mój program nie tworzy wcale mniejszych plików? =)

Co do metody z patykiem - dzisiaj fizycy ocenili kwant długości na 10^-19 m, czyli ilość informacji które można zmieścić na patyku jest skończona.

A czy patyk tak jak każdy odcinek mimo, że jeest skonczony to można podzielić go na nieskończoną ilość części ?

I w ten sposób wnioskujemy, że patyk jest de facto jakąś całką ;)

A kodowanie Huffmana jest efektywne dla danych, które się często powtarzają, podobnie jak RLE. Z tego względu kompresja już skompresowanych plików, np. JPG nie daje dobrych rezultatów.

ucho napisał(a)

Co do metody z patykiem - dzisiaj fizycy ocenili kwant długości na 10^-19 m, czyli ilość informacji które można zmieścić na patyku jest skończona.

Ja rozumiem, że fizycy w tym wszechświecie są ograniczeni, a poza tym mają do mnie żal, że to nie oni wpadli na ten genialny pomysł, ale nie zatrzymają mnie ich durne teorie.

lukas_gab napisał(a)

A czy patyk tak jak każdy odcinek mimo, że jeest skonczony to można podzielić go na nieskończoną ilość części ?

Przecież mowa jest o podziale na dwie części, a nie nieskończoną ilość. :|