Kompresia s minimálnou redundanciou Teraz, keď je k dispozícii trieda toku bitov, môžu byť použité pri zvažovaní algoritmov kompresie a obnovy dát. Začneme so štúdiou kódovania algoritmov s minimálnou redundanciou a potom

Kompresia s použitím slovníka do roku 1977, hlavné úsilie v oblasti štúdie kompresných algoritmov bolo koncentrovaných okolo kódovacích algoritmov s minimálnym redundanciou, podobne ako algoritmy Shannon Fano alebo Huffman a boli venované buď

Kompresia dát Akákoľvek ideálna metóda kompresie by nemala umožniť výrazné straty kvality, to znamená, že zníženie množstva údajov by nemalo viesť k strate informácií. To znamená, že všetky zmeny zvukového signálu musia byť pod prahom sluchu. To je obzvlášť dôležité

3.2. Veľkosti a kompresia súborov pre to, čo potrebujete na kompresiu obrazu, obraz získaný pomocou šesťčlennej komory by mal mať 18 MB pamäte. Ak je obrázok zaznamenaný v pamäti v tomto formulári, potom aj do úložného zariadenia veľkého kontajnera bude môcť zapadnúť

Môj vedecký vedúci a ja som pripravil malú monografiu na spracovanie obrazu. Rozhodol som sa predložiť Súdnemu dvoru komunity Hubrasom, kapitolu venovaný algoritmom kompresie obrazu. Vzhľadom k tomu, že súčasť jedného príspevku, celá kapitola je vhodná, som sa rozhodol zlomiť ho na troch príspevkoch:
1. Metódy kompresie údajov;
2. Kompresia obrázkov bez straty;
3. Kompresia obrázkov so stratami.
Nižšie sa môžete oboznámiť s prvým príspevkom série.

V súčasnosti existuje veľký počet kompresných algoritmov bez straty, ktoré možno rozdeliť do dvoch veľkých skupín:
1. Algoritmy prúdu a slovníka. Táto skupina zahŕňa algoritmy rodín RLE (Run-dĺžka kódovanie), LZ *, atď. Funkcia všetkých algoritmov pre túto skupinu je, že keď kódovanie nepoužíva informácie o frekvenciách znakov v správe, ale informácie o sekvenciách sa zúčastnili skôr.
2. Štatistické (entropy) kompresné algoritmy. Táto skupina algoritmov komprimuje informácie pomocou frekvencií nerovnomernosti, s ktorými sa v správe nachádzajú rôzne znaky. Algoritmy tejto skupiny zahŕňajú algoritmy pre aritmetické a predpony kódovanie (pomocou Shannon-Fanno, Huffman stromy).
V samostatnej skupine môžete vybrať algoritmy konverzie informácií. Algoritmy tejto skupiny nevytvárajú priamu kompresiu informácií, ale ich použitie výrazne zjednodušuje ďalšiu kompresiu s použitím prietoku, slovnej zásoby a entropických algoritmov.

ALGORITHMI

Kódovanie sériovej dĺžky

Hlavnou nevýhodou tohto algoritmu je jeho extrémne nízka účinnosť na sekvenciach ne-opakujúcich sa znakov. Napríklad, ak uvažujete o sekvencii "ABABAB" (6 BYTES), potom po nanesení algoritmu RLEA sa zmení na "1A1B1B1A1B" (12 bajtov). Na vyriešenie problému non-opakujúcich sa znakov existujú rôzne metódy.

Najjednoduchšou metódou je nasledujúca modifikácia: Bajt, kódovanie počtu opakovaní, by mal ukladať informácie nielen o počte opakovaní, ale aj na ich dostupnosti. Ak je prvý bit 1, potom ďalších 7 bitov označuje počet opakovaní zodpovedajúceho charakteru, a ak je prvý bit 0, potom ďalšie 7 bitov ukazujú počet znakov, ktoré je potrebné prijať bez opakovania. Ak kódujete "ABABAB" pomocou tejto modifikácie, potom sa dostaneme "-6ABABABAB" (7 BYTES). Je zrejmé, že navrhovaná technika umožňuje výrazne zvýšiť účinnosť algoritmu RLEA na non-reffection symbolové sekvencie. Implementácia navrhovaného prístupu je uvedená 1:

1. typ
2. funkcia RLEENČKA (INMSG: ShortString): TrleencodedString;
3. Matchfl: Boolean;
4. Matchcount: skratka;
5. Encodedstring: TrleencodedString;
6. N, i: bajt;
7. začať.
8. N: \u003d 0;
9. SetLength (EncodedString, 2 * Dĺžka (INMSG));
10. zatiaľ čo dĺžka (inmsg)\u003e \u003d 1
11. začať.
12. Matchfl: \u003d (dĺžka (inmsg)\u003e 1) a (inmsg [1] \u003d inmsg [2]);
13. Matchcount: \u003d 1;
14. zatiaľ čo (matchcount.<= 126 ) and (MatchCount < length(InMsg) ) and ((InMsg[ MatchCount] = InMsg[ MatchCount + 1 ] ) = MatchFl) do
15. Matchcount: \u003d Matchcount + 1;
16. ak potom.
17. začať.
18. N: \u003d n + 2;
19. EncodedString [N - 2]: \u003d Matchcount + 128;
20. Encodedstring [n - 1]: \u003d ORD (INMSG [1]);
21. inak.
22. začať.
23. ak Matchcount.<> Dĺžka (inmsg)
24. Matchcount: \u003d Matchcount - 1;
25. N: \u003d n + 1 + matchcount;
26. EncodedString [n - 1 - Matchcount]: \u003d - Matchcount + 128;
27. pre I: \u003d 1 na Matchcount
28. ENCODEDSTRING [N - 1 - MATCHCOST + I]: \u003d ORD (INMSG [I]);
29. koniec;
30. vymazať (INMSG, 1, MATCHCOUNT);
31. koniec;
32. Setlength (encodedstring, n);
33. Rleencode: \u003d encodedstring;
34. koniec;

