Pokud mam nejakou informaci ulozenou v N bitech tak tato informace muze byt jednou z 2^N moznosti. Pokud provedu kompresi na M<N bitu, tak touto M bitovou informaci dokazu vyjadrit pouze 2^M moznosti. Z cehoz vyplyva, ze pouze nektere z 2^N moznosti lze zkomprimovat na M <N bitech pokud nema dojit ke ztrate informace. Samozrejme by mohl teoreticky existovat algoritmus, ktery by pro nenahodna data vyextrahoval 100% redundantnich informaci . To by pak byl nejlepsi mozny bezeztratovy kompresni algoritmus. Otazkou je, zda lze takovy kompresni algoritmus najit a zda by jeho vypocetni slozitost nebyla napr. exponencialni.
no jestli prave ten zero space tuner neni neco jako zpusob jak sifrovat zakomprimovana data aby znich vylezly novy ktery pujdou tym samym algoritmem zkomprimovat zase. problem je spis kolik informace potrebuje ten zero space tunner uchovat, aby neco podobnyho dokazal i nazpet ve srovnani s tim kolik dat se muze vklidu zahodit pri dalsim pruchodu kompresnim algoritmem.
Bohuzel si nevzpominam na podrobnosti, ale pred par lety jsem cetl o firme, ktera tvrdila, ze jeji kompresni algoritmus dokaze jakakoliv data vetsi nez 64kb zkompresovat na jednu sestnactinu - rekurzivni aplikaci se pak dalo cokoliv zakompresovat na 64kb.
To mi pripomina neco, cemu jsme na vejsce rikali SImonova komprese (podle spoluzaka). Rekurzivni aplikaci se pak cokoliv dalo zakompresovat na 1 bit a podle toho jste si budto udelali nebo neudelali uzel na kapesniku :)
Taky si vzpominam (odkaz je tusim ve Compression FAQ) na jakousi firmu, ktera kdysi mela dabelsky algoritmus komprese (asi 1:10) a dokonce nabizela EXE, ktery to dokazoval. A opravdu to fungovalo.
Tedy do te doby, nez se prislo na to, ze cele soubory presouva do nepouzitych sektoru na disku a pri rozbalovani je opet odtud vytahuje :)))).
nerozumim tomu, nejsem zadnej matematik, ale o co jde ? proc se divite ze by nekdo mohl udelat neztratovou komprimaci s velkou ucinnosti ? samozrejme nepujde udelat neco takovyho ze bysme to zkomprimovali na jeden bit, ale dyt i obycenjen zip dokaze text komprimovat 1:10. tak o co jde v tomto pripade ? nerozumim co ma ta firma tak prevratnyho ? a ani nerozumim tomu co se snazite vyvratit ze neni mozny, muzete mi to nekdo normalne vysvetlit ?
No ono text jde komprimovat 1:10 právě proto, že se ukládá už na začátku s každým znakem dost místa navrch, a že se velmi často opakují stejná slova (vzory, sekvence...). Tenhle balast se samozřejmě dá uložit mnohem úsporněji už od začátku a pak ta komprese tak dobře nevyjde. Ale když už to jednou uložím blbě, tak si to potom můžu zkomprimovat :-))
Ale komprimovat náhodná data, to už je úplně jiné kafe. Tam totiž žádné neužitečné místo nebo opakující se vzory nejsou. A tak je otázka, o co přijdu, když to zkomprimuju. Něco se zřejmě ztratit musí!
Nemůžu si pomoct, ale algoritmus, který dokáže zkomprimovat (chápejte: zmenšit počet bitů alespoň o 1) libovolná náhodná data beze ztráty informací existovat prostě nemůže. To by pak bylo možné zkomprimovat libovolná (tím rozumím opravdu LIBOVOLNÁ) data původní délky N na nejhůř N-1 bitů. Ale pak můžeme znovu komprimovat tato data a budeme dostávat nejhůř N-2 bitů, N-3, .... a zůstane nám jen jeden bit. A ten obsahuje jen 1 nebo 0. A selským rozumem: každá data by bylo možno zkomprimovat do tohoto tvaru, což evidentně není příliš jednoznačné...
A co kdyz pouzivaj opravdu nejakej druh komprese, kterej jeste nikoho nenapad, nebo ho nedokazal uskutecnit. Kdyz jsem byl malej, tak jsem snil o kompresnim algoritmu, kterej by vyuzival nahodny posloupnosti kuprikladu v cislu Pi, nebo v eulerove cisle. Vzdyt i v Pi je obsazenej Otuv slovnik naucny, jenom jeste nikdo nerek, na jakym offsetu se nachazi.
Sakra lidi, delate si srandu nebo ne? Samozrejme, ze existuji iracionalni cisla, ktera NEOBSAHUJI jakoukoli posloupnost pevne delky (treba 0,1010010001...1<n nul>1...). Kdysi jsem slysel neco o tom, ze pi je nejak lepsi a fialovejsi iracionalni cislo, ale tohle se mi nezda...
to je docela blbost. takovy offset by pak byl stejne obecne vetsi, nez samotna velikost komprimovanych dat ->
opet by musel existovat jednoznacny offset, ze ktereho by slo jednoznacne urcit, na co se ma dekomprimovat, tzn. muselo by existovat tolik offsetu, kolika zpusoby lze usporadat pismenka pouzita v Ottove slovniku -> to je sakra hodne...
jenomže i pro ty offsety platí ten původní důkaz. Ten není založený na metodě, ale na počtu vstupních a výstupních posloupností. Prostě abys mohl zakódovat jakékoli číslo mezi 0-15, tak na to prostě potřebuješ čtyři bity i kdyby ses rozkrájel, protože když to schováš do menšího počtu, tak to nerozkóduješ nazpátek. Nemůžeš 16 možností nacpat do 15 hodnot, protože pak z těch 15 hodnot dokážeš vyndat jenom 15 původních možností.
Mimochodem - zkoušeli jste někdo zazipovat JGEGy? Když to vyjde dobře, tak je to asi stejně velké, jinak větší než originál :O)
Kdybyste si peclive precetli ten rozhovor na wired, tak byste si mohli vsimnout, ze na otazku jestli umi zkomprimovat jakakoliv nahodna data, odpovedel, ze umi zkomprimovat nejakou posloupnost,kterou uvedl nekdo ve sve knize jako nezkomprimovatelnou.
U nahodnych dat se muze jen ciste nahodou stat ze by nesli vubec zkomprimovat.
Takovou radu umim zkomprimovat taky. Proste napisu program ktery nahradi takovouhle radu nejakym znakem a naopak pricemz si tu radu bude cucat z vlastniho .exe :) Ano, podobnych uz tu bylo :) Jinak takove zpravy komercnich spolecnosti ktere uvadeji neco revolucniho co popira prostou matematiku, ale neuvedou ani zakladni popis algoritmu a dokonce ani jakykoliv priklad nebo byt jen statistiky, tak takove zpravy jsou na 100% bud podvod nebo cokoliv jineho jen ne to co bylo uvedeno v te zprave.
Taky jsem uvazoval o skvelem kompresnim programu. Umi zkomprimovat cokoliv na stejnou velikost a sebe na nulovou velikost. Jmenuje se cat. Pak mi doslo ze sebe nekomprimuje na nulovou velikost ale na nedigitalne schovanou informaci o tom ze byl pouzit.<BR>
Jinak receno, klidne napisu program ktery bude velice efektivne komprimovat treba 254 naprosto nezkomprimovatelnych posloupnosti znaku a ostatni soubory prodlouzi pouze o jeden byte.
Bezestratova komprese neni nicim jinym, nez odstranenim redundantni (tady vicenasobne) informace. (Redundantni jsou napriklad vsechny samoopravne kody - jinak by nemohly opravit chybu). Z toho plyne, ze stupen komprese je zavisly na stupni redundance vstupnich dat. Jiste lze vymyslet konkretni posloupnost bitu s takovou redundanci, kterou lze komprimovat i 1:100. Nicmene obecne to neplati. Informaci bez redundance nelze komprimovat beze strat, protoze kazdy bit je jedinecny a nezastupitelny. Proste kde nic neni ani cert nebere.
podtrzeno/secteno:
1. bud ve skutecnosti pujde o nejakou kompresi, ktera *nekdy* zabere a bude lepsi nez cokoliv jineho a v jinych pripadech bude zase na nic (to v lepsim pripade)
2. nebo se ta firma chce jenom nejak zviditelnit (negativni reklama je taky reklama - hlavne ze se o nich mluvi)
:-(
Pro ty co jim to jeste uplne nedocvaklo:
Na chvili zapomente na pocitace a matematiku. Ta firma je startup, ale pry na tom delaji uz deset let :-) Delaji velkohuba prohlaseni pro ekonomicky platky ale na vedecke fronte ticho po pesine. Kolikpak patricne zblbnutych lidi nakoupi jejich akcie behem IPO? Nejaka reklama je jin na nic, ale prachy, s tema uz se da delat veci...
Ano, presne tohle jsem chtel napsat, nez jsem objevil tento prispevek. Vsichni ti, co se snazi naznacit neco ve stylu: co kdyby to nahodou byla pravda, by si meli pripomenout nektere predmety, kterymi prosli (asi opravdu jenom prosli) na vejsce. V obou pripadech (teorie mnozin, teorie kodovani) se relevantni latka probirala na jedne z prvnich prednasek (ne-li na prvni...)).
Hmm možná že je pravda, že si firma dělá jenom reklamu a možná že chce jen prodat dráže akcie, ale to nic nemění na tom že prostě není možné bezstrátově zabalit co chci.. No tedy alespoň tak aby to bylo menší.
Docela hodněkrát se i mě povedlo vymyslet "dokonalou kompresi", nevím čím to bylo ale nikdy se to nepovedlo dekomprimovat..
I když taková drobná možnost existuje, ale pak už to nefunguje na jakákoliv (náhodná multimediální) data...