Rzip - Rzip

tento článek potřebuje další citace pro ověření. Prosím pomozte vylepšit tento článek podle přidávání citací ke spolehlivým zdrojům. Zdroj bez zdroje může být napaden a odstraněn. Najít zdroje: „Rzip“  – zprávy  · noviny  · knihy  · učenec  · JSTOR (Listopad 2010) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

rzip je obrovského rozsahu komprese dat počítačový program navrženo kolem počátečního LZ77 -standardní shoda řetězce v okně slovníku 900 MB, následovaná bzip2 -na základě Burrows – Wheelerova transformace a entropické kódování (Huffman ) na výstupních blocích 900 kB.

Kompresní algoritmus

rzip funguje ve dvou fázích. První fáze vyhledá a zakóduje velké bloky duplicitních dat na potenciálně velmi dlouhé vzdálenosti (900 MB) ve vstupním souboru. Druhá fáze používá standardní kompresní algoritmus (bzip2 ) ke komprimaci výstupu prvního stupně.

V dnešní době je zcela běžné potřebovat komprimovat soubory, které obsahují redundanci na velké vzdálenosti. Například při kompresi sady domovských adresářů může mít několik uživatelů kopie stejného souboru nebo docela podobných souborů. Je také běžné mít jeden soubor, který obsahuje velké duplikované bloky na velké vzdálenosti, například PDF soubory obsahující opakované kopie stejného obrázku. Většina kompresních programů nebude moci využít této redundance, a tak může dosáhnout mnohem nižšího kompresního poměru, než může dosáhnout rzip.

Mezilehlé rozhraní mezi dvěma fázemi je tvořeno datovým tokem zarovnaným do bajtů, který obsahuje dva příkazy, a doslovný („přidat“) s délkou a údaji:

 type: 8 = 0 => literal / add range of count bytes count: 16 = 1..65535 data: 8..∞ = literal data to be entered (n whole bytes)

a a zápas („copy“) s parametry délky a odsazení:

 typ: 8 = 1 => rozsah shody / kopírování počtu bytů počet: 16 = 31..65535 offset: 32 = offset na pozici, ze které se má kopírovat

Doslovné nebo shodné / kopírované délky větší než 65 535 bajtů jsou rozděleny do několika pokynů. Konec proudu je označen příkazem literál / add (typ = 0, počet = 0) s nulovou délkou a bezprostředně za ním 32bitový CRC kontrolní součet.

Referenční implementace

Algoritmus postupného kontrolního součtu založený na jednom v rsync se používá k vyhledání potenciálních shod z tak velké datové sady. Jak se hash kbelíky zaplňují, předchozí hashe („tagy“) se zahodí dvakrát.^{[je zapotřebí objasnění ]} Značky jsou zahozeny takovým způsobem, aby poskytovaly docela dobrý pokrytí s postupně se snižující granularitou shody, jak se vzdálenost zvyšuje. Tato implementace nehledá délky shody menší než 31 po sobě jdoucích bajtů.

Výhody

Klíčovým rozdílem mezi rzip a jinými dobře známými kompresními algoritmy je jeho schopnost využívat výhody redundance na velké vzdálenosti. Známý deflační algoritmus používaný v gzip používá maximální vyrovnávací paměť historie 32 KiB. The Burrows-Wheelerova transformace algoritmus třídění bloků používaný v systému Windows bzip2 je omezena na 900 KiB historie. Vyrovnávací paměť historie v rzip může být až 900 MiB dlouhá, několik řádů větší než gzip nebo bzip2. Rzip je často mnohem rychlejší než bzip2, a to navzdory použití knihovny bzip2 jako koncového zařízení. Je to proto, že rzip napájí bzip2 zmenšenými daty, takže bzip2 musí dělat méně práce. Byla vytvořena jednoduchá srovnání (i když příliš malá na to, aby to byla směrodatná hodnota).^[1][2]

Nevýhody

rzip není vhodný pro všechny účely. Dvě největší nevýhody rzip spočívají v tom, že jej nelze pipeline (takže nemůže číst ze standardního vstupu nebo zapisovat na standardní výstup) a že používá velké množství paměti: typický běh komprese u velkého souboru může využívat stovky megabajtů z RAM. Pokud je k dispozici hodně RAM a je vyžadován velmi vysoký kompresní poměr, měl by být použit rzip, ale pokud tyto podmínky nejsou splněny, měly by být použity alternativní metody komprese jako gzip a bzip2, které jsou méně náročné na paměť místo rzip. Existuje alespoň jedna oprava, která umožňuje pipeline.^[3]

