Predloženi materijali činili su osnovu testnog rada za predmet "Matematičke osnove informatike" (autora A. Geina), koji sam uspješno završio 2011. godine na daljinskom univerzitetu "1. septembar". Materijali su prilagođeni za prošireni kurs informatike u 11. razredu.

Skinuti:

Pregled:

Kompresija podataka Licej br. 329

Andreeva O.A.

Plan lekcije

11. razred

Tema lekcije: Kompresija podataka.

Vrsta lekcije : proučavanje novog nastavnog materijala sa elementima frontalnog razgovora.

Ciljevi lekcije : širenje kompetencija u kreiranju vlastitog informacionog prostora.

Ciljevi lekcije:

nastavni plan i program - razmotrite koncept kompresiju podataka i upoznati se s algoritmima za komprimiranje znakovnih podataka;

kognitivni - uvesti konceptredundantnost podataka;

edukativni – stvoriti uslove za energičnu aktivnost svakog učenika.

Softver

odredba lekcije:- prezentacija na temu "Kompresija podataka";

Technical

pružanje lekcije: - radno mjesto studenta sa PentiumIII PC;

1. ploča od filca;
2. projektor za demonstraciju prezentacije.

TOKOM NASTAVE

Faza I : izlaz na temu časa i motivacija za proučavanje gradiva;

II faza : poruka nastavnog materijala;

Faza III : aktualizacija stečenog znanja - odgovori na pitanja za konsolidaciju;

Faza IV : poruka domaćeg zadatka; sumiranje lekcije.

Sažetak lekcije

I faza:

Količina informacija koje su potrebne osobi stalno raste. Mogućnosti skladištenja i propusni opseg takođe rastu. Međutim, količina informacija raste brže.
Postoje tri načina za rješavanje ovog problema:

prvo - ograničavanje količine informacija. Nažalost, to nije uvijek prihvatljivo. Za slike, na primjer, to znači smanjenje rezolucije, što će dovesti do gubitka finih detalja i može učiniti slike općenito beskorisnim (na primjer, za medicinske ili svemirske slike). Ova putanja nije primjenjiva za programe i tekstove.
sekunda - povećanje obima nosilaca informacija i kapaciteta komunikacijskih kanala. Ova odluka je povezana s materijalnim troškovima, a ponekad i vrlo značajnim.
treći - korištenje kompresije informacija. Ovo rješenje omogućava višestruko smanjenje zahtjeva za volumenom uređaja za pohranu podataka i propusnim opsegom komunikacijskih kanala bez dodatnih troškova (osim troškova implementacije algoritama kompresije). Uslovi za njegovu primenljivost su redundantnost informacija i mogućnost instaliranja posebnog softvera ili hardvera za obavljanje ovih procedura.

Karakteristična karakteristika većine vrsta digitalnih podataka je njihova redundantnost. Količina redundantnosti podataka ovisi o vrsti podataka. Na primjer, za video podatke, stepen redundancije je nekoliko puta veći nego za grafičke podatke, a stepen redundantnosti grafičkih podataka je, zauzvrat, veći od stepena redundantnosti tekstualnih podataka. Drugi faktor koji utiče na stepen redundancije je usvojeni sistem kodiranja. Efikasnost kodiranja se može povećati kada se radi sa određenim skupom podataka.

Teorijski je dokazano da je redundancija ruskog književnog teksta 0,6. Drugim riječima, kada se tekst prenosi putem komunikacionog kanala, svakih šest od deset prenijetih slova ne nosi nikakvu informaciju i jednostavno se ne može prenijeti bez ikakvih gubitaka.

Ostali izvori informacija imaju istu, ako ne i veću (ρi = 0,9 ... 0,95) redundantnost - govor, a posebno muzika, televizijske slike itd.

Kompresija podataka se koristi u mnogim informacionim sistemima. Savremeni radio-tehnički sistemi prenosa i komunikacije jednostavno ne bi mogli da rade da se u njima ne vrši ovakva kompresija. Ne bi bilo digitalne mobilne komunikacije GSM i CDMA standarda. Sistemi digitalne satelitske televizije ne bi radili, internet bi bio vrlo neefikasan, a ne bi moglo biti govora o gledanju videa ili slušanju dobre muzike sa laserskog diska. Sve je to osigurano efikasnim ili ekonomičnim kodiranjem informacija u ovim sistemima.

II faza:

Demonstracija prezentacije u pravom tempu sa objašnjenjima materijala na svakom slajdu.

Slajd 5 (dodatna objašnjenja):

Izbor nedestruktivnog (bez gubitaka) ili destruktivnog (sa gubicima) kompresijskog sistema zavisi od vrste podataka koji se kompresuju. Prilikom kompresije tekstualnih podataka, kompjuterskih programa, dokumenata, crteža itd. sasvim je očito da je potrebno koristiti nedestruktivne metode, jer je potrebno apsolutno precizno vratiti izvornu informaciju nakon njenog kompresije. Prilikom kompresije govornih, muzičkih podataka i slika, naprotiv, češće se koristi destruktivna kompresija, jer uz gotovo neprimjetna izobličenja daje red veličine, a ponekad i dva puta niže R ... U opštem slučaju, destruktivna kompresija daje, po pravilu, znatno veće omjere kompresije od nedestruktivne.

Slajd 18 (dodatna objašnjenja):

Pogledajmo princip kompresije zasnovane na rječniku. LZ je tehnika kompresije podataka koja koristi prednosti ponavljajućih lanaca podataka. Izvorni rječnik za kompresiju sadrži rječnik korištenih simbola. Zatim će se nizovi znakova koji se razlikuju za jedan znak dodati u rječnik. Lanci će se produžavati, a u tekstu će se sve češće pojavljivati ​​lanci riječi koje će zamijeniti linkovi ka rječniku. Riječi, fraze, redovi teksta bit će dodani u rječnik. Efekat kompresije se postiže kodiranjem nizova znakova koji se ponavljaju.

Zamislimo ovaj proces na primjeru kompresije fraze. Rječnik je već napravljen, a nizovi koji nas zanimaju dodani su u rječnik (ponovit će se u frazi). Imaju digitalne veze. Kada ponovo unesete frazu, oni se zamjenjuju vezama. Očigledno, podaci se komprimiraju.

Postoji čitava porodica LZ algoritama koji su efikasni za različite tipove podataka.

Zaključak II faze:

Dakle, budućnost pripada novim algoritmima sa visokim zahtjevima za resursima i sve većim omjerima kompresije.

Ne samo da algoritmi postaju zastarjeli, već i vrste informacija na koje su orijentirani. Tako su grafike s malim brojem boja i neformatiranim tekstom zamijenjene visokokvalitetnim slikama i elektronskim dokumentima u različitim formatima. Poznati algoritmi nisu uvijek efikasni na novim tipovima podataka. Ovo čini problem sinteze novih algoritama izuzetno hitnim.

Pregled:

