Metody komprese dat. Metody komprese informací

Odeslat svou dobrou práci do znalostní báze je jednoduché. Použijte níže uvedený formulář

Studenti, postgraduální studenti, mladí vědci, kteří využívají znalostní základnu ve svém studiu a práci, vám budou velmi vděční.

Hostováno na http://www.allbest.ru/

Komprese dat

1. Informace. Jeho druhy a vlastnosti

V literatuře lze nalézt poměrně mnoho definic pojmu „informace“, které reflektují různé přístupy k výkladu tohoto pojmu. Slovník Ruský jazyk Ozhegova uvádí 2 definice slova „informace“:

Informace o okolním světě a procesech v něm probíhajících, vnímané člověkem nebo speciálním zařízením.

Zprávy informující o stavu věcí, o stavu něčeho. (Vědecko-technické a novinové informace, masmédia - tisk, rozhlas, televize, kino).

Informace a jejich vlastnosti jsou předmětem studia řady vědních oborů, jako je teorie informace (matematická teorie systémů přenosu informací), kybernetika (nauka o komunikaci a řízení ve strojích a zvířatech, ale i ve společnosti a člověku). bytostí), sémiotika (nauka o znacích a znakových systémech), teorie masová komunikace(studium médií a jejich vlivu na společnost), informatika (nauka o procesech shromažďování, přeměny, ukládání, ochrany, vyhledávání a předávání všech typů informací a prostředků jejich automatizovaného zpracování), fyzika a matematika.

Informace mají dvojí charakter: materiální – lze je přenášet, ukládat atd.; a nehmotné - podle síry převodovky lze doplnit. Informace bez ní nemohou existovat nosič materiálu, prostředky pro jeho přenos v prostoru a čase. Fyzický objekt sám o sobě nebo jeho energetický ekvivalent může fungovat jako nosič zvukových, světelných, elektrických a jiných signálů.

K tomu bylo v současnosti vynalezeno mnoho metod pro ukládání informací na externích (vzhledem k lidskému mozku) médií a jejich přenos na velké vzdálenosti.

Hlavní typy informací ve formě jejich prezentace, způsoby jejich kódování a ukládání, které má nejvyšší hodnotu pro informatiku je to:

· grafický nebo obrazový - první typ, pro který byl implementován způsob ukládání informací o okolním světě ve formě skalních maleb a později ve formě maleb, fotografií, diagramů, kreseb na papíře, plátně, mramoru a dalších materiálech zobrazujících obrázky skutečného světa;

· zvuk- svět kolem nás je plný zvuků a problém jejich ukládání a replikace byl vyřešen vynálezem zařízení pro záznam zvuku v roce 1877; jeho rozmanitostí jsou hudební informace - pro tento typ byla vynalezena metoda kódování pomocí speciálních znaků, která umožňuje ukládat je podobným způsobem grafické informace;

· textový- způsob kódování lidské řeči speciální znaky- dopisy a různé národy různé jazyky a používat různé sady písmena pro zobrazení řeči; tato metoda se stala zvláště důležitou po vynálezu papíru a tisku;

· číselné- kvantitativní měření objektů a jejich vlastností v okolním světě; nabylo zvláště velkého významu s rozvojem obchodu, hospodářství a směny peněz; rovněž textové informace k jeho zobrazení se používá metoda kódování se speciálními znaky - čísly a kódovací systémy (čísla) mohou být různé;

· informace o videu- způsob, jak zachovat "živé" obrazy světa kolem nás, které se objevily s vynálezem kinematografie.

K přenosu informací do dlouhé vzdálenosti zpočátku se používaly kódované světelné signály, s vynálezem elektřiny - přenos signálu kódovaného určitým způsobem po drátech, později - pomocí rádiových vln.

S příchodem počítačů (nebo, jak se u nás poprvé říkalo počítačům – elektronickým počítačům), prostředku pro zpracování číselné informace. Nicméně v budoucnu, zejména po širokém používání osobní počítače(PC) se počítače začaly používat pro ukládání, zpracování, přenos a vyhledávání textových, numerických, obrazových, zvukových a obrazových informací. Od nástupu prvních osobních počítačů – PC (80. léta 20. století) – je až 80 % jejich pracovní doby věnováno práci s textovými informacemi.

Ukládání informací při používání počítačů se provádí na magnetické disky nebo stuhy, laserové disky(CD a DVD), speciální energeticky nezávislá paměťová zařízení (flash paměť atd.). Tyto metody se neustále zdokonalují, vymýšlejí se nová zařízení a nosiče informací. Zpracování informací (reprodukce, konverze, přenos, záznam na externí média) provádí procesor počítače. Pomocí počítače je možné vytvářet a ukládat nové informace jakéhokoli druhu, pro které speciální programy používané na počítačích a vstupních zařízeních.

Za zvláštní typ informací lze v současnosti považovat informace prezentované v globální síť Internet. Využívá speciální techniky pro ukládání, zpracování, vyhledávání a přenos distribuovaných informací velkých objemů a speciální způsoby práce s nimi různé typy informace. Neustále se zlepšovat software, která zajišťuje kolektivní práci s informacemi všeho druhu.

Informační vlastnosti

Lze citovat mnoho různých vlastností informací. Každá vědní disciplína zvažuje ty, které jsou pro ni důležitější. Z hlediska informatiky jsou nejdůležitější tyto vlastnosti:

1. Objektivita a subjektivita informací. Za objektivnější informaci se považuje ta informace, do které metody vnášejí menší subjektivní prvek. Během informačního procesu míra objektivity informací je vždy snížena.

2. Úplnost informací. Úplnost informací do značné míry charakterizuje kvalitu informací a určuje dostatečnost dat pro rozhodování nebo pro vytváření nových dat na základě stávajících.

3. Spolehlivost informací. Data se vyskytují v okamžiku registrace signálů, ale ne všechny signály jsou "užitečné" - vždy existuje úroveň cizích signálů.

5. Dostupnost informací.

6. Relevance.

2. Komprese dat

Známé pravidlo v počítačový svět ta kapacita pevný disk se moc neděje. Ve skutečnosti je těžké s ním nesouhlasit: bez ohledu na to, jak velký pevný disk se může při nákupu zdát, rychle se ucpe jakýmkoli zbytečné informace. Protože je škoda vše smazat, vyplatí se čas od času všechny tyto věci „uložit“ do nějakého úložiště, archivu.

Skomprese dat- postup pro překódování dat, prováděný za účelem snížení jejich objemu. Používá se pro racionálnější využití zařízení pro ukládání a přenos dat. Pokud se na hotové dokumenty aplikují metody komprese informací, pak se pojem „komprese dat“ často nahrazuje pojmem „archivace dat“.

Komprese je založena na odstranění redundance informací obsažených v původních datech. Příkladem redundance je opakování fragmentů v textu (například slova přirozeného nebo strojového jazyka). Taková redundance je obvykle eliminována nahrazením opakující se sekvence kratší hodnotou (kódem). Další typ redundance je způsoben tím, že některé hodnoty se v komprimovaných datech vyskytují častěji než jiné, přičemž je možné nahradit často se vyskytující data kratšími kódy a vzácná delšími (pravděpodobnostní komprese). Komprese dat, která nemají vlastnost redundance (např. náhodný signál nebo hluk) je nemožné bez ztráty. Obvykle také není možné komprimovat šifrované informace.

Algoritmy pro kompresi textů / souborů neznámého formátu

Existují 2 hlavní přístupy ke kompresi souborů neznámého formátu.

V každém kroku kompresního algoritmu je buď další znak umístěn tak, jak je (se speciálním příznakem označujícím, že není komprimován), nebo jsou určeny hranice slova z předchozího bloku, který odpovídá dalším znakům v souboru. Rozbalování souborů komprimovaných tímto způsobem je velmi rychlé, proto se tyto algoritmy používají k vytváření samorozbalovacích programů.

Pro každou sekvenci se v každém okamžiku shromažďuje statistika jejího výskytu v souboru. Na základě těchto statistik se vypočítá pravděpodobnost hodnot pro další symbol. Některá forma entropického kódování, jako je aritmetické kódování nebo Huffmanovo kódování, pak může být použita k nahrazení často se vyskytujících sekvencí kratšími a méně časté sekvencemi delšími.

