Prednáška číslo 4. Kompresia informácií

Princípy kompresie informácií

Účelom kompresie dát je poskytnúť kompaktnú reprezentáciu dát generovaných zdrojom pre ich ekonomickejšie ukladanie a prenos cez komunikačné kanály.

Povedzme, že máme 1 (jeden) megabajtový súbor. Musíme z toho dostať menší súbor. Nič zložité - spustíme archivátor, napríklad WinZip, a výsledkom je, povedzme, súbor s veľkosťou 600 kB. Kam zmizlo zvyšných 424 kilobajtov?

Kompresia informácií je jedným zo spôsobov, ako ich zakódovať. Vo všeobecnosti sa kódy delia do troch veľkých skupín – kompresné kódy (efektívne kódy), kódy odolné voči hluku a kryptografické kódy. Kódy určené na komprimáciu informácií sú rozdelené na bezstratové kódy a stratové kódy. Bezstratové kódovanie znamená absolútne presné obnovenie dát po dekódovaní a možno ho použiť na kompresiu akýchkoľvek informácií. Stratové kódovanie má zvyčajne oveľa vyšší kompresný pomer ako bezstratové kódovanie, ale umožňuje určité odchýlky dekódovaných údajov od originálu.

Druhy kompresie

Všetky metódy kompresie informácií možno podmienečne rozdeliť do dvoch veľkých neprekrývajúcich sa tried: kompresia s stratu informácií a kompresie bez straty informácie.

Kompresia bez straty informácií.

Nás predovšetkým zaujímajú tieto spôsoby kompresie, pretože sa používajú pri prenose textových dokumentov a programov, pri vydávaní hotových prác zákazníkovi alebo pri vytváraní záložných kópií informácií uložených v počítači.

Kompresné metódy tejto triedy nedokážu pripustiť stratu informácie, preto sú založené len na odstránení jej redundancie a informácie majú redundanciu takmer vždy (pravda, ak ich už niekto predtým nekomprimoval). Ak by neexistovala redundancia, nebolo by čo komprimovať.

Tu je jednoduchý príklad. Ruský jazyk má 33 písmen, desať číslic a asi tucet ďalších interpunkčných znamienok a iných špeciálnych znakov. Za text, ktorý je napísaný len veľkými ruskými písmenami(ako v telegramoch a rádiogramoch) by stačilo šesťdesiat rôznych významov. Každý znak je však zvyčajne zakódovaný ako bajt, ktorý obsahuje 8 bitov a môže predstavovať 256 rôznych kódov. Toto je prvý dôvod prepúšťania. Pre náš „telegrafický“ text by stačilo šesť bitov na znak.

Tu je ďalší príklad. V medzinárodnom kódovaní znakov ASCII na zakódovanie akéhokoľvek znaku je pridelený rovnaký počet bitov (8), pričom každý už dávno a dobre vie, že najčastejšie sa vyskytujúce znaky má zmysel kódovať s menším počtom znakov. Takže napríklad v "Morseovej abecede" sú písmená "E" a "T", ktoré sú spoločné, zakódované jedným znakom (v tomto poradí je to bodka a pomlčka). A také zriedkavé písmená ako "Yu" (- -) a "C" (- -) sú kódované štyrmi znakmi. Neefektívne kódovanie je druhým dôvodom redundancie. Programy, ktoré komprimujú informácie, môžu zadať svoje vlastné kódovanie (odlišné pre rôzne súbory) a priradiť komprimovanému súboru určitú tabuľku (slovník), z ktorej sa dekompresný program dozvie, ako sú v tomto súbore zakódované určité znaky alebo ich skupiny. Algoritmy založené na prekódovaní informácií sa nazývajú Huffmanove algoritmy.

Prítomnosť opakovaných fragmentov je tretím dôvodom nadbytočnosti. V textoch je to zriedkavé, ale v tabuľkách a grafikách je opakovanie kódov bežné. Ak sa teda napríklad číslo 0 opakuje dvadsaťkrát za sebou, potom nemá zmysel vkladať dvadsať nulových bajtov. Namiesto toho dali jednu nulu a koeficient 20. Takéto algoritmy založené na detekcii opakovaní sa nazývajú metódyRLE (Bežať Dĺžka Kódovanie).

Grafické ilustrácie sa vyznačujú najmä veľkými opakujúcimi sa sekvenciami rovnakých bajtov, nie však fotografickými (je tam veľa šumu a susedné body sa výrazne líšia parametrami), ale tými, ktoré umelci kreslia s „hladkou“ farbou, ako v animovaných filmoch.

Stratová kompresia.

Stratová kompresia znamená, že po dekomprimovaní komprimovaného archívu dostaneme dokument, ktorý je v niečom odlišný od toho, ktorý bol na úplnom začiatku. Je jasné, že čím väčší kompresný pomer, tým väčšia strata a naopak.

Samozrejme, takéto algoritmy sú nepoužiteľné pre textové dokumenty, databázové tabuľky a najmä pre programy. Drobné skreslenia v obyčajnom neformátovanom texte sa ešte dajú nejako prežiť, ale skreslenie čo i len jedného bitu v programe ho úplne znefunkční.

Zároveň existujú materiály, v ktorých sa oplatí obetovať niekoľko percent informácií, aby ste získali desaťnásobnú kompresiu. Patria sem fotografické ilustrácie, videozáznamy a hudobné kompozície. Strata informácií počas kompresie a následnej dekompresie v takýchto materiáloch je vnímaná ako vznik nejakého dodatočného „šumu“. Ale keďže pri vytváraní týchto materiálov je stále prítomný určitý „šum“, jeho malý nárast nevyzerá vždy kriticky a nárast veľkosti súborov je obrovský (10-15-krát pre hudbu, 20-30-krát pre fotografie a video materiály) .

Algoritmy stratovej kompresie zahŕňajú také dobre známe algoritmy ako JPEG a MPEG. Algoritmus JPEG sa používa pri kompresii statických obrázkov. Grafické súbory komprimované touto metódou majú príponu JPG. Algoritmy MPEG sa používajú pri kompresii videa a hudby. Tieto súbory môžu mať rôzne prípony v závislosti od konkrétneho programu, no najznámejšie sú .mpg pre video a .mp3 pre hudbu.

Algoritmy stratovej kompresie sa používajú iba pre spotrebiteľské aplikácie. To znamená, že ak sa napríklad prenáša fotografia na prezeranie a hudba na prehrávanie, potom je možné použiť takéto algoritmy. Ak sa prenesú na ďalšie spracovanie, napríklad na úpravu, potom nie je žiadna strata informácií v zdrojovom materiáli neprijateľná.

Tolerovateľné množstvo straty kompresie môže byť zvyčajne kontrolované. To vám umožní experimentovať a dosiahnuť optimálny pomer veľkosť / kvalita. Vo fotografických ilustráciách určených na zobrazenie na obrazovke zvyčajne nie je kritická strata 5 % informácií av niektorých prípadoch možno tolerovať 20 – 25 %.

Bezstratové kompresné algoritmy