Da biste koristili pregled prezentacija, kreirajte sebi Google račun (nalog) i prijavite se na njega: https://accounts.google.com

Naslovi slajdova:

Kompresija podataka

Svrha kompresije podataka je ušteda resursa prilikom pohranjivanja ili prijenosa podataka Kompresija podataka je proces smanjenja količine podataka. Metode kompresije Modifikacija sadržaja podataka (smanjenje redundantnosti podataka) Modifikacija strukture podataka (efikasno kodiranje) Modifikacija sadržaja i strukture podataka Originalni podaci Obnovljeni podaci Novi format Originalni format Komprimovani podaci Arhiviranje podataka - potpuna kompresija podataka

Omjer kompresije je vrijednost za efikasnost metode kompresije, jednaka omjeru količine informacija prije i nakon kompresije Originalni podaci Kompresovani podaci Veličina datoteke 2MB Veličina datoteke 512 KB K komprimirano = 2 MB / 0,5 MB = 4

Kompresija podataka se može dogoditi sa gubitkom i bez gubitka Kompresija bez gubitaka (potpuno reverzibilna) je metoda kompresije podataka u kojoj se podaci vraćaju nakon potpunog raspakiranja bez ikakvih promjena (koristi se za tekstove, programe) Kszh do 50% kompresije bez gubitaka je kompresija podataka metode u kojima se dio podataka odbacuje i ne može se povratiti (koristi se za video, zvuk, slike) Kszh do 99%

Kompresija sa gubitkom Tip podataka Tip datoteke nakon kompresije Omjer kompresije Graphics.JPG do 99% Video.MPG Audio.MP3 Tip podataka Tip datoteke nakon kompresije Omjer kompresije Graphics.GIF .TIF .PCX Do 50% Video.AVI Bilo koja vrsta.ZIP . ARJ .RAR .LZH Kompresija bez gubitaka

Algoritmi kompresije znakovnih podataka Statističke metode su metode kompresije zasnovane na statističkoj obradi teksta. Kompresija rječnika je tehnika kompresije zasnovana na konstrukciji internog rječnika.

Pakovanje homogenih podataka 0 0000 1 0001 2 0010 3 0011 4 0100 5 0101 6 0110 7 0111 8 1000 9 1001 _ 1010 + 1011 - 1010 + 1011 - 11010, 1 koda od 5 A 1010, 1 koda od 1 SC, 1 koda od 5 a2. poruka je 16 bajtova. Nova tabela kodova za pakovanje: Šifra poruke nakon pakovanja je 8 bajtova: 000011010 01010101 00011000 0100011 110101011 01100011 00011010 0000001 K comp = 1

Omjer kompresije se povećava s veličinom poruke znakova; potrebno je navesti novu tabelu kodova za raspakivanje; efektivno samo za homogene poruke koje koriste ograničen skup znakova u originalnom alfabetu; + - - Prednosti i nedostaci metode

Metoda statističke kompresije Huffmanov algoritam Različiti znakovi se nalaze u poruci s različitim frekvencijama, na primjer, za rusku abecedu, u prosjeku za 1000 znakova: razmak znakova ponavljanja: što se znak češće pojavljuje, to je njegov kod kraći (nejednako kodiranje)

Huffmanovo kodiranje (kompresija) je tehnika kompresije koja dodjeljuje kodove promjenjive dužine znakovima u abecedi na osnovu učestalosti pojavljivanja tih znakova u poruci. znak znak kodni razmak 00 o 01 p 101 do 110 s 0110 f 1001

Problem dekodiranja Primjer: Neka znakovni kodovi a -10, b -101, c -1010 Dešifriraju poruku 10101011010 10 101 1010 10 10 101 10 10 1010 101 1010 kodnu riječ.

Prefiksni kod je kod u kojem nijedna kodna riječ nije prefiksirana bilo kojoj drugoj kodnoj riječi. Primjer koda prefiksa: 00 10 010 110 0110 0111 1110 1111 0 0 0 0 0 0 0 1 1 1 1 1 1 1 Šifra prefiksa je data digrafom sa označenim listovima

Primjer: napravite Huffman kod za frazu FROM_HOOT_HOOPS_DUST_PO_FIELD_LETTER Odredite učestalost pojavljivanja znakova u frazi: Napravite Huffman digraf: -simbol specificira vrh lista digrafa; -težina temena jednaka je učestalosti pojavljivanja simbola; - parovi vrhova sa najmanjom težinom su povezani: - leve grane su označene sa 0; - desni ogranci su označeni sa 1; -odrediti šifru karaktera od korijena do lista; simbol A E I K L O P T S Y _ frekvencija 1 1 1 1 3 6 5 6 2 1 1 6

KORIJEN DRVETA T- O- S- _ P- L- Y- L- E- K- I- A- 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 00011 00010 11000 11001 11011 11010 001 010 011 111 10 0000 Svaki vrh je označen strelicom

Konstruisani prefiksni kodovi znakova: Poruka u novim kodovima sadrži 110 bita, u ASCII kodiranju - 34 * 8 = 272 bita zatim K sr = 272/110 = 2, 47 Simbol A E I K L O P T Y L Y _ Kod 11011 11010 00 00 110100 0000 00011 00010 111 Dužina koda 5 5 5 5 3 2 3 3 4 5 5 3

Huffmanov algoritam je univerzalan, može se koristiti za kompresiju podataka bilo kojeg tipa; Klasični Huffmanov algoritam zahtijeva skladištenje stabla kodiranja, što povećava veličinu datoteke. + - Prednosti i mane metode

Metoda rječnika LZ algoritam kompresije Ovaj algoritam su prvi opisali A. Lempel i J. Ziv (Abraham Lempel, Jacob Ziv) 1977-78, stoga se ovaj metod često naziva Lempel-Ziv, ili skraćeno LZ. Zasnovan je na ideji zamjene najčešće susrećenih znakovnih nizova (stringova) u datoteci vezama na "uzorak" nizova pohranjenih u posebno kreiranoj tabeli (rječniku).

Algoritam su razvili matematičari za ogradu Jaco Ziv i Abrakhum Lempel. Rječnik sadrži, između mnogih drugih, sljedeće lance: 1-pa 2-ab 3-at 4-mate 5-mi_ 6-am 7-bo 8-th_ 9-bom 10-th 11-lem Algoritam je razvio izraelski matematičari 5Yako7 Ziv821x68 L10ne11 Što je duži lanac zamijenjen vezom rječnika, to je veći efekat kompresije.

Primjenjivo za sve podatke; - vrlo visoka brzina kompresije; - visok stepen kompresije; + - Prednosti i nedostaci metode - rečnik je konfigurisan za vrstu teksta; - rečnik može biti veoma velik;

Predavanje broj 4. Kompresija informacija

Principi kompresije informacija

Svrha kompresije podataka je da obezbedi kompaktnu reprezentaciju podataka koje generiše izvor za ekonomičnije skladištenje i prenos preko komunikacionih kanala.

