Vitajte na [www.pocitac.win] Pripojiť k domovskej stránke Obľúbené stránky
Tu je rozdelenie bežných bezstratových binárnych metód kompresie:
1. Identifikácia redundancie a vzorov:
* Opakovanie: Najjednoduchšia forma. Ak sa rovnaký bajt alebo sekvencia bajtov opakuje viackrát, algoritmus ich nahrádza markerom označujúcou opakovanú sekvenciu a počet opakovaní. Toto sa často nazýva kódovanie dĺžky (rle) . Napríklad:
* Originál:`aaaaabbbbcccdd`
* Rle komprimované:`5a3b3c2d` (5 A, 3 B's, 3 C's, 2 d'S)
* RLE je najúčinnejšia, keď existujú dlhé zjazdy rovnakých údajov.
* Kompresia založená na slovní: Táto metóda vytvára slovník (alebo tabuľku) často vyskytujúcich sekvencií bajtov. Namiesto ukladania celej sekvencie zakaždým algoritmus ukladá index (alebo kód) predstavujúci túto sekvenciu v slovníku.
* lz77 a lz78 (a ich varianty lzw, deflate): Jedná sa o algoritmy založené na základnom kamennom slovníku. Pracujú udržiavaním posuvného okna nedávno videných údajov.
* lz77: Vyzerá porovnávacie sekvencie * v * posuvnom okne. Keď nájde zhodu, ukladá `(vzdialenosť, dĺžka) pár, kde:
* `Vzdialenosť":Ako ďaleko späť v okne sa zápas začína.
* `Dĺžka:Ako dlho je zodpovedajúca sekvencia.
* lz78: Stavia slovník * nových * fráz, keď sa s nimi stretáva. Kóduje každú novú frázu ako `(index, znak)`, kde:
* `INDEX`:Index najdlhšej * predpony frázy už v slovníku.
* `Charakter`:znak, ktorý rozširuje predponu, aby vytvorila novú frázu.
* lzw (Lempel-Ziv-Welch): Zlepšenie LZ78. Začína sa predinitializovaným slovníkom obsahujúcim všetky jednotlivé znaky. Dynamicky vytvára slovník, keď spracováva údaje. LZW je známa tým, že sa používa vo formáte obrazu GIF (hoci patenty na LZW na chvíľu spôsobili problémy).
* deflate: Kombinuje LZ77 s kódovaním Huffman (vysvetlené nižšie) pre ešte lepšiu kompresiu. Používa sa v GZIP, ZLIB a PNG. Je to veľmi bežné.
2. Štatistické kódovanie (kódovanie entropie):
* Tieto metódy analyzujú frekvenciu rôznych symbolov (bajtov) v údajoch a priraďujú kratšie kódy častejším symbolom a dlhším kódom menej častým. Je to založené na teórii informácií, kde pravdepodobnejšie udalosti vyžadujú prenos menej informácií.
* Huffman Coding: Schéma kódovania s premenlivou dĺžkou. Vytvára binárny strom na základe frekvencií symbolov. Častejšie symboly sú umiestnené bližšie ku koreňu stromu, čo vedie k kratším dĺžkam kódu.
* Algoritmus generuje kód predpony, čo znamená, že žiadny kód nie je predponou iného kódu, ktorý bráni nejednoznačnosti počas dekódovania.
* aritmetické kódovanie: Predstavuje celý tok údajov ako jedno frakčné číslo medzi 0 a 1. Dĺžka frakcie je určená pravdepodobnosťou symbolov. Aritmetické kódovanie často dosahuje lepšiu kompresiu ako kódovanie Huffmana, najmä pri riešení symbolov, ktoré majú veľmi odlišné pravdepodobnosti. Je to však výpočtovejšie intenzívne.
ilustratívny príklad (zjednodušené):
Predstavte si, že máme nasledujúce údaje:`aabbbbcccaadddeeeffff`
1. rle: Môže komprimovať na `2a3b3c2a3d3e4f` (redukuje ho, ale nie drasticky).
2. Huffman Coding:
* Frekvenčná analýza:
* A:5
* B:3
* C:3
* D:3
* E:3
* F:4
* Konštrukcia stromov Huffman (príklad):
* Kombinujte najmenej časté:B (3) a C (3) -> Uzol BC (6)
* Kombinujte d (3) a e (3) -> uzol de (6)
* Kombinujte BC (6) a DE (6) -> uzol BCDE (12)
* Kombinujte f (4) a a (5) -> uzol AF (9)
* Kombinujte AF (9) a BCDE (12) -> Root (21)
* Priraďte kódy (0 pre ľavú stranu, 1 pre pravé prechádzanie stromu) - * To sa môže líšiť v závislosti od implementácie! *
* A:00
* B:100
* C:101
* D:110
* E:111
* F:01
* Komprimované údaje:`000010010010010110110111111111110101010101` (oveľa kratšia ako originál, najmä pre veľké súbory údajov!)
Kľúčové úvahy:
* zložitosť: Rôzne algoritmy majú rôzne výpočtové zložitosti. Niektoré sú rýchlejšie pre kódovanie/dekódovanie, ale dosahujú nižšie kompresné pomery. Ostatné sú pomalšie, ale dosahujú vyššiu kompresiu.
* Kompresný pomer: Pomer pôvodnej veľkosti súboru k veľkosti komprimovaného súboru. Vyšší pomer naznačuje lepšiu kompresiu.
* Použitie pamäte: Algoritmy vyžadujú pamäť pre vyrovnávacie pamäte, slovníky a stromové štruktúry. Použitie pamäte môže byť obmedzujúcim faktorom, najmä pri komprimovaní veľkých súborov.
* Typ údajov: Niektoré algoritmy sú vhodnejšie pre konkrétne typy údajov (napr. Text, obrázky, zvuk). Napríklad algoritmy, ktoré využívajú priestorovú lokalitu, sú dobré pre obrázky.
V súhrne fungujú binárne kompresné algoritmy:
1. Analýza údajov: Identifikačné vzorce, opakovania a štatistické frekvencie.
2. , ktoré predstavujú údaje efektívnejšie: Použitie kratších kódov pre spoločné prvky a dlhšie kódy pre vzácne prvky.
3. Ukladanie metadát: Ukladanie informácií potrebných na dekomprimovanie údajov (napr. Slovníky, Huffman stromy).
Výber algoritmu závisí od konkrétnych požiadaviek aplikácie vrátane požadovaného pomeru kompresie, dostupných výpočtových zdrojov a typu komprimovaných údajov. Hybridné prístupy (napríklad deflát) sa často používajú na kombináciu sily rôznych techník.