Komprese může být bezeztrátová (kdy je možné obnovit původní data bez zkreslení) nebo ztrátová (obnova je možná s deformacemi, které jsou z hlediska dalšího využití obnovených dat nevýznamné). Při zpracování se běžně používá bezeztrátová komprese počítačové programy a data, méně často - ke snížení hlasitosti informací o zvuku, fotografiích a videu. Ztrátová komprese se používá ke snížení hlasitosti audio, foto a video informací, je mnohem efektivnější než bezztrátová komprese.

3. Software pro kompresi dat

Pokud se na hotové dokumenty použijí metody komprese informací. Pojem „komprese dat“ je často nahrazen pojmem „archivace dat“ a software které tyto operace provádějí, se nazývají archivátory.

Archivátory jsou určeny ke kompresi souborů, tzn. snížit jejich místo na disku. Umožňují pomocí speciálních metod balení informací komprimovat informace na disky a vytvářet kopie souborů do jednoho archivního souboru. Navzdory tomu, že množství paměti počítače neustále roste, potřeba archivace neklesá.

Archivace se tedy může hodit:

1) Při ukládání kopií souborů a disket, protože disketa má omezenou velikost;

2) Pro uvolnění místa na pevném disku;

3) Při přenosu informací po síti.

Archivace informací je taková transformace informace, při které se nezmenšuje její objem, ale množství informací zůstává stejné.

Komprimovaný soubor se nazývá archiv. archivní soubor- jedná se o speciálně organizovaný soubor obsahující jeden nebo více souborů v komprimované a nekomprimované podobě a servisní informace o jejich názvech.

Stupeň komprese informací závisí na typu zdrojového souboru, na použitém programu a také na zvoleném způsobu balení. Nejlepší soubory ke kompresi grafické objekty, textové soubory a datové soubory, u kterých může kompresní poměr dosáhnout 5-40 %, soubory jsou komprimovány méně spustitelné programy a boot moduly -60-90%.

Různí vývojáři vytvořili mnoho archivačních programů. Mezi nejběžnější pro Windows patří WINRAR, WINZIP.

Díky své popularitě archivátor WinRAR , je bezpochyby na prvním místě v Rusku a jedním z prvních - na celém světě. Archivátor vyvinul Evgeny Roshal v roce 2003. Program poskytuje plná kontrola soubory v archivech, obnova poškozené archivy, šifrování, vytváření samorozbalovacích a vícesvazkových archivů.

WinZip je jedním z nejpopulárnějších programů na internetu, který získal značný počet ocenění od různých počítačových publikací po celém světě.

Zip sám - algoritmus je volně používán v desítkách programů, ale pro velmi mnoho Uživatelé Windows PŘESNĚ WinZip je standardní program pracovat s archivy. Vestavěné nástroje pro zpracování archivů WinZIP umožňují sbalit, prohlížet a extrahovat soubory z široce používaných archivních formátů, jako jsou ZIP, CAB, Microsoft Compress, GZIP, TAR atd. WinZip je velmi jednoduchý a snadno použitelný.

Ne vždy je však opodstatněné používat samostatné archivátory s vlastními grafické shelly. Nejpohodlnější shell pro archivátory je obvyklý správce souborů, například Windows Commander, který má možnost prohlížet a rozbalovat archivní soubory ZTP, ARJ, RAR, TAR, GZ, CAB, ACE. Přesto se většina operací se soubory, včetně archivů, provádí v těchto správcích.

4. Ztrátová komprese dat

Ztrátová komprese dat je metoda komprese dat, kde se dekomprimovaný soubor liší od originálu, ale je „dostatečně blízko“, aby byl nějakým způsobem užitečný. Tento typ komprese se často používá na internetu, zejména při streamování a telefonování. Tyto metody se v této souvislosti často označují jako kodeky. Alternativou je bezztrátová komprese.

Typy ztrátové komprese

Existují dvě hlavní schémata ztrátové komprese:

V transformačních kodecích se snímají snímky obrazu nebo zvuku, rozřezávají se na malé segmenty, transformují se do nového základního prostoru a provádí se kvantizace. Výsledek je pak komprimován entropickými metodami.

V prediktivních kodecích se předchozí a/nebo následující data používají k predikci aktuálního snímku obrazu nebo zvuku. Chyba mezi predikovanými daty a skutečnými daty, spolu s dodatečnými informacemi potřebnými k vytvoření predikce, je poté kvantována a zakódována.

Některé systémy kombinují tyto dvě techniky pomocí transformačních kodeků ke kompresi chybných signálů generovaných během fáze predikce.

Ztrátová vs bezztrátová komprese

Výhodou ztrátových kompresních metod oproti metodám bezztrátové komprese je, že první výrazně překonávají kompresní poměr a přitom stále splňují požadavky.

Ke kompresi zvuku nebo obrázků se často používají techniky ztrátové komprese.

V takových případech může být dekomprimovaný soubor velmi odlišný od originálu na úrovni bit po bitu, ale ve většině praktických aplikací prakticky nerozeznatelný pro lidské ucho nebo oko.

Mnoho metod se zaměřuje na strukturální rysy lidských smyslových orgánů. Psychoakustický model definuje, kolik zvuku lze komprimovat, aniž by došlo ke snížení vnímané kvality zvuku. Nedokonalosti způsobené ztrátovou kompresí, které jsou viditelné pro lidské ucho nebo oko, se nazývají kompresní artefakty.

Ztrátově komprimovaná zvuková data nejsou soudy akceptována jako hmotný důkaz (a ani se k nim nepřihlíží) z důvodu, že komprimované informace nabývají kompresních artefaktů a ztrácejí přirozený šum prostředí, ze kterého byl záznam pořízen. V této souvislosti není možné určit, zda je nahrávka pravá nebo syntetizovaná. Proto se doporučuje pořizovat důležité nahrávky ve formátu PCM nebo použít magnetofon.

Fotografie zaznamenané v formát JPEG, může být soudem akceptován (i přesto, že data prošla ztrátovou kompresí). Zároveň ale musí být poskytnut fotoaparát, kterým byly vyrobeny, případně odpovídající tabulka podání barev.

Ztrátové metody komprese dat

v Komprese obrazu:

Snížená barevná hloubka

· Metoda hlavní složky;

· Fraktální komprese;

v Komprese videa:

Flash (podporuje také pohyb obrázky JPEG);

MPEG-1 část 2;

· MPEG-2 část 2;

· MPEG-4 část 2;

v Komprese zvuku:

· MP3 - Definováno specifikací MPEG-1;

Ogg Vorbis (pozoruhodný pro absenci patentových omezení a další vysoká kvalita);

· AAC, AAC+ - existuje v několika verzích definovaných specifikacemi MPEG-2 a MPEG-4, používanými např. v Apple Computer;

eAAC+ je formát nabízený společností Sony jako alternativa k AAC a AAC+;

· WMA - vlastnictví společnosti Microsoft;

ztráta archivátoru komprese informací

5. Bezeztrátová komprese dat

Bezeztrátová komprese(angl. Bezztrátová komprese dat) - metoda komprese informací, pomocí které lze zakódované informace obnovit s přesností na bit. V tomto případě jsou původní data zcela obnovena z komprimovaného stavu. Tento typ komprese se zásadně liší od ztrátové komprese dat. Pro každý typ digitální informace Zpravidla existují optimální bezeztrátové kompresní algoritmy.

Bezztrátová komprese dat se používá v mnoha aplikacích. Používá se například v populárním souboru ZIP formát a unixový nástroj Gzip. Používá se také jako komponent ve ztrátové kompresi.

Bezeztrátová komprese se používá, když je důležitá identita komprimovaných dat s originálem. Častým příkladem je spustitelné soubory A zdroj. Nějaká grafika formáty souborů, jako je PNG nebo GIF, používejte pouze bezeztrátovou kompresi; zatímco jiné (TIFF, MNG) mohou používat ztrátovou i bezeztrátovou kompresi.

Technika bezztrátové komprese

Z kombinatoriky vyplývá, že neexistuje žádný bezeztrátový kompresní algoritmus, který by dokázal zmenšit jakýkoli soubor alespoň o jeden bajt. To však není známkou kvality kompresního algoritmu – algoritmus musí efektivně pracovat s daty, pro která je navržen.

Víceúčelové kompresní algoritmy se vyznačují tím, že jsou schopny redukovat širokou škálu dat - spustitelné soubory, datové soubory, texty, grafiku atd. a používají se v archivátorech. Specializované algoritmy jsou navrženy pro určitý typ souborů (text, grafika, zvuk atd.), ale komprimují takové soubory mnohem silněji. Například: archivátory komprimují zvuk přibližně na třetinu (1,5krát), zatímco FLAC jej komprimuje na 2,5krát. Většina specializovaných algoritmů je pro „mimozemské“ typy souborů málo použitelná: například zvuková data jsou špatně komprimována algoritmem určeným pro texty.

