2 spôsoby komprimácie informácií v súboroch. Kompresia pomocou kódovacích sérií. Prenos e -mailom

Dobrý deň.
Dnes sa chcem dotknúť témy bezstratovej kompresie dát. Napriek tomu, že už boli články o Habrém venované niektorým algoritmom, chcel som o tom hovoriť trochu podrobnejšie.
Skúsim dať ako matematický popis, ako aj popis v obvyklej forme, aby si každý našiel niečo zaujímavé pre seba.

V tomto článku sa dotknem základov kompresie a hlavných typov algoritmov.

Kompresia Je to v našej dobe nevyhnutné?

Samozrejme áno. Všetci samozrejme chápeme, že teraz máme prístup k veľkoobjemovým úložným médiám a vysokorýchlostným kanálom prenosu údajov. Objemy prenášaných informácií však zároveň rastú. Ak sme pred niekoľkými rokmi sledovali 700-megabajtové filmy, ktoré sa zmestia na jeden disk, dnes môžu filmy v HD kvalite zabrať desiatky gigabajtov.
Z kompresie všetkého a všetkého samozrejme nie je veľký úžitok. Ale stále existujú situácie, v ktorých je kompresia mimoriadne užitočná, ak nie je potrebná.

• Odosielanie dokumentov do e-mail(obzvlášť veľké objemy dokumentov pomocou mobilných zariadení)
• Pri publikovaní dokumentov na webových stránkach je potrebné šetriť návštevnosť
• Ukladá sa miesto na disku v prípadoch, keď je výmena alebo pridanie skladovacích prostriedkov náročné. Stáva sa to napríklad v prípadoch, keď nie je ľahké vyňať rozpočet na kapitálové výdavky a na disku nie je dostatok miesta.

Samozrejme, môžete myslieť na mnoho ďalších situácií, v ktorých bude kompresia užitočná, ale týchto pár príkladov nám úplne stačí.

Všetky metódy kompresie je možné rozdeliť do dvoch širokých skupín: stratová kompresia a bezstratová kompresia. Bezstratová kompresia sa používa vtedy, keď je potrebné obnoviť informácie s bitovou presnosťou. Tento prístup je jediný možný pri kompresii napríklad textových údajov.
V niektorých prípadoch však nie je potrebná presná obnova informácií a sú povolené algoritmy implementujúce stratovú kompresiu, ktoré sa na rozdiel od bezstratovej kompresie zvyčajne implementujú jednoduchšie a poskytujú vyšší stupeň archivácie.

Prejdeme teda k zváženiu bezstratových kompresných algoritmov.

Všestranné bezstratové metódy kompresie

Vo všeobecnosti existujú tri základné možnosti, na ktorých sú postavené kompresné algoritmy.
Prvá skupina metódy - transformácia prúdu. To zahŕňa popis nových prichádzajúcich nekomprimovaných údajov prostredníctvom už spracovaných. V tomto prípade nie sú vypočítané žiadne pravdepodobnosti, kódovanie znakov sa vykonáva iba na základe údajov, ktoré už boli spracované, ako napríklad v metódach LZ (pomenovaných po Abrahámovi Lempelovi a Jacobovi Zivovi). V tomto prípade sú druhý a ďalšie výskyty určitého podreťazca, ktoré sú už kodéru známe, nahradené odkazmi na jeho prvý výskyt.

Druhá skupina Metódy sú metódy štatistickej kompresie. Na druhej strane sú tieto metódy rozdelené na adaptívne (alebo tok) a blokové.
V prvej (adaptívnej) verzii je výpočet pravdepodobností pre nové údaje založený na údajoch, ktoré už boli spracované počas kódovania. Tieto metódy zahŕňajú adaptívne verzie algoritmov Huffman a Shannon-Fano.
V druhom (blokovom) prípade sa štatistika každého dátového bloku vypočíta oddelene a pridá sa k najviac komprimovanému bloku. To zahŕňa statické verzie metód Huffman, Shannon-Fano a aritmetické kódovanie.

Tretia skupina Metódy sú takzvané metódy blokovej konverzie. Prichádzajúce údaje sú rozdelené do blokov, ktoré sú potom transformované ako celok. Niektoré metódy, najmä tie, ktoré sú založené na blokovej permutácii, nemusia zároveň viesť k významnému (alebo dokonca akémukoľvek) zníženiu množstva údajov. Po takomto spracovaní sa však dátová štruktúra výrazne zlepší a následná kompresia inými algoritmami je úspešnejšia a rýchlejšia.

Všeobecné zásady, na ktorých je založená kompresia údajov

Všetky metódy kompresie údajov sú založené na jednoduchom logickom princípe. Ak si predstavíme, že najbežnejšie prvky sú kódované kratšími kódmi a menej bežné prvky s dlhšími kódmi, potom uloženie všetkých údajov zaberie menej miesta, ako keby všetky prvky predstavovali kódy rovnakej dĺžky.
Presný vzťah medzi frekvenciami prvkov a optimálnymi dĺžkami kódu je popísaný v takzvanej Shannonovej vete o zdrojovom kódovaní, ktorá definuje maximálny limit bezstratovej kompresie a Shannonovu entropiu.

Trochu matematiky

Ak je pravdepodobnosť výskytu prvku s i rovná p (s i), potom bude najvýhodnejšie reprezentovať tento prvok - log 2 p (s i) v bitoch. Ak je počas kódovania možné dosiahnuť, aby sa dĺžka všetkých prvkov zmenšila na log 2 p (s i) bitov, potom bude dĺžka celej kódovanej sekvencie minimálna pre všetky možné metódy kódovania. Navyše, ak je rozdelenie pravdepodobnosti všetkých prvkov F = (p (s i)) nezmenené a pravdepodobnosti prvkov sú na sebe nezávislé, potom priemernú dĺžku kódov je možné vypočítať ako

Táto hodnota sa nazýva entropia rozdelenia pravdepodobnosti F alebo entropia zdroja v danom časovom okamihu.
Pravdepodobnosť výskytu prvku však spravidla nemôže byť nezávislá, naopak, závisí to od niektorých faktorov. V tomto prípade bude pre každý nový zakódovaný prvok s i distribúcia pravdepodobnosti F mať určitú hodnotu F k, to znamená pre každý prvok F = F k a H = H k.

Inými slovami, môžeme povedať, že zdroj je v stave k, ktorý zodpovedá určitému súboru pravdepodobností p k (s i) pre všetky prvky s i.

