Metody kódování. Komprese metodou sériového kódování: algoritmus RLE

Základní klasifikace reverzibilních kompresních algoritmů

Existuje mnoho různých praktické metody kompresi bez ztráty informací, které mají zpravidla různou účinnost odlišné typy data a různé objemy. Tyto metody jsou však založeny na třech hlavních klasických kompresních schématech:

sekvenční sériové kódování (RLE);

Statistické kompresní metody;

Slovníkové (heuristické) kompresní metody.

Komprese metodou sériového kódování: algoritmus RLE

Nejznámější jednoduchý přístup a reverzibilní kompresní algoritmus je Run Length Encoding (RLE). Podstatou metod tohoto přístupu je nahrazení řetězců nebo řad opakujících se bajtů nebo jejich sekvencí jedním kódovacím bajtem a čítačem počtu jejich opakování. Problém se všemi podobnými metodami je určit způsob, jakým by dekompresní algoritmus mohl odlišit zakódovanou řadu od jiných nezakódovaných sekvencí bajtů ve výsledném toku bajtů. Řešení problému je obvykle dosaženo umístěním štítků na začátek kódovaných řetězců. Takovými značkami mohou být například charakteristické bitové hodnoty v prvním bajtu kódovaného běhu, hodnoty prvního bajtu kódovaného běhu a podobně. Tyto metody jsou obvykle docela účinné pro kompresi bitmap. grafické obrázky(BMP, PCX, TIF, GIF), protože posledně jmenované obsahují nemálo dlouhých sérií opakujících se sekvencí bajtů. Nevýhodou metody RLE je spíše nízký kompresní poměr nebo cena kódování souborů s malým počtem sérií a co je horší, s malým počtem opakujících se bajtů v sérii.

Algoritmus RLE je založen na myšlence identifikace opakovaných datových sekvencí a jejich nahrazení jednodušší strukturou, která specifikuje datový kód a faktor opakování. Nechť je uvedena například sekvence dat, která podléhá kompresi: 1 1 1 1 2 2 3 4 4 4 . V algoritmu RLE se navrhuje nahradit jej následující strukturou: 1 4 2 2 3 1 4 3 , kde první číslo každé dvojice čísel je datový kód a druhé je opakovací faktor. Pokud je pro uložení každého datového prvku vstupní sekvence přidělen 1 bajt, pak celá sekvence zabere 10 bajtů paměti, zatímco výstupní sekvence (komprimovaná verze) bude zabírat 8 bajtů paměti. Je jasné, že algoritmus RLE dá nejlepší efekt kompresi při větší délce opakující se datové sekvence. V případě výše uvedeného příkladu, pokud vstupní sekvence vypadá takto: 1 1 1 1 1 1 3 4 4 4, pak bude kompresní poměr 60 %. V tomto ohledu je vyšší efektivity algoritmu RLE dosaženo komprimací grafických dat (zejména u jednotónových obrázků).

Heuristické (slovníkové) algoritmy komprese (LZ, LZW) hledejte v souboru řádky, které se opakují, a vytvořte si slovník frází, se kterými se již setkali. Typicky mají takové algoritmy řadu specifických parametrů (velikost vyrovnávací paměti, maximální délka fráze atd.), jejichž výběr závisí na zkušenostech autora práce, a tyto parametry jsou voleny tak, aby bylo dosaženo optimální poměr doby běhu algoritmu, kompresního poměru a seznamu souborů, které se dobře komprimují.

Statistické algoritmy(Huffman, Shannon-Fano, aritmetika) Statistické algoritmy používají statistický datový model a kvalita komprese informací přímo závisí na tom, jak dobrý je tento model. Účetnictví statistické vlastnosti data v nejjednodušším případě znamenají použití nejednotných kódů pro kódování - často se vyskytující znaky jsou zakódovány do krátkých kódů, zřídka do dlouhých. To znamená, že takové algoritmy potřebují znát pravděpodobnosti výskytu znaků v obraze, kterou lze v jednoduchém případě odhadnout četností výskytu znaků ve vstupních datech. Tyto pravděpodobnosti jsou zpravidla neznámé. Účelem kódování je převést vstupní tok na bitový tok minimální délky, čehož je dosaženo snížením entropie (chaotiky) vstupního toku zohledněním frekvencí symbolů.

Délka kódu reprezentujícího znaky z abecedy proudu musí být úměrná množství informací ve vstupním proudu a délka znaků proudu v bitech nesmí být násobkem 8 nebo dokonce proměnná. Pokud je známo rozdělení pravděpodobnosti četností výskytu znaků z abecedy vstupního proudu, pak je možné sestavit optimální model kódování. Ovšem vzhledem k existenci velkého počtu různé formáty souborů je úkol mnohem složitější, protože. rozdělení frekvence datových symbolů není předem známo. V tomto případě se používají dva přístupy.

První spočívá v prohlížení vstupního toku a vytvoření kódování na základě shromážděných statistik (to vyžaduje dva průchody souborem – jeden pro prohlížení a sběr statistické informace, druhý - pro kódování, což poněkud omezuje rozsah takových algoritmů, protože tím je možnost jednoprůchodového kódování "za chodu", používaného v telekomunikačních systémech, kde někdy není známo množství dat, a jejich opakovaný přenos nebo analýza může trvat nepřiměřeně dlouho). V takovém případě je entropické schéma použitého kódování zapsáno do výstupního proudu. Tato metoda známé jako statické Huffmanovo kódování. Tabulka symbolů se přenese spolu s komprimovaným souborem. Takové algoritmy komprimují většinu souborů docela dobře, ale je nutný dodatečný přenos frekvenční tabulky symbolů, stejně jako potřeba dvou průchodů zdrojového souboru pro sběr statistik a kompresi.

Druhá metoda- metoda adaptivního kódování. Jeho principem je změna kódovacího schématu v závislosti na povaze změn ve vstupním toku. Adaptivní - začněte pracovat s pevnou počáteční tabulkou četností znaků (obvykle jsou zpočátku všechny znaky stejně pravděpodobné) a v průběhu práce se tato tabulka mění v závislosti na znacích, které se v souboru vyskytují. Výhody: jednoprůchodový algoritmus, není třeba přenášet frekvenční tabulku symbolů, poměrně efektivně komprimuje širokou třídu souborů. Tento přístup má jednoprůchodový algoritmus a nevyžaduje explicitní ukládání informací o použitém kódování. Adaptivní kódování může dát větší stupeň komprese ve srovnání se statickou, protože změny ve frekvencích vstupního proudu jsou plně zohledněny. Tato technika je známá jako dynamické Huffmanovo kódování.

S ohledem na to lze statistické algoritmy rozdělit do tří tříd:

1. Neadaptivní – použijte pevné, předem určené pravděpodobnosti symbolů. Pravděpodobnostní tabulka symbolů se nepřenáší se souborem, protože je známa předem. Nevýhoda: úzká oblast použití pro konkrétní tabulku frekvencí, pro kterou je dosaženo přijatelného kompresního poměru.