Většina bezeztrátových kompresních algoritmů pracuje ve dvou fázích: první generuje statistický model pro příchozí data, druhý bitmapuje příchozí data, přičemž pomocí modelu vytváří „pravděpodobnostní“ (tj. často se vyskytující) data, která se používají častěji než "nepravděpodobné" údaje.

Modely statistických algoritmů pro text (nebo textová binární data, jako jsou spustitelné soubory) zahrnují:

Burrows-Wheelerova transformace (předzpracování blokového třídění, které zefektivňuje kompresi)

LZ77 a LZ78 (pomocí DEFLATE)

Algoritmy kódování prostřednictvím generování bitových sekvencí:

Huffmanův algoritmus (také používá DEFLATE)

aritmetické kódování

Bezeztrátové kompresní metody

· Víceúčelový

· Kódování délek běhů - jednoduchý obvod, což poskytuje dobrou kompresi dat obsahujících mnoho duplicitních hodnot

· LZW - používá se v gif a mnoha dalších.

· Deflate – používá se v gzip, pokročilé verzi zipu, a jako součást procesu komprese PNG.

· LZMA - používá se v 7-zip.

v Komprese zvuku:

· Apple Lossless - ALAC (Apple Lossless Audio Codec);

· Audio Lossless Coding – také známé jako MPEG-4 ALS;

· Direct Stream Transfer - DST;

· Bezeztrátový zvukový kodek - FLAC;

v Komprese grafiky

ABO - Adaptivní binární optimalizace;

· GIF - (bezeztrátový pouze pro obrázky obsahující méně než 256 barev);

· JBIG2 - (se ztrátovými černobílými obrazy nebo bez nich);

· JPEG-LS - (bezztrátový / téměř bezztrátový standard komprese);

· JPEG 2000 - (zahrnuje bezeztrátovou kompresi; testováno také Sunilem Kumarem, profesorem Státní univerzity v San Diegu);

· PGF - Progressive Graphics File (komprese se ztrátou/bez ztráty);

PNG – přenosná síťová grafika;

· WMPhoto - (včetně metody bezztrátové komprese);

v Komprese videa

Animační kodek;

· Video kodek CamStudio;

6. Ukládání informací (textové, grafické, zvukové)

Informace se ukládají pomocí určitých paměťových médií. Člověk si své znalosti ukládá buď do své paměti, nebo na nějaké externí médium.

Nejprve člověk používal svou paměť k ukládání a hromadění informací – přijaté informace si jednoduše zapamatoval a nějakou dobu si je zapamatoval. Postupně lidé přišli na to, že tento způsob uchovávání informací má řadu nevýhod. Uvědomil si nespolehlivost takového způsobu ukládání a shromažďování informací, a proto začal zapisovat informace ve formě kreseb s vynálezem písma - na papyrus a později do knih. Poté se jako prvky objevily fotografické desky a zařízení pro záznam zvuku externí paměť obrazové a zvukové informace, notebooky, adresáře, encyklopedie atd., kterým říkáme externí úložiště dat. V polovině 20. století byl vynalezen počítač. Okamžitě vyvstala otázka, jak bude informace uchovávat.

Nosič informace může být různého charakteru: papír. Mechanické, magnetické, elektrické. Informace zaznamenané na médiu mohou být ve formě symbolu čitelného člověkem nebo v zakódované formě. Informace pro magnetofon, videorekordér, videokameru - zvuk uložené na speciálních zařízeních: audiokazety, videokazety, filmy. Pomocí mikrofonu a dalších zařízení se zvukové informace zaznamenávají na magnetickou pásku.

V počítačích se jako zařízení pro zápis začalo používat čtení informací: čtečky děrných štítků; magnetické páskové jednotky, disketové (diskové jednotky) a pevné (pevné disky) magnetické diskové jednotky; jednotky kompaktních disků (CD-ROM) a další moderní zařízení hromadění a ukládání informací.

Bibliografický seznam

1. Federální zákon Ruské federace „o informacích, informatizaci a ochraně informací“ ze dne 27. července 2006 č. 149-FZ.

2. Levin A.Sh. Počítačový tutoriál. - Petrohrad: Petr, 2006. - 655 s.

3. Romanova N.I. Základy informatiky. - Petrohrad: Polytechnika, 2004. -224 s.

4. Simonovič S.V. Počítačová věda. Základní kurz. - Petrohrad: Petr, 2008 - 640 s.

Hostováno na Allbest.ru

Podobné dokumenty

Typy komprese dat: ztrátová (ztrátová) a bezztrátová (bezztrátová). Komprese s minimální redundancí. Shannon-Fano kódování. Kontrola programu pro kompresi souborů bmp a xls. Implementace Shannonova a Huffmanova kompresního algoritmu v Delphi.

semestrální práce, přidáno 26.01.2011


Klasifikace a hlavní charakteristiky metody komprese dat. Výpočet kompresních poměrů a odhad jejich účinnosti. Algoritmy pro polynomiální, extrapolační a interpolační kompresní metody a jejich srovnání. Optimální lineární predikce.

semestrální práce, přidáno 17.03.2011


Archivace a komprese jako metody komprese obrazu. Algoritmy komprese dat. Pomocné nástroje, které se používají ke snížení velikosti souborů: změna barevný model obrázky, změna rozlišení bitmapový soubor, převzorkování.

prezentace, přidáno 01.06.2014


Studium hlavních typů archivačních programů. Komprimace souborů při archivaci. Stupeň komprese souboru. Hodnocení funkčnosti nejoblíbenějších baličů. Specifikace kompresní procesy. Bezeztrátové metody archivace.

abstrakt, přidáno 12.5.2013


Zveřejnění účelu komprese souborů a popis účelu archivátorů jako programů, které balí a rozbalují soubory do archivu pro usnadnění přenosu a ukládání. Hlavní typy archivátorů: soubor, program, disk. Bezeztrátová kompresní metoda.

prezentace, přidáno 04.05.2011


Základní pojmy a metody komprese dat. Převod informací uložených v souboru do formy, která snižuje redundanci při jejich prezentaci. Statistické a slovníkové kompresní metody. Archivace programů, hlavní funkce WinRAR.

kontrolní práce, přidáno 3.12.2011


Krátká recenze hlavní teorie komprese. Koncepty nápadů a jejich realizace. Komprese dat pomocí Burrows-Wheelerovy transformace. Statický Huffmanův algoritmus. Lokálně adaptivní kompresní algoritmus. Algoritmus Ziv-Lempel (Welch) a metoda Shannon-Fano.

praktické práce, přidáno 24.04.2014


Entropie a množství informací. Kombinatorický, pravděpodobnostní a algoritmický odhad množství informací. Modelování a kódování. Některé algoritmy komprese dat. Aritmetický kódovací algoritmus. Přírůstkové odesílání a přijímání.

semestrální práce, přidáno 28.07.2009


Použití algoritmů, které poskytují vysoký stupeň komprese pro zvýšení rychlosti přenosu dat komunikačními kanály. Vlastnosti a metody hledání singulárního rozkladu hodnot. Vývoj programu, který implementuje kompresi obrazu pomocí SVD komprese.

práce, přidáno 13.10.2015


Programy pro vytváření archivů. Účinnost komprese dat as nejdůležitější charakteristika archivátory. Základní metody komprese dat. Charakteristika programu pro balení textů a programy WinRar. Rozbalení souborů, sbalení souborů a složek do sdíleného archivu.

Účel přednášky: studovat hlavní typy a algoritmy komprese dat a naučit se řešit problémy s kompresí dat pomocí Huffmanovy metody a pomocí kódových stromů.

Claude Shannon je považován za zakladatele vědy o kompresi informací. Jeho optimální kódovací teorém ukazuje, o co by se měl člověk při kódování informace snažit a jak moc bude ta či ona informace komprimována. Kromě toho prováděl experimenty s empirickým hodnocením redundance anglického textu. Shannon požádal lidi, aby uhodli další písmeno, a odhadl pravděpodobnost, že uhodnou správně. Na základě řady experimentů dospěl k závěru, že množství informací v anglickém textu kolísá mezi 0,6 - 1,3 bity na znak. Navzdory skutečnosti, že výsledky Shannonova výzkumu byly skutečně žádané až o desítky let později, je obtížné přeceňovat jejich význam.