Shannon-Fano kód

Pre ďalšie uvažovanie bude vhodné reprezentovať náš zdrojový súbor textom ako zdrojom znakov, ktoré sa v jeho výstupe objavujú jeden po druhom. Dopredu nevieme, ktorý znak bude ďalší, ale vieme, že s pravdepodobnosťou p1 sa objaví písmeno „a“, s pravdepodobnosťou p2 písmeno „b“ atď.

V najjednoduchšom prípade budeme všetky znaky textu považovať za navzájom nezávislé, t.j. pravdepodobnosť výskytu nasledujúceho symbolu nezávisí od hodnoty predchádzajúceho symbolu. Samozrejme, toto nie je prípad zmysluplného textu, ale teraz uvažujeme o veľmi zjednodušenej situácii. V tomto prípade platí tvrdenie „symbol nesie čím viac informácií, tým menšia je pravdepodobnosť jeho výskytu“.

Predstavme si text, ktorého abecedu tvorí iba 16 písmen: A, B, C, D, D, E, F, Z, I, K, L, M, N, O, P, R. Každý z týchto znakov môže byť zakódujte iba so 4 bitmi: od 0000 do 1111. Teraz si predstavte, že pravdepodobnosť výskytu týchto znakov je rozdelená nasledovne:

Súčet týchto pravdepodobností je samozrejme jednota. Rozdeľme tieto symboly do dvoch skupín tak, aby celková pravdepodobnosť symbolov každej skupiny bola ~0,5 (obr.). V našom príklade to budú skupiny znaky A-B a G-R. Kruhy na obrázku, označujúce skupiny symbolov, sa nazývajú vrcholy alebo uzly (uzly) a samotná konštrukcia týchto uzlov je binárny strom (B-strom). Každému uzlu priraďme kód, pričom jeden označíme číslom 0 a druhý číslom 1.

Opäť rozdeľme prvú skupinu (A-B) na dve podskupiny tak, aby ich celkové pravdepodobnosti boli čo najbližšie k sebe. Ku kódu prvej podskupiny pridajme číslo 0 a ku kódu druhej podskupiny číslo 1.

Túto operáciu budeme opakovať dovtedy, kým nezostane len jeden symbol na každom vrchole nášho „stromu“. Kompletný strom pre našu abecedu bude mať 31 uzlov.

Kódy znakov (uzly stromu úplne vpravo) majú kódy nerovnakej dĺžky. Takže písmeno A, ktoré má pre náš imaginárny text pravdepodobnosť p=0,2, je zakódované iba dvoma bitmi a písmeno P (na obrázku nie je znázornené), ktoré má pravdepodobnosť p=0,013, je zakódované šestkou -bitová kombinácia.

Princíp je teda zrejmý - často sa vyskytujúce znaky sú kódované menším počtom bitov, zriedkavo sa vyskytujúce znaky väčším počtom. V dôsledku toho sa priemerný počet bitov na znak bude rovnať

kde ni je počet bitov kódujúcich i-tý znak, pi je pravdepodobnosť výskytu i-tého znaku.

Huffmanov kód.

Huffmanov algoritmus elegantne implementuje všeobecnú myšlienku kódovania entropie pomocou sád prefixov a funguje takto:

1. Všetky znaky abecedy vypíšeme do radu vzostupne alebo zostupne podľa pravdepodobnosti ich výskytu v texte.

2. Dôsledne skombinujte dva symboly s najnižšou pravdepodobnosťou výskytu do nového zloženého symbolu, ktorého pravdepodobnosť výskytu sa považuje za rovnajúcu sa súčtu pravdepodobností jeho základných symbolov. Nakoniec zostrojíme strom, ktorého každý uzol má súčet pravdepodobnosti všetkých uzlov pod ním.

3. Nakreslíme cestu ku každému listu stromu a označíme smer ku každému uzlu (napríklad vpravo - 1, vľavo - 0) . Výsledná sekvencia dáva kódové slovo zodpovedajúce každému znaku (obr.).

Poďme vytvoriť strom kódu pre správu s nasledujúcou abecedou:

Nevýhody metód

Najväčším problémom s kódmi, ako naznačuje predchádzajúca diskusia, je potreba mať tabuľky pravdepodobnosti pre každý typ údajov, ktoré sa majú komprimovať. Toto nie je problém, ak je známe, že anglický alebo ruský text je komprimovaný; kodéru a dekodéru jednoducho poskytneme strom kódov vhodný pre anglický alebo ruský text. Vo všeobecnom prípade, keď je neznáma pravdepodobnosť znakov pre vstupné dáta, statické Huffmanove kódy fungujú neefektívne.

Riešením tohto problému je štatistická analýza zakódovaných údajov vykonaná počas prvého prechodu údajmi a na jej základe zostavenie kódového stromu. V tomto prípade sa skutočné kódovanie vykoná druhým prechodom.

Ďalšou nevýhodou kódov je, že minimálna dĺžka kódového slova pre ne nemôže byť menšia ako jedna, zatiaľ čo entropia správy môže byť 0,1 alebo 0,01 bitov/písmeno. V tomto prípade sa kód stáva v podstate nadbytočným. Problém je vyriešený aplikáciou algoritmu na bloky znakov, ale potom sa procedúra kódovania / dekódovania skomplikuje a výrazne sa rozšíri strom kódu, ktorý sa nakoniec musí uložiť spolu s kódom.

Tieto kódy neberú do úvahy vzťahy medzi znakmi, ktoré sú prítomné takmer v akomkoľvek texte. Napríklad, ak je text na anglický jazyk stretneme sa s písmenom q, potom môžeme s istotou povedať, že po ňom bude nasledovať písmeno u.

Run Length Encoding (RLE) je jedným z najstarších a najjednoduchších archivačných algoritmov. Kompresia v RLE nastáva nahradením reťazcov identických bajtov pármi "počítadlo, hodnota". („červená, červená, ..., červená“ sa píše ako „N červených“).

Jedna z implementácií algoritmu je nasledovná: hľadajú najmenej často sa vyskytujúci bajt, nazývajú ho predponou a nahradia reťazce identických znakov trojitými „predpona, počítadlo, hodnota“. Ak sa tento bajt vyskytuje v zdrojovom súbore raz alebo dvakrát za sebou, potom je nahradený dvojicou „predpona, 1“ alebo „predpona, 2“. Existuje jeden nepoužitý pár „predpona, 0“, ktorý možno použiť ako terminátor pre zbalené dáta.

Pri kódovaní súborov .exe môžete vyhľadávať a zbaliť sekvencie ako AxAyAzAwAt..., ktoré sa často nachádzajú v zdrojoch (reťazce Unicode)

Pozitívne aspekty algoritmu zahŕňajú skutočnosť, že počas prevádzky nevyžaduje dodatočnú pamäť a je rýchlo spustený. Algoritmus je aplikovaný vo formátoch PCX, TIFF, BMP. Zaujímavou vlastnosťou dávkového kódovania v PCX je, že stupeň archivácie niektorých obrázkov možno výrazne zvýšiť jednoduchou zmenou poradia farieb v palete obrázkov.