Preto s prihliadnutím na tento dodatok môžeme priemernú dĺžku kódov vyjadriť ako

Kde P k je pravdepodobnosť nájdenia zdroja v stave k.

V tejto fáze teda vieme, že kompresia je založená na nahradení často sa vyskytujúcich prvkov krátkymi kódmi, a naopak, a tiež vieme, ako určiť priemernú dĺžku kódov. Čo je to však kód, kódovanie a ako sa to deje?

Kódovanie bez pamäte

Kódy bez pamäte sú najjednoduchšie kódy, na základe ktorých je možné vykonať kompresiu údajov. V kóde bez pamäte je každý znak v kódovanom dátovom vektore nahradený kódovým slovom z vopred nastavenej sady binárnych sekvencií alebo slov.
Podľa mňa to nie je najjasnejšia definícia. Uvažujme o tejto téme trochu podrobnejšie.

Nech je daná nejaká abeceda , pozostávajúci z určitého (konečného) počtu písmen. Nazvime každú konečnú postupnosť symbolov z tejto abecedy (A = a 1, a 2, ..., a n) slovo, a číslo n je dĺžka tohto slova.

Nech je daná aj iná abeceda ... Podobne označme slovo v tejto abecede ako B.

Predstavíme ešte dva zápisy pre množinu všetkých neprázdnych slov v abecede. Nech je počet neprázdnych slov v prvej abecede a - v druhej.

Nech je tiež uvedené mapovanie F, ktoré každému slovu A z prvej abecedy priradí nejaké slovo B = F (A) z druhej. Potom sa bude volať slovo B. kód slovo A a bude sa volať prechod z pôvodného slova do jeho kódu kódovanie.

Pretože slovo môže pozostávať aj z jedného písmena, môžeme identifikovať korešpondenciu medzi písmenami prvej abecedy a zodpovedajúcimi slovami z druhej:
a 1<->B 1
a 2<->B 2
…
a n<->B n

Táto korešpondencia sa nazýva schéma, a sú označené ∑.
V tomto prípade volajú slová B 1, B 2, ..., B n elementárne kódy, a typ kódovania s ich pomocou je abecedné kódovanie... Samozrejme, väčšina z nás sa stretla s týmto druhom kódovania, dokonca aj bez toho, aby vedela všetko, čo som popísal vyššie.

Preto sme definovali pojmy abeceda, slovo, kód, a kódovanie... Teraz predstavíme koncept predpona.

Slovo B nech má tvar B = B "B" ". Potom sa B" nazýva začiatok, príp predpona slovo B a B "" je jeho koniec. Toto je pomerne jednoduchá definícia, treba však poznamenať, že pre každé slovo B je možné ako prázdne slovo ʌ („medzera“), tak aj samotné slovo B považovať za začiatky aj konce.

Približujeme sa teda k chápaniu definície kódov bez pamäte. Posledná definícia, ktorú musíme pochopiť, je sada predpon. Schéma ∑ má vlastnosť predpony, ak pre akékoľvek 1≤i, j≤r, i ≠ j slovo B i nie je predponou slova B j.
Jednoducho povedané, sada predpony je konečná množina, v ktorej žiadny prvok nie je predponou (alebo začiatkom) žiadneho iného prvku. Jednoduchý príklad taká množina je napríklad obyčajná abeceda.

Zistili sme teda základné definície. Ako teda prebieha skutočné kódovanie bez pamäte?
Prebieha v troch fázach.

1. Zostaví sa abeceda symbolov of pôvodnej správy a symboly abecedy sa zoradia zostupne podľa ich pravdepodobnosti výskytu v správe.
2. Každý symbol a i z abecedy Ψ je spojený s určitým slovom B i z množiny predpon Ω.
3. Každý znak je zakódovaný a potom nasleduje skombinovanie kódov do jedného dátového toku, ktorý bude výsledkom kompresie.

Jeden z kanonických algoritmov, ktoré ilustrujú túto metódu, je Huffmanov algoritmus.

Huffmanov algoritmus

Huffmanov algoritmus používa frekvenciu výskytu rovnakých bytov v bloku vstupných údajov a mapuje často sa vyskytujúce bloky s kratšími bitovými reťazcami a naopak. Tento kód je minimálny - nadbytočný. Zvážte prípad, keď bez ohľadu na vstupný prúd, abeceda výstupného toku pozostáva iba z 2 znakov - nula a jedna.

V prvom rade, pri kódovaní pomocou Huffmanovho algoritmu, musíme vytvoriť obvod ∑. To sa robí nasledovne:

1. Všetky písmená vstupnej abecedy sú zoradené zostupne podľa pravdepodobností. Všetky slová z abecedy výstupného toku (to znamená, čo budeme kódovať) sa na začiatku budú považovať za prázdne (pripomíname, že abeceda výstupného toku pozostáva iba zo znakov (0,1)).
2. Dva symboly a j-1 a a j vstupného toku, ktoré majú najnižšiu pravdepodobnosť výskytu, sa skombinujú do jedného „pseudoznaku“ s pravdepodobnosťou p sa rovná súčtu pravdepodobností symbolov v ňom zahrnutých. Potom pridáme 0 na začiatok slova B j-1 a 1 na začiatok slova B j, čo budú následne kódy znakov a j-1 a a j.
3. Tieto symboly odstránime z abecedy pôvodnej správy, ale vygenerovaný pseudoznak do tejto abecedy pridáme (samozrejme, musí byť vložený do abecedy na správnom mieste, pričom sa zohľadní jej pravdepodobnosť).

Kroky 2 a 3 sa opakujú, kým v abecede nezostane iba 1 pseudo znak obsahujúci všetky pôvodné znaky abecedy. V tomto prípade, pretože v každom kroku a pre každý znak sa zmení zodpovedajúce slovo B i (pridaním jednej alebo nuly), potom po dokončení tohto postupu bude každému počiatočnému symbolu abecedy a zodpovedať určitý kód B i i.

Pre lepšiu ilustráciu zvážte malý príklad.
Predpokladajme, že máme abecedu pozostávajúcu iba zo štyroch znakov - (a 1, a 2, a 3, a 4). Predpokladajme tiež, že pravdepodobnosti výskytu týchto symbolov sú p 1 = 0,5; p2 = 0,24; p3 = 0,15; p 4 = 0,11 (súčet všetkých pravdepodobností je evidentne rovný jednej).

Vytvorme teda schému pre danú abecedu.