Komprese dat je proces, který snižuje objem dat snížením jejich redundance. Komprese dat je spojena s kompaktním uspořádáním datových bloků. standardní velikost. Komprese dat lze rozdělit do dvou hlavních typů:

• Bezeztrátová komprese (plně reverzibilní)- Jedná se o metodu komprese dat, při které je dříve zakódovaná část dat obnovena po úplné dekomprimaci bez provedení změn. Pro každý typ dat zpravidla existují optimální bezeztrátové kompresní algoritmy.
• Ztrátová komprese je metoda komprese dat, ve které za účelem poskytnutí maximální stupeň komprimaci původního datového pole, část dat v něm obsažených je zahozena. Pro textová, numerická a tabulková data je použití programů, které implementují takové kompresní metody, nepřijatelné. V zásadě se takové algoritmy používají ke kompresi audio a video dat, statických obrázků.

Algoritmus komprese dat (algoritmus archivace) je algoritmus, který eliminuje nadbytečnost záznamu dat.

Uvádíme řadu definic, které budou dále použity při prezentaci materiálu.

Kódová abeceda je množina všech symbolů vstupního proudu. Při kompresi anglických textů se obvykle používá sada 128 ASCII kódů. Při kompresi obrázků může sada hodnot pixelů obsahovat 2, 16, 256 nebo jiný počet prvků.

symbol kódu je nejmenší jednotka dat, která má být komprimována. Obvykle má znak 1 bajt, ale může to být bit, trit (0,1,2) nebo cokoli jiného.

Kódové slovo je sekvence kódových symbolů z kódové abecedy. Pokud mají všechna slova stejnou délku (počet znaků), pak se takový kód zavolá uniforma (pevná délka) a pokud jsou povolena slova různých délek, pak - nerovnoměrné (proměnná délka).

Kód je kompletní sada slov.

Žeton– jednotka dat zapsaná do komprimovaného toku pomocí nějakého komprimačního algoritmu. Token se skládá z několika polí s pevnou nebo proměnnou délkou.

Fráze– část dat umístěná ve slovníku pro další použití při kompresi.

Kódování je proces komprese dat.

Dekódování– proces zpětného kódování, při kterém se provádí obnova dat.

Kompresní poměr je jednou z nejčastěji používaných veličin k označení účinnosti kompresní metody.

Kompresní poměr je převrácená hodnota kompresního poměru.

Hodnoty větší než 1 znamenají kompresi a hodnoty menší než 1 označují expanzi.

Průměrná délka kódového slova je hodnota, která se vypočítá jako pravděpodobnostmi vážený součet délek všech kódových slov.

L cp = p 1 L 1 +p 2 L 2 +...+p n L n ,

kde jsou pravděpodobnosti kódových slov;

L 1 ,L 2 ,...,L n jsou délky kódových slov.

Existují dva hlavní způsoby, jak provést kompresi.

Statistické metody– kompresní metody, které přiřazují znakům ve vstupním toku kódy s proměnnou délkou, přičemž kratší kódy se přiřazují znakům nebo skupinám znaků, které se pravděpodobněji objeví ve vstupním toku. Nejlepší statistické metody Používá se Huffmanovo kódování.

Slovníková komprese jsou kompresní metody, které ukládají části dat do „slovníku“ (něk datová struktura). Pokud je řetězec nových vstupních dat identický s fragmentem, který se již nachází ve slovníku, do výstupního proudu se umístí ukazatel na tento fragment. Nejlepší slovníkové metody používají metodu Ziv-Lempel.

Podívejme se podrobněji na několik známých algoritmů komprese dat.

Huffmanova metoda

Tento algoritmus kódování informací navrhl D.A. Huffman v roce 1952. Huffmanovo kódování (komprese) je široce používaná kompresní metoda, která přiřazuje znaky abecedy kódy s proměnnou délkou založené na pravděpodobnosti výskytu těchto znaků.

Myšlenka algoritmu je následující: se znalostí pravděpodobnosti výskytu znaků ve zdrojovém textu je možné popsat postup pro konstrukci kódů s proměnnou délkou sestávajících z celého čísla bitů. Znakům je pravděpodobnější přiřadit kratší kódy. Při této metodě je tedy při komprimaci dat každému znaku přiřazen optimální prefixový kód na základě pravděpodobnosti jeho výskytu v textu.

Kód předpony je kód, ve kterém žádné kódové slovo není předponou žádného jiného kódového slova. Tyto kódy mají proměnnou délku.

Optimální prefixový kód je prefixový kód s minimální průměrnou délkou.

Huffmanův algoritmus lze rozdělit do dvou etap.

1. Stanovení pravděpodobnosti výskytu znaků ve zdrojovém textu.

   Zpočátku je nutné celý zdrojový text přečíst a vypočítat pravděpodobnosti výskytu znaků v něm (někdy počítají, kolikrát se který znak vyskytuje). Pokud to vezme v úvahu všech 256 znaků, pak nebude žádný rozdíl v komprimaci textu nebo souboru jiného formátu.

2. Nalezení optimálního prefixového kódu.

   Dále jsou nalezeny dva symboly a a b s nejnižší pravděpodobností výskytu a nahrazeny jedním fiktivním symbolem x , který má pravděpodobnost výskytu rovnou součtu pravděpodobností výskytu symbolů a a b . Potom se pomocí tohoto postupu rekurzivně najde optimální kód předpony pro menší sadu znaků (kde jsou znaky aab nahrazeny jediným znakem x ). Kód pro původní znakovou sadu se získá z kódů náhradních znaků přidáním 0 nebo 1 před kód náhradního znaku a tyto dva nové kódy jsou přijaty jako kódy náhradních znaků. Například kód znaku a bude odpovídat kódu x s ​​nulou přidanou před tímto kódem a pro znak b bude před kód znaku x přidána jednička.

Huffmanovy kódy mají jedinečnou předponu , která umožňuje jejich jednoznačné dekódování i přes jejich proměnnou délku.

Příklad 1. Softwarová implementace Huffmanova metoda.

#include "stdafx.h" #include pomocí jmenného prostoru std; void Expectance(); dlouhé MinK(); void SumUp(); void BuildBits(); void OutputResult(char **Result); voidClear(); const int MaxK = 1000; dlouhé k, a, b; charbity; charsk; bool Zdarma; char*res; dlouhé i, j, n, m, kj, kk1, kk2; charstr; int _tmain(int argc, _TCHAR* argv)( char *BinaryCode; Clear(); cout<< "Введите строку для кодирования: "; cin >>str; očekávání(); shrnout(); BuildBits(); OutputResult(&BinaryCode); cout<< "Закодированная строка: " << endl; cout << BinaryCode << endl; system("pause"); return 0; } //описание функции обнуления данных в массивах void Clear(){ for (i = 0; i < MaxK + 1; i++){ k[i] = a[i] = b[i] = 0; sk[i] = 0; Free[i] = true; for (j = 0; j < 40; j++) bits[i][j] = 0; } } /*описание функции вычисления вероятности вхождения каждого символа в тексте*/ void Expectancy(){ long *s = new long; for (i = 0; i < 256; i++) s[i] = 0; for (n = 0; n < strlen(str); n++) s]++; j = 0; for (i = 0; i < 256; i++) if (s[i] != 0){ j++; k[j] = s[i]; sk[j] = i; } kj = j; } /*описание функции нахождения минимальной частоты символа в исходном тексте*/ long MinK(){ long min; i = 1; while (!Free[i] && i < MaxK) i++; min = k[i]; m = i; for (i = m + 1; i <= kk2; i++) if (Free[i] && k[i] < min){ min = k[i]; m = i; } Free[m] = false; return min; } //описание функции подсчета суммарной частоты символов void SumUp(){ long s1, s2, m1, m2; for (i = 1; i <= kj; i++){ Free[i] = true; a[i] = 0; b[i] = 0; } kk1 = kk2 = kj; while (kk1 >2)( s1 = MinK(); m1 = m; s2 = MinK(); m2 = m; kk2++; k = s1 + s2; a = m1; b = m2; Volné = pravda; kk1--; )) / /popis funkce pro generování prefixových kódů void BuildBits()( strcpy(bits,"1"); Free = false; strcpy(bits],bits); strcat(bits] , "0"); strcpy(bits], bity); strcat(bity] , "1"); i = MinK(); strcpy(bity[m],"0"); Free[m] = true; strcpy(bity],bity[m]); strcat (bits] , "0"); strcpy(bits],bits[m]); strcat(bits] , "1"); for (i = kk2 - 1; i > 0; i--) if (!Free [i] ) ( strcpy(bity],bity[i]); strcat(bity], "0"); strcpy(bity],bity[i]); strcat(bity], "1"); )) / /popis funkce výstup dat void OutputResult(char **Result)( (*Result) = new char; for (int t = 0; i< 1000 ;i++) (*Result)[t] = 0; for (i = 1; i <= kj; i++) res] = bits[i]; for (i = 0; i < strlen(str); i++) strcat((*Result) , res]); } Листинг.