1. typ
2. Trleencodedstring \u003d rad bajtov;
3. funkcia ROLECODE (INMSG: TRLEUNDOCODEDSTRING): ShortString;
4. RepeatCount: Krátk;
5. i, j: slovo;
6. Outmsg: gratsstring;
7. začať.
8. Outmsg: \u003d "";
9. i: \u003d 0;
10. kým.< length(InMsg) do
11. začať.
12. Opakovanie: \u003d inmsg [i] - 128;
13. i: \u003d i + 1;
14. ak sa opakuje.< 0 then
15. začať.
16. RepeatCount: \u003d abs (RepeatCount);
17. pre j: \u003d i až i + repeatcount - 1
18. Outmsg: \u003d outmsg + CHR (inmsg [j]);
19. i: \u003d i + repeatcount;
20. inak.
21. začať.
22. pre j: \u003d 1 na opakovanie
23. Outmsg: \u003d outmsg + CHR (inmsg [i]);
24. i: \u003d i + 1;
25. koniec;
26. koniec;
27. ROLECODE: \u003d OUTMSG;
28. koniec;

1. const.
2. Eomsg \u003d "|" ; \\ T
3. funkcia BWTencode (INMSG: ShortString): ShortString;
4. Outmsg: gratsstring;
5. Lastchar: Ansichar;
6. N, i: slovo;
7. začať.
8. Inmsg: \u003d inmsg + eomsg;
9. N: \u003d dĺžka (inmsg);
10. SHANCETTABLE [1]: \u003d INMSG;
11. pre i: \u003d 2 až n
12. začať.
13. Lastchar: \u003d inmsg [n];
14. Inmsg: \u003d lastchar + kópia (inmsg, 1, n - 1);
15. SHOUPTTABLE [I]: \u003d INMSG;
16. koniec;
17. Trieda;
18. Outmsg: \u003d "";
19. pre i: \u003d 1 až n
20. OUTMSG: \u003d OUTMSG + SHOUPTTABLE [I] [N];
21. BWTENCODE: \u003d OUTMSG;
22. koniec;

Tí. Výsledkom priamej transformácie bude línia "| nnai". Je ľahké si všimnúť, že tento riadok je oveľa lepší ako originál, stlačenie rle algoritmus, pretože Existuje dlhá subsekvencia opakovaných písmen.
Tento účinok sa môže dosiahnuť inými transformáciami, ale výhodou transformácie BWT je, že je reverzibilná, hoci reverzná transformácia je zložitejšia. Ak chcete obnoviť pôvodnú čiaru, musia sa vykonať nasledujúce kroky:
Vytvorte prázdnu maticu s veľkosťou n * n, kde n-počet znakov v kódovanej správe;
Vyplňte prázdny stĺpec kódovanej správy;
Zoradiť rady tabuľky v lexikografickom poradí;
Opakujte kroky 2-3, kým neexistujú prázdne stĺpce;
Vráťte reťazec, ktorý končí koncom symbolu čiary.

Implementácia reverznej transformácie na prvý pohľad nepredstavuje zložitosť a jeden z uskutočnení je uvedený v zozname 4.

1. const.
2. Eomsg \u003d "|" ; \\ T
3. fUNKCIA BWTDDECODE (INMSG: ShortString): ShortString;
4. Outmsg: gratsstring;
5. SHOWTTTABLE: ARRAY ROKUMENTU;
6. N, i, j: slovo;
7. začať.
8. Outmsg: \u003d "";
9. N: \u003d dĺžka (inmsg);
10. Setlength (posuntateľný, n + 1);
11. pre i: \u003d 0 až n
12. SHANCETTABLE [I]: \u003d "";
13. pre i: \u003d 1 až n
14. začať.
15. pre j: \u003d 1 až n
16. SHOUNTTABLE [J]: \u003d INMSG [J] + SHOUNTTABLE [J];
17. Trieda;
18. koniec;
19. pre i: \u003d 1 až n
20. ak sa snímateľná [i] [n] \u003d eomsg, že
21. OUTMSG: \u003d SHOUPTTTABLE [I];
22. odstránenie (OUTMSG, N, 1);
23. BWTDECODE: \u003d OUTMSG;
24. koniec;

Po triedení tabuľky získaného na siedmom kroku musíte vybrať zo stola reťazca končiacim symbolom "|". Je ľahké si všimnúť, že toto je len reťazec. Tak Konverziu BWT sme považovali za konkrétny príklad.