2. Poloadaptivní - pro každý soubor je sestavena tabulka četností znaků a na jejím základě je soubor komprimován. Tabulka symbolů se přenese spolu s komprimovaným souborem. Takové algoritmy komprimují většinu souborů docela dobře, ale je nutný dodatečný přenos frekvenční tabulky symbolů, stejně jako potřeba dvou průchodů zdrojového souboru pro sběr statistik a kompresi.

3. Adaptivní - začněte pracovat s pevnou počáteční tabulkou četností znaků (obvykle jsou zpočátku všechny znaky stejně pravděpodobné) a v průběhu práce se tato tabulka mění v závislosti na znacích, které se v souboru vyskytují. Výhody: jednoprůchodový algoritmus, není třeba přenášet frekvenční tabulku symbolů, poměrně efektivně komprimuje širokou třídu souborů.

Huffmanův algoritmus je založen na myšlence kódování pomocí bitových skupin. Nejprve provedeno frekvenční analýza je nastavena posloupnost vstupních dat, tedy frekvence výskytu každého znaku, který se v ní vyskytuje. Poté jsou znaky seřazeny podle klesající frekvence výskytu.

Základní myšlenkou je, že čím běžnější znak je, tím méně bitů zakóduje. Výsledek kódování je vložen do slovníku potřebného pro dekódování. Zvažte jednoduchý příklad ilustrující fungování Huffmanova algoritmu.

Ve statickém Huffmanově kódování jsou vstupním znakům (řetězcům bitů různé délky) přiřazeny bitové řetězce, rovněž proměnné délky - jejich kódy. Délka kódu každého znaku je úměrná binárnímu logaritmu jeho frekvence s opačným znaménkem. A celkový soubor všech nalezených různých znaků je abeceda proudu. Toto kódování je prefixové, což usnadňuje jeho dekódování do výsledného streamu, protože při kódování prefixem není kód žádného znaku prefixem kódu žádného jiného znaku – abeceda je jedinečná.

První verze algoritmu

Tento algoritmus je extrémně snadno implementovatelný. Skupinové kódování – z anglického Run Length Encoding (RLE) – je jedním z nejstarších a nejjednodušších algoritmů archivace grafiky. Obraz v něm (stejně jako v několika algoritmech popsaných níže) je nakreslen do řetězce bajtů podél čar rastru. K samotné kompresi v RLE dochází kvůli tomu, že v původním obrázku jsou řetězce identických bajtů. Nahraďte je páry<счетчик повторений, значение>snižuje redundanci dat.

Algoritmus dekomprese vypadá to takto:

inicializace(...);
dělat(
if(je čítač(bajt)) (
čítač = Low6bits(byte)+1;
for(i=1 na počítadlo)
De
}
jiný(
DecompressedFile.WriteByte(byte)
) while(ImageFile.EOF());

V tomto algoritmu jsou znaménka čítače (čítače) ty v horních dvou bitech čteného souboru:

V souladu s tím je zbývajících 6 bitů utraceno na čítači, který může nabývat hodnot od 1 do 64. Řetězec 64 opakovaných bytů převedeme na dva byty, tzn. komprimovat 32krát.

Cvičení: Vytvořte algoritmus komprese pro první verzi algoritmu RLE.

Otázka pro sebeovládání: Navrhněte dva nebo tři příklady „špatných“ obrázků pro algoritmus RLE. Vysvětlete, proč velikost komprimovaného souboru nad velikostí zdrojový soubor.

Druhá verze algoritmu

Druhá varianta tohoto algoritmu má větší maximální poměr archivace a méně zvětšuje velikost zdrojového souboru.

Dekompresní algoritmus pro to vypadá takto:

inicializace(...);
dělat(
byte = ImageFile.ReadNextByte();
čítač = Low7bits(byte)+1;
if(if opakovací znak (byte)) (
value = ImageFile.ReadNextByte();
pro (i=1 na počítadlo)
CompressedFile.WriteByte(hodnota)
}
jiný(
for(i=1 na počítadlo)(
value = ImageFile.ReadNextByte();
CompressedFile.WriteByte(hodnota)
}
CompressedFile.WriteByte(byte)
) while(ImageFile.EOF());

Znakem opakování v tomto algoritmu je jednotka vyššího řádu odpovídajícího bajtu:

Jak lze snadno vypočítat, nejlepší případ tento algoritmus zkomprimuje soubor 64krát (místo 32krát jako v předchozí verzi), v nejhorším případě se zvýší o 1/128. Průměrné kompresní poměry tento algoritmus jsou na úrovni ukazatelů první varianty.

Cvičení: Napište kompresní algoritmus pro druhou verzi algoritmu RLE.

Vlastnosti algoritmu RLE:

Kompresní poměry: První možnost: 32, 2, 0,5. Druhá možnost: 64, 3, 128/129.(nejlepší, průměr, nejhorší šance)

Třída obrázků: Algoritmus je zaměřen na obrázky s malým počtem barev: obchodní a vědecká grafika.

Symetrie: Přibližně jedna.

Charakteristické vlastnosti: Jediné pozitivní aspekty algoritmu lze snad přičíst pouze skutečnosti, že nevyžaduje přídavná paměť při archivaci a rozbalování a také funguje rychle. Zajímavá vlastnost skupinové kódování spočívá v tom, že míru archivace u některých obrázků lze výrazně zvýšit právě změnou pořadí barev v paletě obrázků.

Název algoritmu byl dán prvními písmeny jmen jeho vývojářů - Lempel, Ziv a Welch. Komprese v něm, na rozdíl od RLE, se již provádí kvůli stejným řetězcům bajtů.

Algoritmus LZ

Existuje poměrně velká rodina algoritmů podobných LZ, které se liší například způsobem vyhledávání opakovaných řetězců. jeden z dost jednoduché možnosti tento algoritmus například předpokládá, že vstupní proud obsahuje buď pár<счетчик, смещение относительно текущей позиции>, nebo prostě<счетчик>„přeskočené“ bajty a samotné hodnoty bajtů (jako ve druhé verzi algoritmu RLE). Při rozepínání pro pár<счетчик, смещение>zkopírován<счетчик>bajtů z výstupního pole vyplývajícího z rozbalení do<смещение>bajtů před a<счетчик>(tj. číslo rovné čítači) hodnoty „přeskočených“ bajtů jsou jednoduše zkopírovány do výstupního pole ze vstupního toku. Tento algoritmus je časově asymetrický, protože při hledání identických podřetězců vyžaduje úplné prohledání vyrovnávací paměti. V důsledku toho je pro nás obtížné nastavit velký buffer kvůli prudkému nárůstu doby komprese. Potenciálně však konstrukce algoritmu, ve kterém<счетчик>a dál<смещение>Budou přiděleny 2 bajty (vysoký bit horního bajtu čítače je známkou opakování řetězce / kopírování toku), dá nám možnost zkomprimovat všechny opakované podřetězce až na 32 Kb v 64 Kb vyrovnávací paměti.

V tomto případě dostaneme zvětšení velikosti souboru v nejhorším případě o 32770/32768 (ve dvou bytech je napsáno, že dalších 2 15 bytů se má přepsat do výstupního proudu), což není vůbec špatné. Maximální kompresní poměr bude v limitu 8192krát. V limitu, protože maximální kompresi získáme přeměnou 32Kb vyrovnávací paměti na 4 bajty a nebudeme hned akumulovat vyrovnávací paměť této velikosti. Minimální podřetězec, pro který je pro nás výhodné komprimovat, by však měl obecně obsahovat alespoň 5 bajtů, což určuje nízkou hodnotu tohoto algoritmu. Mezi výhody LZ patří extrémní jednoduchost dekompresního algoritmu.

Cvičení: Navrhněte jinou variantu algoritmu LZ, ve kterém pár<счетчик, смещение>Budou přiděleny 3 bajty a vypočítají se hlavní charakteristiky vašeho algoritmu.

Varianta algoritmu zvažovaná níže bude používat strom k reprezentaci a ukládání řetězců. Je zřejmé, že se jedná o poměrně silné omezení typu řetězců a ne všechny totožné podřetězce na našem obrázku budou během komprese použity. V navrženém algoritmu je však výhodné komprimovat i řetězce sestávající ze 2 bajtů.

Proces komprese vypadá docela jednoduše. Postupně čteme znaky vstupního proudu a kontrolujeme, zda v námi vytvořené tabulce řetězců takový řetězec existuje. Pokud je tam řádek, tak přečteme další znak, a pokud tam žádný řádek není, tak zadáme do streamu kód předchozího nalezeného řádku, řádek vložíme do tabulky a spustíme vyhledávání znovu.

Funkce InitTable() vymaže tabulku a vloží do ní všechny řádky jedné délky.

InitTable();
CompressedFile.WriteCode(ClearCode);
CurStr=prázdný řetězec;
while(not ImageFile.EOF())( //Do konce souboru
C=ImageFile.ReadNextByte();
if(CurStr+C je v tabulce)
CurStr=CurStr+C;//Přilepí znak k řetězci
jiný(
code=CodeForString(CurStr);//kód-není bajt!
AddStringToTable(CurStr+C);
CurStr=C; // Řetězec jednoho znaku
}
}
code=CodeForString(CurStr);
CompressedFile.WriteCode(code);
CompressedFile.WriteCode(CodeEndOfInformation);

Jak bylo uvedeno výše, funkce InitTable() inicializuje tabulku řetězců tak, aby obsahovala všechny možné jednoznakové řetězce. Pokud například komprimujeme bajtová data, pak v tabulce bude 256 takových řádků („0“, „1“, ..., „255“). Hodnoty 256 a 257 jsou vyhrazeny pro kód smazání (ClearCode) a kód pro konec informace (CodeEndOfInformation). V uvažované verzi algoritmu je použit 12bitový kód a podle toho hodnoty ​pro kódy řádků zbývá od 258 do 4095. Přidané řádky se do tabulky zapisují postupně, přičemž index řádku v tabulce se stává jejím kódem.

Funkce ReadNextByte() čte znak ze souboru. Funkce WriteCode() zapíše kód (velikost se nerovná bajtu) do výstupního souboru. Funkce AddStringToTable() přidá nový řádek do tabulky a přiřadit k ní kód. Tato funkce navíc řeší situaci přetečení tabulky. V tomto případě jsou kód předchozího nalezeného řádku a kód čištění zapsány do proudu, načež je tabulka vymazána funkcí InitTable(). Funkce CodeForString() najde řetězec v tabulce a vrátí kód pro tento řetězec.

Příklad:

Zkomprimujme sekvenci 45, 55, 55, 151, 55, 55, 55. Poté, podle výše popsaného algoritmu, nejprve umístíme kód čištění do výstupního proudu<256>, pak k původně prázdnému řetězci přidejte „45“ a zkontrolujte, zda je v tabulce řetězec „45“. Jelikož jsme při inicializaci zadali do tabulky všechny řádky jednoho znaku, je v tabulce řetězec „45“. Dále načteme další znak 55 ze vstupního proudu a zkontrolujeme, zda je v tabulce řetězec „45, 55“. V tabulce zatím žádný takový řádek není. Do tabulky zadáme řetězec „45, 55“ (s prvním volným kódem 258) a zapíšeme kód do streamu<45>. Archivaci si můžete stručně představit takto:

• "45" - je v tabulce;
• "45, 55" - ne. Přidat do tabulky<258>"45, 55". Chcete-li streamovat:<45>;
• "55, 55" - ne. Ke stolu:<259>"55, 55". Chcete-li streamovat:<55>;
• „55, 151“ – ne. Ke stolu:<260>"55, 151". Chcete-li streamovat:<55>;
• „151, 55“ – ne. Ke stolu:<261>"151, 55". Chcete-li streamovat:<151>;
• „55, 55“ - je v tabulce;
• „55, 55, 55“ – ne. Ke stolu: „55, 55, 55“<262>. Chcete-li streamovat:<259>;

Zvláštností LZW je, že pro dekompresi nepotřebujeme ukládat tabulku řetězců do souboru pro dekompresi. Algoritmus je postaven tak, že jsme schopni obnovit tabulku řetězců pouze pomocí proudu kódu.

Víme, že pro každý kód musíme přidat do tabulky řádek, který se skládá z řádku, který se tam již nachází, a znaku, kterým začíná další řádek v proudu.

Dekompresní algoritmus, který provádí tuto operaci, je následující:

code=File.ReadCode();
while(code != CodeEndOfInformation)(
if(code = ClearCode) (
InitTable();
code=File.ReadCode();
if(code = CodeEndOfInformation)
(dokončit práci);
ImageFile.WriteString(StrFromTable(kód));
starý_kód=kód;
}
jiný(
if(InTable(code)) (
ImageFile.WriteString(FromTable(code));
AddStringToTable(StrFromTable(starý_kód)+
FirstChar(StrFromTable(kód)));
starý_kód=kód;
}
jiný(
OutString= StrFromTable(starý_kód)+
FirstChar(StrFromTable(starý_kód));
ImageFile.WriteString(OutString);
AddStringToTable(OutString);
starý_kód=kód;
}
}
}

Zde funkce ReadCode() načte další kód z dekomprimovaného souboru. Funkce InitTable() provádí stejné akce jako při kompresi, tzn. vymaže tabulku a vloží do ní všechny řádky jednoho znaku. Funkce FirstChar() nám poskytuje první znak řetězce. Funkce StrFromTable() vrací řádek z tabulky podle kódu. Funkce AddStringToTable() přidá do tabulky nový řádek (přiřazením prvního volného kódu). Funkce WriteString() zapíše řetězec do souboru.

Poznámka 1. Jak vidíte, kódy zapisované do streamu postupně přibývají. Dokud se v tabulce poprvé neobjeví například kód 512, budou všechny kódy menší než 512. Navíc se při kompresi a dekompresi přidávají kódy v tabulce při zpracování stejného symbolu, tzn. děje se to „synchronně“. Tuto vlastnost algoritmu můžeme využít ke zvýšení kompresního poměru. Dokud nebude do tabulky přidán znak 512, budeme do výstupního bitového toku zapisovat kódy 9 bitů a hned při přidání 512 kódy 10 bitů. V souladu s tím bude muset dekompresor také přijmout všechny kódy vstupního toku jako 9bitové, dokud nebude kód 512 přidán do tabulky, načež bude všechny vstupní kódy vnímat jako 10bitové. Totéž uděláme při přidávání kódů 1024 a 2048 do tabulky. Tato technika umožňuje zvýšit kompresní poměr asi o 15 %:

Poznámka 2. Při komprimaci obrázku je pro nás důležité zajistit rychlost vyhledávání řádků v tabulce. Můžeme využít toho, že každý další podřetězec je o jeden znak delší než předchozí, navíc předchozí řádek jsme již našli v tabulce. Stačí tedy vytvořit seznam odkazů na řetězce začínající daným podřetězcem a celý proces hledání v tabulce se zredukuje na hledání v řetězcích obsažených v seznamu na předchozí řetězec. Je jasné, že taková operace může být provedena velmi rychle.

Všimněte si také, že ve skutečnosti nám stačí uložit do tabulky jen pár<код предыдущей подстроки, добавленный символ>. Tyto informace jsou dostačující pro to, aby algoritmus fungoval. Tedy pole od 0 do 4095 s prvky<код предыдущей подстроки; добавленный символ; список ссылок на строки, начинающиеся с этой строки>řeší problém hledání, i když velmi pomalu.

V praxi se k uložení tabulky používá hashovací tabulka, stejně rychlá jako v případě seznamů, ale kompaktnější v paměti. Stůl se skládá z 8192 (2 13) prvků. Každý prvek obsahuje<код предыдущей подстроки; добавленный символ; код этой строки>. 20bitový vyhledávací klíč je tvořen pomocí prvních dvou prvků uložených v tabulce jako jediné číslo (klíč). Spodních 12 bitů tohoto čísla je dáno pro kód a dalších 8 bitů pro hodnotu symbolu.

Zde se používá jako hashovací funkce:

Index(klíč)= ((klíč >> 12) ^ klíč) & 8191;

Kde >> - bitový posun doprava (klávesa >> 12 - získáme hodnotu znaku), ^ - logická operace bitový XOR a logický bitový AND.

Pro spočítaný počet porovnání tedy dostaneme požadovaný kód nebo zprávu, že v tabulce žádný takový kód není.

Pojďme vypočítat nejlepší a nejhorší kompresní poměry pro tento algoritmus. Nejlepší koeficient samozřejmě získáme pro řetězec identických bytů velké délky (tj. pro 8bitový obrázek, jehož všechny body mají pro jistotu barvu 0). Zároveň do řádku 258 tabulky zapíšeme řetězec „0, 0“, do řádku 259 - „0, 0, 0“, ... do řádku 4095 - řetězec 3839 (=4095-256 ) nuly. V tomto případě se do streamu dostane 3840 kódů (zkontrolujte podle algoritmu!) , včetně čistícího kódu. Výpočtem součtu aritmetické progrese od 2 do 3839 (tj. délky komprimovaného řetězce) a jeho vydělením 3840*12/8 (12bitové kódy se zapisují do streamu) tedy získáme nejlepší kompresní poměr .

Cvičení: Vypočítejte přesnou hodnotu nejlepšího kompresního poměru. Obtížnější úkol: vypočítat stejný koeficient s přihlédnutím k poznámce 1.

Cvičení: Napište algoritmus pro generování takových řetězců. Zkuste takto získaný soubor zkomprimovat standardními archivátory (zip, arj, gz). Pokud dostanete kompresi, pak je algoritmus generování napsán nesprávně.

LZW implementováno v formáty GIF a TIFF.

Charakteristika algoritmu LZW:

Kompresní poměry: Přibližně 1000, 4, 5/7 (nejlepší, průměr, nejhorší poměry). Komprese 1000krát je dosaženo pouze u jednobarevných obrázků, které jsou násobkem asi 7 MB.

Třída obrázku: LZW se zaměřuje na 8bitové obrázky vytvořené v počítači. Komprimuje se kvůli stejným podřetězcům ve streamu.

Symetrie: Téměř symetrické, za předpokladu optimální implementace operace vyhledávání řádků v tabulce.

Vlastnosti: Situace, kdy algoritmus zvětší obraz, je extrémně vzácná. LZW je univerzální – právě jeho varianty se používají v běžných archivátorech.

Klasický Huffmanův algoritmus

Jeden z klasických algoritmů známých již od 60. let. Používá pouze frekvenci výskytu identických bajtů v obrázku. Odpovídá znakům ve vstupním proudu, které se vyskytují více krát, řetězec bitů menší délky. A naopak vzácný - řetěz větší délky. Pro sběr statistik vyžaduje dva průchody přes obrázek.

Nejprve si uveďme některé definice.

Definice. Nechť abecedu Y =( A 1, ..., ř ) skládající se z konečného počtu písmen. Konečná posloupnost znaků z Y

zavoláme slovo v abecedě Y a číslo n - délka slova A. Délka slova je označena jako Los Angeles).

Nechť je dána abeceda W, W =( b 1 , ..., nar q ). Přes B označte slovo v abecedě W a skrz S (W)je množina všech neprázdných slov v abecedě W .

Nechat S =S(Y) -množina všech neprázdných slov v abecedě Y a S"- nějaká podmnožina množiny S. Nechte také mapování F, které každé slovo A, A? S(Y), odpovídá slovu

B=F(A), B ? J(W) .

Slovo V zavoláme kód zprávy A, a přechod od slova A na jeho kód - kódování.

Definice. Zvažte shodu mezi písmeny abecedy Y a některými slovy abecedy W:

A 1 - B 1 ,
A 2 - B 2 ,
. . .
A r- B r

Tato korespondence se nazývá systém a označeno S. Definuje kódování následovně: každé slovo od S" (W)=S (W)se shoduje se slovem tzv slovní kód A. Slova B 1 ... B r volal elementární kódy. Tenhle typ se nazývá kódování abecední kódování.

Definice. Nechte slovo V má formu

B=B"B"

Potom slovo B" volal Start nebo předpona slova B, a B" - konec slova B. V tomto případě prázdné slovo L a slovo samotné B jsou považovány za začátek a konec slova B .

Definice . S schéma má vlastnost prefix, pokud pro nějakéi A j(1? i , j? r, já? j) slovo B inení předpona slova B j

Věta 1. Pokud schéma S má vlastnost prefix, pak bude abecední kódování jedna ku jedné.

Předpokládejme, že máme abecedu Y =( A 1 ,..., A r} (r >1 ) a soubor pravděpodobností p 1 , . . . , p r vzhled postav A 1 ,..., A r. Nechť je dále uvedena abeceda W, W =( b 1 , ..., b q} (q >1 ). Pak je možné sestrojit celou řadu schémat S abecedního kódování

1 - B 1 ,
. . .
A r- B r

mající vlastnost vzájemné jedinečnosti.

Pro každý okruh můžete zadat průměrnou délku l St , definované jako matematické očekávání délky elementárního kódu:

- délky slov.

Délka l St ukazuje, kolikrát se průměrná délka slova zvětší při kódování se schématem S .

Dá se to ukázat l St dosáhne svého minima l * na některých S a je definován jako

Definice . Kódy definované schématem S sl cf = l * , jsou nazývány kódy s minimální redundancí nebo Huffmanovy kódy.

Kódy s minimální redundancí poskytují v průměru minimální nárůst délek slov při vhodném kódování.

V našem případě abeceda Y =( A 1 ,..., A r) určuje symboly vstupního proudu a abecedu W =(0,1), tzn. skládá se pouze z nuly a jedničky.

Algoritmus pro konstrukci obvodu S může být reprezentován následovně:

Krok 1. Uspořádáme všechna písmena vstupní abecedy v sestupném pořadí pravděpodobnosti. Počítání všech odpovídajících slov B iz abecedy W =(0,1) jsou prázdné.

Krok 2 Spojení dvou postav a i r-1 A a i rnejméně pravděpodobné pí r-1 A pí rna pseudo postavu A"{a i r-1 a i r ) s pravděpodobností pí r-1+pí r. Přidejte 0 na začátek slova B i r-1(B i r-1=0B i r-1 ) a 1 na začátek slova B i r(B i r= 1B i r).

Krok 3 Odebrání ze seznamu uspořádaných znaků a i r-1 A a i r, vložte tam pseudosymbol A"{a i r-1 a i r ). Provedeme krok 2 a v případě potřeby přidáme 1 nebo nulu pro všechna slova B i, odpovídající pseudoznakům, dokud v seznamu nezůstane 1 pseudoznak.

Příklad:Řekněme, že máme 4 písmena v abecedě Y =( A 1 ,..., A 4 } (r =4 ), p 1 =0.5, p 2 =0.24,p 3 =0.15,p 4 =0,11. Potom lze proces konstrukce obvodu znázornit takto:

Provedením akcí odpovídajících 2. kroku získáme pseudoznak s pravděpodobností 0,26 (a odpovídajícím slovům přiřadíme 0 a 1). Opakováním těchto akcí pro upravený seznam dostaneme pseudosymbol s pravděpodobností 0,5. A nakonec v posledním kroku dostaneme celkovou pravděpodobnost 1.

Abychom obnovili kódovací slova, musíme sledovat šipky od počátečních znaků až po konec výsledného binárního stromu. Tedy pro symbol s pravděpodobností p 4, dostaneme B4 =101, pro p 3 dostaneme B 3 =100, pro p 2 dostaneme B 2 =11, pro p 1 dostaneme B1 =0. Co znamená schéma: A 1 - 0,
A 2 - 11
A 3 - 100
A 4 - 101 Toto schéma je předponový kód, který je Huffmanovým kódem. Nejčastěji se vyskytující postava v proudu A 1 zakódujeme nejkratší slovo 0 a nejméně časté A 4 dlouhé slovo 101.

Pro sekvenci 100 znaků, ve které je znak A 1 se sejde 50krát, symbol A 2 - 24krát, symbol A 3 - 15krát a symbol A 4 - 11krát vám tento kód umožní získat sekvenci 176 bitů ( ). Tito. v průměru utratíme 1,76 bitů na symbol proudu.

Důkazy teorému, stejně jako skutečnost, že sestrojený obvod ve skutečnosti definuje Huffmanův kód, viz .

Jak bylo zřejmé z výše uvedeného, ​​klasický Huffmanův algoritmus vyžaduje zapsání tabulky shody kódovaných znaků a kódovacích řetězců do souboru.

V praxi se používají jeho odrůdy. V některých případech je tedy rozumné buď použít konstantní tabulku, nebo ji sestavit „adaptivní“, tzn. v procesu archivace/unarchivace. Tyto triky nám ušetří dva přejezdy přes obrázek a nutnost ukládat tabulku spolu se souborem. Pevné kódování tabulek se používá jako poslední krok při archivaci JPEG a v algoritmu CCITT Group 3 popsaném níže.

Charakteristika klasického Huffmanova algoritmu:

Kompresní poměry: 8, 1,5, 1 (nejlepší, průměr, nejhorší kurz).

Třída obrázku: Téměř nikdy neaplikováno na čisté obrázky. Obvykle se používá jako jeden z kompresních kroků ve složitějších obvodech.

Symetrie: 2 (vzhledem k tomu, že vyžaduje dva průchody polem komprimovaných dat).

Vlastnosti: Jediný algoritmus, který v nejhorším případě nezvětší velikost původních dat (kromě nutnosti uložit vyhledávací tabulku spolu se souborem).

Obdobná modifikace algoritmu se používá při kompresi černobílých obrázků (jeden bit na pixel). Celý název tohoto algoritmu je CCITT Group 3. To znamená, že tento algoritmus navrhla třetí normalizační skupina Mezinárodního poradního výboru pro telegrafii a telefonii (Consultative Committee International Telegraph and Telephone). Posloupnosti po sobě jdoucích černých a bílých teček v něm jsou nahrazeny číslem rovným jejich počtu. A tato řada je zase komprimována podle Huffmana s pevným stolem.

Definice: Nazývá se sada po sobě jdoucích obrazových bodů stejné barvy série.Délka této množiny bodů se nazývá délka série.

Níže uvedená tabulka definuje dva typy kódů:

• Kódy dokončení série- nastavit od 0 do 63 v krocích po 1.
• Složené (doplňkové) kódy- jsou nastaveny od 64 do 2560 v krocích po 64.

V praxi v těch případech, kdy obrázku dominuje černá, obrázek před kompresí invertujeme a informaci o tom zapíšeme do hlavičky souboru.

Algoritmus komprese vypadá takto:

pro (na všech řádcích obrázku) (
Převeďte řetězec na sadu délek běhu;
pro (ve všech sériích) (
if (série bílá) (
L= délka série;
while(L > 2623) ( // 2623=2560+63
L=L-2560;
WriteWhiteCodeFor(2560);
}
if(L > 63) (
L2=MaximumConstCodeLessL(L);
L=L-L2;
WriteWhiteCodeFor(L2);
}
WriteWhiteCodeFor(L);
//Toto je vždy výstupní kód
}
jiný(
[Kód podobný bílé řadě,
s tím rozdílem, že jsou psané
černé kódy]
}
}
// Konec řádku obrázku
}

Vzhledem k tomu, že se černá a bílá řada střídají, bude kód pro bílou řadu a kód pro černou řadu skutečně fungovat střídavě.

V termínech regulární výrazy dostaneme pro každý řádek našeho obrázku (dostatečně dlouhý, začínající bílou tečkou) výstupní bitový proud formuláře:

((<Б-2560>)*[<Б-сст.>]<Б-зв.>(<Ч-2560>)*[<Ч-сст.>]<Ч-зв.>) +

[(<Б-2560>)*[<Б-сст.>]<Б-зв.>]

Kde ()* - opakovat 0 nebo vícekrát, () + .- opakovat 1 nebo vícekrát, - zahrnovat 1 nebo 0krát.

Pro výše uvedený příklad: 0, 3, 556, 10... algoritmus vygeneruje následující kód:<Б-0><Ч-3><Б-512><Б-44><Ч-10>, nebo podle tabulky 00110101 10 0110010100101101 0000100 (různé kódy ve vláknu jsou pro usnadnění zvýrazněny). Tento kód má vlastnost prefixových kódů a lze jej snadno složit zpět do sekvence délek běhu. Je snadné spočítat, že pro daný řetězec 569 bitů jsme dostali kód 33 bitů, tzn. kompresní poměr je asi 17krát.

Otázka: Kolikrát se zvětší velikost souboru v nejhorším případě? Proč? (Odpověď uvedená ve specifikacích algoritmu není úplná, protože mohou existovat vyšší hodnoty nejhoršího kompresního poměru. Najděte je.)

Cvičení: Daný řetězec obrázku zapsaný jako délky běhu - 442, 2, 56, 3, 23, 3, 104, 1, 94, 1, 231, 120 bajtů o velikosti ((442+2+..+231)/8). Vypočítejte kompresní poměr tohoto řetězce pomocí algoritmu CCITT Group 3.

Tabulka kódů dokončení:

Tabulka složených kódů:

Tento algoritmus je implementován ve formátu TIFF.

Charakteristika algoritmu Skupina CCITT 3

Typický obraz z digitálního fotoaparátu má rozlišení asi 3000x2000, tzn. asi 6 megapixelů; K reprezentaci barev se obvykle používá 24 bitů na pixel. Množství počátečních dat je tedy asi 17 megabajtů. U profesionálních obrazových vstupních zařízení může být velikost výsledné bitmapy mnohem větší a barevná hloubka může být až 48 bitů na pixel ("Moderní bitmapový grafický hardware"). Podle toho může být velikost jednoho obrázku více než 200 megabajtů. Proto jsou algoritmy velmi důležité. komprese obrázky, nebo jinými slovy, algoritmy, které umožňují snížit množství dat představujících obrázek.

Existují dvě hlavní třídy algoritmů:

1. A se nazývá algoritmus bezeztrátovou kompresi(angl. bezeztrátová komprese ), pokud existuje algoritmus A -1 (inverzní k A ) takový, že pro jakýkoli obrázek I A (I) = I 1 a A -1 (I 1) = I . Obrázek I je definován jako soubor hodnot atributů pixelů; po aplikaci algoritmu A na I dostaneme datovou sadu I 1 . Používá se bezeztrátová komprese grafických formátů obrazové reprezentace jako: GIF, PCX, PNG, TGA, TIFF 1 Obecně řečeno, daný formát podporuje také ztrátovou kompresi., hromada vlastní formáty od výrobců digitálních fotoaparátů atd.);
2. A se nazývá algoritmus ztrátová komprese(angl. ztrátová komprese), pokud neposkytuje možnost přesné obnovy původního obrazu. Algoritmus spárovaný s A, který poskytuje přibližnou obnovu, bude označen jako A * : pro obraz I A(I) = I 1 , A * (I 1) = I 2 a výsledný obnovený obraz I 2 se nemusí nutně přesně shodovat s I . Dvojice A, A * je zvolena tak, aby poskytovala vysoké kompresní poměry a přitom zachovala vizuální kvalitu, tzn. dosáhnout minimálního rozdílu ve vnímání mezi I a I 2 . Ztrátová komprese se používá v následujících grafických formátech: JPEG, JPEG2000 atd.

