Vlákno názorů k článku Kompresní algoritmy v souborech ZIP: Reduce a LZ77 od Pavel Šrubař - Pokud potřebujeme co nejlepší bezeztrátovou kompresi, např. pro...

Pokud potřebujeme co nejlepší bezeztrátovou kompresi, např. pro dlouhodobou archivaci, je v dnešní době rychlých počítačů zpozdilé nutit uživatele, aby zkoušel různé archivační aplikace a předem zadával kompresní metodu.
Efektivní kompresor by měl sám potichu vyzkoušet všechny známé, patentově nezatížené bezeztrátové algoritmy a použít ten s nejlepším výsledkem,
případně vyzkoušet i jejich kaskádní kombinace.

Namísto čísla kompresní metody by uživatel zadával požadovanou propustnost v bitech za sekundu, podobně jako to dělají ztrátové komprimátory videa.
Kompresor by pak v dalším průchodu mohl rozdělit vstupní solid-block na poloviny a na každou z nich opět aplikovat výběr optimální kompresní metody. To celé by rekurzivně opakoval s každou polovinou, dokud se nevyčerpá přidělený čas.

V datech reálných souborů se mohou střídat úseky optimálně komprimovatelné různými metodami, a jejich střídání by umožnilo z nich vyždímat každou kapku entalpie. Výsledkem by byl ultimátně efektivní blokový i proudový bezeztrátový kompresor. Nechcete se toho někdo ujmout?

Ten napad je dobry na papire, ale pak to znamena, ze vystup z komprese muze v zavislosti na situaci potrebovat ruzne decompressory. Coz vytvari dost barokni zavislosti.

Ono staci kdyz se budeme bavit o dve urovne nizsi komplexity.

Kdyz vam v praxi zmeni na storagi ktera jako backend pouziva ZFS zakaznik zmeni 4x kompresni algoritmus na jednom datasetu (nevim proc... asi jaro), mate tam hromadu bloku ruzne nakomprimovanych dat tak jak sel provoz. Fakt chutovka. Grafy vykonu pak vypadaji jako tratranska hrebenovka prazaka v sandalich...

26. 5. 2021, 11:46 editováno autorem komentáře

Ono lidem leckdy nedojde, ze to, co prave udelali, vytvorilo API. Jejich starsi ja poskytuje data jejich budoucimu ja... A je potreba setsakra myslet na kompatibilitu.

Výstup z hypotetického ultimátního kompresoru by samozřejmě k rozbalení musel vystačit s jediným dekomprimačním programem, který bude znát všechny potenciálně použitelné metody. Z komprimovaného souboru by nejprve přečetl délku jednoho bloku, identifikátor metody použité pro tento blok, rozbalil jej do výstupu a to celé opakoval pro všechny další bloky.

Je dobrým zvykem, že kompresor i dekompresor jsou napsány tímtéž autorem a dodávány v rámci jedné aplikace, viz PKZIP a PKUNZIP, ARJ a UNARJ, RAR a UNRAR atd.

No a vyplatilo by se to vůbec? A není to náhodou tak, že moderní kompresní algoritmy něco dost podobného už dělají (nevím, ptám se)?

To je takovy typicky vlhky sen vyvojare nebo naivniho startupisty.

V soucasne dobe je takove reseni prilis komplexni na to aby se vyplatilo v pomeru ku zvysovani kapacity hrubou silou.

Tudiz moznou kompresi/kapacitu urcuje admin s odbornymi znalostmi a ne uzivatel. Taky ne pro kazdy hw je ta ktera komprese efektivni. Je tam hromady zavislosti.

Dale se obavam ze bezny user nevi nic o propustnosti v bitech za sekundu. Pro nektere aplikace ktere maji velke zmeny v architekture nebo jsou velke nepredvidatelne zmeny chovani uzivatelu to neni prilis definovatelne.

Pokud by se nad tim mela delat nejaka statistika je to zase dalsi vrstva komplexity. Resit problemy na produkci v takovem systemu musi byt za trest.

Tak do tohohle se nikdo schopný na 100% hrnout nebude.

Zkoušet všechny nepatentované algoritmy je blbost. Hromada jich je zastaralých. Další hromada je navržená např. pro rychlost a ne pro maximální kompresi. I kdybych vyloučil úplné úlety, tak hromada algoritmů krát hromada nastavení umocněné ještě na ty kaskádní pokusy je taková kombinační exploze, že by se výsledku dočkala možná tak moje vnoučata.