Súčet, možno povedať, že hlavná výhoda skupiny RLE ALGORITHMS je jednoduchosť a rýchlosť práce (vrátane rýchlosti dekódovania) a hlavná mínus je neefektívnosť na non-rafinujúcich znakov. Použitie špeciálnych permutácií zvyšuje účinnosť algoritmu, ale tiež výrazne zvyšuje prevádzkový čas (najmä dekódovanie).

Slovo kompresia (LZ algoritmy)

Najjednoduchší variant algoritmu slovnej zásoby je opísaný nižšie:
Inicializujte slovník všetkými znakmi nachádzajúcimi sa v vstupnom riadku;
Nájdite v dlhej sekvencii (s) v slovníku, ktorý sa zhoduje so začiatkom kódovanej správy;
Výstup nájdeného sekvencie a odstrániť ho zo začiatku zakódovaného správy;
Ak nedosiahnete koniec správy, počítať nasledujúci znak a pridajte SC do slovníka, prejdite na krok 2. Inak výstup.

Napríklad inicializovaný slovník pre frázu "cukushkukukukukuupylusushon" je uvedený v tabuľke. 3:

V procese kompresie bude slovník doplnený sekvenciami. Proces dobíjania slovníka je uvedený v tabuľke. štyri.

Pri opise algoritmu bol popis situácie zámerne vynechaný, keď je slovník úplne vyplnený. V závislosti od variantu algoritmu je možné rôzne správanie: plné alebo čiastočné čistenie slovníka, prestaňte naplniť slovník alebo rozšírenie slovníka s vhodným zvýšením bitového kódu. Každý z týchto prístupov má určité nevýhody. Napríklad, zastavenie dopĺňania slovníka môže viesť k situácii, keď v slovenčina uložené sekvencie, ktoré sa vyskytujú na začiatku stlačiteľného reťazca, ale neboli nájdené v budúcnosti. Zároveň môže čistenie slovníka viesť k odstráneniu častých sekvencií. Väčšina implementácií použitých pri plnení slovníka začína sledovať stupeň kompresie a keď sa zníži pod určitú úroveň, slovník je reštrukturalizácia. Ďalej bude zvážiť najjednoduchšie vykonávanie, zastavenie dobíjania slovníka, keď je plnenie.

Ak chcete začať, definujeme slovník ako záznam uložený nielen na splnenie podreťazca, ale aj počet uložených v slovníku Substering:

Včasné následky sú uložené v slovách masívu a ich kód sú v tomto poli.
Taktiež definujeme funkcie vyhľadávania v slovníku a pridanie do slovníka:

1. const.
2. Max_dict_length \u003d 256;
3. funkcia FindinDict (D: T-Thictionary; Str: ShortString): Integer;
4. r: Integer;
5. i: Integer;
6. fl: boolean;
7. začať.
8. r: \u003d - 1;
9. ak D. WordCount\u003e 0 Potom
10. začať.
11. i: \u003d D. WordCOUNT;
12. fl: \u003d false;
13. zatiaľ čo (nie fl) a (i\u003e \u003d 0)
14. začať.
15. i: \u003d I - 1;
16. fL: \u003d D. Slová [i] \u003d str;
17. koniec;
18. koniec;
19. ak sa potom.
20. r: \u003d I;
21. FindEdict: \u003d r;
22. koniec;
23. postup AddDodstika (VAR D: TDICÁCIE; STR: SHRIVENTING);
24. začať.
25. ak D. WordCount.< MAX_DICT_LENGTH then
26. začať.
27. D. WordCount: \u003d D. WordCOUNT + 1;
28. Dĺžka (d. Slová, D. WordCOUNT);
29. D. Slová [D. WordCount - 1]: \u003d Str;
30. koniec;
31. koniec;

1. funkcia LZWENCODE (INMSG: ShortString): TencodedString;
2. OUTMSG: TencodedString;
3. tMPSTR: ShortString;
4. D: NEBEZPEČNOSTI;
5. i, N: Bajt;
6. začať.
7. Dĺžka (outmsg, dĺžka (inmsg));
8. N: \u003d 0;
9. Initdikt (d);
10. zatiaľ čo dĺžka (inmsg)\u003e 0
11. začať.
12. tMPstr: \u003d inmsg [1];
13. zatiaľ čo (nájdené (D, TMPSTR)\u003e \u003d 0) a (dĺžka (inmsg)\u003e Dĺžka (TMPSTR))
14. tMPSTR: \u003d TMPSTR + INMSG [D lengthŽKA (TMPSTR) + 1];
15. ak FindEdict (D, TMPST)< 0 then
16. odstráňte (TMPstr, dĺžka (TMPSTR), 1);
17. Outmsg [n]: \u003d FindIndict (D, TMPST);
18. N: \u003d n + 1;
19. odstrániť (inmsg, 1, dĺžka (TMPSTR));
20. ak je dĺžka (inmsg)\u003e 0
21. AddDodikt (D, TMPSTR + INMSG [1]);
22. koniec;
23. Dĺžka (outmsg, n);
24. Lzwencode: \u003d outmsg;
25. koniec;