Tato přednáška je o bezeztrátové kompresi, která je vyžadována v případech, kdy byly informace získány za vysoké náklady (například lékařské snímky nebo satelitní snímky), nebo v jiných případech, kdy i sebemenší zkreslení nežádoucí.

13.2. Neexistence ideálního algoritmu

Jak již bylo zmíněno v předchozím odstavci, obrázek I je považován za množinu (sekvenci) hodnot atributů pixelů. Dále v této přednášce všechny algoritmy a tvrzení platí jak pro obrázky, tak pro libovolné posloupnosti, jejichž prvky mohou nabývat konečného počtu hodnot.

Vyjádření 13.2.1. Neexistuje žádný algoritmus, který by dokázal bezeztrátově komprimovat jakýkoli soubor dat.

Existuje 2 N sekvencí o velikosti N bitů (za minimální informační nosič budeme považovat bit). Nechť existuje algoritmus A takový, že , kde |I| - objem dat (délka sekvence). Nechť M = max M k, pak M< N . Существует 2 1 + 2 2 + ... + 2 M последовательностей длины, меньшей или равной M . Но 21+2 2 +...+2 M = 2 M+1-2< 2 N . Rozpor.

Z konstatování vyplývá, že má smysl vyvíjet algoritmy, které by efektivně komprimovaly určitou třídu obrázků; zároveň pro tyto algoritmy vždy budou existovat obrázky, pro které nebudou poskytovat kompresi.