Kód LZW (Lempel-Ziv & Welch) je dnes jedným z najbežnejších bezstratových kompresných kódov. Pomocou kódu LZW sa kompresia vykonáva v takých grafických formátoch ako TIFF a GIF, pomocou úprav LZW vykonáva svoje funkcie mnoho univerzálnych archivátorov. Činnosť algoritmu je založená na vyhľadávaní opakovaných sekvencií znakov vo vstupnom súbore, ktoré sú kódované kombináciami s dĺžkou 8 až 12 bitov. Tento algoritmus je teda najúčinnejší pri textových súboroch a grafických súboroch, ktoré majú veľké jednofarebné oblasti alebo opakujúce sa sekvencie pixelov.

Nedostatok straty informácií počas kódovania LZW viedol k širokému používaniu formátu TIFF, ktorý je na ňom založený. Tento formát nekladie žiadne obmedzenia na veľkosť a farebnú hĺbku obrazu a je široko používaný napríklad pri tlači. Ďalší formát založený na LZW – GIF – je primitívnejší – umožňuje vám ukladať obrázky s farebnou hĺbkou nie väčšou ako 8 bitov / pixel. Na začiatku súboru GIF je paleta - tabuľka, ktorá stanovuje súlad medzi indexom farieb - číslom v rozsahu od 0 do 255 a skutočnou, 24-bitovou hodnotou farby.

Stratové kompresné algoritmy

Algoritmus JPEG bol vyvinutý skupinou spoločností s názvom Joint Photographic Experts Group. Cieľom projektu bolo vytvoriť vysoko efektívny kompresný štandard pre čiernobiele aj farebné obrázky a tento cieľ sa vývojárom podarilo splniť. V súčasnosti je JPEG široko používaný tam, kde sa vyžaduje vysoký stupeň kompresie – napríklad na internete.

Na rozdiel od algoritmu LZW je kódovanie JPEG stratové. Samotný kódovací algoritmus je založený na veľmi zložitej matematike, ale vo všeobecnosti ho možno opísať takto: obrázok sa rozdelí na štvorce 8 * 8 pixelov a potom sa každý štvorec prevedie na sekvenčný reťazec 64 pixelov. Ďalej je každý takýto reťazec podrobený takzvanej DCT-transformácii, ktorá je jednou z odrôd diskrétnej Fourierovej transformácie. Spočíva v tom, že vstupná sekvencia pixelov môže byť reprezentovaná ako súčet sínusových a kosínusových zložiek s viacerými frekvenciami (tzv. harmonické). V tomto prípade nám stačí poznať amplitúdy týchto komponentov, aby sme s dostatočnou mierou presnosti zrekonštruovali vstupnú sekvenciu. Čím viac harmonických zložiek poznáme, tým menší je nesúlad medzi pôvodným a komprimovaným obrázkom. Väčšina kódovačov JPEG vám umožňuje nastaviť mieru kompresie. To sa dosiahne veľmi jednoduchým spôsobom: čím vyšší je kompresný pomer nastavený, tým menej harmonických bude reprezentovať každý 64-pixelový blok.

Silnou stránkou tohto typu kódovania je samozrejme veľký kompresný pomer pri zachovaní pôvodnej farebnej hĺbky. Práve táto vlastnosť viedla k jeho širokému využívaniu na internete, kde má redukcia veľkosti súborov prvoradý význam, v multimediálnych encyklopédiách, kde je potrebné uložiť čo najviac grafiky v obmedzenom množstve.

Negatívnou vlastnosťou tohto formátu je inherentná degradácia kvality obrazu, ktorú nemožno žiadnym spôsobom eliminovať. Práve tento smutný fakt nedovoľuje jeho využitie v tlači, kde je kvalita na prvom mieste.

Formát JPEG však nie je hranicou dokonalosti v snahe zmenšiť veľkosť výsledného súboru. V poslednej dobe prebieha intenzívny výskum v oblasti takzvanej waveletovej transformácie (alebo burst transform). Na základe najkomplexnejších matematických princípov vám vlnkové kódovače umožňujú získať väčšiu kompresiu ako JPEG s menšou stratou informácií. Napriek zložitosti matematiky waveletovej transformácie je v softvérovej implementácii jednoduchšia ako JPEG. Hoci algoritmy na kompresiu vlniek sú stále k dispozícii počiatočná fáza rozvoj, majú pred sebou veľkú budúcnosť.

fraktálna kompresia

Fraktálna kompresia obrazu je stratový algoritmus kompresie obrazu založený na aplikácii systémov iterovaných funkcií (IFS, zvyčajne afinné transformácie) na obrazy. Tento algoritmus je známy tým, že v niektorých prípadoch umožňuje získať veľmi vysoké kompresné pomery (najlepšie príklady sú až 1000-krát s prijateľnou vizuálnou kvalitou) pre skutočné fotografie prírodných objektov, čo nie je dostupné pre iné algoritmy kompresie obrázkov v princíp. Vzhľadom na zložitú situáciu s patentovaním nebol algoritmus široko používaný.

Archivácia fraktálov je založená na tom, že pomocou koeficientov systému iterovaných funkcií je obraz reprezentovaný v kompaktnejšej podobe. Skôr než sa pozrieme na proces archivácie, pozrime sa, ako IFS vytvára obraz.

Presne povedané, IFS je súbor trojrozmerných afinných transformácií, ktoré transformujú jeden obrázok na druhý. Body v trojrozmernom priestore (súradnica x, súradnica y, jas) podliehajú transformácii.

Základom metódy fraktálneho kódovania je detekcia sebepodobných oblastí v obraze. Možnosť aplikácie teórie iterovaných funkčných systémov (IFS) na problém kompresie obrazu prvýkrát preskúmali Michael Barnsley a Alan Sloan. Svoj nápad si patentovali v rokoch 1990 a 1991. Jacquin predstavil metódu fraktálneho kódovania, ktorá využíva systém doménových a rozsahových subobrazových blokov, štvorcových blokov pokrývajúcich celý obraz. Tento prístup sa stal základom pre väčšinu dnes používaných metód fraktálneho kódovania. Vylepšil ju Yuval Fisher a množstvo ďalších výskumníkov.

V súlade s touto metódou sa obraz rozdelí na množinu neprekrývajúcich sa hodnotových podobrazov (rozsahové podobrazy) a určí sa množina prekrývajúcich sa doménových podobrazov (doménové podobrazy). Pre každý blok poradia kódovací algoritmus nájde najvhodnejší blok domény a afinnú transformáciu, ktorá preloží tento blok domény do daného bloku poradia. Štruktúra obrazu je mapovaná do systému radových blokov, doménových blokov a transformácií.

Myšlienka je takáto: predpokladajme, že pôvodný obrázok je pevným bodom nejakého mapovania kontrakcií. Potom si namiesto samotného obrázku možno toto mapovanie nejakým spôsobom zapamätať a na jeho obnovenie stačí toto mapovanie opakovane aplikovať na ľubovoľný štartovací obrázok.