1. Spojíme dva znaky s najnižšou pravdepodobnosťou (0,11 a 0,15) do pseudoznaku p “.
2. Skombinujte dva znaky s najnižšou pravdepodobnosťou (0,24 a 0,26) do pseudoznaku p "".
3. Odstráňte zreťazené znaky a výsledný pseudo-znak vložte do abecedy.
4. Nakoniec spojíme zvyšné dva symboly, aby sme získali vrchol stromu.

Ak tento proces ilustrujete, dostanete niečo takéto:

Ako vidíte, pri každom zlúčení priradíme zlúčeným znakom kódy 0 a 1.
Týmto spôsobom, keď je strom zostavený, môžeme ľahko získať kód pre každý znak. V našom prípade budú kódy vyzerať takto:

A 1 = 0
a 2 = 11
a 3 = 100
a 4 = 101

Pretože žiadny z týchto kódov nie je predponou akéhokoľvek iného (to znamená, že sme získali známu sadu predpon), môžeme každý kód vo výstupnom toku jednoznačne identifikovať.
Dosiahli sme teda, že najčastejší znak je kódovaný najkratším kódom a naopak.
Ak predpokladáme, že pôvodne bol na uloženie každého znaku použitý jeden bajt, potom môžeme vypočítať, o koľko sa nám podarilo údaje zmenšiť.

Predpokladajme, že sme na vstupe mali reťazec 1 000 znakov, v ktorom sa znak a 1 vyskytol 500 -krát, 2 - 240, 3 - 150 a 4 - 110 -krát.

Spočiatku daný reťazec obsadil 8 000 bitov. Po zakódovaní dostaneme reťazec s dĺžkou ∑p i l i = 500 * 1 + 240 * 2 + 150 * 3 + 110 * 3 = 1760 bitov. Takže sa nám podarilo skomprimovať údaje 4,54 -krát, pričom sme v priemere utratili 1,76 bita na kódovanie každého znaku streamu.

Pripomeniem, že podľa Shannona je priemerná dĺžka kódov. Nahradením našich pravdepodobností do tejto rovnice dostaneme priemernú dĺžku kódu rovnajúcu sa 1,75496602732291, čo je veľmi, veľmi blízko nášho výsledku.
Malo by sa však pamätať na to, že okrem samotných údajov musíme uložiť aj kódovaciu tabuľku, ktorá mierne zvýši konečnú veľkosť kódovaných údajov. Je zrejmé, že v rôznych prípadoch je možné použiť rôzne variácie algoritmu - napríklad niekedy je efektívnejšie použiť vopred danú tabuľku pravdepodobnosti a niekedy - je potrebné ich zostaviť dynamicky tak, že prejdeme cez stlačiteľné údaje.

Záver

V tomto článku som sa teda pokúsil hovoriť o všeobecných zásadách, pomocou ktorých dochádza k bezstratovej kompresii, a tiež som zvážil jeden z kanonických algoritmov - Huffmanovo kódovanie.
Ak sa vám článok páči v habro komunite, rád napíšem pokračovanie, pretože s bezstratovou kompresiou súvisí ešte veľa zaujímavých vecí; sú to jednak klasické algoritmy, jednak predbežné transformácie údajov (napríklad Burrowsova-Wheelerova transformácia) a samozrejme konkrétne algoritmy na kompresiu zvuku, videa a obrazu (podľa mňa najzaujímavejšia téma).

Literatúra

• Vatolin D., Ratushnyak A., Smirnov M., Yukin V. Metódy kompresie údajov. Zariadenie archivátorov, kompresia obrázkov a videí; ISBN 5-86404-170-X; 2003 r.
• D. Salomon. Kompresia údajov, obrazu a zvuku; ISBN 5-94836-027-X; 2004

Zásady kompresie informácií

Akákoľvek metóda kompresie informácií je založená na modeli zdroja informácií alebo konkrétnejšie na modeli redundancie. Inými slovami, na kompresiu informácií sa používajú niektoré informácie o tom, aký druh informácií sa komprimuje - bez toho, aby sme o nich mali akékoľvek informácie, nemožno absolútne predpokladať, ktorá transformácia zníži objem správy. Tieto informácie sa používajú v procese kompresie a dekompresie. Redundančný model môže byť tiež zostavený alebo parametrizovaný počas kompresného stupňa. Metódy, ktoré umožňujú zmeniť model redundancie informácií na základe vstupných údajov, sa nazývajú adaptívne. Neadaptívne sú zvyčajne úzko špecifické algoritmy používané na prácu s dobre definovanými a nezmenenými charakteristikami. Drvivá väčšina dostatočne univerzálnych algoritmov je do jedného alebo druhého stupňa adaptívna.

Akákoľvek metóda kompresie informácií zahŕňa dve navzájom prevrátené konverzie:

• kompresná konverzia;
• expanzná konverzia.

Kompresná transformácia poskytuje komprimovanú správu z originálu. Dekompresia zaisťuje, že pôvodná správa (alebo jej aproximácia) je získaná z komprimovanej správy.

Všetky metódy kompresie sú rozdelené do dvoch hlavných tried

• žiadna strata,
• so stratami.

Zásadný rozdiel medzi nimi je v tom, že bezstratová kompresia poskytuje schopnosť presne zrekonštruovať pôvodnú správu. Stratová kompresia vám umožňuje získať iba určitú aproximáciu pôvodnej správy, to znamená, že sa líši od pôvodnej správy, ale v rámci niektorých vopred určených chýb. Tieto chyby by mal určiť iný model - model prijímača, ktorý určuje, ktoré údaje a s akou presnosťou sú prijímaču prezentované a ktoré je prijateľné vyradiť.

Charakteristiky a použiteľnosť kompresného algoritmu

Pomer kompresie

Kompresný pomer je hlavnou charakteristikou kompresného algoritmu, ktorá vyjadruje kvalitu hlavnej aplikácie. Je definovaný ako pomer veľkosti nekomprimovaných údajov k komprimovaným údajom, tj.

k = S o / S c,

kde k- pomer kompresie, S o je veľkosť nekomprimovaných údajov a S c - veľkosť stlačeného. Čím je teda kompresný pomer vyšší, tým je algoritmus lepší. Je potrebné poznamenať:

• keby k= 1, potom algoritmus nekomprimuje, to znamená, že dostane výstupnú správu s veľkosťou rovnou vstupnej;
• keby k < 1, то алгоритм порождает при сжатии сообщение большего размера, нежели несжатое, то есть, совершает «вредную» работу.