Jediný problém je možný v nasledujúcej situácii: keď je potrebné dekódovať následnosť, ktorá ešte nie je v slovníku. Je ľahké sa uistiť, že je možné len vtedy, keď je potrebné extrahovať podklad, ktorý sa má pridať v aktuálnom kroku. A to znamená, že podreťazc spĺňa šablónu CSc, t.j. Spustí sa a končí rovnakým symbolom. V rovnakej dobe CS je podklad pridaná v predchádzajúcom kroku. Uvažovaná situácia je jediná, keď je potrebné dekódovať ešte nepridané do reťazca. Vzhľadom na vyššie uvedené môžete ponúknuť nasledujúcu možnosť dekódovať komprimovaný reťazec:

1. funkcia LZWDECODE (INMSG: TencodedString): ShortString;
2. D: NEBEZPEČNOSTI;
3. Outmsg, TMPstr: ShortString;
4. i: Bajt;
5. začať.
6. Outmsg: \u003d "";
7. tMPSTR: \u003d "";
8. Initdikt (d);
9. pre i: \u003d 0 na dĺžku (inmsg) - 1
10. začať.
11. ak inmsg [i]\u003e \u003d D. Wordcountte
12. tMPSTR: \u003d D. Slová [inmsg [i - 1]] + D. Slová [inmsg [i - 1]] [1]
13. inak.
14. tMPstr: \u003d D. Slová [inmsg [i]];
15. Outmsg: \u003d outmsg + tmpstr;
16. ak i\u003e 0
17. AddDodict (D, D. Slová [inmsg [i - 1]] + TMPstr [1]);
18. koniec;
19. Lzwdecode: \u003d outmsg;
20. koniec;

Kódovanie entropie

Kódovanie Shannon Fano Strom

Bez použitia kódovania, správa bude trvať 40 bitov (za predpokladu, že každý symbol je kódovaný 4 bitmi) a pomocou algoritmu Shannon Fano 4 * 2 + 2 + 4 + 4 + 3 + 3 + 3 \u003d 27 bitov. Objem správy sa znížil o 32,5%, ale ukázané, že tento výsledok sa môže výrazne zlepšiť.

Kódovanie s Huffmanmi

Zvážte ten istý príklad ako v prípade algoritmu Shannon Fano. Huffman Strom a kódy získané pre správu "AAAAABVGDEZH" sú uvedené na obr. 2:

Je ľahké vypočítať, že objem kódovanej správy bude 26 bitov, čo je menšie ako v algoritme Shannon Fano. Samostatne stojí za zmienku, že vzhľadom na popularstvo algoritmu Huffman v súčasnosti existuje mnoho variantov Huffman kódovania, vrátane adaptívne kódovanie, ktoré nevyžaduje prenos symbolov.
Medzi nevýhody algoritmu Huffmanom, významnou časťou je problémy spojené s komplexnosťou implementácie. Použitie na skladovanie frekvencií identických symbolov premenných je spojené so stratou presnosti, takže v praxi celé premenné premenné často používajú, ale preto Hmotnosť rodičovských uzlov neustále rastie, skôr alebo neskorší prepad. Tak, napriek jednoduchosti algoritmu, jeho správna implementácia stále môže spôsobiť určité ťažkosti, najmä pre veľké abecedy.

Kódovanie pomocou rezacích stromov funkcií

Strom je postavený tak, aby každý uzol rozdelil abecedu na najzákladnejšie časti. Na obr. 3 znázorňuje príklad pokračovania:

Strom partície vo všeobecnosti nezaručuje optimálne kódovanie, ale poskytuje extrémne vysokú rýchlosť práce na úkor prevádzky prevádzky v uzloch.

Aritmetické kódovanie

Komprimovať informácie - (kompresia dát) Prezentácia informácií (údaje) menším počtom bitov v porovnaní s pôvodnou. Na základe odstránenia redundancie. Rozlišovať S. a. Bez straty informácií as stratou časti informácií, bezvýznamné riešenie úloh. ... ... Encyklopedický slovník psychológie a pedagogiky

adaptívna kompresia informácií bez straty - - [L.G.SUMENKO. \\ T Anglický Ruský slovník o informačnom technológii. M.: GP TSNIIS, 2003.] Témy Informačné technológie Vo všeobecnosti EN APAPTIVE ZMRAZUJÚCEJ ÚDAJE COMPEATIONALDC ... Technický adresár prekladateľa

informácie o tesnení / kompresii - - [L.G.SUMENKO. \\ T Anglický Ruský slovník o informačnom technológii. M.: GP TSNNIIS, 2003.] Témy Informačné technológie Vo všeobecnosti En Compaction ... Technický adresár prekladateľa

digitálne informácie o kompresii - - [L.G.SUMENKO. \\ T Anglický Ruský slovník o informačnom technológii. M.: GP TSNIIS, 2003.] Témy Informačné technológie vo všeobecnosti EN Compression ... Technický adresár prekladateľa

Zvuk je jednoduchá vlna a digitálny signál je reprezentáciou tejto vlny. To sa dosahuje zapamätaním amplitúdy analógového signálu na jednu sekundu. Napríklad v bežnom CD sa zapamätal signál 44100 krát ... ... Wikipedia

Proces, ktorý znižuje množstvo údajov znížením ich nadbytočnosti. Kompresia dát je spojená s kompaktným umiestnením častí dát štandardnej veľkosti. Rozlišovať kompresiu so stratou a bez straty informácií. V angličtine: Údaje ... ... Finančná slovná zásoba