Pretpostavimo da imamo datoteku veličine 1 (jedan) megabajt. Moramo uzeti manji fajl iz njega. Ništa komplikovano - pokrenemo arhiver, na primjer, WinZip, i dobijemo, recimo, datoteku veličine 600 kilobajta. Gdje su otišla preostala 424 kilobajta?

Kompresija informacija je jedan od načina za njihovo kodiranje. Općenito, kodovi su podijeljeni u tri velike grupe - kompresijski kodovi (efektivni kodovi), kodovi za ispravljanje grešaka i kriptografski kodovi. Kodovi dizajnirani za komprimiranje informacija podijeljeni su, zauzvrat, na kodove bez gubitaka i kodove sa gubicima. Kodiranje bez gubitaka podrazumijeva apsolutno precizan oporavak podataka nakon dekodiranja i može se koristiti za kompresiju bilo koje informacije. Kodiranje s gubitkom obično ima mnogo veći omjer kompresije od kodiranja bez gubitaka, ali dopušta neka odstupanja dekodiranih podataka od originala.

Vrste kompresije

Sve metode kompresije informacija mogu se uslovno podijeliti u dvije velike klase koje se ne preklapaju: kompresiju sa gubitak informacije i kompresiju nema gubitka informacije.

Kompresija bez gubitka informacija.

Nas prvenstveno zanimaju ovi načini kompresije, jer se koriste prilikom prijenosa tekstualnih dokumenata i programa, prilikom izdavanja završenog posla kupcu ili prilikom kreiranja rezervnih kopija informacija pohranjenih na računalu.

Metode kompresije ove klase ne mogu dozvoliti gubitak informacija, stoga se zasnivaju samo na eliminisanju njihove suvišnosti, a informacija ima redundantnost skoro uvek (mada, ako je neko ranije nije kompresovao). Da nema zaliha, ne bi se imalo šta komprimirati.

Evo jednostavnog primjera. U ruskom jeziku ima 33 slova, deset brojeva i desetak znakova interpunkcije i drugih specijalnih znakova. Za tekst koji je napisan samo velikim ruskim slovima(kao u telegramima i radiogramima) bilo bi dovoljno šezdeset različitih vrijednosti. Međutim, svaki znak je obično kodiran bajtom koji sadrži 8 bita i može izraziti 256 različitih kodova. Ovo je prvi razlog za višak. Za naš "telegrafski" tekst bilo bi dovoljno šest bitova po karakteru.

Evo još jednog primjera. Međunarodno kodiranje znakova ASCII za kodiranje bilo kog znaka dodeljuje se isti broj bitova (8), dok svi odavno dobro znaju da ima smisla najčešće znakove kodirati sa manje znakova. Tako, na primjer, u "Morseovom kodu" slova "E" i "T", koja se često nalaze, kodirana su jednim znakom (odnosno, tačkom i crticom). I takva rijetka slova kao što su "U" (- -) i "C" (- -) su kodirana sa četiri znaka. Neefikasno kodiranje je drugi razlog za redundantnost. Programi koji vrše kompresiju informacija mogu unijeti vlastito kodiranje (različito za različite datoteke) i dodijeliti tabelu (rječnik) komprimiranoj datoteci, iz koje program za raspakivanje saznaje kako su određeni znakovi ili njihove grupe kodirani u ovoj datoteci. Pozivaju se algoritmi zasnovani na transkodiranju informacija Huffmanovi algoritmi.

Prisustvo fragmenata koji se ponavljaju je treći razlog za redundantnost. Ovo je rijetko u tekstovima, ali u tabelama i grafikama, ponavljanje kodova je uobičajeno. Tako, na primjer, ako se broj 0 ponavlja dvadeset puta zaredom, onda nema smisla stavljati dvadeset nula bajtova. Umjesto toga, stavljaju jednu nulu i koeficijent 20. Takvi algoritmi zasnovani na otkrivanju ponavljanja nazivaju se metodeRLE (Trči Dužina Kodiranje).

Grafičke ilustracije posebno se odlikuju velikim ponavljajućim nizovima istih bajtova, ali ne fotografskih (puno je šuma i susjednih tačaka značajno se razlikuju po parametrima), već onih koje umjetnici slikaju "glatkim" bojama, kao u animiranim filmovima .

Kompresija sa gubitkom.

Kompresija sa gubitkom znači da nakon raspakivanja komprimirane arhive dobijemo dokument koji se malo razlikuje od onog koji je bio na samom početku. Podrazumijeva se da što je veći omjer kompresije, veći je gubitak, i obrnuto.

Naravno, takvi algoritmi nisu primjenjivi za tekstualne dokumente, tabele baze podataka, a posebno za programe. Mala izobličenja u jednostavnom neformatiranom tekstu se još nekako mogu preživjeti, ali izobličenje barem jednog bita u programu će ga učiniti apsolutno neoperativnim.

Istovremeno, postoje materijali u kojima vrijedi žrtvovati nekoliko postotaka informacija kako bi se kompresija udeseterostručila. To uključuje fotografske ilustracije, video zapise i muzičke kompozicije. Gubitak informacija tokom kompresije i naknadnog raspakivanja u takvim materijalima se doživljava kao pojava neke dodatne "buke". Ali pošto je neka „šuma“ i dalje prisutna pri kreiranju ovih materijala, njeno malo povećanje ne izgleda uvek kritično, a dobitak u veličini fajla je ogroman (10-15 puta za muziku, 20-30 puta za foto i video materijale).

Algoritmi kompresije sa gubitkom uključuju dobro poznate algoritme kao što su JPEG i MPEG. JPEG algoritam se koristi za kompresiju fotografskih slika. Grafičke datoteke komprimirane ovom metodom imaju ekstenziju JPG. MPEG algoritmi se koriste za kompresiju videa i muzike. Ovi fajlovi mogu imati različite ekstenzije, u zavisnosti od konkretnog programa, ali najpoznatiji su .MPG za video i .MP3 za muziku.

Algoritmi kompresije sa gubitkom koriste se samo za korisničke aplikacije. To znači, na primjer, ako se fotografija pošalje na gledanje, a muzika za reprodukciju, onda se mogu koristiti slični algoritmi. Ako se prenose na dalju obradu, na primjer, za uređivanje, tada gubitak informacija u originalnom materijalu nije prihvatljiv.

Količina dozvoljenog gubitka kompresije obično se može kontrolisati. To vam omogućava da eksperimentirate i postignete optimalni omjer veličine/kvaliteta. U fotografskim ilustracijama namijenjenim prikazivanju na ekranu, gubitak od 5% informacija obično nije kritičan, au nekim slučajevima može se tolerirati 20-25%.

Algoritmi kompresije bez gubitaka

Shannon-Fano kod