Huffmanův algoritmus je univerzální, lze s ním komprimovat data libovolného typu, ale pro malé soubory je neúčinný (kvůli nutnosti ukládat slovník). V současné době se tato metoda v čisté podobě prakticky nepoužívá, obvykle se používá jako jeden z kompresních stupňů ve složitějších schématech. Toto je 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).

Metody komprese dat mají poměrně dlouhou historii vývoje, která začala dávno před příchodem prvního počítače. Tento článek se pokusí podat stručný přehled hlavních teorií, konceptů myšlenek a jejich implementací, který si však nečiní nárok na absolutní úplnost. Podrobnější informace lze nalézt např. v Krichevsky R.E. , Ryabko B.Ya. , Witten I.H. , Rissanen J., Huffman D.A., Gallager R.G. , Knuth D.E. , Vitter J.S. atd.

Komprese informací je problém, který má poměrně dlouhou historii, mnohem starší než historie vývoje výpočetní techniky, která (historie) obvykle šla souběžně s historií vývoje problému kódování a šifrování informací. Všechny kompresní algoritmy pracují se vstupním proudem informací, jehož minimální jednotkou je bit a maximální jednotkou je několik bitů, bajtů nebo několik bajtů. Cílem kompresního procesu je zpravidla získat kompaktnější výstupní proud informačních jednotek z nějakého původně nekompaktního vstupního proudu pomocí nějaké jejich transformace. Hlavní technické vlastnosti kompresních procesů a výsledky jejich práce jsou:

Stupeň komprese (hodnota komprese) nebo poměr (poměr) objemů zdroje a výsledných toků;

Rychlost komprese - čas strávený komprimací určitého množství informací ve vstupním toku, dokud z něj není získán ekvivalentní výstupní tok;

Kvalita komprese – hodnota ukazující, jak silně je výstupní tok zahuštěn tím, že na něj použijete opětovnou kompresi pomocí stejného nebo jiného algoritmu.

Existuje několik různých přístupů k problému komprese informací. Některé mají velmi složitý teoretický matematický základ, jiné jsou založeny na vlastnostech informačního toku a jsou algoritmicky zcela jednoduché. Jakýkoli přístup a algoritmus, který implementuje kompresi nebo kompresi dat, je navržen tak, aby zmenšil objem výstupního informačního toku v bitech pomocí jeho vratné nebo nevratné transformace. Proto za prvé, podle kritéria spojeného s povahou nebo formátem dat, lze všechny kompresní metody rozdělit do dvou kategorií: vratná a nevratná komprese.

Nevratnou kompresí se rozumí taková transformace vstupního datového toku, kdy výstupní tok na základě určitého informačního formátu představuje z určitého úhlu pohledu objekt, který je vnějšími charakteristikami dosti podobný vstupnímu toku, ale liší se z toho v objemu. Stupeň podobnosti vstupních a výstupních toků je určen mírou korespondence některých vlastností objektu (tj. komprimované a nekomprimované informace v souladu s určitým specifickým datovým formátem) reprezentované tímto informačním tokem. Takové přístupy a algoritmy se používají ke kompresi například dat rastrových grafických souborů s nízkou rychlostí opakování bajtů v proudu. Při tomto přístupu se využívá vlastnosti struktury formátu grafického souboru a schopnosti prezentovat grafický obraz přibližně podobnou kvalitou zobrazení (pro vnímání lidským okem) několika (nebo spíše n) způsoby. Proto kromě stupně nebo velikosti komprese v takových algoritmech vzniká pojem kvality, protože Protože se původní obrázek během procesu komprese mění, lze kvalitu chápat jako míru korespondence mezi originálem a výsledným obrázkem, která se subjektivně posuzuje na základě formátu informací. U grafických souborů je tato korespondence určena vizuálně, ačkoli existují i ​​odpovídající inteligentní algoritmy a programy. Nevratnou kompresi nelze použít v oblastech, kde je nutné mít přesnou shodu mezi informační strukturou vstupního a výstupního toku. Tento přístup je implementován v populárních formátech videa a fotografií známých jako algoritmy JPEG a JFIF a formáty souborů JPG a JIF.

Reverzibilní komprese vede vždy ke snížení objemu výstupního informačního toku bez změny jeho informačního obsahu, tzn. - bez ztráty informační struktury. Vstupní tok lze navíc získat z výstupního toku pomocí dekompresního nebo dekompresního algoritmu a proces obnovy se nazývá dekomprese nebo dekomprese a teprve po procesu dekomprese jsou data vhodná ke zpracování v souladu s jejich vnitřním formátem.

U reverzibilních algoritmů lze kódování považovat za proces ze statistického hlediska, což je ještě užitečnější nejen pro konstrukci kompresních algoritmů, ale také pro hodnocení jejich účinnosti. U všech reverzibilních algoritmů existuje pojem nákladů na kódování. Cena kódování je průměrná délka kódového slova v bitech. Redundance kódování se rovná rozdílu mezi cenou a entropií kódování a dobrý kompresní algoritmus by měl redundanci vždy minimalizovat (připomeňme, že entropie informace je chápána jako míra její neuspořádanosti). Shannonova základní věta o kódování informací říká, že „náklady na kódování nejsou vždy nižší než entropie zdroje, i když se jí může libovolně blížit“. Proto pro jakýkoli algoritmus vždy existuje určitá hranice stupně komprese, určená entropií vstupního proudu.

Pojďme nyní přímo k algoritmickým vlastnostem reverzibilních algoritmů a uvažujme o nejdůležitějších teoretických přístupech ke kompresi dat souvisejících s implementací kódovacích systémů a metod komprese informací.

Komprese kódování série

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 pouze v určení způsobu, jakým by dekompresní algoritmus mohl odlišit zakódovanou řadu od jiných nezakódovaných bajtových sekvencí ve výsledném bajtovém proudu. Ř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 zpravidla velmi účinné pro kompresi bitmapových grafických obrázků (BMP, PCX, TIF, GIF). 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.

Komprese bez použití metody RLE

Proces komprese dat bez použití metody RLE lze rozdělit do dvou fází: modelování (modelování) a vlastně kódování (kódování). Tyto procesy a jejich implementační algoritmy jsou zcela nezávislé a různorodé.

Proces kódování a jeho metody

Kódování je obvykle chápáno jako zpracování proudu znaků (v našem případě bajtů nebo nibble) v nějaké abecedě, přičemž frekvence výskytu znaků v proudu jsou různé. Cílem kódování je převést tento tok na bitový tok minimální délky, čehož je dosaženo snížením entropie 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í. Vzhledem k existenci velkého množství různých formátů souborů se však úkol stává mnohem komplikovanějším. rozdělení frekvence datových symbolů není předem známo. V tomto případě se obecně používají dva přístupy.

První spočívá v prohlížení vstupního toku a konstrukci 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ých informací, druhý pro kódování, což poněkud omezuje rozsah takových algoritmů, protože, tedy , eliminuje možnost jednoprůchodového on-the-fly kódování používaného v telekomunikačních systémech, kde někdy není známo množství dat a jejich opětovné odeslání 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 technika je známá jako statické Huffmanovo kódování.

Úvod.

Komprese snižuje množství místa potřebného k ukládání souborů v počítači a

množství času potřebného k přenosu informací přes určený kanál

šířku pásma. Je to forma kódování. Jiné účely kódování

jsou vyhledávání a oprava chyb a také šifrování. proces vyhledávání a

oprava chyb je opakem komprese – zvyšuje redundanci dat,

když je není třeba prezentovat v lidsky čitelné podobě. Odebírání

z redundance textu podporuje komprese šifrování, což ztěžuje vyhledávání

šifrovat statistickou metodou dostupnou crackerovi.

Uvažujme vratnou kompresi nebo kompresi bez rušení, kde je iniciál

text lze přesně obnovit z komprimovaného stavu. nevratné popř