Podľa Banachovej vety takéto iterácie vždy vedú k pevnému bodu, teda k pôvodnému obrazu. V praxi spočíva celý problém v nájdení najvhodnejšieho kompresného mapovania z obrázka a v jeho kompaktnom uložení. Mapovacie vyhľadávacie algoritmy (t. j. kompresné algoritmy) sú zvyčajne silne hrubou silou a sú výpočtovo nákladné. Algoritmy obnovy sú zároveň pomerne efektívne a rýchle.

Stručne, spôsob navrhnutý Barnsleym možno opísať nasledovne. Obraz je zakódovaný niekoľkými jednoduchými transformáciami (v našom prípade afinnými), to znamená, že je určený koeficientmi týchto transformácií (v našom prípade A, B, C, D, E, F).

Napríklad obraz Kochovej krivky je možné zakódovať štyrmi afinnými transformáciami, jednoznačne ho zadefinujeme len pomocou 24 koeficientov.

Výsledkom je, že bod bude nevyhnutne niekde vo vnútri čiernej oblasti na pôvodnom obrázku. Po vykonaní tejto operácie mnohokrát vyplníme celý čierny priestor, čím obnovíme obraz.

Dva najznámejšie obrázky IFS sú Sierpinského trojuholník a Barnsleyho papraď. Prvá je daná tromi a druhá piatimi afinnými transformáciami (alebo v našej terminológii šošovkami). Každá transformácia je nastavená doslova v bajtoch, pričom obraz zostavený s ich pomocou môže zabrať niekoľko megabajtov.

Je jasné, ako funguje archivátor a prečo to zaberá toľko času. V skutočnosti je fraktálna kompresia hľadaním sebepodobných oblastí v obraze a určovaním parametrov afinných transformácií pre ne.

V najhoršom prípade, ak sa nepoužije optimalizačný algoritmus, bude potrebné spočítať a porovnať všetky možné fragmenty obrazu rôznych veľkostí. Dokonca aj pre malé obrázky, berúc do úvahy diskrétnosť, dostaneme astronomický počet možností, ktoré treba vyriešiť. Ani prudké zúženie transformačných tried, napríklad škálovaním len na určitý počet krát, nám neumožní dosiahnuť prijateľný čas. Navyše sa stráca kvalita obrazu. Prevažná väčšina výskumov v oblasti fraktálnej kompresie je teraz zameraná na skrátenie doby archivácie potrebnej na získanie vysokokvalitného obrazu.

Pre algoritmus fraktálnej kompresie, ako aj pre iné stratové kompresné algoritmy, sú veľmi dôležité mechanizmy, ktorými bude možné riadiť stupeň kompresie a stupeň straty. K dnešnému dňu bol vyvinutý dostatočne veľký súbor takýchto metód. Po prvé, je možné obmedziť počet transformácií zabezpečením toho, aby kompresný pomer nebol nižší ako pevná hodnota. Po druhé, možno požadovať, aby v situácii, keď je rozdiel medzi spracovávaným fragmentom a jeho najlepšou aproximáciou nad určitou prahovou hodnotou, bol tento fragment rozdrvený (na to je potrebných niekoľko šošoviek). Po tretie, je možné zakázať fragmentáciu fragmentov menších ako napríklad štyri body. Zmenou prahových hodnôt a priority týchto podmienok môžete veľmi flexibilne ovládať pomer kompresie obrazu: od bitovej zhody po akýkoľvek stupeň kompresie.

Porovnanie s JPEG

Dnes je najbežnejším algoritmom archivácie grafiky JPEG. Porovnajte to s fraktálnou kompresiou.

Najprv si všimnite, že oba algoritmy pracujú s 8-bitovými (odtiene šedej) a 24-bitovými plnofarebnými obrázkami. Oba sú stratové kompresné algoritmy a poskytujú úzke archivačné pomery. Fraktálny algoritmus aj JPEG majú schopnosť zvýšiť kompresný pomer zvýšením straty. Okrem toho sa oba algoritmy veľmi dobre paralelizujú.

Rozdiely začínajú, keď vezmeme do úvahy čas, ktorý algoritmom trvá archivácia/zrušenie archivácie. Takže fraktálny algoritmus komprimuje stovky a dokonca tisíckrát dlhšie ako JPEG. Naopak, rozbalenie obrázka bude 5-10 krát rýchlejšie. Preto, ak je obrázok komprimovaný iba raz, ale prenášaný cez sieť a dekomprimovaný mnohokrát, potom je výhodnejšie použiť fraktálny algoritmus.

JPEG využíva kosínusový rozklad obrazu, takže strata sa v ňom (aj pri danej minimálnej strate) objavuje vo vlnách a halo na hranici ostrých farebných prechodov. Práve pre tento efekt ho neradi používajú pri kompresii obrázkov, ktoré sú pripravené na kvalitnú tlač: tam sa tento efekt môže stať veľmi viditeľným.

Fraktálny algoritmus nemá tento nedostatok. Okrem toho pri každej tlači obrázka musíte vykonať operáciu zmeny mierky, pretože raster (alebo lineatúra) tlačového zariadenia sa nezhoduje s rastrom obrázka. Pri konverzii môže dôjsť aj k niekoľkým nepríjemným efektom, s ktorými sa dá vysporiadať buď programovým škálovaním obrazu (pri lacných tlačových zariadeniach, akými sú klasické laserové a atramentové tlačiarne), alebo dodaním tlačového zariadenia vlastným procesorom, pevným diskom a súbor programov na spracovanie obrazu (pre drahé fotosádzacie stroje). Ako asi viete, pri použití fraktálneho algoritmu takéto problémy prakticky nevznikajú.

Nahradenie JPEG fraktálovým algoritmom v širokom rozšírení sa tak skoro nestane (aspoň z dôvodu nízkej rýchlosti archivácie druhého), avšak v oblasti multimediálnych aplikácií v r. počítačové hry jeho použitie je opodstatnené.

ARCHIVERS

Kompresia informácií je proces transformácie informácií uložených v súbore znížením redundancie údajov. Účelom tohto procesu je znížiť objem zaberaný dátami.

archívny súbor je špeciálne vytvorený súbor obsahujúci jeden alebo viac komprimovaných súborov.

Pomer kompresie: K c \u003d V c / V o * 100 %

K c je kompresný pomer, Vc– veľkosť komprimovaného súboru, V o je pôvodná veľkosť súboru.

Kompresný pomer závisí od:

1) použitý program - archivátor,

2) metóda kompresie,

3) typ zdrojového súboru: text, grafika, video, zvuk atď.

Programy, ktoré balia a rozbaľujú súbory, sa nazývajú archivátory. Najbežnejšie sú: ARJ, ZIP, RAR. Prípona archívnych súborov zodpovedá názvu archivátora použitého na ich vytvorenie.

Archivátory umožňujú vytvárať samorozbaľovacie archívne súbory, t.j. na ich rozbalenie nie je potrebné spúšťať program archivácie, pretože. samotné obsahujú program na rozbalenie. Tieto archívy sa nazývajú archívy SFX.
(Sebaextrahovanie). Prípona takýchto súborov je *.EXE.