13.3. Algoritmy kódování délky opakování (RLE).

Tento typ algoritmů (algoritmy kódování délky opakování 2 V literatuře se často vyskytuje i jiný název – skupinové kódování.(RLE 3 Angličtina Kódování délky běhu)) je založen na nejjednodušším principu: opakující se skupiny prvků původní posloupnosti nahradíme dvojicí (veličina, prvek), nebo pouze kvantitou.

RLE - bitová úroveň

Původní data budeme uvažovat na úrovni posloupnosti bitů; například reprezentovat černobílý obrázek. Obvykle je několik 0 nebo 1 v řadě a zapamatujete si pouze počet stejných číslic v řadě. Tito. sekvence 0000 11111 000 11111111111 odpovídá množině čísel počtu opakování 4 5 3 11 . Vzniká následující nuance: čísla udávající počet opakování musí být také zakódována v bitech. Můžeme předpokládat, že každý počet opakování se mění od 0 do 7 (tj. může být zakódován právě třemi bity), sekvence 11111111111 pak mohou být spojeny s čísly 7 0 4, tzn. 7 jedniček, 0 nul, 4 jedničky. Například sekvence skládající se z 21 jedniček, 21 nul, 3 jedniček a 7 nul je zakódována takto: 111 000 111 000 111 111 000 111 000 111 011 111 , tj. z původní sekvence, která má délku 51 bitů, byla získána sekvence 36 bitů.

