ROLZ (z anglického R reduced O ffset LZ - algoritmus Lempel-Ziv s redukovanými offsety) je slovníkový algoritmus komprese dat blízký LZ77 , ale využívající některé kontextové techniky ke snížení počtu aktivních offsetů. Samotný koncept ROLZ poprvé představil Malcolm Taylor ve svém archivátoru RK v roce 1999 a tento algoritmus je jedním z nejmodernějších přístupů k budování rychlých a účinných kompresních algoritmů.
Ve standardním LZ77 jsou shody kódovány jako pár:
Problémem tohoto schématu je redundance v kódování. Například při velikosti slovníku 4 KB je k dispozici 4096 možností posunu. Je jasné, že většina offsetů nebude využita, a pokud se použije například jen 512 ze 4096 možností, tak pro zakódování offsetu stačí 9 bitů místo 12 (25% snížení).
Mnoho autorů se pokusilo snížit možné hodnoty offsetů, mezi ně patří:
Autoři: Edward R. Fiala, Daniel H. Greene, 1989.
Shody nejsou kódovány dvojicí [délka, offset], ale speciálním indexem odpovídajícím určitému řetězci ve slovníku. Jinými slovy, stejné fráze mají stejný index, který zajišťuje ekonomické kódování shod.
Autor: Ross Williams, 1991.
V podstatě je LZRW4 podobný ROLZ. Přestože se autor nepokusil o vytvoření plnohodnotného programu, na zobrazeném demo kompresoru můžete vidět obvod ROLZ v jeho pracovní verzi.
Autor: Charles Bloom, 1995.
LZP je slovníkový kompresní algoritmus, který se při kódování shody zcela obejde bez posunů. To je možné díky skutečnosti, že offsety vzhledem k aktuálnímu kontextu jsou uloženy ve speciální tabulce a kompresor a dekompresor pracují na této tabulce stejným způsobem.
Autor Dzung T. Hoang, Philip M. Long, Jeffrey Scott Vitter, 1995.
Tento algoritmus je podobný ROLZ, s tím rozdílem, že kontexty s proměnnou délkou se používají ke snížení aktivních posunů namísto kontextů s pevným pořadím.
Podle popisu autora se jedná o rychlý Lempel-Zivův algoritmus s velkým slovníkem, který je schopen rychle a efektivně pokrýt velké vzdálenosti ve slovníku.
Je třeba poznamenat, že RK je uzavřený komerční archivátor a mnoho podrobností o použitých algoritmech nebylo zveřejněno. Ale díky jistým lidem bylo tajemství odkryto a na tomto kompresním algoritmu bylo napsáno dokonce několik bezplatných programů.
Ke snížení aktivních posunů se tedy používá kontext pevného pořadí. V originále se jedná o kontext prvního řádu (tedy jeden znak předcházející aktuálnímu znaku), je možné použít i jiné kontexty - řekněme kontext druhého řádu (dva znaky předcházející aktuálnímu) atd.
Namísto hledání shod pro všechny offsety ve slovníku se omezíme na hledání pouze z těch offsetů, kterým předcházel aktuální kontext. V nejjednodušším případě můžete použít nějaký druh ofsetové tabulky:
// nalezení nejdelšího kontextu shody = buf [ pozice - 1 ]; // aktuální kontext prvního řádu max_match = 0 ; // délka shody pro kódování index = 0 ; // index shody for ( i = 0 ; i < TAB_SIZE ; i ++ ) { // pro každý offset uložený v tabulce pro tento kontext offset = tab [ context ][ i ]; // najdi offset match_length = get_match ( offset ); // zjistěte délku shody if ( délka_shody > max_shoda ) { // nalezena delší shoda max_shoda = délka_shody ; index = i ; // uložit index } } // aktualizuje tabulku pro ( i = TAB_SIZE - 1 ; i > 0 ; i -- ) // nejprve přesune všechny offsety nahoru, odstraní nejstarší tab [ kontext ][ i ] = tab [ kontext ][ i - 1 ]; tab [ kontext ][ 0 ] = pozice ; // pak přidá aktuální offset // zakóduje literál nebo shodu if ( max_match >= MIN_MATCH ) { encode_match_length ( max_match ); // zakóduje délku shody encode_match_index ( index ); // kódování pozice indexu shody += max_match ; } else { // nenalezena žádná odpovídající délka encode_literal ( buf [ pozice ]); // zakódování doslovné pozice ++ ; }Toto je nejjednodušší způsob. V praxi může iterace přes řekněme 1024 offsetů v každém kroku trvat příliš dlouho. Pro urychlení vyhledávání lze použít hashování a různé struktury pro rychlé vyhledávání, které se používají v rozšířených implementacích rodiny algoritmů LZ77.
V původním ROLZ jsou literály kódovány pomocí kontextového modelu prvního řádu a není to náhoda. Faktem je, že toto schéma kóduje větší počet literálů ve srovnání se standardním LZ77, protože velmi krátkých shod se schéma ROLZ prostě nedotkne. Například při použití kontextu prvního řádu a s minimální délkou shody tří znaků by skutečná délka minimální shody byla čtyři (1 (kontext) + 3 (minimální délka shody) = 4). Kontextový model prvního řádu nebo složitější model PPM 1-0 pro kódování literálů je schopen kompenzovat tento nedostatek algoritmu.
Autor: Malcolm Taylor, 2005.
Tyto algoritmy jsou dalším vývojem ROLZ:
Oba algoritmy používají kontext prvního řádu ke snížení aktivních posunů a jsou také schopny používat tabulku až 32 000 posunů na kontext.
Ale hlavním rozlišovacím znakem těchto algoritmů je použití optimální analýzy při kódování. Dynamické programování (Dynamic Programming) – zde použitý trik je schopen vypočítat optimální sekvenci literálů/shod mnoho kroků dopředu, přičemž při výběru zohledňuje skutečné náklady na kódování literálu nebo shody.
| Kompresní metody | |||||||
|---|---|---|---|---|---|---|---|
| Teorie |
| ||||||
| Bezztrátový |
| ||||||
| Zvuk |
| ||||||
| snímky |
| ||||||
| Video |
| ||||||