Princípy kompresie informácií

Akýkoľvek text obsahuje opakujúce sa znaky. Je možné určiť jeden znak a počet opakovaní. Účinnosť tohto algoritmu je ešte vyššia v porovnaní s grafickými súbormi. Ak sa pozriete na monitor, môžete vidieť veľa opakujúcich sa bodov rovnakej farby. Formát grafického súboru PCX je založený na tomto princípe kompresie informácií. Moderné archivátory zvýrazňujú nielen opakované znaky, ale aj reťazce znakov, jednotlivé slová.

Ak sa v texte nepoužívajú všetky znaky PC abecedy, potom na ich kódovanie môžete použiť jeden bajt, 8 bitov, menej ako číslo. Tento princíp sa používa v telegrafnom stroji, kde sa používajú iba ruské veľké písmená, na ich znázornenie stačí 5 bitov, čo umožňuje napísať tri znaky do dvoch bajtov.

3. Nasledujúci princíp využíva zákonitosť, že písmená sa v texte vyskytujú s rôznou frekvenciou. Napríklad v tomto texte je najčastejším znakom medzera, veľmi časté sú znaky „a“, „a“. Tieto často sa vyskytujúce znaky môžu byť reprezentované krátkou kombináciou bitov, ostatné znaky môžu byť zakódované dlhšou sekvenciou. Napríklad:

4. Fyzicky PC vyčleňuje miesto na umiestnenie súborov na disku v klastroch - blokoch po 4 kB. Nie je možné vyzdvihnúť menej. Napríklad, ak má súbor veľkosť 8193 bajtov (8 kB a 1 bajt), fyzicky zaberie 16 kB alebo 16 384 bajtov. Spojenie skupiny súborov do jedného vám umožní ušetriť na týchto zvyškoch. Pri balení malých súborov to prináša veľké úspory.

Celkovo sa pri samostatnom umiestnení súborov nevyužíva 6 kB, čo je 100 % obsahu súborov. V druhom prípade zostávajú nevyužité 2 kB, 33 %.

Archivátor zipsov

Balenie súborov pkzip [možnosti]<имя архива>[cesty k súborom]

kľúče: -rp archivácia s podadresármi pri zachovaní štruktúry

S OZP ochrana archívu heslom (PWD)

Pridať súbory do archívu

M presunúť súbory do archívu

V zobraziť obsah archívu

Ak archivujete všetky súbory v adresári, musíte zadať masku *.*

Rozbaľte súbory pkunzip [možnosti]<имя архива>[názvy súborov]

Prepínače: -d rozbalenie s podadresármi so zachovaním štruktúry

Archív hesiel SPWD (PWD)

archivátor arj

arj<команда>[klávesy]<имя архива>[názvy súborov]

V prípade archivátora arj jeden súbor vykonáva operácie rozbaľovania aj balenia.

Tímy: a archivácia

e rozbalenie bez zachovania adresárovej štruktúry

X rozbalenie zachovávajúce štruktúru

l prezeranie obsahu archívu

m presunúť súbory do archívu

d odstrániť súbory z archívu

Prepínače: -r balenie s podadresármi pri zachovaní štruktúry

V rozdelenie archívu na zväzky s objemom zväzku (ak je špecifikovaný)

veľkosť štandardných diskiet (360, 720, 1200, 1440) je uvedená v kilobajtoch, veľkosť neštandardných diskiet je uvedená v bajtoch

V je uvedené pri rozbaľovaní viaczväzkového archívu

G OZP archívne heslo ( OZP)

Balenie súborov

Rozbaľovanie súborov

©2015-2019 stránka
Všetky práva patria ich autorom. Táto stránka si nenárokuje autorstvo, ale poskytuje bezplatné používanie.
Dátum vytvorenia stránky: 8. 8. 2016

GORKOFF 24. februára 2015 o 11:41 hod

Metódy kompresie údajov

Algoritmy

S mojím vedúcim pripravujeme krátku monografiu o spracovaní obrazu. Rozhodol som sa predložiť súdu komunity habra kapitolu o algoritmoch kompresie obrazu. Keďže je ťažké zmestiť celú kapitolu do jedného príspevku, rozhodol som sa to rozdeliť do troch príspevkov:
1. Metódy kompresie údajov;
2. Bezstratová kompresia obrazu;
3. Stratová kompresia obrazu.
Prvý príspevok zo série si môžete prečítať nižšie.

V súčasnosti existuje veľké množstvo bezstratových kompresných algoritmov, ktoré možno podmienečne rozdeliť do dvoch veľkých skupín:
1. Streamové a slovníkové algoritmy. Táto skupina zahŕňa algoritmy rodín RLE (run-length encoding), LZ* atď. Vlastnosťou všetkých algoritmov tejto skupiny je, že kódovanie nevyužíva informácie o frekvencii symbolov v správe, ale informácie o sekvenciách stretli skôr.
2. Algoritmy pre štatistickú (entropickú) kompresiu. Táto skupina algoritmov komprimuje informácie pomocou nerovnomerných frekvencií, s ktorými sa v správe vyskytujú rôzne znaky. Algoritmy tejto skupiny zahŕňajú aritmetické a prefixové kódovacie algoritmy (používajúce Shannon-Fanno, Huffman, secantové stromy).
Algoritmy transformácie informácií možno vyčleniť ako samostatnú skupinu. Algoritmy tejto skupiny informácie priamo nekomprimujú, ale ich aplikácia značne zjednodušuje ďalšiu kompresiu pomocou streamovacích, slovníkových a entropických algoritmov.

Streamové a slovníkové algoritmy

Kódovanie dĺžky chodu

Run-Length Encoding (RLE) je jedným z najjednoduchších a najbežnejších algoritmov kompresie údajov. V tomto algoritme je sekvencia opakovaných znakov nahradená znakom a počtom opakovaní.
Napríklad reťazec "AAAAA", ktorý vyžaduje 5 bajtov na uloženie (za predpokladu, že bajt je pridelený na uloženie jedného znaku), môže byť nahradený reťazcom "5A" pozostávajúcim z dvoch bajtov. Je zrejmé, že tento algoritmus je tým efektívnejší, čím je séria opakovaní dlhšia.

Hlavnou nevýhodou tohto algoritmu je extrémne nízka účinnosť na sekvencie neopakujúcich sa znakov. Napríklad, ak vezmeme do úvahy sekvenciu „ABABAB“ (6 bajtov), potom sa po použití algoritmu RLE zmení na „1A1B1A1B1A1B“ (12 bajtov). Na vyriešenie problému neopakujúcich sa znakov existujú rôzne metódy.