Za dalje razmišljanje, biće zgodno zamisliti našu izvornu datoteku sa tekstom kao izvor znakova koji se pojavljuju jedan po jedan na njegovom izlazu. Ne znamo unapred koji će znak biti sledeći, ali znamo da će se slovo "a" pojaviti sa verovatnoćom p1, slovo "b" sa verovatnoćom p2, itd.

U najjednostavnijem slučaju, smatraćemo da su svi likovi teksta nezavisni jedni od drugih, tj. vjerovatnoća pojavljivanja sljedećeg simbola ne ovisi o vrijednosti prethodnog simbola. Naravno, to nije slučaj sa smislenim tekstom, ali sada razmatramo vrlo pojednostavljenu situaciju. U ovom slučaju, izjava "simbol nosi što više informacija, to je manja vjerovatnoća njegovog pojavljivanja".

Zamislimo tekst čija se abeceda sastoji od samo 16 slova: A, B, C, D, D, E, F, Z, I, K, L, M, N, O, P, R. Svako od ovih znakovi se mogu kodirati sa samo 4 bita: od 0000 do 1111. Sada zamislite da su vjerovatnoće pojave ovih znakova raspoređene na sljedeći način:

Zbir ovih vjerovatnoća je, naravno, jedan. Podijelimo ove simbole u dvije grupe tako da ukupna vjerovatnoća simbola svake grupe bude ~0,5 (sl.). U našem primjeru, to će biti grupe znakova A-B i G-R. Krugovi na slici, koji označavaju grupe simbola, nazivaju se čvorovi ili čvorovi, a sama konstrukcija ovih čvorova naziva se binarno stablo (B-stablo). Dodijelimo svakom čvoru vlastiti kod, označavajući jedan čvor brojem 0, a drugi brojem 1.

Podijelimo opet prvu grupu (AB) u dvije podgrupe tako da njihove ukupne vjerovatnoće budu što bliže jedna drugoj. Dodajmo broj 0 šifri prve podgrupe, a broj 1 šifri druge.

Ponavljaćemo ovu operaciju dok ne ostane po jedan simbol na svakom vrhu našeg "drveta". Kompletno stablo za našu abecedu će imati 31 čvor.

Kodovi znakova (krajnji desni čvorovi stabla) imaju kodove nejednake dužine. Dakle, slovo A, koje ima vjerovatnoću p = 0,2 za naš imaginarni tekst, kodirano je sa samo dva bita, a slovo P (nije prikazano na slici), koje ima vjerovatnoću p = 0,013, je kodirano sa šest-bitna kombinacija.

Dakle, princip je očigledan - znakovi koji se često pojavljuju su kodirani s manje bitova, rijetki - s više. Kao rezultat, prosječan broj bitova po karakteru će biti

gdje je ni broj bitova koji kodiraju i-ti simbol, pi je vjerovatnoća i-tog simbola.

Huffman kod.

Huffmanov algoritam graciozno implementira opću ideju entropijskog kodiranja koristeći skupove prefiksa i radi na sljedeći način:

1. Napišite redom sve simbole abecede uzlaznim ili silaznim redoslijedom vjerovatnoće njihovog pojavljivanja u tekstu.

2. Uzastopno kombinovati dva simbola sa najmanjim verovatnoćama pojavljivanja u novom kompozitnom simbolu, čija se verovatnoća pretpostavlja da je jednaka zbiru verovatnoća njegovih sastavnih simbola. Na kraju ćemo izgraditi stablo, čiji svaki čvor ima ukupnu vjerovatnoću svih čvorova ispod njega.

3. Pratite putanju do svakog lista drveta, označavajući pravac do svakog čvora (na primjer, desno - 1, lijevo - 0). Rezultirajući niz daje kodnu riječ koja odgovara svakom znaku (Sl.).

Napravimo stablo koda za poruku sa sljedećim alfabetom:

Nedostaci metoda

Najveća poteškoća s kodovima, kao što prethodna diskusija sugerira, je potreba da se imaju tablice vjerovatnoća za svaki tip podataka koji se komprimiraju. Ovo nije problem ako se zna da je engleski ili ruski tekst komprimovan; mi jednostavno dajemo koderu i dekoderu odgovarajuće stablo koda za engleski ili ruski tekst. U opštem slučaju, kada je verovatnoća simbola za ulazne podatke nepoznata, statički Hafmanovi kodovi rade neefikasno.

Rješenje ovog problema je statistička analiza kodiranih podataka, koja se vrši pri prvom prelasku preko podataka i na osnovu toga se pravi kodno stablo. U ovom slučaju, stvarno kodiranje se izvodi u drugom prolazu.

Još jedan nedostatak kodova je što minimalna dužina kodne riječi za njih ne može biti manja od jedan, dok entropija poruke može biti i 0,1 i 0,01 bita/slovo. U ovom slučaju, kod postaje značajno suvišan. Problem se rješava primjenom algoritma na blokove simbola, ali tada procedura kodiranja/dekodiranja postaje složenija i stablo koda se značajno širi, koje se na kraju mora pohraniti zajedno sa kodom.

Ovi kodovi ne uzimaju u obzir odnose između znakova, koji su prisutni u gotovo svakom tekstu. Na primjer, ako u tekstu na engleskom naiđemo na slovo q, onda možemo sa sigurnošću reći da će iza njega doći slovo u.

Run Length Encoding (RLE) jedan je od najstarijih i najjednostavnijih algoritama za arhiviranje. Kompresija u RLE-u se događa zamjenom nizova identičnih bajtova parovima protuvrijednosti. (“Crveno, crveno, ..., crveno” je napisano kao “N crveno”).

Jedna od implementacija algoritma je sljedeća: traže najmanji bajt, nazivaju ga prefiksom i zamjenjuju nizove identičnih znakova trojkama "prefiks, brojač, vrijednost". Ako se ovaj bajt pojavljuje u izvornoj datoteci jednom ili dvaput zaredom, tada se zamjenjuje parom "prefiks, 1" ili "prefix, 2". Postoji jedan neiskorišteni par "prefiks, 0" koji se može koristiti kao znak kraja upakovanih podataka.

Kada kodirate exe datoteke, možete pretraživati ​​i pakirati sekvence oblika AxAyAzAwAt ..., koje se često nalaze u resursima (nizovi kodirani u Unicode)

Pozitivni aspekti algoritma uključuju činjenicu da ne zahtijeva dodatnu memoriju tokom rada i da se brzo izvršava. Algoritam se koristi u PCX, TIFF, BMP formatima. Zanimljiva karakteristika paketnog kodiranja u PCX-u je da se stepen arhiviranja nekih slika može značajno povećati jednostavnom promenom redosleda boja u paleti slike.