Situácia s k < 1 вполне возможна при сжатии. Невозможно получить алгоритм сжатия без потерь, который при любых данных образовывал бы на выходе данные меньшей или равной длины. Обоснование этого факта заключается в том, что количество различных сообщений длиной n Vzor: E: bit je presne 2 n... Potom počet rôznych správ s dĺžkou menšou alebo rovnou n(ak je aspoň jedna správa kratšej dĺžky) bude menšia ako 2 n... To znamená, že nie je možné jednoznačne priradiť všetky pôvodné správy k komprimovanej: buď niektoré z pôvodných správ nebudú mať komprimovanú reprezentáciu, alebo niekoľko pôvodných správ bude zodpovedať tej istej komprimovanej, čo znamená, že ich nemožno rozlíšiť.

Kompresný pomer môže byť buď konštantný (niektoré kompresné algoritmy pre zvuk, obrázky atď., Napríklad A-zákon, μ-zákon, ADPCM), alebo premenný. V druhom prípade môže byť stanovená buď pre konkrétnu správu, alebo hodnotená podľa niektorých kritérií:

• priemer (zvyčajne nad nejakým testovacím súborom údajov);
• maximum (prípad najlepšej kompresie);
• minimálna (najhoršia kompresia);

alebo nejaký iný. Stratový kompresný pomer v tomto prípade silne závisí od prípustnej chyby kompresie alebo od nej kvalita, ktorý zvyčajne slúži ako parameter algoritmu.

Strata tolerancie

Hlavným kritériom na rozlíšenie medzi kompresnými algoritmami je prítomnosť alebo neprítomnosť strát opísaných vyššie. Algoritmy bezstratovej kompresie sú vo všeobecnosti univerzálne v tom zmysle, že ich možno použiť na akýkoľvek typ údajov, pričom použitie stratovej kompresie by malo byť odôvodnené. Niektoré typy údajov netolerujú žiadnu stratu:

• symbolické údaje, ktorých zmena nevyhnutne vedie k zmene ich sémantiky: programy a ich zdrojové kódy, binárne polia atď.;
• životne dôležité údaje, zmeny, ktoré môžu viesť ku kritickým chybám: napríklad získané z lekárskych meracích zariadení alebo riadiacich zariadení lietadiel, kozmických lodí atď.
• údaje opakovane vystavované kompresii a dekompresii: pracovné grafické, zvukové a video súbory.

Stratová kompresia vám však umožňuje dosiahnuť oveľa vyššie kompresné pomery vyradením nepodstatných informácií, ktoré sa nekomprimujú dobre. Napríklad bezztrátový algoritmus kompresie zvuku FLAC vo väčšine prípadov umožňuje komprimáciu zvuku 1,5 až 2,5 krát, zatiaľ čo stratový algoritmus Vorbis v závislosti od nastaveného parametra kvality dokáže komprimovať až 15 krát pri zachovaní prijateľnej kvality. .zvuk.

Požiadavky na systém algoritmu

Rôzne algoritmy môžu vyžadovať rôzne množstvo zdrojov výpočtový systém na ktorých sa vykonávajú:

• RAM (pre prechodné údaje);
• trvalá pamäť (pre programový kód a konštanty);
• čas procesora.

Vo všeobecnosti tieto požiadavky závisia od zložitosti a „inteligencie“ algoritmu. Všeobecne platí, že čím je algoritmus lepší a univerzálnejší, tým väčšie nároky na stroj kladie. V špecifických prípadoch však môžu jednoduché a kompaktné algoritmy fungovať lepšie. Systémové požiadavky určujú ich spotrebiteľské vlastnosti: čím menej je algoritmus náročný, tým je jednoduchší, a preto kompaktnejší, spoľahlivejší a lacnejší systém, na ktorom môže pracovať.

Pretože algoritmy kompresie a dekompresie pracujú vo dvojiciach, je pomer Požiadavky na systém im. Jeden algoritmus môžete často skomplikovať, ten druhý môžete výrazne zjednodušiť. Môžeme teda mať tri možnosti:

Kompresný algoritmus je oveľa náročnejší na zdroje ako dekompresný algoritmus. Toto je najbežnejší vzťah a je použiteľné hlavne v prípadoch, keď sa skomprimované údaje použijú viackrát. Medzi príklady patria digitálne prehrávače zvuku a videa. Kompresné a dekompresné algoritmy majú zhruba rovnaké požiadavky. Najprijateľnejšia možnosť pre komunikačnú linku, keď dochádza ku kompresii a dekompresii raz na jej dvoch koncoch. Napríklad to môže byť telefónia. Kompresný algoritmus je výrazne menej náročný ako dekompresný algoritmus. Dosť exotický prípad. Môže sa použiť v prípadoch, keď je vysielač ultra prenosným zariadením, kde je veľmi dôležité množstvo dostupných zdrojov, napríklad kozmická loď alebo veľká distribuovaná sieť senzorov, alebo to môže byť rozbaľovanie údajov, ktoré sú potrebné v veľmi malé percento prípadov, napríklad záznam CCTV kamier.

pozri tiež

Nadácia Wikimedia. 2010.

Pozrite sa, čo je „kompresia informácií“ v iných slovníkoch:

kompresia informácií- konsolidácia informácií - [L.G. Sumenko. Anglický ruský slovník informačných technológií. M.: GP TsNIIS, 2003.] Témy informačné technológie vo všeobecnosti Synonymá zhutnenie informácií EN redukcia informácií ...

KOMPRESNÉ INFORMÁCIE- (kompresia údajov) prezentácia informácií (údajov) v menšom počte bitov ako originál. Na základe odstránenia nadbytočnosti. Rozlišujte S. a. bez straty informácií a so stratou niektorých informácií, ktoré sú pre riešené úlohy nepodstatné. TO…… Encyklopedický slovník psychológie a pedagogiky

adaptívna bezstratová kompresia- - [L. G. Sumenko. Anglický ruský slovník informačných technológií. M.: GP TsNIIS, 2003.] Témy informačné technológie vo všeobecnosti EN adaptívna bezstratová kompresia dátALDC ... Technická príručka prekladateľa

kompresia / kompresia informácií- - [L. G. Sumenko. Anglický ruský slovník informačných technológií. M.: GP TsNIIS, 2003.] Témy informačné technológie vo všeobecnosti zhutnenie EN ... Technická príručka prekladateľa

kompresia digitálnych informácií- - [L. G. Sumenko. Anglický ruský slovník informačných technológií. M.: GP TsNIIS, 2003.] Témy informačné technológie vo všeobecnosti EN kompresia ... Technická príručka prekladateľa