škodlivá komprese se používá k digitálnímu záznamu analogových signálů, jako je např

lidská řeč nebo kresby. Reverzibilní komprese je zvláště důležitá pro texty

napsané v přirozených a umělých jazycích, protože v tomto případě

chyby jsou obvykle nepřijatelné. Ačkoli primární oblastí použití

z uvažovaných metod je komprese textů, která také odráží naši terminologii,

tato technika však může být použita v jiných případech, včetně reverzibilních

kódování diskrétních datových sekvencí.

Existuje mnoho dobrých důvodů, proč alokovat počítačové zdroje z hlediska komprimace

výkon, protože rychlejší přenos dat a menší prostor pro

jejich skladování ušetří spoustu peněz a často se zlepší

počítačové indikátory. Komprese pravděpodobně zůstane v centru pozornosti kvůli všem

rostoucí množství dat uložených a přenášených do počítače, navíc může být

použít k překonání některých fyzických omezení, jako např.

například relativně malá šířka pásma telefonních kanálů.

APLIKACE EXPANDOVANÝCH STROMŮ PRO KOMPRESI DAT.

Kompresní algoritmy mohou zlepšit efektivitu ukládání a přenosu dat

snížením jejich nadbytečnosti. Zabere kompresní algoritmus

zdrojový text jako vstup a vytváří odpovídající komprimovaný text,

když rozbalovací algoritmus má komprimovaný text jako vstup a přijímá z

vypíše původní text zdroje. Většina kompresních algoritmů

považujte zdrojový text za sadu řetězců skládajících se z písmen abecedy

původní text.

Redundance v reprezentaci řetězce S je L(S) - H(S), kde L(S) je délka

reprezentace v bitech a H(S) - entropie - míra informačního obsahu, také

vyjádřeno v bitech. Algoritmy, které lze komprimovat bez ztráty informací

řetězec na méně bitů, než jeho entropie neexistuje. Pokud od

ze zdrojového textu extrahujte jedno písmeno nějaké náhodné množiny,

pomocí abecedy A se pak entropie zjistí podle vzorce:

H(S) = C(S) p(c) log ----,

kde C(S) je počet písmen v řetězci, p(c) je statická pravděpodobnost

výskyt nějakého písmene C. Pokud se četnost výskytu použije k odhadu p(c)

každé písmeno c v řetězci S, pak H(C) se nazývá vlastní entropie řetězce S.

člen H(S) bude použit k označení vlastní entropie řetězce převzatého z

statický zdroj.

Rozšiřující se stromy obvykle popisují formy lexikografického uspořádání

binární vyhledávací stromy, ale stromy používané při kompresi dat nemusí

být v neustálém pořádku. Eliminace řádu vede k

výrazné zjednodušení základních expanzních operací. Přijato jako výsledek

Algoritmy jsou extrémně rychlé a kompaktní. Při použití Huffmanových kódů

expanze vede k místně přizpůsobenému kompresnímu algoritmu, který

pozoruhodně jednoduché a rychlé, i když nedosahuje optimální komprese.

Když se použije na aritmetické kódy, výsledek komprese se blíží

optimální a přibližně optimální v čase.

PREFIX KÓDY.

Většina široce studovaných algoritmů komprese dat je založena na kódech

Huffman. V Huffmanově kódu je každé písmeno zdrojového textu zastoupeno v archivu

kód s proměnnou délkou. Častější písmena jsou reprezentována krátkými kódy,

méně časté - dlouhé. Kódy použité ve zhuštěném textu se musí řídit

vlastnosti prefixu, a to: kód použitý v komprimovaném textu nemůže být

prefix jakéhokoli jiného kódu.

Předponové kódy lze nalézt prostřednictvím stromu, ve kterém jsou jednotlivé listy

odpovídá jednomu písmenu zdrojové abecedy. Obrázek 1 ukazuje strom kódu

předpona pro abecedu o 4 písmenech. Předponový kód pro písmeno lze přečíst

průchod stromu od kořene k tomuto písmenu, kde 0 odpovídá volbě jeho levé větve,

a 1 - vpravo. Strom Huffmanova kódu je strom s vahou vyrovnaný, kde každý

list má váhu rovnou četnosti výskytu písmene ve zdrojovém textu a

vnitřní uzly nemají vlastní váhu. Strom v příkladu bude optimální, pokud

frekvence písmen A, B, C a D budou 0,125, 0,125, 0,25 a 0,5 v tomto pořadí.

Běžné Huffmanovy kódy vyžadují předchozí informace o frekvenci výskytu

písmen v původním textu, což vede k nutnosti dvojího prohlížení – jedno

pro získání hodnot frekvence písmen, druhý pro provedení samotné komprese. V

Následně musí být hodnoty těchto frekvencí zkombinovány se samotným komprimovaným textem, aby to bylo možné

umožnit jeho nasazení v budoucnu. Probíhá adaptivní komprese

v jednom kroku, protože je založen kód použitý pro každé písmeno zdrojového textu

na frekvencích všech ostatních písmen abecedy kromě něj. Základy pro efektivní

adaptivní implementace Huffmanova kódu byly stanoveny Gallagherem, publikoval Knuth

praktickou verzi takového algoritmu a Witter ji vyvinul.

Optimálně přizpůsobený Witter kód vždy leží v rámci jednoho bitu na

zdrojové písmeno s ohledem na optimální statický Huffmanův kód, který obvykle bývá

je několik procent H. Kromě toho jsou vždy statické Huffmanovy kódy

leží do jednoho bitu na písmeno prostého textu od H (dosahují tohoto

limit pouze tehdy, když pro všechna písmena p(C) = 2). Existují kompresní algoritmy

které mohou tato omezení překonat. Algoritmus Ziv-Lempell, např.

přiřazuje slova z archivu pevné délky k řádkům zdrojového textu

proměnná délka a aritmetická komprese lze použít ke kódování

zdrojová písmena dokonce zlomky bitů.

Použijte rozšíření na kódy předpon.

Rozšířené stromy byly poprvé popsány v roce 1983 a podrobněji

uvažováno v roce 1985. Zpočátku byly chápány jako typ sebevyrovnaných

binární vyhledávací stromy a také se ukázalo, že umožňují

nejrychlejší implementace prioritních front. Pokud je uzel rozšiřujícího stromu

k dispozici, je rozšířena. To znamená, že dostupným uzlem se stane

kořen, všechny uzly nalevo od něj tvoří nový levý podstrom, uzly napravo -

nový pravý podstrom. Rozšíření je dosaženo procházením stromu ze starého

root k cílovému uzlu při provádění místních změn, takže cena

expanze je úměrná délce ujeté dráhy.

Tarjan a Slayton ukázali, že expandující stromy jsou staticky optimální.

Jinými slovy, pokud jsou kódy dostupných uzlů brány podle stat

rozdělení pravděpodobnosti, dále pak rychlost přístupu k rozšiřujícímu se stromu a

staticky vyvážené, optimalizované touto distribucí, bude

se od sebe liší konstantním faktorem, patrným při dostatečně

dlouhá řada přístupů. Protože Huffmanův strom je příkladem

staticky vyvážený strom, pak při použití kompresního rozšíření

data, bude velikost komprimovaného textu ležet v rámci určitého koeficientu od

velikost archivu získaného pomocí Huffmanova kódu.

Jak bylo původně popsáno, rozšíření se vztahuje na stromy, které ukládají

data jsou ve vnitřních uzlech, ne v listech. Stromy předponových kódů nesou vše

jejich údaje pouze v listech. Existuje však možnost rozšíření tzv

semi-přípona, která je použitelná pro strom předponového kódu. S ním, cíl

uzel se nepřesune do kořene a jeho potomci se nezmění,

místo toho se cesta od kořene k cíli jednoduše zkrátí na polovinu. Poloviční expanze dosahuje

stejné teoretické meze v rámci konstantního koeficientu jako

rozšíření.

V případě klikatého procházení lexikografického stromu, držení jako

prodloužení a poloviční prodloužení se na rozdíl od přímé trasy podél

levý nebo pravý okraj stromu k cílovému uzlu. Tento jednoduchý případ je znázorněn v

Obrázek 2. Dopad polovičního prodloužení na cestu od kořene (uzel w) k listu

uzel A má zaměnit každý pár vnitřních za sebou

další uzly, v důsledku čehož se délka cesty od kořenového k listovému uzlu zkrátí o

2krát. V procesu semi-expanze uzly každého páru, vzdálenější od kořene,

jsou zahrnuty v nové cestě (uzly x a z) a bližší z ní