LZW kod (Lempel-Ziv & Welch) je daleko jedan od najčešćih kompresijskih kodova bez gubitaka. Uz pomoć LZW-koda vrši se kompresija u takvim grafičkim formatima kao što su TIFF i GIF, uz pomoć LZW modifikacija, mnogi univerzalni arhivari obavljaju svoje funkcije. Rad algoritma zasniva se na traženju u ulaznoj datoteci ponovljenih nizova znakova, koji su kodirani kombinacijama dužine od 8 do 12 bita. Stoga je ovaj algoritam najefikasniji kod tekstualnih i grafičkih datoteka koje imaju velike jednobojne površine ili ponavljajuće sekvence piksela.

Odsustvo gubitka informacija tokom LZW kodiranja dovelo je do široke upotrebe TIFF formata zasnovanog na njemu. Ovaj format ne nameće nikakva ograničenja na veličinu i dubinu boje slike i široko se koristi, na primjer, u štamparskoj industriji. Drugi format zasnovan na LZW-u - GIF - je primitivniji - omogućava vam pohranjivanje slika s dubinom boje ne većom od 8 bita/piksel. Na početku GIF datoteke nalazi se paleta - tabela koja uspostavlja korespondenciju između indeksa boja - broja u rasponu od 0 do 255 i prave, 24-bitne vrijednosti boje.

Algoritmi kompresije sa gubitkom

JPEG algoritam je razvila grupa firmi pod nazivom Joint Photographic Experts Group. Cilj projekta je bio stvaranje visokoefikasnog standarda kompresije za crno-bijele i slike u boji, a taj cilj su programeri i ostvarili. Trenutno, JPEG se široko koristi tamo gdje je potreban visok omjer kompresije - na primjer, na Internetu.

Za razliku od LZW-a, JPEG kodiranje je sa gubicima. Sam algoritam kodiranja baziran je na vrlo složenoj matematici, ali općenito se može opisati na sljedeći način: slika se dijeli na kvadrate od 8 * 8 piksela, a zatim se svaki kvadrat pretvara u sekvencijalni lanac od 64 piksela. Nadalje, svaki takav lanac je podvrgnut takozvanoj DCT-transformaciji, koja je jedna od varijanti diskretne Fourierove transformacije. Sastoji se u tome da se ulazna sekvenca piksela može predstaviti kao zbir sinusoidnih i kosinusnih komponenti sa više frekvencija (tzv. harmonici). U ovom slučaju, potrebno je samo znati amplitude ovih komponenti da bismo rekonstruisali ulazni niz sa dovoljnim stepenom tačnosti. Što više harmoničnih komponenti poznajemo, to će biti manje neslaganja između originalne i komprimirane slike. Većina JPEG kodera vam omogućava da prilagodite stopu kompresije. Ovo se postiže na vrlo jednostavan način: što je veći omjer kompresije postavljen, to će svaki blok od 64 piksela predstavljati manje harmonika.

Naravno, jača strana ove vrste kodiranja je visok omjer kompresije uz zadržavanje originalne dubine boje. Upravo je ovo svojstvo odredilo njegovu široku upotrebu na Internetu, gdje je smanjenje veličine datoteka od najveće važnosti, u multimedijalnim enciklopedijama, gdje je potrebno pohraniti najveću moguću količinu grafike u ograničenom iznosu.

Negativna osobina ovog formata je da degradira kvalitetu slike, koja se ni na koji način ne može ukloniti. Upravo ta tužna činjenica ne dozvoljava njegovu upotrebu u štamparskoj industriji, gdje je kvalitet na prvom mjestu.

Međutim, JPEG format nije granica izvrsnosti u nastojanju da se smanji veličina konačne datoteke. U posljednje vrijeme provode se intenzivna istraživanja u oblasti takozvane talasne transformacije (ili burst transformacije). Bazirani na najsloženijim matematičkim principima, talasni koderi vam omogućavaju da dobijete veću kompresiju od JPEG-a, uz manji gubitak informacija. Uprkos složenosti matematičke wavelet transformacije, u softverskoj implementaciji je jednostavnija od JPEG. Iako su algoritmi talasne kompresije još uvijek u ranoj fazi razvoja, oni imaju veliku budućnost.

Fraktalna kompresija

Fraktalna kompresija slike je algoritam kompresije slike sa gubicima zasnovan na primjeni sistema iterativnih funkcija (IFS, obično afine transformacije) na slike. Ovaj algoritam je poznat po tome što u nekim slučajevima omogućava dobijanje vrlo visokih omjera kompresije (najbolji primjeri su do 1000 puta sa prihvatljivim vizualnim kvalitetom) za stvarne fotografije prirodnih objekata, što u principu nije dostupno za druge algoritme kompresije slike. . Zbog teške situacije sa patentiranjem, algoritam nije bio u širokoj upotrebi.

Fraktalno arhiviranje se zasniva na činjenici da se pomoću koeficijenata sistema iteriranih funkcija slika prikazuje u kompaktnijem obliku. Prije nego što pogledamo proces arhiviranja, pogledajmo kako IFS gradi sliku.

Strogo govoreći, IFS je skup trodimenzionalnih afinih transformacija koje pretvaraju jednu sliku u drugu. Tačke u trodimenzionalnom prostoru (x koordinata, y koordinata, svjetlina) se transformiraju.

Osnova metode fraktalnog kodiranja je detekcija samosličnih područja na slici. Mogućnost primjene teorije sistema iterativnih funkcija (IFS) na problem kompresije slike prvi su istraživali Michael Barnsley i Alan Sloan. Svoju ideju su patentirali 1990. i 1991. godine. Jacquin je uveo fraktalni metod kodiranja koji koristi sistem blokova podslike domene i raspona, blokova kvadratnog oblika koji pokrivaju cijelu sliku. Ovaj pristup je postao osnova za većinu fraktalnih metoda kodiranja koje se danas koriste. Rafinirao ga je Yuval Fisher i brojni drugi istraživači.

Ova metoda dijeli sliku na skup podslika raspona koji se ne preklapa i definira skup podslika domena koji se preklapa. Za svaki blok ranga, algoritam kodiranja pronalazi najprikladniji blok domene i afinu transformaciju koja prevodi ovaj blok domene u dati blok ranga. Struktura slike je mapirana u sistem rang blokova, blokova domena i transformacija.

Ideja je sljedeća: pretpostavimo da je originalna slika fiksna tačka neke karte kontrakcije. Tada, umjesto same slike, možete nekako zapamtiti ovo mapiranje, a da biste ga vratili, dovoljno je više puta primijeniti ovo mapiranje na bilo koju početnu sliku.

Prema Banachovoj teoremi, takve iteracije uvijek vode do fiksne tačke, odnosno do originalne slike. U praksi, cijela poteškoća leži u pronalaženju najprikladnijeg mapiranja kompresije iz slike iu njenom kompaktnom pohranjivanju. Tipično, algoritmi za pretragu prikaza (tj. algoritmi kompresije) su uglavnom iscrpni i računarski intenzivni. Istovremeno, algoritmi oporavka su prilično efikasni i brzi.