Zvuk je jednoduchá vlna a digitálny signál je znázornením tejto vlny. To sa dosiahne zapamätaním amplitúdy analógový signál viackrát v priebehu jednej sekundy. Napríklad na obyčajnom disku CD sa signál uloží 44 100 -krát do ... ... Wikipedie

Proces, ktorý znižuje množstvo dát znížením nadbytočnosti. Kompresia údajov zahŕňa zhutnenie štandardných kúskov údajov. Rozlišuje sa medzi stratovou a bezstratovou kompresiou. V angličtine: Data ... ... Finančná slovná zásoba

kompresia digitálnej mapy- Spracovanie digitálnych kartografických informácií za účelom zníženia ich objemu vrátane eliminácie nadbytočnosti v rámci požadovanej presnosti ich prezentácie. [GOST 28441 99] Témy digitálnej kartografie Zovšeobecnenie pojmov metódy a technológie ... ... Technická príručka prekladateľa

Účel hodiny: rozvíjať pozornosť, inteligenciu a vzbudiť záujem o predmet.
Vybavenie: počítače, laboratórne disky, vhodné softvér, karty s testovacou úlohou.

Počas vyučovania

1. Organizačná časť.
2. Aktualizácia základných znalostí.
3. Učenie sa nového materiálu
4. Zabezpečenie nového materiálu.
5. Domáca úloha.
6. Zhrnutie lekcie.

Učenie sa nového materiálu

1. Čo je archivácia. Koncept kompresie údajov.
2. Hlavné typy archivačných programov.
3. Programový archivátor WIN-RAR.
4. Ako pridať súbor do archívu a ako ho extrahovať z archívu.

S rozvojom informačné technológie ostro vyvstala otázka, ako uchovávať údaje. Vedci od 40. rokov dvadsiateho storočia vyvíjajú metódy na prezentáciu údajov, v ktorých by bol priestor na nosičoch informácií využívaný ekonomickejšie. Výsledkom je technológia kompresie a archivácie údajov (zálohovanie).

Archivácia údajov je zlúčenie niekoľkých súborov alebo adresárov do jedného archívneho súboru.

Kompresia údajov - zmenšenie veľkosti pôvodných súborov odstránením nadbytočných informácií.

Na vykonanie týchto úloh slúžia archivačné programy, ktoré poskytujú kompresia údajov: najmä archivácia súborov. Archivátory pomocou špeciálnych algoritmov odstránia všetky nadbytočné informácie zo súborov a počas operácií spätného rozbalenia obnovia informácie v pôvodnej podobe. Veľkosť komprimovaný súbor dva až desaťkrát menej ako pôvodný súbor. V tomto prípade dôjde k kompresii a obnove informácií bez straty. Bezstratová kompresia je dôležitá pri práci s textovými a programovými súbormi v kryptografických úlohách. Existujú aj stratové kompresné techniky.

Kompresný pomer závisí od typu súboru a programu archivátora. Predovšetkým sa zmenšujú textové súbory, najmenej zo všetkých - zvukové a video súbory.

Archivácia súborov. Úlohy

Doteraz sme hovorili o jednom účele archivácie údajov - ekonomickejšom ako pri použití pamäťových médií. Pomocou archivácie však môžete vykonávať celý rad úloh:
1. Zníženie objemu súborov (dôležité nielen kvôli šetreniu miesta na médiu, ale aj pre rýchly prenos súborov cez sieť).
2. Zálohovanie na externé médiá na ukladanie dôležitých informácií.

3. Archivácia pri šifrovaní údajov, aby sa znížila pravdepodobnosť prelomenia kryptosystému.

Proces zápisu informácií do archívneho súboru sa nazýva archivácia.
Extrahovanie súborov z archívu - rozbalenie.

Prvé archivačné programy sa objavili v polovici 80. rokov minulého storočia. Zamerali sa na prácu v MS-DOC a podporovali obľúbené archívne formáty: ARC, ICE, ARJ, ZIP a RAR atď. Existovala aj skupina archivátorov, ktorí balili údaje do samorozbaľovacích archívov-súborov s. áno,. kam. Rezidentné archivátory boli vytvorené na kompresiu celého disku. Umožnili zvýšiť efektivitu využitia miesta na disku vytvorením veľkých archívnych súborov - diskových „kompresií“.

Práca s archívmi sa stala oveľa pohodlnejšou s príchodom verzií archivátorov pre Windows a Windows. Z bývalých archívnych formátov medzi Používatelia systému Windows ARJ, ZIP - programy, ktoré rozbalujú súbory, sa skutočne udomácnili. Archívne súbory veľkej veľkosti môžu byť umiestnené na niekoľkých disketách (zväzkoch). Takéto archívy sa nazývajú viaczväzkové.

Tom je zložka viaczväzkový archív.

Teraz sa používajú desiatky archivačných programov, ktoré sa líšia v zozname funkcií a prevádzkových parametrov, ale najlepšie z nich majú približne rovnaké vlastnosti. Vieme, že balenie a rozbaľovanie súborov vykonáva ten istý program, ale v niektorých prípadoch sa to robí rôzne programy napríklad program RKZIP zabalí súbory a RKUNZIP rozbalí súbory.
Archivačné programy vám umožňujú vytvárať také archívy, na extrahovanie ktorých nepotrebujete žiadne programy, pretože archívne súbory obsahujú samorozbaľovací program. Takéto archívy sa nazývajú archívy SFX.

Vkladanie súborov do archívu: Spustite Programy WINRAR alebo ako skratku na ploche.

Univerzálny archivátor WINRAR

Na archiváciu súborov je určený aj archivátor WINRAR. Má praktické grafické rozhranie a podporuje technológiu Drag and Drop. Softvér WINRAR vám umožňuje pracovať nielen s archívom rar súbory, ale aj s inými formátmi archívov: zip, cab, arj, lzh. WINRAR spúšťa ktorýkoľvek z možné spôsoby poskytované vo Windows. Spustenie programu pomocou hlavnej ponuky tlačidla Štart Programy WINRAR WINRAR alebo pomocou skratky na pracovnej ploche.

Testovací prieskum zo základov práce s diskami.
Domáca úloha.
Lekcia introspekcie.

Na vykonanie týchto úloh slúžia archivačné programy, ktoré poskytujú archiváciu aj kompresiu údajov. Archivátory pomocou špeciálnych algoritmov odstránia všetky nadbytočné informácie zo súborov a počas operácií spätného rozbalenia obnovia informácie v pôvodnej podobe. Veľkosť komprimovaného súboru je dva až desaťkrát menšia ako pôvodný súbor.