jsou vyloučeny (uzly w a y).

Zachování lexikografického řádu v kódových stromech pomocí semi-expanzní operace

předpona je volitelná. Důležité pouze při operacích s kódem

prefix je přesná shoda stromu použitého kompresní rutinou

strom používaný postupem nasazení. Jakákoli změna povolena

mezi po sobě jdoucími písmeny, se provádí pouze v případě

oba postupy provádějí stejné změny ve stejném pořadí.

Absence podpory lexikografického řádu značně zjednodušuje implementaci

operace poloviční expanze odstraněním klikatého pouzdra. To může být

Se školitelem připravujeme krátkou monografii o zpracování obrazu. Rozhodl jsem se předložit soudu komunity habra kapitolu o algoritmech komprese obrazu. Protože je těžké vměstnat celou kapitolu do jednoho příspěvku, rozhodl jsem se to rozdělit do tří příspěvků:
1. Metody komprese dat;
2. Bezeztrátová komprese obrazu;
3. Ztrátová komprese obrazu.
Níže si můžete přečíst první příspěvek ze série.

V současné době existuje velké množství bezeztrátových kompresních algoritmů, které lze podmíněně rozdělit do dvou velkých skupin:
1. Streamové a slovníkové algoritmy. Tato skupina zahrnuje algoritmy rodin RLE (run-length encoding), LZ* atd. Charakteristickým rysem všech algoritmů této skupiny je, že kódování nepoužívá informace o frekvenci symbolů ve zprávě, ale informace o sekvencích setkali dříve.
2. Algoritmy pro statistickou (entropickou) kompresi. Tato skupina algoritmů komprimuje informace pomocí nerovnoměrných frekvencí, se kterými se ve zprávě vyskytují různé znaky. Algoritmy této skupiny zahrnují aritmetické a prefixové kódovací algoritmy (používající Shannon-Fanno, Huffman, secant stromy).
Algoritmy transformace informací lze vyčlenit jako samostatnou skupinu. Algoritmy této skupiny informace přímo nekomprimují, ale jejich aplikace značně zjednodušuje další kompresi pomocí streamovacích, slovníkových a entropických algoritmů.

Algoritmy proudů a slovníků

Kódování délky běhu

Hlavní nevýhodou tohoto algoritmu je extrémně nízká účinnost na sekvence neopakujících se znaků. Pokud například vezmeme v úvahu sekvenci „ABABAB“ (6 bajtů), pak se po použití algoritmu RLE změní na „1A1B1A1B1A1B“ (12 bajtů). Problém s neopakujícími se znaky lze vyřešit různými způsoby.

Nejjednodušší metodou je následující úprava: bajt kódující počet opakování musí uchovávat informace nejen o počtu opakování, ale také o jejich přítomnosti. Pokud je první bit 1, pak dalších 7 bitů označuje počet opakování odpovídajícího znaku, a pokud je první bit 0, pak dalších 7 bitů označuje počet znaků, které se mají vzít bez opakování. Pokud zakódujeme "ABABAB" pomocí této modifikace, dostaneme "-6ABABAB" (7 bajtů). Je zřejmé, že navrhovaná technika může významně zlepšit účinnost algoritmu RLE na neopakujících se sekvencích znaků. Implementace navrhovaného přístupu je uvedena ve výpisu 1:

1. typ
2. function RLEEncode(InMsg: ShortString) : TRLEEncodedString;
3. MatchFl: boolean ;
4. MatchCount: shortint ;
5. EncodedString: TRLEEncodedString;
6. N, i: bajty;
7. začít
8. N:=0;
9. SetLength(EncodedString, 2 * délka(InMsg) ) ;
10. zatímco délka (InMsg) >= 1 do
11. začít
12. MatchFl : = (délka (InMsg) > 1) a (InMsg[ 1 ] = InMsg[ 2 ] );
13. Počet shod := 1 ;
14. zatímco (MatchCount<= 126 ) and (MatchCount < length(InMsg) ) and ((InMsg[ MatchCount] = InMsg[ MatchCount + 1 ] ) = MatchFl) do
15. MatchCount : = MatchCount + 1 ;
16. pokud MatchFl pak
17. začít
18. N: = N + 2;
19. EncodedString[ N - 2 ] : = MatchCount + 128 ;
20. EncodedString[ N - 1 ] : = ord (InMsg[ 1] ) ;
21. jiný
22. začít
23. pokud MatchCount<>délka (InMsg).
24. MatchCount: = MatchCount - 1;
25. N:= N + 1 + MatchCount;
26. EncodedString[ N - 1 - MatchCount] : = - MatchCount + 128 ;
27. for i := 1 to MatchCount udělat
28. EncodedString[ N - 1 - MatchCount + i] : = ord (InMsg[ i] ) ;
29. konec ;
30. delete(InMsg, 1, MatchCount) ;
31. konec ;
32. SetLength(EncodedString, N) ;
33. RLEncode := EncodedString;
34. konec ;

1. typ
2. TRLEEncodedString = pole bajtů ;
3. function RLEDecode(InMsg: TRLEEncodedString) : ShortString;
4. RepeatCount: shortint ;
5. i, j: slovo;
6. OutMsg: ShortString;
7. začít
8. OutMsg := "" ;
9. i:=0;
10. zatímco já< length(InMsg) do
11. začít
12. RepeatCount : = InMsg[i] - 128 ;
13. i: = i + 1;
14. pokud RepeatCount< 0 then
15. začít
16. RepeatCount := abs(RepeatCount) ;
17. for j : = i až i + RepeatCount - 1 do
18. OutMsg := OutMsg + chr (InMsg[ j] ) ;
19. i := i + RepeatCount;
20. jiný
21. začít
22. for j := 1 to RepeatCount do
23. OutMsg := OutMsg + chr (InMsg[ i] ) ;
24. i: = i + 1;
25. konec ;
26. konec ;
27. RLEDecode := OutMsg;
28. konec ;

1. konst
2. EOMsg="|" ;
3. function BWTEncode(InMsg: ShortString) : ShortString;
4. OutMsg: ShortString;
5. LastChar: ANSIChar;
6. N, i: slovo;
7. začít
8. InMsg := InMsg + EOMsg;
9. N := délka(InMsg) ;
10. ShiftTable[ 1 ] := InMsg;
11. pro i := 2 až N do
12. začít
13. LastChar := InMsg[N] ;
14. InMsg : = LastChar + copy(InMsg, 1, N - 1 );
15. ShiftTable[i] := InMsg;
16. konec ;
17. Seřadit(ShiftTable) ;
18. OutMsg := "" ;
19. pro i := 1 až N do
20. OutMsg : = OutMsg + ShiftTable[ i] [ N] ;
21. BWTEncode := OutMsg;
22. konec ;

Tito. výsledkem přímé konverze bude řetězec "|NNAAAC". Je snadné vidět, že tento řetězec je mnohem lepší než původní, je komprimován algoritmem RLE, protože obsahuje dlouhé podsekvence opakovaných písmen.
Podobného efektu lze dosáhnout i pomocí jiných transformací, ale výhodou transformace BWT je, že je reverzibilní, nicméně zpětná transformace je složitější než přímá. Chcete-li obnovit původní řetězec, musíte provést následující kroky:
Vytvořte prázdnou matici o velikosti n*n, kde n je počet znaků v zakódované zprávě;
Vyplňte prázdný sloupec zcela vpravo kódovanou zprávou;
Řazení řádků tabulky v lexikografickém pořadí;
Opakujte kroky 2-3, dokud jsou prázdné sloupce;
Vraťte řetězec, který končí znakem konce řádku.

Implementace inverzní transformace není na první pohled obtížná a jedna z implementací je uvedena ve výpisu 4.

1. konst
2. EOMsg="|" ;
3. function BWTDecode(InMsg: ShortString) : ShortString;
4. OutMsg: ShortString;
5. ShiftTable: pole ShortString;
6. N, i, j: slovo;
7. začít
8. OutMsg := "" ;
9. N := délka(InMsg) ;
10. SetLength(ShiftTable, N + 1) ;
11. pro i := 0 až N do
12. ShiftTable[i] := "" ;
13. pro i := 1 až N do
14. začít
15. pro j := 1 až N do
16. ShiftTable[ j] : = InMsg[ j] + ShiftTable[ j] ;
17. Seřadit(ShiftTable) ;
18. konec ;
19. pro i := 1 až N do
20. if ShiftTable[ i] [N] = EOMsg pak
21. OutMsg := ShiftTable[i] ;
22. delete(OutMsg, N, 1 ) ;
23. BWTDecode := OutMsg;
24. konec ;

