Účel prednášky: študovať hlavné typy a algoritmy kompresie údajov a naučiť sa riešiť problémy s kompresiou údajov pomocou Huffmanovej metódy a pomocou kódových stromov.
Claude Shannon je považovaný za zakladateľa vedy o kompresii informácií. Jeho teorém o optimálnom kódovaní ukazuje, o čo sa pri kódovaní informácií snažiť a nakoľko budú v tomto prípade tie či oné informácie komprimované. Okrem toho robil experimenty na empirickom hodnotení redundancie anglického textu. Chenon požiadal ľudí, aby uhádli ďalšie písmeno, a vyhodnotil pravdepodobnosť, že uhádnu správne. Na základe množstva experimentov dospel k záveru, že množstvo informácií v Anglický text sa pohybuje od 0,6 do 1,3 bitov na znak. Napriek tomu, že výsledky Shannonovho výskumu boli skutočne žiadané až po desaťročiach, je ťažké preceňovať ich význam.
Kompresia údajov Je proces, ktorý znižuje množstvo údajov znížením redundancie. Kompresia dát je spojená s kompaktným usporiadaním dátových blokov štandardná veľkosť... Kompresiu údajov možno rozdeliť do dvoch hlavných typov:
- Bezstratová kompresia (plne reverzibilná) Ide o metódu kompresie údajov, pri ktorej sa predtým zakódovaná časť údajov obnoví po úplnom rozbalení bez vykonania akýchkoľvek zmien. Každý typ údajov má zvyčajne svoje vlastné optimálne algoritmy bezstratová kompresia.
- Stratová kompresia Je to metóda kompresie údajov, pri ktorej sa má zabezpečiť maximálny stupeň pri kompresii pôvodného dátového poľa sa niektoré údaje, ktoré obsahuje, zahodia. Pre textové, číselné a tabuľkové údaje je použitie programov, ktoré implementujú takéto kompresné metódy, neprijateľné. V zásade sa takéto algoritmy používajú na kompresiu zvukových a obrazových údajov, statických obrázkov.
Algoritmus kompresie údajov (algoritmus archivácie) Je to algoritmus, ktorý eliminuje nadbytočnosť zaznamenávania údajov.
Uveďme niekoľko definícií, ktoré sa budú ďalej používať pri prezentácii materiálu.
Kódová abeceda- množina všetkých symbolov vstupného toku. Pri komprimácii textov v anglickom jazyku sa zvyčajne používa veľa zo 128 kódov ASCII. Pri kompresii obrázkov môže sada hodnôt pixelov obsahovať 2, 16, 256 alebo akýkoľvek iný počet prvkov.
Znak kódu Je najmenšia jednotka údajov, ktorá sa má komprimovať. Znak má zvyčajne 1 bajt, ale môže to byť bit, trit (0,1,2) alebo čokoľvek iné.
Kódové slovo Je postupnosť kódové znaky z abecedného kódu. Ak majú všetky slová rovnakú dĺžku (počet znakov), potom sa takýto kód volá jednotné (pevná dĺžka) a ak sú povolené slová rôznych dĺžok, potom - nerovnomerné ( variabilná dĺžka) .
Kód je kompletný súbor slov.
Token- jednotka dát zapísaná do komprimovaného prúdu nejakým kompresným algoritmom. Token pozostáva z niekoľkých polí s pevnou alebo premenlivou dĺžkou.
Fráza- časť údajov umiestnená do slovníka na ďalšie použitie pri kompresii.
Kódovanie- proces kompresie údajov.
Dekódovanie- spätný proces kódovania, pri ktorom sa vykonáva obnova dát.
Pomer kompresie Je jednou z najčastejšie používaných veličín na označenie účinnosti kompresnej metódy.
Hodnota 0,6 znamená, že údaje predstavujú 60 % pôvodného objemu. Hodnoty väčšie ako 1 znamenajú, že výstupný tok je väčší ako vstupný tok (negatívna kompresia alebo expanzia).Pomer kompresie Je to prevrátená hodnota kompresného pomeru.
Hodnoty väčšie ako 1 označujú kompresiu a hodnoty menšie ako 1 označujú expanziu.
Priemerná dĺžka kódového slova Ide o hodnotu, ktorá sa vypočíta ako pravdepodobnosťou vážený súčet dĺžok všetkých kódových slov.
L cp = p 1 L 1 + p 2 L 2 + ... + p n L n,
kde sú pravdepodobnosti kódových slov;
L 1, L 2, ..., L n sú dĺžky kódových slov.
Existujú dva hlavné spôsoby kompresie.
Štatistické metódy- kompresné metódy, ktoré priraďujú kódy premenlivej dĺžky k symbolom vstupného toku a ďalšie krátke kódy sú priradené k symbolom alebo skupinám symbolov, ktoré majú vysokú pravdepodobnosť výskytu v vstupný prúd... Najlepší štatistické metódy Používa sa Huffmanovo kódovanie.
Slovníková kompresia Sú metódy kompresie, ktoré ukladajú kusy údajov do „slovníka“ (niektoré dátová štruktúra). Ak je riadok nových údajov prichádzajúcich na vstup identický s ktorýmkoľvek fragmentom, ktorý sa už nachádza v slovníku, do výstupného toku sa umiestni ukazovateľ na tento fragment. Najlepšie metódy slovnej zásoby používajú metódu Ziv-Lempel.
Pozrime sa podrobnejšie na niekoľko známych algoritmov kompresie údajov.
Huffmanova metóda
Tento algoritmus informácie o kódovaní navrhol D.A. Huffman v roku 1952. Huffmanovo kódovanie (kompresia) Je široko používaná kompresná metóda, ktorá priraďuje symboly abecedy kódy s premenlivou dĺžkou na základe pravdepodobnosti výskytu týchto znakov.
Myšlienka algoritmu je nasledovná: ak poznáte pravdepodobnosť výskytu znakov v zdrojovom texte, môžete opísať postup vytvárania kódov s premenlivou dĺžkou, ktoré pozostávajú z celého čísla bitov. Je pravdepodobnejšie, že symbolom budú priradené kratšie kódy. Pri tejto metóde je teda pri komprimácii dát každému znaku priradený optimálny prefixový kód na základe pravdepodobnosti jeho výskytu v texte.
Predponový kód Je kód, v ktorom žiadne kódové slovo nie je predponou žiadneho iného kódového slova. Tieto kódy majú premenlivú dĺžku.
Optimálny prefixový kód Ide o predponový kód s minimálnou priemernou dĺžkou.
Huffmanov algoritmus možno rozdeliť do dvoch etáp.
- Určenie pravdepodobnosti výskytu znakov v zdrojovom texte.
Na začiatok je potrebné prečítať celý zdrojový text a vypočítať v ňom pravdepodobnosti znakov (niekedy počítajú, koľkokrát sa ktorý znak vyskytuje). Ak sa vezme do úvahy všetkých 256 znakov, nebude žiadny rozdiel v kompresii textu alebo iného formátu súboru.
- Nájdenie optimálneho prefixového kódu.
Ďalej sa nájdu dva symboly a a b s najnižšou pravdepodobnosťou výskytu a nahradia sa jedným fiktívnym symbolom x, ktorý má pravdepodobnosť výskytu rovnajúcu sa súčtu pravdepodobností výskytu symbolov a a b. Potom pomocou tohto postupu rekurzívne nájdite optimálny prefixový kód pre menšiu množinu znakov (kde sú znaky a a b nahradené jedným znakom x). Kód pre pôvodnú znakovú sadu sa získa z kódov náhradných znakov pridaním 0 alebo 1 pred kód náhradného znaku a tieto dva nové kódy sa berú ako kódy náhradných znakov. Napríklad kód znaku a sa bude zhodovať s kódom x s nulou pridanou pred týmto kódom a pre znak b sa pred kód znaku x pripojí jedna.
Huffmanove kódy majú jedinečnú predponu, ktorá im umožňuje jedinečne ich dekódovať aj napriek ich premenlivej dĺžke.
Príklad 1. Softvérová implementácia Huffmanova metóda.
#include "stdafx.h" #include
Huffmanov algoritmus je univerzálny, dá sa ním komprimovať dáta ľubovoľného typu, ale pre malé súbory je neúčinný (kvôli potrebe uložiť slovník). V súčasnosti sa táto metóda prakticky nepoužíva vo svojej čistej forme, zvyčajne sa používa ako jeden z kompresných stupňov v zložitejších schémach. Toto je jediný algoritmus, ktorý v najhoršom prípade nezväčší veľkosť pôvodných údajov (okrem potreby uložiť vyhľadávaciu tabuľku so súborom).
Moderní používatelia sa často stretávajú s problémom nedostatku voľného miesta na pevnom disku. Mnohí sa v snahe uvoľniť aspoň trochu voľného miesta pokúšajú odstrániť všetky nepotrebné informácie z pevného disku. Pokročilejší používatelia používajú špeciálne kompresné algoritmy na zníženie množstva údajov. Napriek účinnosti tohto procesu o ňom mnohí používatelia nikdy nepočuli. Pokúsme sa zistiť, čo sa myslí pod pojmom kompresia údajov, aké algoritmy možno na to použiť.
Kompresia dát je dnes pomerne dôležitý postup, ktorý potrebuje každý používateľ PC. Dnes si každý používateľ môže dovoliť kúpiť moderné zariadenie na ukladanie dát, ktoré poskytuje možnosť využitia veľkého množstva pamäte. Takéto zariadenia sú spravidla vybavené vysokorýchlostnými kanálmi na vysielanie informácií. Je však potrebné poznamenať, že každým rokom sa objem informácií požadovaných používateľmi zvyšuje a zvyšuje. Len pred 10 dolármi objem štandardného videofilmu nepresiahol 700 MB. V súčasnosti môže objem filmov v HD kvalite dosiahnuť niekoľko desiatok gigabajtov.
Kedy je potrebná kompresia údajov?
Od procesu kompresie informácií by ste nemali veľa očakávať. Napriek tomu existujú situácie, v ktorých je kompresia informácií jednoducho nevyhnutná a mimoriadne užitočná. Pozrime sa na niektoré z týchto prípadov.
Prenos e-mailom.
Veľmi často dochádza k situáciám, keď potrebujete poslať veľké množstvo dát e-mailom. Kompresia môže výrazne znížiť veľkosť prenášaných súborov. Výhody tohto postupu ocenia najmä používatelia, ktorí na odosielanie informácií využívajú mobilné zariadenia.
Publikovanie údajov na internetových stránkach a portáloch.
Postup kompresie sa často používa na zníženie objemu dokumentov používaných na publikovanie na rôznych internetových zdrojoch. To vám umožní výrazne ušetriť na premávke.
Úspora voľného miesta na disku.
Ak nie je možné do systému pridať nové úložné médium, môžete použiť komprimačný postup, aby ste ušetrili voľné miesto na disku. Stáva sa, že rozpočet používateľa je extrémne obmedzený a na pevnom disku nie je dostatok voľného miesta. Tu prichádza na rad postup kompresie.
Okrem situácií uvedených vyššie existuje pravdepodobne oveľa viac prípadov, v ktorých môže byť proces kompresie údajov veľmi užitočný. Uviedli sme len tie najbežnejšie.
Metódy kompresie informácií
Všetky existujúce metódy kompresie informácií možno rozdeliť do dvoch hlavných kategórií. Ide o bezstratovú a stratovú kompresiu. Prvá kategória je relevantná iba vtedy, keď je potrebné obnoviť údaje s vysokou presnosťou bez straty jediného bitu pôvodnej informácie. Jediným prípadom, kedy musíte použiť tento konkrétny prístup, je kompresia textových dokumentov.
V prípade, že neexistuje špeciálna potreba čo najpresnejšej obnovy komprimovaných informácií, je potrebné zabezpečiť možnosť použitia algoritmov s určitými kompresnými stratami.
Kompresia bez straty informácií
Tieto spôsoby kompresie informácií sú zaujímavé predovšetkým, pretože sa používajú pri prenose veľkého množstva informácií e-mailom, pri vystavení hotového diela zákazníkovi alebo pri vytváraní záložných kópií informácií uložených v počítači. Tieto spôsoby kompresie informácií neumožňujú stratu informácií, keďže sú založené len na odstránení ich redundancie, pričom informácie majú redundanciu takmer vždy, ak by tam tá druhá nebola, nebolo by čo komprimovať.
Príklad 1
Uveďme si jednoduchý príklad. Ruský jazyk obsahuje písmená 33 $, čísla 10 $ a asi 15 $ ďalších interpunkčných znamienok a ďalšie špeciálne znaky. Pre text napísaný iba veľkými ruskými písmenami (napríklad ako v telegramoch) by stačilo 60 $ rôznych hodnôt. Každý znak je však zvyčajne zakódovaný bajtom obsahujúcim to, o čom vieme, že je 8 bitov, a môže byť vyjadrený v 256 $ rôznych kódoch. Toto je jeden z prvých faktorov, ktoré charakterizujú redundanciu. Pre telegrafický text by stačilo 6 $ bitov na znak.
Príklad 2
Pozrime sa na ďalší príklad. Pri medzinárodnom kódovaní znakov ASCII je rovnaký počet bitov (8 $) pridelený na kódovanie akéhokoľvek znaku, pričom každý už dávno vie, že má zmysel kódovať najbežnejšie znaky v menšom počte znakov. Takže napríklad v Morseovej abecede sú písmená „E“ a „T“, ktoré sú veľmi bežné, zakódované znakom $ 1 $ (v tomto poradí ide o bodku a pomlčku). A také zriedkavé písmená ako "U" ($ - - $) a "C" ($ - - $) sú zakódované v znakoch $ 4 $.
Poznámka 1
Neefektívne kódovanie je druhým faktorom, ktorý charakterizuje redundanciu. Programy, vďaka ktorým sú informácie komprimované, môžu zadať svoje vlastné kódovanie, ktoré môže byť pre rôzne súbory odlišné, a priradiť ho ku komprimovanému súboru vo forme tabuľky (slovníka), z ktorej bude rozbaľovací program čítať informácie o ako sú v súbore zakódované určité symboly alebo ich skupiny.
Algoritmy založené na prekódovaní informácií sa nazývajú Huffmanove algoritmy.
Huffmanov algoritmus
V tomto algoritme sa kompresia informácií vykonáva entropickým kódovaním alebo na základe predtým vytvoreného slovníka. Podľa štatistického Huffmanovho algoritmu je každému vstupnému symbolu priradený špecifický kód. V tomto prípade je najčastejšie používaným symbolom najkratší kód a najčastejšie používaným dlhším. Ako príklad je na diagrame znázornené rozdelenie frekvencie používania jednotlivých písmen anglickej abecedy (obr. 1). Takáto distribúcia môže byť skonštruovaná aj pre ruský jazyk. Tabuľky kódov sú vopred vytvorené a ich veľkosť je obmedzená. Tento algoritmus poskytuje najrýchlejšiu a najnižšiu latenciu. Štatistická metóda vyžaduje veľké množstvo pamäte na získanie vysokých kompresných pomerov.
Obrázok 1. Rozdelenie anglických písmen podľa frekvencie ich používania
Veľkosť kompresie je určená redundanciou spracovávaného bitového poľa. Každý z prirodzených jazykov má určitú redundanciu. Spomedzi európskych jazykov má ruština najvyššiu úroveň redundancie. To možno posúdiť podľa veľkosti ruského prekladu anglického textu. Zvyčajne je to o 30 $ \% $ viac. Ak hovoríme o poetickom texte, nadbytočnosť môže byť až 2 $ krát vyššia.
Poznámka 2
Najväčšou výzvou pri kódoch je potreba mať tabuľky pravdepodobnosti pre každý typ komprimovaných údajov. Toto nie je problém, ak je známe, že anglický alebo ruský text je komprimovaný. V tomto prípade kodéru a dekodéru jednoducho poskytneme vhodný strom kódov pre anglický alebo ruský text. Vo všeobecnom prípade, keď nie je známa pravdepodobnosť symbolov pre vstupné dáta, statické Huffmanove kódy nefungujú efektívne.
Riešením tohto problému je štatistická analýza zakódovaných údajov vykonaná počas prvého prechodu údajov a na jej základe zostavenie kódového stromu. V tomto prípade sa skutočné kódovanie vykoná v druhom prechode.
Ďalšou nevýhodou kódov je, že minimálna dĺžka kódového slova pre ne nemôže byť menšia ako jedna, pričom entropia správy môže byť $ 0,1 $ aj $ 0,01 $ bitov/písmeno. V tomto prípade sa kód stáva výrazne nadbytočným. Problém je vyriešený aplikáciou algoritmu na bloky symbolov, ale potom sa procedúra kódovania / dekódovania skomplikuje a výrazne sa rozšíri strom kódu, ktorý musí byť nakoniec uložený spolu s kódom.
Tieto kódy neberú do úvahy vzťahy medzi znakmi, ktoré sú prítomné takmer v akomkoľvek texte.
Poznámka 3
Dnes, v dobe informácií, napriek tomu, že takmer každý používateľ má prístup k vysokorýchlostným kanálom na prenos údajov a veľkoobjemovým médiám, zostáva otázka kompresie údajov stále aktuálna. Existujú situácie, v ktorých je kompresia údajov jednoducho nevyhnutnou operáciou. Týka sa to najmä prenosu údajov e-mailom a zverejňovania informácií na internete.
Metódy kompresie dát majú pomerne dlhú históriu vývoja, ktorá začala dávno pred príchodom prvého počítača. Tento článok sa pokúsi poskytnúť stručný prehľad hlavných teórií, konceptov myšlienok a ich realizácií, bez toho, aby sa tváril ako absolútny. Podrobnejšie informácie možno nájsť napríklad u R.E.Krichevského. , Ryabko B.Ya. , Witten I.H. , Rissanen J., Huffman D.A., Gallager R.G. , Knuth D.E. , Vitter J.S. atď.
Kompresia informácií je problém, ktorý má pomerne dlhú históriu, oveľa staršiu ako história vývoja výpočtovej techniky, ktorá (história) zvyčajne išla spolu s históriou vývoja problému kódovania a šifrovania informácií. Všetky kompresné algoritmy pracujú na vstupnom toku informácií, ktorých minimálna jednotka je bit a maximálna jednotka je niekoľko bitov, bajtov alebo niekoľko bajtov. Účelom kompresného procesu je spravidla získať kompaktnejší výstupný tok informačných jednotiek z nejakého pôvodne nekompaktného vstupného toku pomocou nejakej ich transformácie. Hlavné technické charakteristiky procesov kompresie a výsledky ich práce sú:
Kompresný pomer (kompresný pomer) alebo pomer (pomer) objemov počiatočného a konečného prúdu;
Rýchlosť kompresie - čas strávený kompresiou určitého množstva informácií vo vstupnom toku, kým sa z neho nezíska ekvivalentný výstupný tok;
Kvalita kompresie je hodnota, ktorá ukazuje, ako silne je výstupný tok zbalený tým, že naň aplikuje opätovnú kompresiu pomocou rovnakého alebo iného algoritmu.
Existuje niekoľko rôznych prístupov k problému kompresie informácií. Niektoré majú veľmi zložitý teoretický matematický základ, iné sú založené na vlastnostiach toku informácií a sú algoritmicky celkom jednoduché. Každý prístup a algoritmus, ktorý implementuje kompresiu alebo kompresiu dát, je navrhnutý tak, aby zmenšil objem výstupného informačného toku v bitoch pomocou jeho reverzibilnej alebo ireverzibilnej transformácie. Preto v prvom rade, podľa kritéria týkajúceho sa povahy alebo formátu údajov, všetky metódy kompresie možno rozdeliť do dvoch kategórií: reverzibilná a nevratná kompresia.
Ireverzibilnou kompresiou sa rozumie taká transformácia vstupného dátového toku, pri ktorej výstupný tok na základe určitého informačného formátu predstavuje z určitého uhla pohľadu objekt, ktorý je vonkajšími charakteristikami dosť podobný vstupnému toku, ale líši sa z toho v objeme. Stupeň podobnosti medzi vstupným a výstupným tokom je určený stupňom zhody medzi určitými vlastnosťami objektu (t.j. komprimovanými a nekomprimovanými informáciami v súlade s určitým špecifickým dátovým formátom), ktoré predstavuje tento informačný tok. Takéto prístupy a algoritmy sa používajú napríklad na kompresiu údajov bitmapových grafických súborov s nízkou opakovateľnosťou bajtov v prúde. Tento prístup využíva vlastnosť štruktúry formátu grafického súboru a schopnosť prezentovať grafický obraz približne podobnej kvality zobrazenia (pre vnímanie ľudským okom) niekoľkými (alebo skôr n) spôsobmi. Preto sa v takýchto algoritmoch okrem stupňa alebo množstva kompresie objavuje aj pojem kvality. pôvodný obrázok sa počas procesu kompresie mení, potom kvalitu môžeme chápať ako mieru zhody medzi originálom a výsledným obrázkom, posudzovanú subjektívne na základe informačného formátu. Pre grafické súbory je táto korešpondencia určená vizuálne, hoci existujú aj zodpovedajúce inteligentné algoritmy a programy. Ireverzibilnú kompresiu nie je možné aplikovať v oblastiach, v ktorých je potrebné mať presnú zhodu informačnej štruktúry vstupného a výstupného toku. Tento prístup je implementovaný v populárnych formátoch na prezentáciu informácií o videu a fotografii, známych ako algoritmy JPEG a JFIF a formáty súborov JPG a JIF.
Reverzibilná kompresia vedie vždy k zníženiu objemu výstupného informačného toku bez zmeny jeho informačného obsahu, t.j. - bez straty informačnej štruktúry. Navyše z výstupného toku pomocou algoritmu obnovy alebo dekompresie môžete 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 interným formátom.
V reverzibilných algoritmoch sa na kódovanie ako na proces môžeme pozerať zo štatistického hľadiska, čo je ešte užitočnejšie nielen pre konštrukciu kompresných algoritmov, ale aj pre hodnotenie ich účinnosti. Pre všetky reverzibilné algoritmy existuje koncept nákladov na kódovanie. Náklady na kódovanie sa vzťahujú na priemernú dĺžku kódového slova v bitoch. Redundancia kódovania sa rovná rozdielu medzi nákladmi a entropiou kódovania a dobrý kompresný algoritmus by mal vždy minimalizovať redundanciu (pripomeňme, že entropia informácie sa chápe ako miera jej neusporiadanosti). Shannonova základná veta o kódovaní informácií hovorí, že „náklady na kódovanie nie sú vždy menšie ako entropia zdroja, hoci sa k nej môžu ľubovoľne blížiť“. Preto pre každý algoritmus vždy existuje určitý limit kompresného pomeru, určený entropiou vstupného toku.
Prejdime teraz priamo k algoritmickým vlastnostiam reverzibilných algoritmov a zvážme najdôležitejšie teoretické prístupy ku kompresii dát spojené s implementáciou kódovacích systémov a metód kompresie informácií.
Kompresia pomocou dávkového kódovania
Najznámejším jednoduchým prístupom a algoritmom na kompresiu informácií reverzibilným spôsobom je Run Length Encoding (RLE). Podstatou metód tohto prístupu je nahradenie reťazcov alebo série opakujúcich sa bajtov alebo ich sekvencií jedným kódovacím bajtom a počítadlom počtu ich opakovaní. Problém všetkých analogických metód je len v určení spôsobu, akým by rozbaľovací algoritmus mohol rozlíšiť zakódovanú sériu vo výslednom bajtovom toku od ostatných - nekódovaných bajtových sekvencií. Riešenie problému sa zvyčajne dosiahne umiestnením značiek na začiatok kódovaných reťazcov. Takéto označenia môžu byť napríklad charakteristické bitové hodnoty v prvom byte kódovaného cyklu, hodnoty prvého bajtu kódovaného cyklu atď. Tieto metódy sú spravidla dosť efektívne na kompresiu rastrových grafických obrázkov (BMP, PCX, TIF, GIF), pretože tie posledné obsahujú pomerne veľa dlhých sérií opakujúcich sa sekvencií bajtov. Nevýhodou metódy RLE je pomerne nízky kompresný pomer alebo cena kódovania súborov s malým počtom sérií a čo je horšie, s malým počtom opakujúcich sa bajtov v sérii.
Kompresia bez použitia metódy RLE
Proces kompresie dát bez použitia metódy RLE možno rozdeliť do dvoch etáp: modelovanie a vlastne kódovanie. Tieto procesy a ich implementačné algoritmy sú celkom nezávislé a rôznorodé.
Proces kódovania a jeho metódy
Kódovanie sa zvyčajne chápe ako spracovanie prúdu znakov (v našom prípade bajtov alebo nibble) v určitej abecede, pričom frekvencie výskytu znakov v prúde sú rôzne. Účelom kódovania je previesť tento tok na bitový tok s minimálnou dĺžkou, čo sa dosiahne znížením entropie vstupného toku s prihliadnutím na frekvencie symbolov. Dĺžka kódu reprezentujúceho znaky z abecedy prúdu musí byť úmerná množstvu informácií vo vstupnom prúde a dĺžka symbolov prúdu v bitoch nesmie byť násobkom 8 alebo dokonca premenlivá. Ak je známe rozloženie pravdepodobnosti frekvencií výskytu symbolov z abecedy vstupného toku, potom je možné zostaviť optimálny model kódovania. Vzhľadom na existenciu veľkého množstva rôznych formátov súborov sa však úloha stáva oveľa komplikovanejšou. frekvenčné rozdelenie dátových symbolov nie je vopred známe. V tomto prípade sa vo všeobecnosti používajú dva prístupy.
Prvým je zobrazenie vstupného toku a vytvorenie kódovania na základe zozbieraných štatistík (to si vyžaduje dva prechody cez súbor – jeden na prezeranie a zhromažďovanie štatistických informácií, druhý na kódovanie, čo trochu obmedzuje rozsah takýchto algoritmov, pretože , je vylúčená možnosť jednopriechodového kódovania „za chodu“, ktoré sa používa v telekomunikačných systémoch, kde niekedy nie je známe množstvo dát a ich opätovný prenos alebo analýza môže trvať neprimerane dlho). V takom prípade sa štatistická schéma použitého kódovania zapíše do výstupného toku. Táto technika je známa ako statické Huffmanovo kódovanie.
|
|
Úvod.
Kompresia znižuje množstvo miesta potrebného na ukladanie súborov v počítači a
množstvo času potrebného na prenos informácií cez sadu kanálov
šírku pásma. Toto je forma kódovania. Iné účely kódovania
sú vyhľadávanie a oprava chýb, ako aj šifrovanie. Proces vyhľadávania a
oprava chýb je opakom kompresie – zvyšuje redundanciu dát,
keď ich netreba prezentovať v ľudsky čitateľnej forme. Odstránením
redundancia z textu, kompresia podporuje šifrovanie, čo komplikuje vyhľadávanie
šifra pomocou štatistickej metódy, ktorú má cracker k dispozícii.
Zvážte reverzibilnú kompresiu alebo kompresiu bez rušenia, kde je iniciál
text je možné presne obnoviť z komprimovaného stavu. Nezvratné resp
chybná kompresia sa používa na digitálny záznam analógových signálov ako napr
ľudská reč alebo kresby. Reverzibilná kompresia je obzvlášť dôležitá pre texty,
zaznamenané v prirodzených a umelých jazykoch, keďže v tomto prípade
chyby sú zvyčajne neprijateľné. Hoci primárna oblasť použitia
uvažovanými metódami sú kompresia textu, čo sa odráža v našej terminológii,
táto technika má však aj iné využitie, vrátane reverzibilného
kódovanie sekvencií diskrétnych dát.
Existuje veľa dobrých dôvodov na pridelenie počítačových zdrojov na komprimované súbory
zastupovanie, pretože rýchlejší prenos dát a menší priestor pre
ich skladovanie umožňuje ušetriť značné finančné prostriedky a často aj prilepšiť
počítačové indikátory. Kompresia pravdepodobne zostane v centre pozornosti kvôli všetkým
zvýšenie objemov dát uložených a prenášaných do počítača, navyše môže
použiť na prekonanie niektorých fyzických obmedzení, ako napr.
napríklad relatívne nízka šírka pásma telefónnych kanálov.
APLIKÁCIA EXPANDOVANÝCH STROMOV NA KOMPRESU ÚDAJOV.
Kompresné algoritmy môžu zlepšiť ukladanie údajov a efektívnosť prenosu
znížením množstva ich nadbytočnosti. Zaberá kompresný algoritmus
ako vstup zdrojového textu a vytvára zodpovedajúci komprimovaný text,
keď má ako rozbaľovací algoritmus komprimovaný text ako vstup a prijíma z
vypíše pôvodný text zdroja. Väčšina kompresných algoritmov
považovať zdrojový text za súbor reťazcov písmen abecedy
zdrojový text.
Redundancia v reprezentácii reťazca S je L (S) - H (S), kde L (S) je dĺžka
reprezentácia v bitoch a H (S) - entropia - miera informačného obsahu, tiež
vyjadrené v bitoch. Algoritmy, ktoré by mohli komprimovať bez straty informácií
reťazec s menším počtom bitov ako je jeho entropia neexistuje. Ak od
extrahovať zdrojový text po jednom písmene z nejakej náhodnej množiny,
pomocou abecedy A sa potom entropia nájde podľa vzorca:
H (S) = C (S) p (c) log ----,
kde C (S) je počet písmen v reťazci, p (c) je statická pravdepodobnosť
výskyt nejakého písmena C. Ak sa frekvencia výskytu použije na odhad p (c)
každého písmena c v reťazci S sa potom H (C) nazýva vlastná entropia reťazca S. V tomto
člen H (S) sa použije na označenie vlastnej entropie reťazca prevzatého z
statický zdroj.
Rozširujúce sa stromy zvyčajne opisujú formy lexikografického usporiadania
stromy pre binárne vyhľadávanie, ale stromy používané pri kompresii údajov nemusia
mať stály poriadok. Odstránenie objednávania vedie k
výrazné zjednodušenie základných expanzných operácií. Výsledný
Algoritmy sú extrémne rýchle a kompaktné. V prípade použitia Huffmanových kódov,
Výsledkom expanzie je lokálne prispôsobený kompresný algoritmus, ktorý
pozoruhodne jednoduchý a rýchly, aj keď nedosahuje optimálnu kompresiu.
Pri použití na aritmetické kódy je výsledok kompresie blízky
optimálne a približne optimálne v čase.
PREDPONOVÉ KÓDY.
Väčšina široko študovaných algoritmov kompresie údajov je založená na kódoch
Huffman. V Huffmanovom kóde je každé písmeno zdrojového textu zastúpené v archíve
kód s premenlivou dĺžkou. Častejšie písmená sú reprezentované krátkymi kódmi,
menej časté - dlhé. Kódy použité v komprimovanom texte sa musia podriaďovať
vlastnosti predpony, a to: kód použitý v komprimovanom texte nemôže byť
predpona akéhokoľvek iného kódu.
Predponové kódy možno nájsť prostredníctvom stromu, v ktorom je každý list
sa zhoduje s jedným písmenom zdrojovej abecedy. Obrázok 1 zobrazuje strom kódu
predpona pre 4-písmenovú abecedu. Predponový kód pre písmeno je možné prečítať pomocou
prechádzanie stromom od koreňa k tomuto písmenu, kde 0 zodpovedá výberu jeho ľavej vetvy,
a 1 - vpravo. Strom Huffmanovho kódu je strom vyrovnaný váhou, kde každý
list má váhu rovnajúcu sa frekvencii výskytu písmena v pôvodnom texte a
vnútorné uzly nemajú vlastnú váhu. Strom v príklade bude optimálny, ak
frekvencie písmen A, B, C a D budú 0,125, 0,125, 0,25 a 0,5.
Bežné Huffmanove kódy vyžadujú predchádzajúce informácie o frekvencii
písmen v pôvodnom texte, čo vedie k potrebe dvojitého prezerania – jedno
na získanie hodnôt frekvencií písmen, ďalšie na vykonanie samotnej kompresie. V
následne sa musia hodnoty týchto frekvencií skombinovať so samotným komprimovaným textom
v budúcnosti umožniť jeho nasadenie. Vykonáva sa adaptívna kompresia
v jednom kroku, pretože kód použitý pre každé písmeno pôvodného textu je založený na
pri frekvenciách všetkých ostatných písmen abecedy. Základy pre efektívne
adaptívne implementácie Huffmanovho kódu stanovil Gallagher, publikoval Knuth
praktickú verziu takéhoto algoritmu a Witter ju vyvinul.
Optimálne prispôsobený Witterov kód vždy leží v rámci jedného bitu na
zdrojové písmeno s ohľadom na optimálny statický Huffmanov kód, ktorý je zvyčajne
je niekoľko percent H. Navyše, statické Huffmanove kódy sú vždy
ležia do jedného bitu na zdrojové písmeno od H (dosiahnu toto
limit je len vtedy, keď pre všetky písmená p (C) = 2). Existujú kompresné algoritmy
ktoré môžu tieto obmedzenia prekonať. Algoritmus Ziv-Lempell, napr.
priraďuje slová z archívu s pevnou dĺžkou k riadkom zdrojového textu
na kódovanie je možné použiť variabilnú dĺžku a aritmetickú kompresiu
zdrojové písmená sú dokonca zlomkom bitov.
Použitie rozšírenia na predponové kódy.
Rozširujúce sa stromy boli prvýkrát opísané v roku 1983 a podrobnejšie.
recenzované v roku 1985. Spočiatku boli chápané ako akési samovyvážené
stromy pre binárne vyhľadávanie a tiež sa ukázalo, že umožňujú
Najrýchlejšia implementácia prioritných frontov. Ak ide o rozširujúci sa uzol stromu
je k dispozícii, potom sa predĺži. To znamená, že dostupný uzol sa stane
koreň, všetky uzly naľavo od neho tvoria nový ľavý podstrom, uzly napravo -
nový pravý podstrom. Rozšírenie sa dosiahne prechádzaním stromu zo starého
root do cieľového uzla a vykonaním miestnych zmien v tomto prípade, teda cenou
expanzia je úmerná dĺžke prejdenej dráhy.
Tarjan a Slayton ukázali, že expandujúce stromy sú staticky optimálne.
Inými slovami, ak sa kódy dostupných uzlov berú podľa stat
rozdelenie pravdepodobnosti, potom rýchlosť prístupu k rozširujúcemu sa stromu a
staticky vyvážené, optimalizované touto distribúciou, bude
sa navzájom líšia konštantným koeficientom, viditeľným pri dostatočnom
dlhý rad prístupov. Pretože Huffmanov strom je príkladom
staticky vyvážený strom, potom pomocou kompresného rozšírenia
údajov, bude veľkosť komprimovaného textu ležať v rámci určitého koeficientu od
veľkosť archívu získaného pomocou Huffmanovho kódu.
Ako bolo pôvodne opísané, rozšírenie sa vzťahuje na skladovanie stromov
dáta vo vnútorných uzloch, nie listy. Stromy prefixového kódu nesú všetko
vaše údaje sú iba v listoch. Existuje však možnosť rozšírenia tzv
polovičná prípona, ktorá je použiteľná pre strom prefixových kódov. S ním, cieľ
uzol sa nepresunie do koreňového adresára a nevykonávajú sa úpravy jeho nástupcov,
namiesto toho je cesta od koreňa k cieľu jednoducho polovičná. Poloexpanzné dosahuje
rovnaké teoretické limity v rámci konštantného koeficientu ako
rozšírenie.
V prípade cik-cak prechádzania lexikografického stromu je držanie as
expanzia a poloexpanzia je komplikovanejšia, na rozdiel od priamej trasy pozdĺž
ľavý alebo pravý okraj stromu k cieľovému uzlu. Tento jednoduchý prípad je znázornený v
Obrázok 2. Vplyv polovičnej expanzie na cestu od koreňa (uzol w) k listu
uzol A spočíva vo výmene každého páru vnútorných za sebou
ďalšie uzly, v dôsledku čoho sa dĺžka cesty od koreňa po listový uzol skráti o
2 krát. V procese polovičnej expanzie uzly každého páru, ďalej od koreňa,
sú zahrnuté v novej ceste (uzly x a z) a bližšie
vylúčené (uzly w a y).
Zachovanie lexikografického poriadku pomocou semi-expanznej operácie v kódových stromoch
predpona je voliteľná. Jediná dôležitá vec v operáciách s kódom
predpona je presná zhoda so stromom použitým pri kompresii
strom používaný v postupe nasadenia. Akákoľvek vykonaná zmena
medzi po sebe idúcimi písmenami, sa vykonáva len vtedy, ak
oba postupy vykonajú rovnaké zmeny v rovnakom poradí.
Potreba udržiavať lexikografický poriadok značne zjednodušuje vedenie o
polovičné expanzné operácie odstránením cikcakového puzdra. To môže byť
Pri zapisovaní alebo prenose údajov je často užitočné zmenšiť veľkosť spracovávaných údajov. Technológia, ktorá tento cieľ dosahuje, sa nazýva kompresia údajov. Existuje mnoho metód kompresie dát, pričom každá má svoju špecifickú oblasť použitia, v ktorej dáva najlepšie alebo naopak najhoršie výsledky.
Metóda kódovania dĺžky behu
Kódovanie dĺžky cyklu poskytuje najlepšie výsledky, ak údaje, ktoré sa majú komprimovať, pozostávajú z dlhých sekvencií rovnakých hodnôt. V podstate takýto spôsob kódovania spočíva práve v nahradení takýchto sekvencií kódovou hodnotou, ktorá určuje opakovanú hodnotu a počet jej opakovaní v danej sérii. Napríklad na písanie kódovanej informácie, že sekvencia bitov pozostáva z 253 jednotiek, za ktorými nasleduje 118 núl a ďalších 87 jednotiek, zaberie podstatne menej miesta ako vymenovanie všetkých týchto 458 bitov.
Príklad. Pomocou metódy kódovania dĺžky série, sekvenciu: 1111111111100000000000000000 - možno znázorniť takto: 10.
Relatívna metóda kódovania
V niektorých prípadoch môžu informácie pozostávať z blokov údajov, z ktorých každý sa len mierne líši od predchádzajúceho. Príkladom môžu byť sekvenčné snímky videa. V takýchto prípadoch sa používa metóda relatívneho kódovania. Tento prístup zahŕňa zaznamenávanie rozdielov, ktoré existujú medzi po sebe nasledujúcimi dátovými blokmi, namiesto zaznamenávania týchto blokov samotných, t.j. každý blok je zakódovaný z hľadiska jeho vzťahu k predchádzajúcemu bloku.
Príklad. Pri použití metódy relatívneho kódovania je postupnosť čísel: 1476; 1473; 1480; 1477 - možno znázorniť takto: 1476; -3; +7; -3.
Kódovanie závislé od frekvencie
Táto technika kompresie dát zahŕňa použitie frekvenčne závislého kódovania, v ktorom je dĺžka bitového vzoru reprezentujúceho dátovú položku nepriamo úmerná frekvencii, pri ktorej sa položka používa. Takéto kódy sú zaradené do skupiny kódov s premenlivou dĺžkou, t.j. dátové prvky v týchto kódoch sú reprezentované bitovými vzormi rôznych dĺžok. Ak vezmeme anglický text zakódovaný pomocou frekvenčne závislej metódy, potom najbežnejšie znaky [e, t, a, i] budú reprezentované krátkymi bitovými kombináciami a tie menej bežné znaky dlhšími bitovými kombináciami. Výsledkom je kratšia reprezentácia celého textu ako pri použití bežného kódu ako Unicode alebo ASCII. Konštrukcia algoritmu, ktorý sa bežne používa pri navrhovaní frekvenčne závislých kódov, sa pripisuje Davidovi Huffmanovi, a preto sa takéto kódy často označujú ako Huffmanove kódy. Väčšina dnes používaných frekvenčne závislých kódov sú Huffmanove kódy.
Príklad. Predpokladajme, že je potrebné zakódovať sekvenciu: αγααβααγααβαλααβαβαβαβαα, ktorá pozostáva zo štyroch symbolov α, β, γ a λ, pomocou frekvenčne závislej metódy: Okrem toho sa v tejto sekvencii α vyskytuje 15-krát, β - 6-krát, γ - 2-krát a λ - 1-krát.
Vyberme si nasledujúci binárny kód na reprezentáciu symbolov v súlade s Huffmanovou metódou:
a - 1
β - 01
γ - 001
λ - 000
Metóda Lempel-Ziv
Táto metóda je pomenovaná po jej tvorcoch Abrahamovi Lempelovi a Jacobovi Zivovi. Systémy kódovania Lempel-Ziv využívajú technológiu kódovania adaptívnej slovnej zásoby. V tomto kontexte pojem slovná zásoba označuje súbor stavebných blokov, z ktorých je zostavená komprimovaná správa. Ak je anglický text komprimovaný, stavebnými blokmi môžu byť znaky abecedy. Ak chcete zmenšiť veľkosť údajov uložených vo vašom počítači, potom sa stavebné kamene môžu stať nulami a jednotkami. Počas adaptívneho kódovania slovnej zásoby sa obsah slovnej zásoby môže meniť. Napríklad pri komprimácii anglického textu môže byť vhodné pridať do slovníka koncovku a člen the. V tomto prípade možno priestor zaberaný budúcimi kópiami koncovky a článku zmenšiť ich napísaním ako samostatných odkazov namiesto kombinácie troch rôznych odkazov. Kódovacie systémy Lempel-Ziv využívajú sofistikované a vysoko efektívne techniky prispôsobenia slovnej zásoby počas kódovania alebo kompresie. Najmä v ktoromkoľvek bode procesu kódovania bude slovník pozostávať z tých kombinácií, ktoré už boli zakódované [komprimované].
Ako príklad zvážte, ako môžete vykonať kompresiu správ pomocou konkrétneho systému Lempel-Ziv známeho ako LZ77. Proces začína prakticky prepísaním začiatočnej časti správy, v určitom momente sa však prejde k reprezentácii budúcich segmentov pomocou trojíc, z ktorých každá bude pozostávať z dvoch celých čísel, za ktorými bude nasledovať jeden znak textu. Každá trojica popisuje, ako je zostavená ďalšia časť správy. Predpokladajme napríklad, že rozbalený text vyzerá takto:
αβααβλβ
Reťazec αβααβλβ je už rozbalenou časťou správy. Ak chcete rozbaliť zvyšok správy, musíte najprv rozšíriť riadok tak, že k nemu pripojíte časť, ktorá sa v ňom už vyskytuje. Prvé číslo v trojici udáva, koľko znakov treba v riadku spätne spočítať, aby sa našiel prvý znak pridaného segmentu. V tomto prípade je potrebné napočítať v opačnom smere 5 znakov a dostaneme sa k druhému znaku a zľava od už rozbaleného reťazca. Druhé číslo v trojici udáva počet po sebe idúcich znakov napravo od iniciály, ktoré tvoria pridaný segment. V našom príklade je toto číslo 4, čo znamená, že pridaný segment bude ααβλ. Skopírujte ho na koniec riadku a získajte novú hodnotu rozbalenej časti správy: αβααβλβααβλ.
Nakoniec posledný prvok [v našom prípade je to symbol α] je potrebné umiestniť na koniec rozšíreného reťazca, v dôsledku čoho dostaneme úplne rozbalenú správu: αβααβλβααβλα.
Kompresia obrázkov
Bitmapový formát používaný v moderných digitálnych konvertoroch obrázkov kóduje obrázky vo formáte troch bajtov na pixel, čo vedie k vytváraniu objemných, nepohodlných pri práci s bitmapovými súbormi. Špeciálne pre tento formát bolo vyvinutých mnoho komprimačných schém, ktoré sú navrhnuté tak, aby zmenšili priestor zaberaný takýmito súbormi na disku. Jednou z takýchto schém je GIF vyvinutý spoločnosťou CompuServe. Použitá metóda spočíva v znížení počtu farebných odtieňov pixelu na 256, v dôsledku čoho môže byť farba každého pixelu reprezentovaná jedným bajtom namiesto troch. Pomocou tabuľky nazývanej farebná paleta je každý z platných pixelových odtieňov spojený s nejakou kombináciou červenej, zelenej a modrej farby. Zmenou použitej palety môžete zmeniť farby, ktoré sa objavia na obrázku.
Zvyčajne sa jedna z farieb v palete GIF interpretuje ako "priehľadnosť". To znamená, že v oblastiach obrázka vyplnených touto farbou sa zobrazuje farba pozadia, na ktorom sa nachádza. Vďaka tomu a relatívnej jednoduchosti použitia obrázkov sa formát GIF rozšíril v počítačových hrách, kde sa po obrazovke pohybuje veľa rôznych obrázkov.
Ďalším príkladom systému kompresie obrazu je formát JPEG. Ide o štandard vyvinutý Spoločnou skupinou fotografických expertov [odtiaľ názov tohto štandardu] v rámci organizácie ISO. Formát JPEG sa ukázal ako efektívny spôsob prezentácie farebných fotografií. Práve z tohto dôvodu tento štandard používajú výrobcovia moderných digitálnych fotoaparátov. Dá sa očakávať, že v budúcnosti bude mať významný vplyv na priemysel digitálneho zobrazovania.
V skutočnosti štandard JPEG obsahuje niekoľko spôsobov reprezentácie obrázka, pričom každý má svoj vlastný účel. Napríklad pri požiadavke na maximálnu vernosť obrazu ponúka formát JPEG „bezstratový“ režim, ktorého názov priamo naznačuje, že procedúra kódovania obrazu prebehne bez akejkoľvek straty informácií. V tomto režime sa miesto šetrí ukladaním rozdielov medzi po sebe nasledujúcimi pixelmi, a nie jasu každého pixelu jednotlivo. Podľa teórie možno vo väčšine prípadov mieru rozdielu medzi susednými pixelmi zakódovať do kratších bitových vzorov, než sú skutočné hodnoty jasu jednotlivých pixelov. Existujúce rozdiely sú zakódované pomocou kódu s premenlivou dĺžkou, ktorý sa používa na ďalšie zníženie spotreby pamäte.
Žiaľ, pri použití „bezstratového“ režimu sú vygenerované rastrové obrazové súbory také veľké, že sa ťažko spracovávajú pomocou moderných technológií, a preto sa v praxi používajú len zriedka. Väčšina existujúcich aplikácií používa inú štandardnú metódu formátu JPEG – základný režim. V tomto režime je každý z pixelov tiež reprezentovaný tromi zložkami, no v tomto prípade ide už o jednu jasovú zložku a dve farebné zložky. Zhruba povedané, ak vytvoríme obraz len z jasových zložiek, potom uvidíme čiernobielu verziu obrazu, keďže tieto zložky odrážajú iba úroveň osvetlenia pixelu.
Dôvodom tohto rozdielu medzi farbou a jasom je, že ľudské oko je citlivejšie na zmeny jasu ako farby. Uvažujme napríklad o dvoch jednotne sfarbených modrých obdĺžnikoch, ktoré sú úplne rovnaké, až na to, že jeden má na sebe malý jasný bod, zatiaľ čo druhý má malý zelený bod s rovnakým jasom ako modré pozadie. Pre oko bude ľahšie rozpoznať svetlý bod ako zelený. Základný režim JPEG využíva túto funkciu tým, že zakóduje jasovú zložku každého pixelu, ale spriemeruje farebné zložky pre bloky so štyrmi pixelmi a zapíše farebné zložky len pre tieto bloky. Výsledkom je, že výsledná prezentácia obrazu si zachováva náhle zmeny jasu, ale náhle zmeny farieb zanecháva rozmazané. Výhodou tejto schémy je, že každý blok štyroch pixelov je reprezentovaný iba šiestimi hodnotami [štyri hodnoty pre jas a dve pre farby], a nie dvanásť, ktoré by bolo potrebné pri použití schémy troch hodnôt. na pixel.
Hodnota avatarov v psychológii
Hodnota avatarov v psychológii
Ako zdôrazniť písmeno v MS Word
Čo to znamená, ak je avatar osoby
Ako si vytvoriť svoj vlastný Twitter moment