Dějiny

rzip původně napsal Andrew Tridgell v rámci jeho doktorského výzkumu.

Alternativní implementace

lrzip

lrzip (Long Range ZIP) je vylepšená verze rzip. Jeho formát souboru je nekompatibilní s rzip. Má následující vylepšení:

• LZMA, LZO, DEFLATE, Bzip2, a ZPAQ komprese (na rozdíl od Bzip2 pouze)
• Žádný limit slovníku, ani omezený dostupnou RAM
• Schopnost před komprimací otestovat stlačitelnost dat a zabránit tak plýtvání počítače pokusem o kompresi nestlačitelných dat
• Možnost pipeline ze standardního vstupu / standardního výstupu (se ztrátou kompresního poměru)
• Možnost zakázat kompresi poslední fáze pro použití s ​​jiným kompresorem
• Volitelný AES-128 šifrování^[4]

rzip64

rzip64 je rozšíření rzip pro velmi velké soubory, které mohou využívat více jader CPU paralelně. Existují srovnávací výsledky.^[5] Nejdůležitější je však schopnost rzip64 kdykoli přerušit. Běžící úloha komprese (u velkých souborů to může snadno trvat několik hodin) tak přežije i restart systému, aniž by ztratila již dokončenou práci, a může být obnovena později. Formát souboru rzip64 je identický s původním rzip.

REP

REP je alternativní implementace rzip algoritmu Bulata Ziganshina použitá v jeho FreeArc archivátor jako preprocesor pro kompresní algoritmy LZMA / Tornado. Ve FreeArc REP najde shody na velké vzdálenosti a pak LZMA komprimuje zbývající data. Například v počítači s 2 GB RAM najde REP shody o délce alespoň 512 bajtů na vzdálenosti do 1 GB a poté LZMA najde všechny zbývající shody na vzdálenosti do 128 MB. Společně tedy poskytují nejlepší možnou kompresi s rozpočtem 2 GB RAM.

Díky optimalizaci pro dekompresi streamů a spolupráci s LZMA má REP rozdíl oproti původní implementaci RZIP. Nejprve ve výchozím nastavení najde pouze shody o délce 512+ bajtů, protože srovnávací testy prokázaly, že je to optimální nastavení pro celkovou kompresi REP + LZMA. Za druhé, používá posuvný slovník dlouhý asi 1/2 RAM, takže dekomprese nemusí znovu číst data z dekomprimovaného souboru. Výhodou REP je jeho multiplikativní válcovací hash, který je rychle vypočítatelný a má téměř ideální distribuci.

Větší minimální délka shody (512 bajtů ve srovnání s 32 bajty v rzip) umožnila další optimalizaci rychlosti, takže REP poskytuje velmi rychlou kompresi (asi 200 MB / s na Intel i3-2100).

SREP

SREP (SuperREP) je implementace myšlenky společnosti Tridgell na kompresor LZ, který neukládá svůj slovník do RAM, místo toho používá SHA1 hash zpracovaných bloků k porovnání jejich obsahu. Umožňuje programu komprimovat soubory, které jsou přibližně 10krát větší než dostupná paměť RAM. Dekomprese se provádí buď čtením dat z dekomprimované části souboru, nebo uložením budoucích shod do paměti (kompresní algoritmus future-LZ). Komprese budoucí LZ samozřejmě vyžaduje 2 průchody vstupním souborem, ale dekomprese vyžaduje malou paměť. V jednom experimentu vyžadoval 22 GB soubor komprimovaný s minimální délkou shody 512 bajtů a plným 22 GB slovníkem jen 2 GB RAM pro dekompresi.

Viz také

• Seznam formátů archivu, Porovnání archivních formátů
• Seznam archivátorů souborů, Porovnání archivátorů souborů

Reference

externí odkazy

• rzip
• lrzip - vylepšení rzip umožňující druhou fázi bzip2 snížení bude nahrazeno LZMA, LZO, nebo žádná druhá fáze (surová, komprese pouze ve slovníku). Autorem je Con Kolivas, který uvádí, že „lrzip“ znamená „Long Range ZIP“.
• rzip64 - paralelní vylepšení „rzip“ s režimem stop-and-go od Kay Gorontzi.
• REP - vylepšená implementace RZIP optimalizovaná pro použití společně s LZMA
• SREP - první LZ kompresor, který používá méně RAM než velikost slovníku
• DataCompression.info - LZ77 / LZSS a deriváty