Witam
W tym temacie Świętowit napisał o pewnym sposobie kompresji
Ś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.
Może ktoś podać jakiegoś linka do konkretnych informacji o tej kompresji? Bo ja szukam i znaleźć nie mogę.</quote>
http://en.wikipedia.org/wiki/Kolmogorov_complexity poczytaj i wszystko stanie się dla ciebie jasne.
OK. Wiem już trochę więcej, ale ciągle nie wiem w jaki sposób wygenerować program/opis danych. Była mowa, że jest to możliwe więc miło by było dostać linka do praktycznej implementacji.
Tzn chcesz wyznaczyć minimalną długość skompresowanych danych + dekompresora? Jest to niepoliczalne, zobacz do rozdziału "Incomputability of Kolmogorov complexity" w przytoczonej przeze mnie stronie na Wiki.
Jako ciekawostkę podam, że przy próbie kompresji losowych danych najlepszym algorytmem kompresji jest po prostu brak kompresji. Skrócenie dowolnego ciągu o jeden bit powoduje, że co najmniej dwa ciągi po skompresowaniu muszą się stać dłuższe o jeden bit. A to powoduje wydłużenie średniej długości skompresowanych danych.
Czyli Świętowit mylił się pisząc "to działa"?
deus (Świętowit) coś chrzanił o wielomianach, ale nie wspominał o minimalnej złożoności, czyli tej w sensie Kołmogorowa. Zależy o co tobie też chodzi. Co chcesz osiągnąć?
Ja myśle że to działa, ale dla pewnych danych. Tak jak i zwykłe kompresory. Dla pewnych danych działają ok, dla innych są bezużyteczne.
Chodzi mi o te wielomiany
Nie znam generalnie żadnej bezstratnej metody kompresji opartej na wielomianach. Stratna kompresja danych dźwiękowych i obrazów dokonywana jest np poprzez wykonanie transformaty DCT, falkowej czy pochodnych, ale niestety komputery mają skończoną dokładność, a i zapis takich danych byłby nieekonomiczny (tzn nie byłoby kompresji). Dlatego wyniki się próbkuje (np dzieli przez 100 i odcina część ułamkową). Mniej więcej w taki sposób działa kompresja MP3, JPEG itp
Czy deus może się wypowiedzieć jaki algorytm miał na myśli?
No może, może, dopiero co tutaj zajrzałem...
Cholera, nie pamiętam konkretów, czytałem o tym koło 2003-2004. Rzecz polegała na tym żeby zamiast typowego algorytmu kompresji i danych stosowanych do dekompresji stworzyć algorytm generowania danych. W pewnym stopniu to analogiczne do rozwiązań zastosowanych w grze .kkreiger. Oczywiście znalezienie równania/układu równań opisującego ciąg, służącego wygenerowaniu większych danych jest raczej trudne. To była bodaj jakaś praca akademicka tylko nie mam nawet pomysłu pod jakimi keywordami tego szukać. Trudno to nazwać kompresją jako taką w ogóle, ale pomysł był ciekawy...
http://en.wikipedia.org/wiki/Procedural_generation
Nie ma to praktycznie nic wspólnego z kompresją danych.
Związek ma taki, że mniejszy kod generuje większe dane, analogicznie do procesu dekompresji. Noo, oczywiście nie zawsze da się ten 'mniejszy kod' uzyskać jako mniejszy, ale o tym już była mowa.
Tyle, że nie ma programów robiących za kompresory, tzn generujące kod generujący na podstawie danych.
Większość z tych proceduralnych generatorów opiera się na funkcji generujących losowe wartości. Gdyby użyć naprawdę losowego źródła, to odwrócenie procesu generowania nie przyniosłoby wielkich zysków (o ile w ogóle byłoby możliwe) - musielibyśmy zapisać osobno te wartości wygenerowane przez generator wartości losowych.
Właśnie na tym polegała zabawa, że szukano sposobu znalezienia w sensownym czasie metody opisu danych. Dlatego wspomniałem że były 'eksperymenty'. Przy niższej entropii potencjalny zysk jest teoretycznie możliwy.
Aha. No to szanse na powodzenie wynosiły około 0,000000000 % i eksperyment oczywiście zakończył się niepowodzeniem.
Ja bym tego tak szybko nie skreślał, przy tych teoretycznych komputerach kwantowych to nawet może mieć faktycznie sens.
@deus: to jak sobie przypomnisz gdzie o tym czytałeś to rzuć linkiem. Będę wdzięczny.