V dnešnej dobe mnoho používateľov uvažuje o tom, ako sa vykonáva proces kompresie informácií, aby sa ušetrilo voľné miesto na pevnom disku, pretože toto je jeden z najlepších účinné prostriedky využitie využiteľného priestoru na akomkoľvek disku. Pomerne často moderní používatelia, ktorí sa stretávajú s nedostatkom voľného miesta na disku, musia odstrániť všetky údaje, aby uvoľnili potrebné miesto, zatiaľ čo pokročilejší používatelia najčastejšie používajú kompresiu údajov, aby zmenšili svoj objem.

Mnohí však ani nevedia, ako sa nazýva proces kompresie informácií, nehovoriac o tom, ktoré algoritmy sa používajú a čo dáva aplikácia každého z nich.

Mali by ste skomprimovať údaje?

Kompresia údajov je dnes veľmi dôležitá a je potrebná pre každého používateľa. V dnešnej dobe si takmer každý môže kúpiť pokročilé zariadenia na ukladanie údajov, ktoré poskytujú možnosť využiť pomerne veľké množstvo voľného miesta, a sú vybavené vysokorýchlostnými kanálmi na prenos informácií.

V tomto prípade však musíte správne pochopiť, že v priebehu času sa zvyšuje aj množstvo údajov, ktoré je potrebné prenášať. A ak bol doslova desať rokov dozadu považovaný za bežný film objem 700 MB, dnes môžu mať filmy vyrobené v kvalite HD objemy rovné niekoľko desiatkam gigabajtov, nehovoriac o tom, koľko voľného miesta zaberajú vysokokvalitné filmy. vo formáte Blu-ray.

Kedy je potrebná kompresia údajov?

Samozrejme by ste nemali očakávať, že proces kompresie informácií vám prinesie veľa výhod, ale existuje množstvo situácií, v ktorých sú niektoré metódy kompresie informácií mimoriadne užitočné a dokonca nevyhnutné:

• Prenos určitých dokumentov e -mailom. To platí najmä pre situácie, keď potrebujete prenášať informácie vo veľkých objemoch pomocou rôznych mobilných zariadení.
• Proces kompresie informácií s cieľom zmenšiť priestor, ktorý zaberá, sa často používa pri publikovaní určitých údajov na rôznych stránkach, keď je potrebné ušetriť návštevnosť;
• Šetrite voľné miesto na pevnom disku, ak neexistuje spôsob, ako vymeniť alebo pridať nové pamäťové médium. Najčastejšia situácia je najmä vtedy, keď existujú určité obmedzenia pre dostupný rozpočet, ale na disku nie je dostatok voľného miesta.

Samozrejme, okrem vyššie uvedeného existuje aj obrovské číslo rôzne situácie, v ktorých môže byť požadovaný proces kompresie informácií, aby sa znížil ich objem, sú však zďaleka najbežnejšie.

Ako je možné komprimovať údaje?

Dnes existuje široká škála spôsobov kompresie informácií, ale všetky sú rozdelené do dvoch hlavných skupín - ide o kompresiu s určitou stratou, ako aj o kompresiu bez straty.

Použitie poslednej skupiny metód je dôležité vtedy, keď je potrebné údaje obnoviť s extrémne vysokou presnosťou až na jeden bit. Tento prístup je jediný relevantný v prípade, že je určitý textový dokument komprimovaný.

Zároveň stojí za zmienku skutočnosť, že v niektorých situáciách nie je potrebná najpresnejšia obnova komprimovaných údajov, preto je možné použiť také algoritmy, v ktorých sú informácie na disku komprimované s určitými stratami . Výhodou stratovej kompresie je, že implementácia tejto technológie je oveľa jednoduchšia a tiež poskytuje najvyššiu možnú úroveň archivácie.

Stratová kompresia

Stratové informácie poskytujú rádovo lepšiu kompresiu pri zachovaní dostatočnej kvality informácií. Vo väčšine prípadov sa tieto algoritmy používajú na kompresiu analógových údajov, ako sú všetky druhy obrazov alebo zvukov. V takýchto situáciách sa rozbalené súbory môžu úplne líšiť od pôvodných informácií, ale sú prakticky na nerozoznanie od ľudského oka alebo ucha.

Bezstratová kompresia

Algoritmy bezstratovej kompresie poskytujú najpresnejšie obnovenie údajov a eliminujú akúkoľvek stratu komprimovaných súborov. Zároveň však musíte správne pochopiť skutočnosť, že v tomto prípade nie je k dispozícii taká efektívna kompresia súborov.

Generické metódy

Okrem iného existuje určitá séria univerzálne metódy, pomocou ktorého sa vykonáva účinný proces kompresie informácií s cieľom zmenšiť priestor, ktorý zaberá. Vo všeobecnosti existujú iba tri hlavné technológie:

• Konverzia streamu. V tomto prípade sa popis nových prichádzajúcich nekomprimovaných informácií vykonáva prostredníctvom už spracovaných súborov, pričom sa síce nevypočítavajú žiadne pravdepodobnosti, ale znaky sú zakódované výlučne na základe súborov, ktoré už prešli určitým spracovaním.
• Štatistická kompresia. Tento proces kompresie informácií s cieľom zmenšiť miesto, ktoré zaberá na disku, je rozdelený do dvoch podkategórií - adaptívna a bloková metóda. Adaptívna verzia poskytuje výpočet pravdepodobnosti nových súborov na základe informácií, ktoré už boli spracované počas procesu kódovania. Tieto metódy by mali predovšetkým zahŕňať aj rôzne adaptívne varianty Shannon-Fano a Huffmanovho algoritmu. Algoritmus bloku zaisťuje samostatný výpočet každého bloku informácií s následným pridaním do najviac komprimovaného bloku.
• Bloková transformácia. Prichádzajúce informácie sú rozdelené do niekoľkých blokov a potom prebieha holistická transformácia. Malo by sa povedať, že určité metódy, najmä tie, ktoré sú založené na permutácii niekoľkých blokov, môžu v konečnom dôsledku viesť k významnému zníženiu množstva stlačiteľných informácií. Je však potrebné správne pochopiť, že po takom spracovaní v konečnom dôsledku dôjde k významnému zlepšeniu, v dôsledku ktorého je následná kompresia prostredníctvom iných algoritmov oveľa jednoduchšia a rýchlejšia.

Kompresia kópie