Pokud se chci výsledku dožít, musím se omezit jen na nadějné kandidáty.

A i kdyby se vám to nakrásně podařilo, tak by výsledkem byl algoritmus efektivní z pohledu jedné jediné metriky, pro kterou jste obětoval všechno ostatní. Výsledkem by byl ultimátně jednoúčelový nástroj.

Obava z nedožití se výsledku je lichá, k tomu právě slouží ta limitace propustnosti. Při vhodném defaultním nastavení, např. 100 Mbps, by komprimace stomegabajtového souboru trvala 8 sekund. Pomalý počítač by za tu dobu možná stihl vyzkoušet jen několik nejnadějnějších komprimačních metod, zatímco moderní PC by za stejnou dobu dospěl k menšímu výslednému souboru. A kdybych chtěl komprimovat ještě důsledněji, třeba před vypálením archivu, snížil bych bitrate třeba jen na 1 Mbps a čtvrthodinu si počkal.

Navržený princip neaspiruje na rychlost komprese (ta je plně nastavitelná jediným parametrem), nýbrž na pohodlí uživatele, který nemusí bádat nad rozličnými kompresními metodami vhodnými pro jeho soubory, ale nechá místo sebe bádat stroj.

KISS

Jo takovouhle bitrate jste myslel. Takže vlastně něco úplně jiného, než je bitrate u ztrátové komprese.

Popravdě si nedokážu představit míň intuitivní parametr pro nastavování kvality/rychlosti než bitrate + nějakou toleranci. Uživatel bude spíš vědět, kdy ten soubor potřebuje a bude si to muset přepočítat podle velikosti souboru.

O jakýchkoliv dalších vlastnostech té komprese ta bitrate neříká lautr nic. Jakýkoliv možný požadavek na tuhle bitrate se dá splnit algoritmem copy+sleep. Samozřejmě že je to blbost, protože to vychází z úplně nesmyslné metriky.

Bitrate je přece přirozená metrika u všech komprimačních programů, i když se jí většinou říká rychlost komprese. Já tento pojem používám ve smyslu
rozděluj vstupní soubor na menší části a zkoušej se pro každou z nich dobrat optimální komprese, aniž bys překročil nastavenou dobu.

Pro čistě textový soubor bývá optimální metodou slovníková komprese.
Soubor ale taky může obsahovat jen omezenou abecedu, třeba pouze znaky 0..F v případě hexadecimálních textových výpisů. Na takové soubory bude lepší nejprve aplikovat Huffmanovo kódování.
Pro bitmapové obrázky s velkými stejnobarevnými plochami bude asi nejúčinnějším algoritmem Run-length encoding.
Reálné soubory bývají mixem, například spustitelný program obsahuje na začátku sekci se strojovým kódem (kandidát pro LZ777),
ve druhé polovině datovou sekci se spoustou prostého textu (Huffman+Reduce)
a poslední čtvrtině sekci resources s bitmapami (kandidát pro RLE).

Běžný kompresní program ale neumí adaptivně měnit komprimační metodu podle dat, proto navrhuji keep it simple, aby BFU nemusel znát parametry komprimačních programů a studovat odborné články na Rootu (jakkoli jsou velice zajímavé :-)

BTW, opravdu si myslíte že uživatelé ocení kompresní program, ze kterého budou padat větší soubory, pokud budou chtít komprimovat víc věcí zároveň, nebo se třeba windowsy rozhodnou stahovat aktualizace?

Jediný co mě napadá je zstd --adapt, to "automaticky" přizpůsobuje úroveň komprese rychlosti I/O, aby to moc nezdržovalo. Hodí se teda při kopírování přes síť třeba, nebo při dočasných zálohách, kde se hodí to mít alespoň trochu komprimované, ale nechce se nám moc dlouho čekat.

Je potřeba použít víc jader -T0 (bez toho to nějak nefunguje) a koukat na stupeň komprese je možné pomocí -v, ukazuje se v závorce jako třeba (L9). Myslím, že stupeň komprese začne na defaultní 3 a ten zvětšuje nebo zmenšuje, podle toho, jak to nestíhá nebo stíha.

zstd --adapt -v -T0 soubor