Myšlenka této metody se používá při odesílání faxů.

RLE - úroveň bajtů

Předpokládejme, že vstupem je obrázek ve stupních šedi, kde je k hodnotě intenzity pixelu přiřazen 1 bajt. Je jasné, že oproti černobílému rastru se výrazně snižuje očekávání dlouhého řetězce identických bitů.

Vstupní proud rozdělíme na bajty (písmena) a opakovaná písmena zakódujeme jako pár (číslo, písmeno).

Tito. AABBBCDAA kóduje (2A) (3B) (1C) (1D) (2A) . Mohou však existovat dlouhé úseky dat, kde se nic neopakuje a každé písmeno kódujeme jako pár (číslo, písmeno).

Řekněme, že máme pevné číslo (písmeno) M (od 0 do 255). Pak lze zakódovat jedno písmeno samo o sobě, - výstup = S , a pokud je několik písmen nebo , pak výstup = CS , kde C > M a C - M je počet po sobě jdoucích písmen S . Uvádíme například pouze dekódovací algoritmus.

// M - pevná hranice // čtení znaků postupně ze vstupního proudu // in - vstup - komprimovaná sekvence // out - výstup - dekomprimovaná sekvence while(in.Read(c)) ( if(c > M) ( // čítač případů n = c - M;in.Čtení(c);for(i = 0;i< n; i++) out.Write(c); } else // случай просто символа out.Write(c); } Výpis 13.1. Algoritmus dekódování RLE - Úroveň bajtů