Najjednoduchším spôsobom je nasledujúca úprava: bajt kódujúci počet opakovaní musí uchovávať informácie nielen o počte opakovaní, ale aj o ich prítomnosti. Ak je prvý bit 1, potom ďalších 7 bitov označuje počet opakovaní zodpovedajúceho znaku a ak je prvý bit 0, potom ďalších 7 bitov označuje počet znakov, ktoré sa majú vziať bez opakovania. Ak zakódujeme "ABABAB" pomocou tejto modifikácie, dostaneme "-6ABABAB" (7 bajtov). Je zrejmé, že navrhovaná technika môže výrazne zlepšiť účinnosť algoritmu RLE na neopakujúcich sa sekvenciách znakov. Implementácia navrhovaného prístupu je znázornená v zozname 1:

typu

function RLEEncode(InMsg: ShortString) : TRLEEncodedString;

MatchFl: boolean ;

MatchCount: shortint ;

EncodedString: TRLEEncodedString;

N, i: bajty;

začať

N:=0;

SetLength(EncodedString, 2 * dlzka(InMsg) ) ;

pričom dĺžka (InMsg) >= 1 do

začať

MatchFl : = (dĺžka (InMsg) > 1) a (InMsg[1] = InMsg[2]);

Pocet zhody := 1 ;

zatiaľ čo (MatchCount<= 126 ) and (MatchCount < length(InMsg) ) and ((InMsg[ MatchCount] = InMsg[ MatchCount + 1 ] ) = MatchFl) do

MatchCount: = MatchCount + 1;

ak MatchFl tak

začať

N: = N + 2;

EncodedString[ N - 2 ] : = MatchCount + 128 ;

EncodedString[ N - 1 ] : = ord (InMsg[ 1 ] );

inak

začať

ak MatchCount<>dĺžka (InMsg) potom

MatchCount: = MatchCount - 1;

N:= N + 1 + počet zhôd;

EncodedString[ N - 1 - Počet zhôd] : = - Počet zhôd + 128 ;

for i := 1 to MatchCount urobiť

EncodedString[ N - 1 - MatchCount + i] : = ord (InMsg[ i] ) ;

koniec ;

delete(InMsg, 1, MatchCount) ;

koniec ;

SetLength(EncodedString, N) ;

RLEncode := EncodedString;

koniec ;

Dekódovanie komprimovanej správy je veľmi jednoduché a spočíva v jedinom prechode komprimovanou správou, pozri Výpis 2:

typu

TRLEEncodedString = pole bajtov ;

function RLEDecode(InMsg: TRLEEncodedString) : ShortString;

RepeatCount: shortint ;

i, j: slovo;

OutMsg: ShortString;

začať

OutSg := "" ;

i:=0;

kým< length(InMsg) do

začať

RepeatCount : = InMsg[i] - 128 ;

i: = i + 1;

ak RepeatCount< 0 then

začať

RepeatCount := abs(RepeatCount) ;

pre j : = i až i + RepeatCount - 1 do

OutMsg := OutMsg + chr (InMsg[ j] );

i := i + Počet opakovaní;

inak

začať

for j := 1 to RepeatCount do

OutMsg := OutMsg + chr (InMsg[ i] );

i: = i + 1;

koniec ;

koniec ;

RLEDecode := OutMsg;

koniec ;

Druhým spôsobom zlepšenia efektívnosti algoritmu RLE je použitie algoritmov transformácie informácií, ktoré dáta priamo nekomprimujú, ale konvertujú ich do formy vhodnejšej na kompresiu. Ako príklad takéhoto algoritmu budeme uvažovať o permutácii BWT pomenovanej po vynálezcoch Burrows-Wheelerovej transformácie. Táto permutácia nemení samotné znaky, ale iba mení ich poradie v reťazci, pričom opakujúce sa podreťazce sa po aplikácii permutácie zhromažďujú do hustých skupín, ktoré sú oveľa lepšie komprimované pomocou algoritmu RLE. Priama transformácia BWT pozostáva z nasledujúcich krokov:
1. Pridanie špeciálneho znaku konca riadka do zdrojového reťazca, ktorý sa nikde inde nevyskytuje;
2. Získanie všetkých cyklických permutácií pôvodného reťazca;
3. Triedenie prijatých reťazcov v lexikografickom poradí;
4. Vrátenie posledného stĺpca výslednej matice.
Implementácia tohto algoritmu je znázornená vo výpise 3.

konšt

EOMsg="|" ;

function BWTEncode(InMsg: ShortString) : ShortString;

OutMsg: ShortString;

LastChar: ANSIChar;

N, i: slovo;

začať

InMsg := InMsg + EOMsg;

N := dĺžka (InMsg) ;

ShiftTable[ 1 ] := InMsg;

pre i := 2 až N do

začať

LastChar := InMsg[N] ;

InMsg : = LastChar + copy(InMsg, 1 , N - 1 );

ShiftTable[i] := InMsg;

koniec ;

Zoradiť(ShiftTable) ;

OutSg := "" ;

pre i := 1 až N do

OutMsg : = OutMsg + ShiftTable[ i] [ N] ;

BWTEncode := OutMsg;

koniec ;

Najjednoduchší spôsob, ako vysvetliť túto transformáciu, je na konkrétnom príklade. Zoberme si reťazec "ananás" a dohodneme sa, že symbol "|" bude koniec reťazca. Všetky cyklické permutácie tohto reťazca a výsledok ich lexikografického triedenia sú uvedené v tabuľke. jeden.

Tie. výsledkom priamej konverzie bude reťazec "|NNAAAC". Je ľahké vidieť, že tento reťazec je oveľa lepší ako pôvodný, je komprimovaný algoritmom RLE, pretože obsahuje dlhé podsekvencie opakujúcich sa písmen.
Podobný efekt je možné dosiahnuť aj pomocou iných transformácií, ale výhodou transformácie BWT je, že je reverzibilná, avšak spätná transformácia je zložitejšia ako priama. Ak chcete obnoviť pôvodný reťazec, musíte vykonať nasledujúce kroky:
Vytvorte prázdnu maticu veľkosti n*n, kde n je počet znakov v zakódovanej správe;
Vyplňte prázdny stĺpec úplne vpravo kódovanou správou;
Triediť riadky tabuľky v lexikografickom poradí;
Opakujte kroky 2-3, pokiaľ sú stĺpce prázdne;
Vráti reťazec, ktorý končí znakom konca riadka.

Implementácia inverznej transformácie nie je na prvý pohľad náročná a jedna z implementácií je zobrazená vo výpise 4.

konšt

EOMsg="|" ;

function BWTDecode(InMsg: ShortString) : ShortString;

OutMsg: ShortString;

ShiftTable: pole ShortString;

N, i, j: slovo;

začať

OutSg := "" ;

N := dĺžka (InMsg) ;

SetLength(ShiftTable, N + 1) ;

pre i := 0 až N do

ShiftTable[i] := "" ;

pre i := 1 až N do

začať

pre j := 1 až N do

ShiftTable[ j] : = InMsg[ j] + ShiftTable[ j] ;

Zoradiť(ShiftTable) ;

koniec ;

pre i := 1 až N do

ak ShiftTable[ i] [N] = EOMsg potom

OutMsg := ShiftTable[i] ;

delete(OutMsg, N, 1 ) ;

BWTDecode := OutMsg;