Ukratko, metoda koju je predložio Barnsley može se opisati na sljedeći način. Slika je kodirana s nekoliko jednostavnih transformacija (u našem slučaju afine), odnosno određena je koeficijentima tih transformacija (u našem slučaju A, B, C, D, E, F).

Na primjer, slika Kochove krive može se kodirati sa četiri afine transformacije, mi ćemo je jednoznačno definirati koristeći samo 24 koeficijenta.

Kao rezultat toga, tačka će nužno otići negdje unutar crnog područja na originalnoj slici. Nakon što smo ovu operaciju izvršili mnogo puta, popunit ćemo sav crni prostor i na taj način vratiti sliku.

Najpoznatije su dvije IFS slike: trokut Sierpinskog i paprat Barnsley. Prva je data sa tri, a druga sa pet afinih transformacija (ili, u našoj terminologiji, sočiva). Svaka transformacija je postavljena doslovno čitanim bajtovima, dok slika izgrađena uz njihovu pomoć može zauzeti nekoliko megabajta.

Postaje jasno kako arhiver radi i zašto je potrebno toliko vremena. U stvari, fraktalna kompresija je traženje samosličnih regija na slici i definiranje parametara afine transformacije za njih.

U najgorem slučaju, ako se ne primeni algoritam optimizacije, biće potrebno nabrajanje i poređenje svih mogućih fragmenata slike različitih veličina. Čak i za male slike, uzimajući u obzir diskretnost, dobijamo astronomski broj opcija koje treba pretraživati. Čak i oštro sužavanje klasa transformacije, na primjer, skaliranjem samo određeni broj puta, neće nam omogućiti da postignemo prihvatljivo vrijeme. Osim toga, gubi se kvalitet slike. Velika većina istraživanja u području fraktalne kompresije sada je usmjerena na smanjenje vremena arhiviranja potrebnog za dobivanje slike visokog kvaliteta.

Za algoritam fraktalne kompresije, kao i za druge algoritme kompresije sa gubicima, veoma su važni mehanizmi pomoću kojih će biti moguće podesiti omjer kompresije i omjer gubitaka. Do danas je razvijen prilično veliki skup takvih metoda. Prvo, možete ograničiti broj konverzija, svjesno osiguravajući da omjer kompresije nije niži od fiksne vrijednosti. Drugo, može se zahtijevati da u situaciji kada je razlika između obrađenog fragmenta i njegove najbolje aproksimacije iznad određene granične vrijednosti, ovaj fragment mora biti zdrobljen (za njega se mora instalirati nekoliko sočiva). Treće, možete zabraniti cijepanje fragmenata manjih od, recimo, četiri točke. Promjenom graničnih vrijednosti i prioriteta ovih uvjeta, možete vrlo fleksibilno kontrolirati omjer kompresije slike: od podudaranja bita do bita do bilo kojeg omjera kompresije.

Poređenje sa JPEG

Danas je najčešći algoritam za arhiviranje grafike JPEG. Uporedimo to sa fraktalnom kompresijom.

Prvo, imajte na umu da oba algoritma rade na 8-bitnim (sivim tonovima) i 24-bitnim slikama u punoj boji. Oba su algoritmi kompresije sa gubitkom i pružaju slične omjere arhiviranja. I fraktalni algoritam i JPEG imaju mogućnost povećanja omjera kompresije povećanjem gubitka. Štaviše, oba algoritma se vrlo dobro paraleliziraju.

Razlike počinju kada uzmemo u obzir vrijeme koje je potrebno algoritmima da zip/raspakuju. Dakle, fraktalni algoritam kompresuje stotine, pa čak i hiljade puta duže od JPEG-a. S druge strane, raspakivanje slike će biti 5-10 puta brže. Stoga, ako će se slika komprimirati samo jednom, ali će se prenositi preko mreže i raspakirati mnogo puta, tada je isplativije koristiti fraktalni algoritam.

JPEG koristi kosinusnu dekompoziciju slike, tako da se gubitak u njoj (čak i sa datim minimalnim gubitkom) pojavljuje u talasima i oreolima na granici oštrih prelaza boja. Upravo zbog ovog efekta ne vole ga koristiti prilikom kompresije slika koje su pripremljene za visokokvalitetno ispisivanje: tamo ovaj efekat može postati vrlo uočljiv.

Fraktalni algoritam eliminiše ovaj nedostatak. Štaviše, kada ispisujete sliku, svaki put morate izvršiti operaciju skaliranja, budući da raster (ili linija) uređaja za štampanje ne odgovara rasteru slike. Prilikom konverzije može doći i do nekoliko neugodnih efekata, koji se mogu riješiti bilo programskim skaliranjem slike (kod jeftinih uređaja za štampanje kao što su konvencionalni laserski i inkjet štampači), bilo opremanjem uređaja za štampanje sopstvenim procesorom, čvrstim diskom i set programa za obradu slike (za skupe mašine za fotosetiranje). Kao što možete pretpostaviti, kada koristite fraktalni algoritam, takvih problema praktički nema.

Do izmještanja JPEG-a fraktalnim algoritmom u širokoj upotrebi neće doći uskoro (barem zbog male brzine arhiviranja potonjeg), međutim, u području multimedijalnih aplikacija, u kompjuterskim igrama, njegova upotreba je sasvim opravdana.

Sažetak lekcije iz informatike i IKT

Tip : Lekcija u učenju novog gradiva

Tema : Arhivari. Metode kompresije informacija.

Ciljevi :

Istražite tehnike kompresije informacija (pakovanje i Huffman)

Razvijati algoritamsko razmišljanje

Negovanje odgovornog odnosa prema izvršenju zadatka.

Metoda: Objašnjavajuće i ilustrativno

Tokom nastave:

Organizacioni trenutak (2 min)

Ažuriranje znanja. (5 minuta)

Objašnjenje gradiva i upisivanje u svesku. (25 minuta)

Početna konsolidacija materijala (10 min)

Rezimirajući. (3 min)

Pitanja o ažuriranju znanja:

Kako shvaćate pojam "komprimiranja informacija"?

Kako se komprimiraju digitalne informacije?

Koje programe arhiviste poznajete?

Informacije u kojem obliku zahtijevaju obavezno sažimanje?

Teorijski materijal:

U životu svakog korisnika računara redovno se javljaju situacije kada, na primer, treba da prenesete jednu ili više datoteka na drugi računar pomoću prenosivog medija ograničene veličine, pošaljete veliki fajl e-poštom itd. Po pravilu, postoji problem razdvajanja velikog fajla na još nekoliko manjih fajlova sa mogućnošću njegove dalje rekonstrukcije, grupisanja većeg broja malih fajlova u veće, komprimovanja fajlova radi smanjenja njihove veličine itd. Za rješavanje takvih problema koriste se arhiveri.

Arhiveri su programi koji vam omogućavaju da pomoću posebnih metoda kompresije kreirate kopije datoteka manje veličine i kombinujete kopije nekoliko datoteka u jednu arhivsku datoteku, kao i da raspakujete arhive (izdvojite datoteke iz arhive).