Číslo M je obvykle 127. Častěji se používá modifikace tohoto algoritmu, kde znakem čítače je přítomnost jedniček ve 2 nejvýznamnějších bitech čteného znaku. Zbývajících 6 bitů je hodnota čítače.

Tato modifikace tohoto algoritmu je použita ve formátu PCX. Úpravy tohoto algoritmu se však samy o sobě používají jen zřídka, protože podtřída sekvencí, na kterých je tento algoritmus účinný, je relativně úzká. Modifikace algoritmu se používají jako jedna z fází kompresního potrubí (například v JPEG,

První verze algoritmu

Tento algoritmus je extrémně snadno implementovatelný. Run Length Encoding (RLE) je jedním z nejstarších a nejjednodušších algoritmů archivace grafiky. Obraz v něm (jako v několika algoritmech popsaných níže) je vtažen do bajtového řetězce podél čar rastru. K samotné kompresi v RLE dochází kvůli tomu, že v původním obrázku jsou řetězce identických bajtů. Nahraďte je páry<счетчик повторений, значение>snižuje redundanci dat.

Algoritmus dekomprese vypadá to takto:

inicializace(...); dělat(

byte= ImageFile.ReadNextByte(); if(is counter(byte)) ( counter = Low6bits(byte)+1; value = ImageFile.ReadNextByte(); for(i=l to counter)

DecompressedFile.WriteByte(value))

DecompressedFile.WriteByte(byte)) while (UmageFile.EOF ()) ;

V tomto algoritmu jsou znaménka čítače (čítače) ty v horních dvou bitech čteného souboru:

V souladu s tím je zbývajících 6 bitů vynaloženo na čítač, který může nabývat hodnot od 1 do 64. Řetězec 64 opakovaných bytů převedeme na 2 byty, to znamená, že jej zkomprimujeme 32krát.

Cvičení. Vytvořte algoritmus komprese pro první verzi algoritmu RLE.

Algoritmus je určen pro obchodní grafiku - obrázky s velkými plochami opakujících se barev. Situace, kdy soubor roste, není pro tento jednoduchý algoritmus tak vzácná. Lze jej snadno získat aplikací dávkového kódování na zpracované barevné fotografie. Aby se obrázek zvětšil 2krát, musí být aplikován na obrázek, ve kterém jsou hodnoty všech pixelů větší než binární 11000000 a neopakují se ve dvojicích za sebou.

Cvičení. Navrhněte 2–3 příklady „špatných“ obrázků pro algoritmus RLE. Vysvětlete, proč velikost komprimovaný soubor větší než původní soubor.

Tento algoritmus je implementován ve formátu PCX. Viz příklad v příloze 2.

Druhá verze algoritmu

Druhá varianta tohoto algoritmu má vyšší maximální kompresní poměr a snižuje velikost původního souboru. Dekompresní algoritmus pro to vypadá takto:

inicializace(...); dělat(

byte = ImageFile.ReadNextByte(); čítač = Low7bits(byte)+1; if(if repeat flag(byte)) ( value = ImageFile.ReadNextByte(); for (i=l to counter)

CompressedFile.WriteByte(hodnota)

for(i"=l na pult) (

value = ImageFile.ReadNextByte(); CompressedFile.WriteByte(hodnota) } ) while (!ImageFile.EOFO) ;

Znakem opakování v tomto algoritmu je jednotka vyššího řádu odpovídajícího bajtu:

j 0 7 bit___ I Co přeskočit I ... Co přeskočit I

^1 7 bit I Co opakovat I

Jak lze snadno vypočítat, v nejlepším případě tento algoritmus zkomprimuje soubor 64krát (a ne 32krát, jako v předchozí verzi), v nejhorším případě se zvýší o 1/128. Průměrné ukazatele stupně komprese tohoto algoritmu jsou na úrovni ukazatelů první varianty.

(Ech cvičení. Napište kompresní algoritmus pro druhou verzi algoritmu RLE.

Podobná kompresní schémata se používají jako jeden z algoritmů podporovaných formátem TIFF a také formátem TGA.

Vlastnosti algoritmu RLE:

Úrovně komprese: první možnost: 32, 2, 0,5. Druhá možnost: 64, 3, I 128/129. (Nejlepší, průměrný, nejhorší stupeň).

Třída obrázku: algoritmus je zaměřen na obrazy s non-I velké množství barvy: obchodní a vědecká grafika.

Symetrie: přibližně jeden.

Vlastnosti: Pozitivní aspekty algoritmu lze možná připsat pouze skutečnosti, že nevyžaduje další paměť \ při archivaci a rozbalování a také funguje rychle. Zajímavý speciál! Zvláštností skupinového kódování je, že míra archivace pro non-! které obrázky lze výrazně vylepšit právě i změnou pořadí barev v paletě obrázků.

Jednoduchá metoda kódování ( KÓDOVÁNÍ DÉLKY BĚHU), který úspěšně používají oblíbené archivátory.

Tato metoda je založena na počítání délky opakujících se znaků v řadě a zápisu do sbaleného souboru namísto sekvence těchto znaků typové informace: počet znaků a samotný opakující se znak. Například existuje řetězec jako " AAAAABBBCCCADDDEEL". Sbalí se do sekvence jako " 5A3B3CADDEEL". Jak je vidět z příkladu, sekvence 5 písmen "A" byla zabalena do dvou znaků "5" a "A" a sekvence "DD", "EE", "L" nebyly zabaleny vůbec , protože nahrazením těchto znaků do sekvence typu "délka" + "písmeno" není žádný zisk.

Při implementaci sbalení souboru pomocí této metody vznikají potíže, například jak bude rozbalovač rozlišovat řídicí informace od sbaleného souboru od rozbalených dat. Například, jako ve výše uvedeném případě, bude rozbalovač rozlišovat řídicí znak „5“ od rozbaleného znaku se stejným kódem? Existují dvě možnosti řešení tohoto problému:

(já). Najděte symbol, který se v komprimovaném souboru vyskytuje méně než ostatní nebo se nevyskytuje vůbec, a použijte jej jako ovládací prvek. V následujícím vysvětlení jej pro usnadnění říkejme předpona. Nyní bude sekvence "AAAAA" baličem převedena na prefix (8 bitů), "A" (8 bitů), kvantitu (8 bitů), tj. 5 bytů bude nahrazeno třemi. Pokud se ve zdrojovém souboru během sbalování objeví bit s kódem prefixu, pak se do výsledného souboru zapíší dva bajty s kódem prefixu a pomocí této funkce unpacker určí, kde je prefix symbol a kde je kontrola. informace. Modifikace této metody jsou možné, např.

1. Kódujte množství ne osmi bity, ale třemi, čtyřmi atd., což zvýší procento balení, ale omezí maximální délka opakující se znaky, které lze sbalit v případě kódování třemi bity (od 3 do 10, tj. 000=3, ..., 111=10), a pokud je délka více než 10 znaků, pak zabalit deset znaků.

2. Je možná druhá modifikace, kdy počet opakovaných znaků není zakódován osmi bity, ale třemi bity a délka opakovaných znaků je omezena na 265. Nabízí se otázka, jak zakódovat 256 různých délek do 3 bitů. Ukazuje se, že je to možné, ale pouze rozsah je od 3 do 9, ale pokud je délka opakovaných znaků větší než 9, pak se "111" zapíše ve třech bitech binární kód, což se rovná "7". To znamená, že skutečná délka sekvence je v následujícím bajtu (8 bitů je přiděleno pro délky od 10 do 256 znaků).

Zde jsou nějaké příklady:

Máme sekvence:

a) "AAAAABBBBBBBBBBCCAAAAAAAAAAAAAAA"

b) "CBBBBBBBBBBEEEEEEEEEEA"

Pojďme je zabalit:

1. Metodou RLE (run-length encoding - pack repeat bytes).

a) Vezměte předponu rovnou "D", dostaneme:
"D", "D", "A", 5, "D", "B", 10, "C", "D", "A", 15.