Po seřazení tabulky získané v sedmém kroku je nutné vybrat z tabulky řádek, který končí symbolem "|". Je snadné vidět, že toto je jediná linie. Že. transformaci BWT jsme zvažovali na konkrétním příkladu.

Souhrnně lze říci, že hlavní výhodou skupiny algoritmů RLE je jednoduchost a rychlost ovládání (včetně rychlosti dekódování) a hlavní nevýhodou je neefektivita na neopakujících se znakových sadách. Použití speciálních permutací zvyšuje efektivitu algoritmu, ale také výrazně zvyšuje dobu běhu (zejména dekódování).

Slovníková komprese (algoritmy LZ)

Nejjednodušší verze slovníkového algoritmu je popsána níže:
Inicializujte slovník se všemi znaky nalezenými ve vstupním řetězci;
Najděte ve slovníku nejdelší sekvenci (S), která odpovídá začátku zakódované zprávy;
Vydejte kód nalezené sekvence a odstraňte jej ze začátku zakódované zprávy;
Pokud není dosaženo konce zprávy, přečtěte si další znak a přidejte Sc do slovníku, přejděte ke kroku 2. V opačném případě ukončete.

Například nově inicializovaný slovník pro frázi "CUCKOOCOOKOOHOOD" je zobrazen v tabulce. 3:

Během procesu komprese bude slovník doplněn o sekvence nalezené ve zprávě. Postup aktualizace slovníku je uveden v tabulce. 4.

Při popisu algoritmu byl záměrně vynechán popis situace, kdy je slovník zcela zaplněn. V závislosti na variantě algoritmu je možné různé chování: úplné nebo částečné vymazání slovníku, zastavení plnění slovníku nebo rozšíření slovníku s odpovídajícím zvýšením kapacity kódu. Každý z těchto přístupů má určité nevýhody. Například zastavení doplňování slovníku může vést k situaci, kdy slovník ukládá sekvence, které se vyskytují na začátku komprimovaného řetězce, ale později se nevyskytují. Současně může vymazání slovníku vést k odstranění častých sekvencí. Většina implementací používaných při plnění slovníku začíná sledovat stupeň komprese, a když klesne pod určitou úroveň, slovník je přestavěn. Dále se budeme zabývat nejjednodušší implementací, která zastaví doplňování slovníku, když je plný.

Nejprve definujeme slovník jako záznam, který uchovává nejen nalezené podřetězce, ale také počet podřetězců uložených ve slovníku:

Dříve nalezené podsekvence jsou uloženy v poli Slov a jejich kód jsou čísla podsekvencí v tomto poli.
Definujeme také vyhledávání ve slovníku a přidáváme do slovníku funkce:

1. konst
2. MAX_DICT_LENGTH = 256 ;
3. function FindInDict(D: TDictionary; str: ShortString) : integer ;
4. r: celé číslo
5. i: celé číslo;
6. fl: boolean ;
7. začít
8. r:= -1;
9. pokud D. WordCount > 0 pak
10. začít
11. i := D.Pocet slov ;
12. fl := false ;
13. zatímco (ne fl) a (i >= 0 ) ano
14. začít
15. i:= i-1;
16. fl:=D.Words[i]=str;
17. konec ;
18. konec ;
19. pokud fl pak
20. r:=i;
21. FindInDict := r;
22. konec ;
23. procedure AddToDict(var D: TDictionary; str: ShortString) ;
24. začít
25. pokud D.WordCount< MAX_DICT_LENGTH then
26. začít
27. D.Pocet slov := D.Pocet slov + 1 ;
28. SetLength(D. Words , D. WordCount ) ;
29. D. Slova [ D. Počet slov - 1 ] : = str;
30. konec ;
31. konec ;

1. function LZWEncode(InMsg: ShortString) : TEncodedString;
2. OutMsg: TEncodedString;
3. tmpstr: ShortString;
4. D: TDslovník;
5. i, N: byty;
6. začít
7. SetLength(OutMsg, length(InMsg) ) ;
8. N:=0;
9. InitDict(D) ;
10. zatímco délka (InMsg) > 0 do
11. začít
12. tmpstr := InMsg[ 1 ] ;
13. zatímco (FindInDict(D, tmpstr) >= 0 ) and (length(InMsg) > length(tmpstr) ) dělají
14. tmpstr : = tmpstr + InMsg[ length(tmpstr) + 1 ] ;
15. if FindInDict(D, tmpstr)< 0 then
16. delete(tmpstr, length(tmpstr) , 1 );
17. OutMsg[N] := FindInDict(D, tmpstr) ;
18. N: = N + 1;
19. delete(InMsg, 1 , length(tmpstr) ) ;
20. pokud délka (InMsg) > 0, pak
21. AddToDict(D, tmpstr + InMsg[ 1 ] );
22. konec ;
23. SetLength(OutMsg, N) ;
24. LZWEncode := OutMsg;
25. konec ;

Jediný problém je možný v následující situaci: když je potřeba dekódovat podsekvenci, která ještě není ve slovníku. Je snadné vidět, že je to možné pouze v případě, kdy je nutné extrahovat podřetězec, který je třeba přidat v aktuálním kroku. A to znamená, že podřetězec vyhovuje vzoru cSc, tzn. začíná a končí stejným znakem. V tomto případě je cS podřetězec přidaný v předchozím kroku. Uvažovaná situace je jediná, kdy je potřeba dekódovat řetězec, který ještě nebyl přidán. Vzhledem k výše uvedenému můžeme nabídnout následující možnost dekódování komprimovaného řetězce:

1. function LZWDecode(InMsg: TEncodedString) : ShortString;
2. D: TDslovník;
3. OutMsg, tmpstr: ShortString;
4. i: byte;
5. začít
6. OutMsg := "" ;
7. tmpstr := "" ;
8. InitDict(D) ;
9. for i := 0 to length (InMsg) - 1 do
10. začít
11. if InMsg[i] >= D.WordCount pak
12. tmpstr : = D. Slova [ InMsg[ i - 1 ] ] + D. Slova [ InMsg[ i - 1 ] ] [ 1 ]
13. jiný
14. tmpstr := D. Slova [ InMsg[ i] ] ;
15. OutMsg := OutMsg + tmpstr;
16. pokud jsem > 0, pak
17. AddToDict(D, D. Slova [ InMsg[ i - 1 ] ] + tmpstr[ 1 ] );
18. konec ;
19. LZWDecode := OutMsg;
20. konec ;

Entropické kódování

Kódování pomocí Shannon-Fano Trees

Bez kódování bude zpráva trvat 40 bitů (za předpokladu, že každý znak je zakódován 4 bity) a pomocí Shannon-Fano algoritmu 4*2+2+4+4+3+3+3=27 bitů. Objem zpráv se snížil o 32,5 %, ale níže bude ukázáno, že tento výsledek lze výrazně zlepšit.

Kódování pomocí Huffman Trees

Uvažujme stejný příklad jako v případě Shannon-Fano algoritmu. Huffmanův strom a kódy přijaté pro zprávu „AAAABVGDEZH“ jsou zobrazeny na Obr. 2:

Je snadné vypočítat, že velikost zakódované zprávy bude 26 bitů, což je méně než v algoritmu Shannon-Fano. Samostatně je třeba poznamenat, že vzhledem k popularitě Huffmanova algoritmu na tento moment Existuje mnoho variant Huffmanova kódování, včetně adaptivního kódování, které nevyžaduje přenos symbolových frekvencí.
Mezi nevýhody Huffmanova algoritmu patří významnou část problémy spojené se složitostí implementace. Použití skutečných variabilních symbolů pro ukládání frekvencí je spojeno se ztrátou přesnosti, proto se v praxi často používají celočíselné proměnné, ale od r. hmotnost rodičovských uzlin neustále roste, dříve nebo později dojde k přetečení. I přes jednoduchost algoritmu může jeho správná implementace stále způsobovat určité potíže, zejména u velkých abeced.

Kódování se sečnými stromy

Strom je postaven tak, že každý uzel rozděluje abecedu na co nejbližší části. Na Obr. 3 ukazuje příklad sečného stromu:

Strom funkcí sečny v obecném případě nezaručuje optimální kódování, ale poskytuje extrémně vysoká rychlost práce díky jednoduchosti ovládání v uzlech.

Aritmetické kódování