Postoje različiti algoritmi za arhiviranje podataka bez gubitka informacija, tj. prilikom raspakivanja, podaci će biti vraćeni u prvobitni oblik. Za Windows, najpopularniji arhivatori su WinRAR, WinZIP, WinACE.

Kompresija informacija je proces pretvaranja informacija pohranjenih u datoteci, zbog čega se smanjuje njena redundantnost, a shodno tome i manje memorije je potrebno za pohranu.

Kompresija informacija u datotekama se vrši eliminacijom suvišnosti na različite načine, na primjer, pojednostavljivanjem kodova, eliminacijom konstantnih bitova iz njih ili predstavljanjem ponavljajućih simbola ili niza simbola koji se ponavljaju u obliku faktora ponavljanja i odgovarajućih simbola. Koriste se različiti algoritmi za takvu kompresiju informacija.

Način pakovanja

Ulazni tekst "BELL_BALL_BALL" sadrži ukupno 5 različitih znakova (K, O, L, A, _). Stoga se svaki simbol može kodirati sa tri bita. U originalnom testu ima ukupno 18 znakova, tako da je potrebno 18X3 = 54 bita. Omjer kompresije je 144/54 = 2,7

Huffmanova metoda.

Slaba tačka metode pakovanja je to što se simboli kodiraju u niz bitova iste dužine. Na primjer, svaki tekst koji sadrži samo slova "A" i "B" komprimuje se metodom pakovanja osam puta. Međutim, ako takvom tekstu dodate samo jedno slovo, na primjer "C", tada će se omjer kompresije odmah prepoloviti, i bez obzira na dužinu teksta i broj dodatih znakova "C"

Poboljšanja omjera kompresije mogu se postići kodiranjem uobičajenih simbola u kratke kodove, a rijetkih u dužim. Upravo je to ideja koja stoji iza metode koju je objavio D. Huffman 1952. godine.

Huffmanov algoritam

Znakovi u ulaznoj abecedi formiraju listu slobodnih čvorova. Svaki čvor ima težinu jednaku broju pojavljivanja znaka u originalnoj poruci.

Dva slobodna čvora sa najmanjim težinama se biraju sa liste.

Njihov "roditeljski" čvor je kreiran sa težinom jednakom zbiru njihovih težina; povezan je sa "decom" lukovima.

Jednom luku koji napušta "roditelj" dodjeljuje se bit 1, drugom - bit 0.

Roditelj je dodat na slobodnu listu, a dva njegova djeteta su uklonjena sa ove liste.

Koraci koji počinju od drugog se ponavljaju sve dok samo jedan slobodni čvor ne ostane na listi slobodnih. On će se smatrati korijenom drveta.

Zadaci

Pakujte poruku na 2 načina: Arkhip_osip._Osip_ocryp.

Pitanja za rezimiranje lekcije:

Šta je kompresija informacija?

Glavna svrha programa arhiviranja.

Koje metode kompresije smo danas naučili?

Koja je najefikasnija metoda kompresije i zašto?

Plan:

Uvod

• 1 Principi kompresije podataka
• 2 Karakteristike kompresijskih algoritama i njihova primjena
  • 2.1 Omjer kompresije
  • 2.2 Tolerancija gubitka
  • 2.3 Algoritamski sistemski zahtjevi
• 3 Algoritmi kompresije podataka nepoznatog formata
Književnost

Uvod

Kompresija podataka(eng. kompresiju podataka) - algoritamska transformacija podataka izvedena u cilju smanjenja njihovog volumena. Koristi se za racionalnije korišćenje uređaja za skladištenje i prenos podataka. Sinonimi - pakovanje podataka, kompresija, kompresijsko kodiranje, izvorno kodiranje. Obrnuti postupak se naziva oporavak podataka (raspakivanje, dekompresija).

Kompresija se zasniva na eliminaciji suvišnosti u originalnim podacima. Najjednostavniji primjer redundancije je ponavljanje fragmenata u tekstu (na primjer, riječi prirodnog ili mašinskog jezika). Ova redundantnost se obično eliminiše zamjenom ponovljene sekvence referencom na već kodirani fragment s naznakom njegove dužine. Druga vrsta redundancije povezana je s činjenicom da se neke vrijednosti u podacima koji se kompresuju javljaju češće od drugih. Smanjenje količine podataka postiže se zamjenom često susrećenih podataka kratkim kodnim riječima, a rijetkih podataka dugim (entropijsko kodiranje). Sažimanje podataka koji nemaju svojstvo redundancije (na primjer, nasumični signal ili šum, šifrirane poruke) u osnovi je nemoguće bez gubitka.

1. Principi kompresije podataka

Bilo koja metoda kompresije je zasnovana na modelu izvora podataka, tačnije, na modelu redundancije. Drugim riječima, kompresija podataka koristi neke a priori informacije o tome koja vrsta podataka se kompresuje. Bez takvog poznavanja izvora nemoguće je napraviti bilo kakvu pretpostavku o transformaciji koja bi smanjila veličinu poruke. Model redundancije može biti statičan, nepromijenjen za cijelu poruku koja se kompresuje, ili se može izgraditi ili parametrirati tokom faze kompresije (i oporavka). Metode koje omogućavaju promjenu modela redundantnosti informacija na osnovu ulaznih podataka nazivaju se adaptivne. Neprilagodljivi su obično visoko specijalizovani algoritmi koji se koriste za rad sa podacima sa dobro definisanim i nepromenljivim karakteristikama. Ogromna većina prilično univerzalnih algoritama je prilagodljiva u jednom ili drugom stepenu.

Sve metode kompresije podataka dijele se u dvije glavne klase:

• Kompresija bez gubitaka
• Kompresija sa gubitkom

Kada koristite kompresiju bez gubitaka, moguć je potpuni oporavak originalnih podataka; kompresija s gubicima vam omogućava da oporavite podatke s izobličenjem, koje su obično beznačajne sa stanovišta daljnje upotrebe oporavljenih podataka. Kompresija bez gubitaka obično se koristi za prijenos i pohranjivanje tekstualnih podataka, kompjuterskih programa, rjeđe za smanjenje jačine audio i video podataka, digitalnih fotografija itd., u slučajevima kada je izobličenje neprihvatljivo ili nepoželjno. Kompresija s gubicima, koja je znatno efikasnija od kompresije bez gubitaka, obično se koristi za smanjenje volumena audio i video podataka i digitalnih fotografija u slučajevima kada je takvo smanjenje prioritet, a potpuna usklađenost originalnih i oporavljenih podataka nije potrebna.

2. Karakteristike kompresijskih algoritama i njihova primjena

2.1. Omjer kompresije

Omjer kompresije je glavna karakteristika algoritma kompresije. Definira se kao omjer volumena originalnih nekomprimiranih podataka i volumena komprimiranih podataka, odnosno:

gdje k- omjer kompresije, S o je količina početnih podataka, i S c - komprimovani volumen. Dakle, što je veći omjer kompresije, to je algoritam efikasniji. Treba napomenuti:

• ako k= 1, tada se algoritam ne komprimira, odnosno izlazna poruka je po volumenu jednaka ulaznoj;
• ako k < 1, то алгоритм порождает сообщение большего размера, нежели несжатое, то есть, совершает «вредную» работу.

Situacija sa k < 1 вполне возможна при сжатии. Принципиально невозможно получить алгоритм сжатия без потерь, который при любых данных образовывал бы на выходе данные меньшей или равной длины. Обоснование этого факта заключается в том, что поскольку число различных сообщений длиной n bit je tačno 2 n, broj različitih poruka čija je dužina manja ili jednaka n(ako postoji barem jedna poruka kraće dužine) bit će manja od 2 n... To znači da je nemoguće nedvosmisleno povezati sve originalne poruke sa komprimovanom: ili neke od originalnih poruka neće imati komprimiranu reprezentaciju, ili će nekoliko originalnih poruka odgovarati istoj komprimiranoj, što znači da se ne mogu razlikovati.

Omjer kompresije može biti ili konstantan (neki algoritmi za kompresiju zvuka, slika, itd., na primjer, A-zakon, μ-zakon, ADPCM, skraćeno kodiranje bloka) ili promjenjiv. U drugom slučaju, može se odrediti ili za svaku konkretnu poruku, ili ocijeniti prema nekim kriterijima:

• prosjek (obično preko nekog skupa testnih podataka);
• maksimum (slučaj najbolje kompresije);
• minimalna (kompresija u najgorem slučaju);

ili šta god. Omjer kompresije s gubicima u ovom slučaju uvelike ovisi o dopuštenoj grešci kompresije ili kvaliteta, koji obično djeluje kao parametar algoritma. Općenito, samo tehnike kompresije podataka sa gubitkom mogu osigurati konstantan omjer kompresije.

2.2. Tolerancija gubitka

Glavni kriterij za razlikovanje algoritama kompresije je prisustvo ili odsustvo gubitaka opisanih gore. Općenito, algoritmi kompresije bez gubitaka su univerzalni u smislu da je njihova upotreba svakako moguća za bilo koju vrstu podataka, dok mogućnost korištenja kompresije s gubicima treba opravdati. Za neke vrste podataka, izobličenja općenito nisu prihvatljiva. Među njima

• simbolički podaci, promjena u kojoj neizbježno dovodi do promjene njihove semantike: programi i njihovi izvorni kodovi, binarni nizovi itd.;
• vitalni podaci, čije promjene mogu dovesti do kritičnih grešaka: na primjer, dobijene iz medicinske mjerne opreme ili kontrolnih uređaja aviona, svemirskih letjelica, itd.;
• Međupodaci koji se više puta podvrgavaju kompresiji i restauraciji tokom višestepene obrade grafičkih, audio i video podataka.

2.3. Algoritamski sistemski zahtjevi

Različiti algoritmi mogu zahtijevati različitu količinu resursa računarskog sistema na kojem su implementirani:

• Memorija sa slučajnim pristupom (za međupodatke);
• trajna memorija (za programski kod i konstante);
• procesorsko vrijeme.

Općenito, ovi zahtjevi zavise od složenosti i "inteligencije" algoritma. Opšti trend je sljedeći: što je algoritam efikasniji i svestraniji, to su veći zahtjevi za računskim resursima na koje postavlja. Ipak, u specifičnim slučajevima, jednostavni i kompaktni algoritmi mogu raditi kao i oni složeni i univerzalni. Sistemski zahtjevi određuju njihove potrošačke kvalitete: što je algoritam manje zahtjevan, to je jednostavniji, a samim tim i kompaktan, pouzdan i jeftin sistem koji se može implementirati.

Pošto algoritmi kompresije i oporavka rade u tandemu, omjer sistemskih zahtjeva prema njima je bitan. Često je moguće da se kompliciranjem jednog algoritma uvelike pojednostavi drugi. Dakle, moguće su tri opcije:

Algoritam kompresije zahtijeva više računskih resursa nego algoritam za oporavak. Ovo je najčešći odnos, tipičan za slučajeve kada će se jednom komprimirani podaci koristiti više puta. Primjeri uključuju digitalne audio i video plejere. Algoritmi kompresije i oporavka zahtijevaju približno jednake računske resurse. Najprihvatljivija opcija za komunikacijske linije, kada se kompresija i restauracija javljaju jednom na dva kraja (na primjer, u digitalnoj telefoniji). Algoritam kompresije je znatno manje zahtjevan od algoritma za oporavak. Ova situacija je tipična za slučajeve kada se postupak kompresije provodi jednostavnim, često prenosivim uređajem za koji je količina raspoloživih resursa vrlo kritična, na primjer, svemirska letjelica ili velika distribuirana mreža senzora. To mogu biti i podaci koje je potrebno raspakovati u vrlo malom procentu slučajeva, na primjer, snimak CCTV kamera.

3. Algoritmi za komprimiranje podataka nepoznatog formata

Postoje dva glavna pristupa komprimiranju podataka nepoznatog formata.

• U svakom koraku algoritma kompresije, sljedeći komprimirani znak se ili stavlja u izlazni međuspremnik kompresirajućeg kodera kakav je (sa posebnom zastavicom koja pokazuje da nije komprimiran), ili se grupa od nekoliko komprimiranih znakova zamjenjuje sa link do grupe već kodiranih znakova koji joj odgovara. Budući da je oporavak podataka komprimiranih na ovaj način vrlo brz, ovaj pristup se često koristi za kreiranje samoraspakujućih programa.
• Za svaki niz komprimiranih znakova, statistika njegovog pojavljivanja u kodiranim podacima se prikuplja jednom ili u svakom trenutku. Na osnovu ove statistike izračunava se vjerovatnoća vrijednosti sljedećeg kodiranog znaka (ili niza znakova). Nakon toga se primjenjuje jedna ili druga vrsta entropijskog kodiranja, na primjer, aritmetičko kodiranje ili Huffmanovo kodiranje, za predstavljanje čestih nizova u kratkim kodnim riječima, a rijetko pronađenih s dužim.

Književnost

• D. Vatolin, A. Ratushnyak, M. Smirnov, V. Yukin. Metode kompresije podataka. Uređaj za arhiviranje, kompresiju slika i video zapisa. - Dialogue-MEPhI, 2002.-- P. 384 .-- ISBN 5-86404-170-X 3000 primjeraka
• D. Salomon. Kompresija podataka, slika i zvuka. - M.: Tehnosfera, 2004.-- S. 368 .-- ISBN 5-94836-027-X 3000 primjeraka

Slajd 2

• Za dugotrajno skladištenje podataka na različitim medijima
• Za prijenos podataka putem komunikacijskih kanala