Procento komprese = 12 bajtů/32 bajtů = 37,5 %

V komprimovaném souboru je bajt předpony prvním bajtem, takže rozbalovač ví, který bajt je předponou.

b) Vezměte prefix rovnající se "A", i když ve skutečnosti to packer neudělá, protože v této sekvenci není mnoho znaků, takže archivátor vezme nepoužitý znak jako prefix.

Zabalená sekvence:
"A", "C", "A", "B", 10, "A", "E", 10, "A", "A"

Procento komprese = 10 bajtů/22 bajtů = 45,5 %

2. Nyní zabalíme stejné řádky podle modifikace 1 metody RLE se stejnými hodnotami prefixů, abychom analyzovali účinnost.

"D", "D", "A", 2, "D", "B", 7,
8 bit 8 bit 8 bit 3 bit 8 bit 8 bit 3 bit

"D", "A", 7, "D", "A", 2
8 bit 8 bit 3 bit 8 bit 8 bit 3 bit

Procento komprese = 84 bitů/(22*8) bitů = 32,8 %

„A“, „C“, „A“, „B“, 7, „A“, „E“, 7, „A“, „A“
8 bit 8 bit 8 bit 8 bit 4 bit 8 bit 8 bit 3 bit 8 bit 8 bit

Procento komprese = 70 bitů/(22*8) bitů = 39,8 %

3. Nyní zkontrolujeme účinnost poslední úpravy:

a) Zabalená sekvence:

"D", "D", "A", 2, "D", "B", 7, 0
8 bit 8 bit 8 bit 3 bit 8 bit 8 bit 3 bit 8 bit

"D", "A", 7, 5
8 bit 8 bit 3 bit 8 bit

Procento komprese = 81 bitů/(32*8) bitů = 31,6 %

b) Zabalená sekvence:

"A", "C", "A", "B", 7, 0, "A", "E"
8 bit 8 bit 8 bit 8 bit 3 bit 8 bit 8 bit 8 bit

7, 0, "A", "A"
3 bity 8 bitů 8 bitů 8 bitů

Procento komprese = 86 bitů/(22*8) bitů = 48,9 %

Tyto příklady ukazují, že v závislosti na obsahu komprimovaných dat je efektivní jeden nebo druhý algoritmus, takže abyste mohli vybrat, který algoritmus je efektivnější, musíte je otestovat na různých typech souborů.

(II). Druhá možnost záznamu řídicí informace pro rozbalovač je následující: pokud se v textu vyskytuje jeden znak, pak se jeden řídicí bit rovná jedné a tento znak samotný se zapíše do výstupního souboru. Pokud existuje sekvence opakovaných bajtů, například „AAAAAA“, pak budou sbalené informace vypadat takto: 0 (1 bit), byte A (8 bitů), počet (3-8 bitů);

Pro názornost uveďme příklad. Chcete-li to provést, vezměte sekvence z předchozích příkladů.

1) Počet opakujících se bajtů je zakódován do 8 bitů.

a) 0 , "A" , 5 , 0 , "B" , 10 , 1 , "C" , 1 , "C", 0 , "A", 15
1b. 8b. 8b. 1b. 8b. 8b. 1b. 8b. 1b. 8b. 1b. 8b. 8b.

Procento komprese = 71 bitů/256 bitů = 27,7 %

b) 1 , "C" , 0 , "B" , 10 , 0 , "E" , 10 , 1 , "A"
1b. 8b. 1b. 8b. 8b. 1b. 8b. 8b. 1b. 8b.

Procento komprese = 52 bitů/176 bitů = 29,5 %

2) Nyní vezměme 3 bity pro zakódování počtu opakovaných bajtů, do kterých lze zakódovat hodnoty od 2 do 8 (0 - 6), pokud je délka opakující se sekvence větší, pak tyto tři bity obsahují "111" (7 desetinných míst) a skutečná délka je v dalším bajtu (délka 9 až 264).

a) 0, "A", 3, 0, "B", 7, 1, 0, "C", 0, 0, "A", 7, 6
1b. 8b. 3b. 1b. 8b. 3b. 8b. 1b. 8b. 3b. 1b. 8b. 3b. 8b.

Procento komprese = 64 bitů/256 bitů = 20,3 %

b) 1 , "C" , 0 , "B" , 7 , 1 , 0 , "E" , 7 , 1 , 1, "A"
1b. 8b. 1b. 8b. 3b. 8b. 1b. 8b. 3b. 8b. 1b. 8b.

Procento komprese = 58 bitů / 176 bitů = 33 %

Pokud je množství zakódováno ve 4 bitech (2..16), pak

1 , "C" , 0 , "B" , 8 , 0 , "E" , 8 , 1 , "A"
1b. 8b. 1b. 8b. 4b. 1b. 8b. 4b. 1b. 8b.

Procento komprese = 44 bitů / 176 bitů = 25 %

Jak můžete vidět z příkladů, druhá možnost balení je efektivnější, protože komprimuje sekvence začínající dvěma znaky, kterých je obvykle velká většina. První varianta obsahovala sekvence začínající od tří znaků.