Hlavní navigace

Re: Kompresní algoritmus

Tomáš Znamenáček

Boření mýtů a pokládání nových hranic žánru je vždycky zajímavým okamžikem, zvláště v matematice a potažmo tedy informatice. Matematika už zažila nějaké dvě tři krize, ale protentokrát to vypadá, že šampaňské můžeme klidně odložit zpátky k ledu.

Sebevědomá (přesněji řečeno asi dosti drzá) společnost ZeoSync ohlásila sedmého ledna, že právě ona hodlá položit nové pražce oboru (jenžto, jak všichni víme, když je doma mazec, děda mráz nám nepřinese ani jeden pražec), a to vynalezením perfektního komprimačního algoritmu. A proto, jestli ještě nemáte pěknou signaturu, doporučuji vřele výkus z prohlášení ZeoSync:

„ZeoSync intentionally randomizes naturally occurring patterns to form entropy-like random sequences through its patent pending technology known as Zero Space Tuner.“

Překládat to nebudu, smíchy bych si naplakal do klávesnice. Další citát ukazuje, že zřejmě nejenom XML je silnou zbraní na poli marketingu:

„ZeoSync has developed the TunerAccelerator in conjunction with some traditional state-of-the-art compression methodologies. This work includes the advancement of Fractals, Wavelets, DCT, FFT, Subband Coding, and Acoustic Compression that utilizes synthetic instruments.“

Nesmírně zajímavý je ovšem rozhovor (Wired news) se samotným CEO ZeoSync, na který Radoomek upozorňoval v sobotu. Cituji:

WN: How do you get around the conventional wisdom that says simple mathematics says it's impossible?

PSG: That's what's being proposed as the reason that our technology won't work. We plan to attack that issue head on. What hasn't been previously proven, we're proving. We can compress every single permutation of an N-member set. These are going to be the details that we're going to be announcing in a few days.

Ve volném překladu:

WN: A jak se hodláte vyrovnat s tradiční představou, která říká, že jednoduchou matematikou lze dokázat nemožnost něčeho podobného?

PSG: Lidé často prohlašují, že právě tohle je důvod, proč naše technologie nemůže fungovat. Hodláme tento mýtus zbořit. Dokazujeme to, co nedokázal nikdo před námi. Umíme komprimovat libovolnou permutaci n-prvkové množiny. Detaily budou uveřejněny během několika dní.

Jelikož jinak ctěný CEO mlží jako ústřice a nehodlá svou state-of-the-art methodu vydat jen tak davu, chytil bych se té permutace libovolné n-prvkové množiny. V jádru to znamená, že v ZeoSync našli algoritmus, který dokáže libovolný soubor velikosti N bytů zkomprimovat na soubor menší N bytů, přičemž nedojde ke ztrátě informace. Tady je důkaz, že to není možné. Doporučuji si ho přečíst, není težký (intelektuálním vrcholem je sečtení geometrické řady). Obávám se, že podobný mýtus se boří těžko…

(PST, nikomu to neříkejte, ale ve skutečnosti je to pravda. Fakt. Nenechte se zmást a investujt*e, bude to jízda století…)

Odkazy:

ZeoSync press release

Reuters

Wired news

Našli jste v článku chybu?
22. 1. 2002 10:56
kubik (neregistrovaný)

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 :)

27. 8. 2006 16:53
uživatel si přál zůstat v anonymitě
Příklad: Dejme tomu, že máme za úkol zkomprimovat např. 256 náhodných bitů. Analogií zůstává, že je to něco jako 256 losovacích zařízení na sobě nezávislých, které vyprodukují stav |0| na 50%, stav |1| též. Definice bitu (jednotka rozhodnutí mezi dvěma stejně pravděpodobnými možnostmi) a definice komprese (odstranění stavové nebo i jiné redundance) a fakt, že podle vzorce pro entropii pro 2 stavy H = p1*log2 (1/p1) + to samé s p2, čili pro p1=p2 H[bit]=1 nám jasně říkají, že 2 stejně pravděpo…