kompresia digitálnych kartografických informácií - spracovanie digitálnych kartografických informácií s cieľom znížiť jeho objem vrátane nadmerných výnimiek v rámci požadovanej presnosti jej prezentácie. [GOST 28441 99] Téma Kartografia Digitálne zovšeobecnenie Pojem Metódy a technológie ... ... Technický adresár prekladateľa

Charakteristickým znakom väčšiny typov údajov je ich nadbytok. Stupeň redundancie dát závisí od typu údajov.
Napríklad pre video dáta, stupeň redundancie niekoľkokrát viac ako pre grafické údaje a stupeň nadbytočnosti grafických údajov je väčší ako stupeň nadbytočnosti textových dát.

Ďalší faktorOvplyvňovanie stupňa redundancie je prijatý kódovací systém. Príkladom kódovacích systémov môže byť konvenčné komunikačné jazyky, ktoré sú akékoľvek iné, ako kódovacie systémy konceptov a myšlienok na vyjadrenie myšlienok. Takže bolo zistené, že kódovanie textových dát s použitím ruského jazyka znamená priemernú redundanciu o 20-25% väčšiu ako kódovanie podobných údajov na prostriedky anglického jazyka.

Pre muža nadbytok Často pripojený z kvalita Informácie, pretože redundancia, spravidla zlepšuje zrozumiteľnosť a vnímanie informácií. Avšak, pokiaľ ide o skladovanie a prenos informácií počítačové vybavenieT. redundancia hrá negatívnu úlohuVzhľadom k tomu, že vedie k zvýšeniu nákladov na skladovanie a prenos informácií. Zvlášť relevantný tento problém sa stáva v prípade spracovania obrovských množstiev informácií s malými množstvami nosičov dát. V tomto ohľade sa problém znižovania redundancie alebo kompresie údajov neustále vznikne.

Ak metódy kompresie údajov sa vzťahujú na pripravené súbory., často namiesto termínu "kompresia dát" konzumuje termín "archiváciu údajov", stlačený Možnosť údajov sa nazýva archív a softvérktoré implementujú metódy kompresie sa nazývajú Archivs.

V závislosti od toho, ktorý objekt je umiestnený údaje, ktoré majú byť komprimované, rozlišuje:

· Kompresia (archivácia) súborov: používa sa na zníženie veľkostí súborov pri ich príprave na prenos komunikačných kanálov alebo na prepravu na externých nosičoch malého kontajnera;

· Kompresné (archivácie) priečinky: Používa sa ako prostriedok na redukciu priečinkov pred dlhým skladom, napríklad so zálohovaním;

· Kompresia (tesnenie) diskov: používa sa na zvýšenie efektivity používania priestranného diskov kompresiou údajov pri ich zaznamenávaní na médiách informácií (spravidla prostredníctvom operačného systému).

Existuje mnoho praktických algoritmus kompresia dát, ale všetky sú založené na tri Teoretické metódy na zníženie zníženia dát.

· Prvá metóda pozostáva v zmena Obsah údajov

· Druhá zmena Štruktúry údaje,

· Tretia - v simultánna zmena Obidve štruktúry a obsah obsahu.

Ak sú údaje komprimované zmena ich obsah metóda kompresie zavolaný nezvratný, To znamená, že pri obnove (rozpínanie) údajov z archívu nedostane úplné vymáhanie informácií. Takéto metódy sa často nazývajú metódy kompresie s regulovanými stratami informácií. Je zrejmé, že tieto metódy môžu byť použité len pre takéto typy údajov, pre ktoré strata časti obsahu nevedie k výraznému skresleniu informácií. Takéto typy údajov zahŕňajú video a zvukové údaje, ako aj grafické údaje. Metódy kompresie s regulovanými stratami informácií poskytujú výrazne väčší kompresný pomer, ale ich je to nemožné aplikovať na textové údaje. Príklady kompresných formátov so stratou informácií môžu byť:

· JPEG - pre grafické údaje;

· MPG - pre video dáta;

· MP3 - pre zvukové údaje.

Ak sú údaje len komprimované pozmeňujúci a doplňujúci návrh údaje,
to metóda kompresie zavolaný reverzibilný. V tomto prípade môžete z archívu tieto informácie úplne obnoviť. Reverzibilné kompresné metódy môžu byť aplikované na všetky typy údajov, ale dávajú malý Stupeň kompresie v porovnaní s ireverzibilnými spôsobmi kompresie. Príklady kompresných formátov bez straty informácií:

· GIF, TIFF - pre grafické údaje;

· AVI - pre video dáta;

· Zip, ARJ, RAR, CAB, LH - pre ľubovoľné typy údajov.

Existuje mnoho rôzne praktické kompresné metódy bez straty informácií, \\ t ktoré spravidla majú rôznu účinnosť rôznych typov údajov a rôznych objemov. Základom týchto metód je však tri teoretické algoritmy:

· Algoritmus dĺžky dĺžky RLE;

Algoritmy skupiny KWE (Kľúčové slovo kódovanie);

· Huffman algoritmus.

Algoritmus RLE.

Algoritmus RLE je založený na myšlienke identifikácie opakovaných dátových sekvencií a nahradenie ich jednoduchšej štruktúry, ktorá označuje kód dát a opakovaný koeficient. Napríklad nechajte taký postup údajov, ktorý podlieha kompresiu:

1 1 1 1 2 2 3 4 4 4

V algoritme RLE sa navrhuje, aby ho nahradil nasledovnou štruktúrou: 1 4 2 2 3 1 4 3, kde prvý počet každého páru čísel je dátový kód a druhý je repetition koeficient. Ak je 1 bajt uložiť každý prvok vstupnej sekvencie, potom celá sekvencia bude trvať 10 bajtov pamäte, zatiaľ čo výstupná sekvencia (komprimovaná možnosť) bude trvať 8 bajtov pamäte. Koeficient v tlakuCharakteristika kompresného pomeru sa vypočíta vzorcom.

Než menej Hodnota kompresného koeficientu Účinný Metóda kompresie. Je zrejmé, že algoritmus RLE sa dá najlepší kompresný efekt s väčšou dĺžkou opakujúcej sa postupnosti údajov. V prípade vyššie uvedeného príkladu, ak bude mať vstupná sekvencia taký formu: 1 1 1 1 1 3 4 4 4, potom je kompresný koeficient bude 60%. V tomto ohľade sa pri kompresii grafických údajov (najmä pre monofónne obrazy) dosahuje väčšia účinnosť algoritmu RLE.

Algoritmy algoritmov skupiny KWE

Kompresný algoritmus pre kľúčové slová je založený na princípe kódovania lexikálnych jednotiek Byetových skupín s pevnou dĺžkou bajtov. Príkladom lexikálnej jednotky môže byť obvyklé slovo. V praxi sú zvolené sekvencie opakovania symbolov pre úlohu lexikálnych jednotiek, ktoré sú kódované reťazcom symbolov (kód) menšou dĺžkou. Výsledok kódovania je umiestnený v tabuľke, ktorý tvorí takzvaný slovná zásoba.

Existuje pomerne niekoľko implementácií tohto algoritmu, medzi ktorými algoritmus LEMPEL-ZIVA (LZ algoritmus) a jeho modifikácia LZW algoritmu (LZW algoritmus) sú najbežnejšia. Slovník v tomto algoritme je potenciálne nekonečný zoznam fráz. Algoritmus začína pracovať s takmer prázdnym slovníkom, ktorý obsahuje iba jeden kódovaný reťazec, takzvaný null reťazec. Pri čítaní nasledujúceho symbolu vstupnej sekvencie údajov sa pridá do aktuálneho riadka. Proces pokračuje, kým súčasný riadok nezodpovedá nejakej frázu zo slovníka. Ale skôr alebo neskôr súčasná čiara prestane hodiť nejaký druh slovníka. V súčasnosti, keď je aktuálna línia posledná zhoda s slovníkom s slovníkom plus, prečítajte si symbol správy, kódovač poskytuje kód, ktorý sa skladá z náhodného indexu a symbolu za ním, čo porušilo línie. Nová fráza pozostávajúca z poradového indexu a nasledujúceho symbolu za ním je pridaný do slovníka. Nabudúce, ak sa táto fráza objaví v správe, môže sa použiť na vybudovanie dlhšej frázy, ktorá zvyšuje mieru kompresii informácií.

Algoritmus LZW je postavený okolo tabuľky frázy (slovník), ktorý nahrádza reťazce znakov stlačiteľnej správy na kódy pevnej dĺžky. Tabuľka má takzvanú pred sebou, to znamená, že pre každú frázu slovníka pozostávajúca z určitej frázy w a symbol K, fráza w je tiež zadaná do slovníka. Ak sú všetky časti slovníka úplne naplnené, kódovanie prestane byť adaptívne (kódovanie nastáva na základe už existujúceho v slovníku fráz).

Algoritmy kompresie tejto skupiny najviac Účinný pre textický Údaje o veľkých objemoch a sú neefektívne pre malé súbory (kvôli potrebe zachovať slovník).

Algoritmus Huffman

Algoritmus Huffmana je založený na myšlienke kódovania bitových skupín. Najprv sa vykonáva frekvenčná analýza sekvencie vstupnej dátovej dát, to znamená, že je nastavená frekvencia každého charakteru. Po tom, znaky sú zoradené znížením frekvencie vstupu.

Základný nápad Je to nasledovné: Čím častejšie sa symbol vyskytne, tým menší je kódovaný. Výsledok kódovania sa zadáva do slovníka potrebného na dekódovanie.

Kompresia dát

Mikhail Svarichevsky

Všetky kompresné algoritmy sú rozdelené do dvoch typov: so stratami a bez.

Kompresia so stratami umožňuje dosiahnuť oveľa väčšiu kompresiu (až 1/30 a menej zo zdrojového objemu).
Napríklad video zachytené GIGABYTE 30 môže byť zapísané na 1 CD.
Avšak stratové kompresné algoritmy vedú k určitým zmenám samotných údajov; Preto je možné použiť takéto algoritmy len na údaje, pre ktoré sú malé deformácie nevýznamné: video, foto-obrázky (algoritmy JPEG), zvuk (MP3 algoritmus).

Kompresia bez strát, samozrejme, nie je tak efektívne (jeho stupeň je veľmi závislý na špecifických údajoch), ale údaje po rozbalení je úplne totožné s originálom. Čo je to absolútne nevyhnutné, napríklad pre textové údaje, programový kód. Tento článok zváži kompresiu bez straty.