koniec ;

V praxi však účinnosť závisí od zvoleného triediaceho algoritmu. Triviálne algoritmy s kvadratickou zložitosťou budú mať samozrejme extrémne negatívny dopad na výkon, preto sa odporúča používať efektívne algoritmy.

Po zoradení tabuľky získanej v siedmom kroku je potrebné vybrať riadok z tabuľky, ktorý končí symbolom "|". Je ľahké vidieť, že toto je jediný riadok. To. transformáciu BWT sme zvážili na konkrétnom príklade.

Ak to zhrnieme, môžeme povedať, že hlavnou výhodou skupiny algoritmov RLE je jednoduchosť a rýchlosť prevádzky (vrátane rýchlosti dekódovania) a hlavnou nevýhodou je neefektívnosť na neopakujúcich sa znakových sadách. Použitie špeciálnych permutácií zvyšuje efektivitu algoritmu, ale tiež výrazne zvyšuje čas chodu (najmä dekódovanie).

Slovníková kompresia (algoritmy LZ)

Skupina slovníkových algoritmov, na rozdiel od algoritmov skupiny RLE, nekóduje počet opakovaní znakov, ale sekvencie znakov, s ktorými sme sa stretli skôr. Počas prevádzky uvažovaných algoritmov sa dynamicky vytvorí tabuľka so zoznamom už nájdených sekvencií a ich zodpovedajúcich kódov. Táto tabuľka sa často nazýva slovník a zodpovedajúca skupina algoritmov sa nazýva slovník.

Najjednoduchšia verzia slovníkového algoritmu je opísaná nižšie:
Inicializujte slovník so všetkými znakmi nájdenými vo vstupnom reťazci;
Nájdite v slovníku najdlhšiu sekvenciu (S), ktorá zodpovedá začiatku zakódovanej správy;
Vydajte kód nájdenej sekvencie a odstráňte ho zo začiatku kódovanej správy;
Ak sa nedosiahne koniec správy, prečítajte si ďalší znak a pridajte Sc do slovníka, prejdite na krok 2. V opačnom prípade ukončite.

Napríklad novo inicializovaný slovník pre frázu „CUCKOOCOOKOOHOOD“ je zobrazený v tabuľke. 3:

Počas procesu kompresie bude slovník doplnený o sekvencie, ktoré sa vyskytujú v správe. Postup aktualizácie slovníka je uvedený v tabuľke. 4.

Pri popise algoritmu bol zámerne vynechaný popis situácie, kedy je slovník úplne zaplnený. V závislosti od variantu algoritmu je možné rôzne správanie: úplné alebo čiastočné vyčistenie slovníka, ukončenie plnenia slovníka alebo rozšírenie slovníka so zodpovedajúcim zvýšením kapacity kódu. Každý z týchto prístupov má určité nevýhody. Napríklad zastavenie dopĺňania slovníka môže viesť k situácii, keď slovník ukladá sekvencie, ktoré sa vyskytujú na začiatku komprimovaného reťazca, ale neskôr sa už nevyskytujú. Vyčistenie slovníka môže zároveň viesť k odstráneniu častých sekvencií. Väčšina implementácií používaných pri plnení slovníka začína sledovať stupeň kompresie a keď klesne pod určitú úroveň, slovník sa prestaví. Ďalej zvážime najjednoduchšiu implementáciu, ktorá zastaví dopĺňanie slovníka, keď je plný.

Najprv definujeme slovník ako záznam, ktorý ukladá nielen podreťazce, s ktorými sme sa stretli, ale aj počet podreťazcov uložených v slovníku:

Predtým nájdené subsekvencie sú uložené v poli Words a ich kódom sú čísla subsekvencií v tomto poli.
Definujeme tiež vyhľadávanie v slovníku a pridávame do slovníka funkcie:

konšt

MAX_DICT_LENGTH = 256 ;

function FindInDict(D: TDictionary; str: ShortString) : integer ;

r: celé číslo

i: celé číslo;

fl: boolean ;

začať

r = -1;

ak D. WordCount > 0 potom

začať

i := D.Pocet slov ;

fl := nepravda ;

zatiaľ čo (nie fl) a (i >= 0 ) áno

začať

i:= i-1;

fl:=D.Words[i]=str;

koniec ;

koniec ;

ak fl tak

r:=i;

FindInDict := r;

koniec ;

procedure AddToDict(var D: TDictionary; str: ShortString) ;

začať

ak D.Počet slov< MAX_DICT_LENGTH then

začať

D.Pocet slov := D.Pocet slov + 1 ;

SetLength(D. Words , D. WordCount ) ;

D. Slová [ D. Počet slov - 1 ] : = str;

koniec ;

koniec ;

Pomocou týchto funkcií možno proces kódovania podľa opísaného algoritmu implementovať takto:

function LZWEncode(InMsg: ShortString) : TEncodedString;

OutMsg: TEncodedString;

tmpstr: ShortString;

D: TDslovník;

i, N: bajty;

začať

SetLength(OutMsg, length(InMsg) );

N:=0;

InitDict(D) ;

pričom dĺžka (InMsg) > 0 do

začať

tmpstr := InMsg[ 1 ] ;

pričom (FindInDict(D, tmpstr) >= 0 ) a (dĺžka(InMsg) > dĺžka(tmpstr) )

tmpstr : = tmpstr + InMsg[ dĺžka(tmpstr) + 1 ] ;

if FindInDict(D, tmpstr)< 0 then

delete(tmpstr, dlzka(tmpstr) , 1 ) ;

OutMsg[N] := FindInDict(D, tmpstr) ;

N: = N + 1;

delete(InMsg, 1 , length(tmpstr) ) ;

ak dĺžka (InMsg) > 0, potom

AddToDict(D, tmpstr + InMsg[ 1 ] );

koniec ;

SetLength(OutMsg, N) ;

LZWEncode := OutMsg;

koniec ;

Výsledkom kódovania budú počty slov v slovníku.
Proces dekódovania je zredukovaný na priame dekódovanie kódov a nie je potrebné prenášať vytvorený slovník, stačí, aby bol slovník pri dekódovaní inicializovaný rovnako ako pri kódovaní. Potom sa slovník úplne obnoví priamo v procese dekódovania zreťazením predchádzajúcej podsekvencie a aktuálneho znaku.

Jediný problém je možný v nasledujúcej situácii: keď je potrebné dekódovať podsekvenciu, ktorá ešte nie je v slovníku. Je ľahké vidieť, že je to možné iba v prípade, keď je potrebné extrahovať podreťazec, ktorý je potrebné pridať v aktuálnom kroku. A to znamená, že podreťazec vyhovuje vzoru cSc, t.j. začína a končí rovnakým znakom. V tomto prípade je cS podreťazec pridaný v predchádzajúcom kroku. Uvažovaná situácia je jediná, kedy je potrebné dekódovať reťazec, ktorý ešte nebol pridaný. Vzhľadom na vyššie uvedené môžeme ponúknuť nasledujúcu možnosť dekódovania komprimovaného reťazca:

function LZWDecode(InMsg: TEncodedString) : ShortString;

D: TDslovník;

OutMsg, tmpstr: ShortString;

i: byte;

začať

OutSg := "" ;

tmpstr := "" ;

InitDict(D) ;

for i := 0 to length (InMsg) - 1 do

začať

if InMsg[i] >= D.WordCount potom

tmpstr : = D. Slová [ InMsg[ i - 1 ] ] + D. Slová [ InMsg[ i - 1 ] ] [ 1 ]

inak

tmpstr := D. Slová [ InMsg[ i] ] ;

OutSg := OutSg + tmpstr;

ak som > 0, potom

AddToDict(D, D. Slová [ InMsg[ i - 1 ] ] + tmpstr[ 1 ] );

koniec ;

LZWDecode := OutMsg;

koniec ;

Medzi výhody slovníkových algoritmov patrí vyššia účinnosť kompresie v porovnaní s RLE. Malo by sa však chápať, že skutočné použitie týchto algoritmov je spojené s určitými implementačnými ťažkosťami.

Entropické kódovanie

Kódovanie pomocou stromov Shannon-Fano

Algoritmus Shannon-Fano je jedným z prvých vyvinutých kompresných algoritmov. Algoritmus je založený na myšlienke reprezentovať častejšie znaky kratšími kódmi. V tomto prípade majú kódy získané pomocou algoritmu Shannon-Fano vlastnosť prefix: t.j. žiadny kód nie je začiatkom žiadneho iného kódu. Vlastnosť prefix zaisťuje, že kódovanie je jedna k jednej. Algoritmus na zostavenie Shannon-Fano kódov je uvedený nižšie:
1. Rozdeľte abecedu na dve časti, pričom celkové pravdepodobnosti symbolov sú čo najbližšie k sebe.
2. K prefixovému kódu prvej časti symbolov pridajte 0, k prefixovému kódu druhej časti symbolov pridajte 1.
3. Pre každú časť (ktorá má aspoň dva znaky) rekurzívne vykonajte kroky 1-3.
Napriek svojej relatívnej jednoduchosti nie je algoritmus Shannon-Fano bez nedostatkov, z ktorých najvýznamnejšou je neoptimálne kódovanie. Aj keď je rozdelenie v každom kroku optimálne, algoritmus nezaručuje optimálny výsledok ako celok. Zvážte napríklad nasledujúci reťazec: "AAAABVGDEZH". Zodpovedajúci Shannon-Fano strom a z neho odvodené kódy sú znázornené na obr. jeden:

Bez kódovania bude správa trvať 40 bitov (za predpokladu, že každý znak je zakódovaný 4 bitmi) a pomocou algoritmu Shannon-Fano 4*2+2+4+4+3+3+3=27 bitov. Objem správ sa znížil o 32,5 %, ale nižšie sa ukáže, že tento výsledok možno výrazne zlepšiť.

Kódovanie pomocou Huffman Trees

Huffmanov kódovací algoritmus, vyvinutý niekoľko rokov po algoritme Shannon-Fano, má tiež vlastnosť predpony a navyše preukázanú minimálnu redundanciu, čo je dôvodom jeho extrémne širokej distribúcie. Na získanie Huffmanových kódov sa používa nasledujúci algoritmus:
1. Všetky symboly abecedy sú reprezentované ako voľné uzly, pričom váha uzla je úmerná frekvencii symbolu v správe;
2. Z množiny voľných uzlov sa vyberú dva uzly s minimálnou váhou a vytvorí sa nový (rodičovský) uzol s váhou rovnajúcou sa súčtu váh vybraných uzlov;
3. Vybrané uzly sa odstránia z voľného zoznamu a nadradený uzol vytvorený na ich základe sa pridá do tohto zoznamu;
4. Kroky 2-3 sa opakujú, kým sa vo voľnom zozname nenachádza viac ako jeden uzol;
5. Na základe vytvoreného stromu je každému znaku abecedy priradený predponový kód;
6. Správa je zakódovaná prijatými kódmi.

Zvážte rovnaký príklad ako v prípade algoritmu Shannon-Fano. Huffmanov strom a kódy prijaté pre správu „AAAAABVGDEZH“ sú znázornené na obr. 2:

Je ľahké vypočítať, že veľkosť zakódovanej správy bude 26 bitov, čo je menej ako v algoritme Shannon-Fano. Samostatne je potrebné poznamenať, že kvôli popularite Huffmanovho algoritmu na tento moment Existuje mnoho variantov Huffmanovho kódovania, vrátane adaptívneho kódovania, ktoré nevyžaduje prenos symbolových frekvencií.
Medzi nevýhodami Huffmanovho algoritmu sú významnou súčasťou problémy spojené so zložitosťou implementácie. Používanie skutočných variabilných symbolov na ukladanie frekvencií je spojené so stratou presnosti, preto sa v praxi často používajú celočíselné premenné, ale od r. hmotnosť rodičovských uzlov neustále rastie, skôr či neskôr dôjde k pretečeniu. Preto, napriek jednoduchosti algoritmu, jeho správna implementácia môže stále spôsobovať určité ťažkosti, najmä pre veľké abecedy.

Kódovanie pomocou sečných stromov

Kódovanie pomocou sekantových funkcií je algoritmus vyvinutý autormi, ktorý umožňuje získavanie prefixových kódov. Algoritmus je založený na myšlienke vybudovať strom, ktorého každý uzol obsahuje funkciu sekantu. Pre detailnejší popis algoritmu je potrebné uviesť niekoľko definícií.
Slovo je usporiadaná postupnosť m bitov (číslo m sa nazýva dĺžka slova).
Sekantový literál je pár bit-hodnota. Napríklad literál (4,1) znamená, že 4 bity slova sa musia rovnať 1. Ak je podmienka literálu pravdivá, potom sa literál považuje za pravdivý, inak je nepravdivý.
K-bitový sekant je množina k literálov. Ak sú všetky literály pravdivé, potom je samotná funkcia sekantu pravdivá, inak je nepravdivá.

Strom je zostavený tak, že každý uzol rozdeľuje abecedu na čo najbližšie časti. Na obr. 3 ukazuje príklad sečného stromu:

Strom sečných funkcií vo všeobecnom prípade nezaručuje optimálne kódovanie, ale poskytuje extrémne vysokú rýchlosť prevádzky vďaka jednoduchosti prevádzky v uzloch.

Aritmetické kódovanie

Aritmetické kódovanie je jedným z najviac efektívnymi spôsobmi kompresiu informácií. Na rozdiel od Huffmanovho algoritmu aritmetické kódovanie umožňuje, aby boli správy zakódované s entropiou menšou ako 1 bit na symbol. Pretože väčšina aritmetických kódovacích algoritmov je chránená patentmi, nižšie budú popísané iba hlavné myšlienky.
Predpokladajme, že v použitej abecede je N znakov a_1,…,a_N, s frekvenciami p_1,…,p_N, resp. Potom bude algoritmus aritmetického kódovania vyzerať takto:
Ako pracovný polinterval vezmite )