Jedna z najdôležitejších súčastí Rezervovaná kópia je zariadenie, na ktoré sa chcete presunúť potrebné užívateľom informácie. Čím viac údajov presuniete, tým objemnejšie zariadenie budete musieť použiť. Ak sa však chystáte vykonať proces kompresie údajov, potom v tomto prípade problém s nedostatkom voľného miesta pravdepodobne nebude pre vás relevantný.

Prečo je to potrebné?

Schopnosť komprimovať informácie a zároveň výrazne skrátiť čas, ktorý bude potrebný na kopírovanie požadované súbory a zároveň dosiahnuť efektívne úspory vo voľnom mieste na disku. Inými slovami, pri použití kompresie budú informácie skopírované oveľa kompaktnejšie a rýchlejšie a vy môžete ušetriť svoje peniaze a financie, ktoré boli potrebné na kúpu väčšieho disku. Kompresiou informácií okrem iného skrátite aj čas, ktorý bude potrebný na prenos všetkých údajov na server alebo ich kopírovanie cez sieť.

Kompresiu údajov na zálohovanie je možné vykonať do jedného alebo viacerých súborov - v tomto prípade bude všetko závisieť od toho, ktorý program použijete a aké informácie komprimujete.

Pri výbere pomocného programu sa zamerajte na to, do akej miery môže vami zvolený program komprimovať údaje. Závisí to od typu informácií, v dôsledku ktorých môže byť účinnosť kompresie textových dokumentov viac ako 90%, zatiaľ čo účinnosť nebude väčšia ako 5%.

Ako bolo uvedené vyššie, jedna z dôležitých úloh predbežná prípravašifrovanie údajov má znížiť ich nadbytočnosť a zosúladiť štatistické vzorce použitého jazyka. Čiastočné odstránenie nadbytočnosti sa dosiahne komprimáciou údajov.

Kompresia informácií je proces prevodu pôvodnej správy z jedného kódového systému na druhý, v dôsledku čoho veľkosť správy... Algoritmy určené na kompresiu informácií možno rozdeliť do dvoch veľkých skupín: na tie, ktoré implementujú bezstratovú kompresiu (reverzibilná kompresia) a na tie, ktoré implementujú stratovú kompresiu (nevratná kompresia).

Reverzibilná kompresia znamená úplne presnú obnovu dát po dekódovaní a možno ich použiť na kompresiu akýchkoľvek informácií. Vždy to vedie k zníženiu objemu výstupného informačného toku bez zmeny jeho informačného obsahu, to znamená bez straty informačná štruktúra... Navyše z výstupného toku môžete pomocou algoritmu obnovy alebo dekompresie získať vstup a proces obnovy sa nazýva dekompresia alebo dekompresia a až po procese dekompresie sú údaje vhodné na spracovanie v súlade s ich vnútorným formátom. Bezstratová kompresia sa používa pre text, spustiteľné súbory, vysokokvalitný zvuk a grafiku.

Nevratná kompresia 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. V praxi existuje široká škála praktických problémov, pri ktorých nie je dodržiavanie požiadavky presného obnovenia pôvodných informácií po dekompresii povinné. To platí najmä pre kompresiu multimediálnych informácií: zvukové, fotografické alebo video obrázky. Široko používané sú napríklad multimediálne formáty JPEG a MPEG, ktoré používajú nevratnú kompresiu. Ireverzibilná kompresia sa zvyčajne nepoužíva v spojení s kryptografickým šifrovaním, pretože hlavnou požiadavkou na kryptosystém je identita dešifrovaných údajov s pôvodnými. Pri použití multimediálnych technológií však údaje uvedené v digitálna forma sú často nevratne skomprimované predtým, ako sú vložené do kryptografického systému na šifrovanie. Potom, čo sú informácie prenesené k spotrebiteľovi a dešifrované, sú multimediálne súbory použité v komprimovanej forme (to znamená, že nie sú obnovené).

Pozrime sa podrobnejšie na niektoré z najbežnejších spôsobov reverzibilnej kompresie údajov.

Najslávnejším jednoduchým prístupom a algoritmom pre reverzibilnú kompresiu informácií je Run Length Encoding (RLE). Podstatou metód tohto prístupu je nahradiť reťazce alebo série opakujúcich sa bajtov jednou kódujúcou bajtovou výplňou a počítadlom počtu ich opakovaní. Problémom všetkých analogických metód je len určiť spôsob, akým by algoritmus rozbaľovania dokázal rozlíšiť kódované série vo výslednom bajtovom toku od iných, nekódovaných bajtových sekvencií. Riešenie problému sa zvyčajne dosiahne umiestnením štítkov na začiatok kódovaných reťazcov. Takýmto označením môžu byť charakteristické bitové hodnoty v prvom bajte kódovaného cyklu, hodnoty prvého bajtu kódovaného cyklu. Nevýhodou metódy RLE je pomerne nízky kompresný pomer alebo náklady na kódovanie súborov s malým počtom sérií a čo je ešte horšie, s malým počtom opakujúcich sa bajtov v sérii.

Pri jednotnom kódovaní informácií je správe priradený rovnaký počet bitov bez ohľadu na pravdepodobnosť jej výskytu. Zároveň je logické predpokladať, že celková dĺžka prenášaných správ sa zníži, ak budú časté správy kódované krátkymi kódovými slovami a vzácne - dlhšími. Problémy vznikajúce v tomto prípade sú spojené s potrebou použitia kódy s premennou dĺžkou... Existuje mnoho prístupov k vytváraniu takýchto kódov.

Jednou z najpoužívanejších v praxi sú slovníkové metódy, ktorých hlavnými predstaviteľmi sú algoritmy rodín Ziv a Lempel. Ich hlavnou myšlienkou je, že fragmenty vstupného prúdu („frázy“) sú nahradené ukazovateľom na miesto, kde sa už v texte objavili. V literatúre sa tieto algoritmy označujú ako algoritmy Kompresia LZ.

Táto metóda sa rýchlo prispôsobí štruktúre textu a dokáže kódovať krátke funkčné slová, pretože sa v nej vyskytujú veľmi často. Nové slová a frázy je možné vytvárať aj z častí predtým stretnutých slov. Dekódovanie komprimovaného textu sa vykonáva priamo - existuje jednoduché nahradenie ukazovateľa hotovou frázou zo slovníka, na ktorý ukazuje. V praxi metóda LZ dosahuje dobrú kompresiu, jej dôležitou vlastnosťou je veľmi rýchla práca dekodéra.

Ďalší prístup k kompresii informácií je Huffmanov kód, ktorého kodér a dekodér majú pomerne jednoduchú hardvérovú implementáciu. Myšlienka algoritmu je nasledovná: Keď poznáme pravdepodobnosti výskytu znakov v správe, môžeme popísať postup na zostavenie kódov s premennou dĺžkou pozostávajúcich z celočíselného počtu bitov. Symboly majú väčšiu pravdepodobnosť priradenia viac ako krátke kódy, pričom menej bežné znaky sú dlhšie. Tým sa dosiahne zníženie priemernej dĺžky kódového slova a vyššia účinnosť kompresie. Huffmanov kódy majú jedinečnú predponu (začiatok kódového slova), ktorá im umožňuje napriek ich variabilnej dĺžke ich jedinečné dekódovanie.

Syntetický postup pre klasický Huffmanov kód kóduje prítomnosť a priori informácií o štatistických charakteristikách zdroja správy. Inými slovami, vývojár si musí byť vedomý pravdepodobnosti výskytu určitých symbolov, z ktorých sa tvoria správy. Uvažujme o syntéze Huffmanovho kódu na jednoduchom príklade.

p (S 1) = 0,2, p (S 2) = 0,15, p (S 3) = 0,55, p (S 4) = 0,1... Zoradme symboly v zostupnom poradí pravdepodobnosti výskytu a predstavme ich vo forme tabuľky (obr. 14.3, a).

Procedúra syntézy kódu pozostáva z troch hlavných fáz. V prvej fáze sa riadky tabuľky sklopia: dva riadky zodpovedajúce symbolom s najnižšou pravdepodobnosťou výskytu sa nahradia jedným s celkovou pravdepodobnosťou, potom sa tabuľka znova usporiada. Konvolucia pokračuje, kým nie je v tabuľke iba jeden riadok s celkovou pravdepodobnosťou rovnou jednej (obr. 14.3, b).

Ryža. 14.3.

V druhej fáze je zostavený kódový strom pomocou zbalenej tabuľky (obr. 14.4, a). Strom je zostavený od posledného stĺpca tabuľky.

Ryža. 14.4.

Koreň stromu tvorí jednotku v poslednom stĺpci. V uvažovanom príklade je táto jednotka vytvorená z pravdepodobností 0,55 a 0,45, znázornených ako dva stromové uzly spojené s koreňom. Prvý z nich zodpovedá symbolu S 3, a preto nedochádza k ďalšiemu vetveniu tohto uzla.

Druhý uzol označený s pravdepodobnosťou 0,45 sa pripája k dvom uzlom tretej úrovne s pravdepodobnosťou 0,25 a 0,2. Pravdepodobnosť 0,2 zodpovedá symbolu S 1 a pravdepodobnosť 0,25 je zase vytvorená z pravdepodobností 0,15 vzhľadu symbolu S 2 a 0,1 vzhľadu symbolu S 4.

Hrany spájajúce jednotlivé uzly stromového kódu sú očíslované 0 a 1 (napríklad ľavé okraje sú 0 a pravé hrany sú 1). V tretej, záverečnej fáze, je zostavená tabuľka, v ktorej sú porovnané zdrojové symboly a zodpovedajúce Huffmanovo kódové slová. Tieto kódové slová sa tvoria prečítaním čísel, ktoré označujú okraje, ktoré tvoria cestu od koreňa stromu k zodpovedajúcemu symbolu. Pre uvažovaný príklad bude mať Huffmanov kód formu uvedenú v tabuľke vpravo (obr. 14.4, b).

Klasický Huffmanov algoritmus má však jednu významnú nevýhodu. Na obnovenie obsahu komprimovanej správy musí dekodér poznať tabuľku frekvencií, ktorú používa kodér. V dôsledku toho sa dĺžka komprimovanej správy zvýši o dĺžku frekvenčnej tabuľky, ktorá sa má odoslať pred údaje, čo môže negovať všetky snahy o kompresiu správy.

Ďalší variant statické Huffmanovo kódovanie spočíva v prezeraní vstupného toku a vytváraní kódovania na základe zhromaždených štatistík. V tomto prípade sú potrebné dva priechody súborom - jeden na prezeranie a zhromažďovanie štatistických informácií a druhý na kódovanie. V statickom Huffmanovom kódovaní sú vstupné symboly (bitové reťazce rôznych dĺžok) asociované s bitovými reťazcami variabilnej dĺžky - ich kódmi. Dĺžka kódu každého symbolu sa berie úmerne k binárnemu logaritmu jeho frekvencie, pričom sa berie s opačným znamienkom. A spoločný súbor všetkých rôznych symbolov, s ktorými sa stretnete, tvorí abeceda prúdu.

Existuje aj iná metóda - adaptívna resp dynamické Huffmanovo kódovanie... Jeho všeobecný princíp je zmeniť kódovaciu schému v závislosti od povahy zmien vo vstupnom toku. Tento prístup má jednopriechodový algoritmus a nevyžaduje ukladanie informácií o použitom kódovaní v explicitnej forme. Adaptívne kódovanie môže poskytnúť vyšší kompresný pomer ako statické kódovanie, pretože zmeny frekvencií vstupného toku sú viac zohľadnené. Pri použití adaptívneho Huffmanovho kódovania spočíva zložitosť algoritmu v potrebe neustále upravovať strom a kódy znakov základnej abecedy v súlade s meniacou sa štatistikou vstupného toku.

Huffmanovej metódy poskytujú pomerne vysokú a strednú rýchlosť dobrá kvalita kompresia. Huffmanovo kódovanie má však minimálnu redundanciu za predpokladu, že každý znak je kódovaný v abecede kódov znakov oddeleným reťazcom dvoch bitov - (0, 1). Hlavná nevýhoda táto metóda je závislosť kompresného pomeru na blízkosti pravdepodobností symbolov k 2 do určitej negatívnej miery, čo je spôsobené skutočnosťou, že každý symbol je kódovaný celým počtom bitov.

Úplne iné riešenie ponúka aritmetické kódovanie... Táto metóda je založená na myšlienke prevodu vstupného toku na jedno číslo s pohyblivou rádovou čiarkou. Aritmetické kódovanie je technika, ktorá umožňuje bezstratové balenie znakov vstupnej abecedy za predpokladu, že je známe frekvenčné rozdelenie týchto znakov.

Odhadovaná požadovaná postupnosť znakov komprimovaných metódou aritmetického kódovania sa považuje za binárnu frakciu z intervalu)