Väčšina kompresných algoritmov je rozdelená do dvoch skupín: text zo zdrojov zdrojového súboru v jednej forme alebo inej (metódy slovnej zásoby) sú viditeľné; Druhá (štatistická metóda) Použite skutočnosť, že rôzne znaky alebo symbolické skupiny sa objavujú v súbore s rôznymi pravdepodobnosťami (napríklad písmeno "A" v textových súboroch je oveľa bežnejšie ako "B").

Metódy slov

Slovník obsahuje niektoré slová (zvyčajne 2x; napríklad 4096).
Kompresia sa dosahuje z dôvodu, že číslo slovo v slovníku je zvyčajne oveľa kratšie ako slovo.
Algoritmy slovnej zásoby sú rozdelené do dvoch skupín:
1) Použitie slovníka explicitne (algoritmy LZ78, LZW, LZC, LZT, LZMV, LZJ, LZFG)
Napríklad podľa slovníka
1. "najviac"
2. "Kompresia"
3. "Bez"
4. "Strata"
5. "algoritmy"
Text "Väčšina kompresných algoritmov bez straty" je komprimovaná v "15234".

2) označujúce namiesto čísla slova - poloha vzhľadom na aktuálnu polohu a dĺžku opakujúcej sa miesta (LZ77, LZR, LZSS, LZB, LZH algoritmy)
Napríklad text "ABABBABBABBABAMBABSKOU"
Zmršťovanie v "05ABABBBB5504ABVG65", kde:
"05ABABB" - Poloha 0 znamená, že ďalej 5 znakov idú bez kompresie.
"55" - 5 písmen z pozície oddelené od aktuálneho prúdu na 5 znakoch.
"04ABVG" - 4 ďalšie symboly nie sú komprimované.
"65" -5 písmená z pozície, oddelené od prúdu na 6 znakov.

Modifikácie LZ-algoritmov sa líšia len v spôsoboch prezerania slovníka, vyhľadávania a pridania slov. Niektoré stlačiť rýchlejšie, ale horšie; Iné vyžadujú viac pamäte.

Zvážte modifikovaný algoritmus LZ77.
Archív bude pozostávať z nasledujúcich typov záznamov:
(N, m) - znamená, že z polohy n začína rovnaký riadok m, ako z aktuálnej polohy.
(0, m, "m znaky") - znamená, že potom nasleduje M znaky, ktoré sa nepodarilo komprimovať.

Kompresný algoritmus bude nasledovný: Hľadáme miesto v súbore, počnúc najdlhšou sekvenciou, ktorá zodpovedá sekvencii začínajúcemu na aktuálnom bajtovi. Ak je jej dĺžka väčšia ako 3, potom v archíve, napíšte začiatok a dĺžku sekvencie; V opačnom prípade písať 0, dĺžka sekvencie a samotné nekomprimované symboly. Rozbalenie je ešte jednoduchšie: zatiaľ čo archívny súbor nekončí, čítať 2 čísla (N, M). Ak n \u003d 0, potom M znaky z archívu okamžite vložte do vyrovnávacej pamäte (tieto znaky budú potrebné tiež potrebné) a zápis do výstupného súboru. Ak N.<>0, ktorá je z vyrovnávacej pamäte z polohy N zvládnutia M prvkov do vyrovnávacej pamäte a výstupného súboru.

Existujú však dva problémy:
1) Obmedzená veľkosť pufra: Ak potrebujeme stlačiť súbor veľkosti v 100 MB, nedávame ho do vyrovnávacej pamäte. Preto, keď je vyplnený (povedzme, 75%), budete musieť posunúť údaje do neho na začiatok (napríklad o 25%; Samozrejme, najstaršie postavy sú stratené). To zhoršuje kompresiu, ale urobí algoritmus nenápadný do pamäte.
2) Rýchlosť kompresného programu je veľmi malá. V skutočnosti, ak potrebujete stlačiť veľkosť veľkosti 10kb, bude to vyžadovať, aby sme držali aspoň približne 10 000 * 10 000/2 operácií (10.000 krát, budeme musieť hľadať zhodnúcu subsekciu a každé takéto vyhľadávanie bude mať priemer 10 000/2 operácií). Ak chcete urýchliť vyhľadávaciu operáciu, môžete uložiť v samostatnom počte políčok sekvenčných polôh začínajúcich na CHR (0) znak, CHR (2) ... CHR (255). Potom, keď hľadáme, budeme musieť skontrolovať iba tie kombinácie, ktorého prvé písmeno, ktoré sa zhoduje s prvým písmom požadovaného sekvencie.

Štatistické metódy

Princíp fungovania aritmetika kódovania:

Napríklad sme priradili symbol "A", "B" - a "C" -. Potom, ak máme číslo 0.4, môžeme povedať, že kód "B" je kódovaný (0,3<=0.4<=0.6), а если 0.9 – то c(0.6<=0.9<=1). Итак, у нас получилось закодировать 1 букву в число. Как же закодировать 2 буквы? Очень просто: например, если первая буква – "b", то интервал равен . Разделим этот интервал на части, в отношении наших первоначальных отрезков. Тогда 2-м буквам "ba" будет соответствовать интервал , "bb" – и "bc" – . Для раскодирования нам достаточно знать любое число из этого интервала.

Pokúsme sa dekódovať: Nech je uvedené číslo 0,15. Toto číslo vstupuje do intervalu písmen "A", čo znamená prvý kódovaný list - "A". Aby ste zistili druhé písmeno, musíte previesť číslo, aby ste označili písmeno v intervale, ale. Na to, z čísla odoberte dolnú hranicu štartovacieho rozsahu (0) a rozdeľte interval na šírku (0,3-0 \u003d 0,3). Získame nové číslo (0,15-0) /0,3 \u003d 0,5. Opakovanie rovnakých akcií sa dozvieme, že druhé písmeno je "B". Ak boli zakódované 3 a viac písmen, potom opakovanie tohto procesu opakovania tohto procesu, nájdeme všetky písmená.

Prečo zobrazenie vo forme čísla umožňuje komprimovať údaje:
Viac ako pravdepodobnejšie symboly zodpovedajú širšiemu intervalu, a po kódovaní takéhoto listu sa interval mierne zníži, preto bude reprezentovať ľubovoľný počet týchto medzery bude potrebovať o niečo viac bitov.

Kompresný algoritmus:
Pre každý znak musíme priradiť príslušnú medzeru v súlade s frekvenciou (pravdepodobnosť stretnutia) v údajoch: Nech symbol "A" má pravdepodobnosť 0,4, "B" - 0,3 a "C" - tiež 0,3; Potom symbol "A" bude zodpovedať medzeru, "B" -, "C" -. Tí, ktorí rozdelia existujúcu medzeru medzi všetkými potrebnými písmenami v súlade s pravdepodobnosťou ich stretnutia (pravdepodobnejší symbol zodpovedá väčšiemu intervalu).

V procese kompresie máme 2 hranice: horná a nižšia, nazývame ich podľa HII LO. Potrebujeme zakódovať symbol, ktorý sme vzali medzeru. Potom v našej medzere "vložená" medzera symbolu a LO sa rovná dolnej hranici vloženej medzery, Ahoj je vrch. Výsledkom je, že keď je kódová medzera medzi Loe Ahoj kódovaná, všetko už je už. Nakoniec, keď sme kódovali všetky údaje, vyberte ľubovoľný počet výsledných medzery a výstup. Bude komprimovaný.

Rozbalenie:
Vystavujeme intervaly pre znaky, ako aj pre kompresiu. Symbol, v ktorom je počet archívov a je prvým symbolom údajov. "Stiahneme" interval symbolu spolu s číselným archívom k medzere (to znamená, že berieme spodnú hranicu intervalu jediného dekódovaného symbolu a rozdelíme šírku tohto intervalu), potom opakujeme operácie, kým sa nerozhodneme.

Problémy:
Ak bolo všetko také jednoduché ... V skutočnosti, pre ukladanie archívneho čísla, bude veľmi veľká presnosť (desiatky a stovky tisíc znakov), takže v praxi musíte použiť konvenčné typy údajov. Na dosiahnutie tohto cieľa sa pozrieme na staršie bity / čísla nočného archívu. Akonáhle Ahoj a Lo, sa zhodujú, môžeme ich okamžite spáliť do archívu a "odrezať". Pri rozbalení, naopak, keď vidíme, že sme sa rozšírili pomerne veľakrát, považujeme niekoľko číslic zo súboru a pridajte ich do konca nášho archívu do konca nášho archívu.
Často sa používa modifikácia aritmetického kódovania - rozsah CODER. Hlavným rozdielom je počiatočný interval. To vám umožní okamžite vydávať údaje Byte a nie je zoškrabať na bitke, čo sa odráža v rýchlosti práce. Na konci článku je to implementácia tejto konkrétnej možnosti.

Definícia pravdepodobností symbolov

Predpoklady, ktoré vykonávame relatívne k stlačiteľným údajom (napríklad závislosť pravdepodobnosti z predchádzajúcich znakov), sa nazývajú pravdepodobnostný model. Pravdepodobnosť modelu, v ktorej nezávisí od predchádzajúcich znakov, sa nazýva model 0. Ak pravdepodobnosť závisia od prvého symbolu, je to model 1. objednávky, ak z 2. - potom 2., atď. Ak chcete efektívne vypočítať pravdepodobnosti znakov v modeloch s vysokou objednávkou Existuje špeciálna skupina algoritmov - ppm a jeho modifikácie.
Modely môžu byť adaptívne, semi-daisy a adaptívne. V non-adaptívnych metódach je pravdepodobnosť všetkých znakov pevne šitá do programu. V semi-daisy na vstupných údajoch existujú 2 pasáže: 1. - určiť pravdepodobnosti, 2. - vlastne na kompresiu. Adaptívne - pravdepodobnosti symbolov sa mení počas procesu kompresie. Adaptívne modely sú najpomalšie, ale zvyčajne komprimujú údaje sú silnejšie ako napadové a polo-daisy modely. Všeobecne platí, že medzi všetkými modelmi je lepšie komprimovať najväčší počet informácií o stlačiteľných dát - závislosť od predchádzajúcich znakov, niektoré fakty, napríklad: v textoch po bode zvyčajne nasleduje veľký list atď.

Algoritmy používané v populárnych archívoch:

Príklad adaptívneho kompresného / rozbaľovacieho programu 0. objednávky: