Rēzeknes Augstskola
Inženieru fakultāte
Datorzinātņu un matemātikas katedra
Algoritmu teorija
Arhivēšanas algoritmi
Referāts
Viktors Ivanovs
RA Inženieru fakultātes
studiju programmas “Programmēšanas inženieris”
pilna laika studiju 4.kursa students
*******
…………………………………………
(paraksts)
Darba vadītājs:
Dr.sc.ing.,docents *********
…………………………………………
(paraksts)
Rēzekne 2007
Ievads
Arhivēšanas vispārīgie principi
Datu formāti lielākoties ir tādi, ka ar informāciju ir viegli strādāt, to ērti lasīt, bet pie tam dati aizņem vairāk atmiņas, nekā vajag. Algoritmus, kas saspiež informāciju (likvidējot to pārpalikumu) sauc par datu saspiešanas algoritmiem, jeb arhivēšanas algoritmiem.
Visus saspiešanas algoritmus var sadalīt divās grupās:
• arhivēšanas algoritmi bez zudumiem (iespējama atarhivēšana bez izmaiņām),
• arhivēšanas algoritmi ar zudumiem (var būt zaudēta neievērojama informācijas daļa, kura neietekmē informācijas būtību vai kuru cilvēks vispār neuztver).
Kriptogrāfijā izmanto tikai arhivēšanu bez zudumiem. Otras grupas algoritmus var pielietot skaņas, zīmējumu un video saspiešanai.
1. Arhivēšanas algoritmi bez zudumiem.
Arhivēšanai bez zudumiem parasti izmanto vienu no trim algoritmiem:
• Haffmana algoritms – neatkarīgu baitu saspiešana,
• Grupu kodēšana (RLE) – blakus stāvošu vienādu simbolu kodēšana,
• Lempela-Ziva algoritms – teksta saspiešana, analizējot atkārtojošas simbolu secības.
Haffmana algoritms (Huffman, 1952.g.) izmanto to, ka tekstā daži simboli sastopas samēra bieži, bet citi – ļoti reti. Parasti (ASCII sistēmā) katrs simbols aizņem 1 baitu (8 bitus), kas ļauj izmantot 256 dažādus simbolus. Haffmansd piedāvāja bieži sastopamus simbolus kodēt ar īsākām bitu secībām, un retākus – ar garākām. Tas var ievērojami samazināt faila izmēru. Starp citu, analogs princips strādā Morze ābecē: populārākiem simboliem atbilst īsi kodi (piemēram, e , t _, m –, i ), mazāk izplatītajiem – garāki kodi (q –-, z –, p –). Un uz tastatūras populārāki simboli ir centrā, retāk vajadzīgi – sānos.
1.1 Haffmana algoritms sāk savu darbu ar teksta analīzi.
1) aprēķinā, cik reizes sastopas tekstā katrs simbols, piemēram: a-7, b-20, k-10, i-15;
2) apvieno divus “visretākos” simbolus: ak-17, b-20, i-15;
3) atkārto 2. punktu līdz kamēr visi simboli tiks apvienoti:
aki-32, b-20;
akib-52.
Pēdējais skaitlis (52) ir teksta garums baitos (simbolu skaits tekstā)
4) attēlo šo procesu uz grafa:
5) simbolu kods binārajā sistēmā ir ceļš no grafa virsotnes līdz šim simbolam:
a-000, k-001, i-01, b-1.
Var redzēt, ka tiešām simbola koda garums ir atkarīgs no simbola “popularitātes” tekstā.
1.2 Grupu kodēšanas algoritmi, jeb RLE (Run Length Encoding) vienkārši aizstāj vienādu simbolu grupu ar vienu simbolu un simbolu skaitu grupā visur, kur tas ir izdevīgi. Piemēram: aaaaabbbbbbccddddddd – (a,5)(b,6)cc(d,7).
1.3 Lempela-Ziva algoritms (1978.g.) analizē atkārtojošas simbolu secības un aizstāj tas ar norādēm formātā “nobīde (смещение) – garums (длина)”. Piemēram: informātika=informācija+automātika – informātika=(-12,7)cija+auto(-22,6).
2. Arhivēšanas algoritmi ar zudumiem.
Fraktāļu algoritms strauji attīstās no 1992.g. Fraktāls ir pašlīdzīgs objekts: tas nozīmē, ka objekta daļas ir līdzīgas pašam objektam. Viens no pazīstamākiem fraktāļiem ir Barnsli paparde – sk.zīm.
Fraktālu algoritms meklē līdzīgus objektus, kuri var būt iegūti cits no cita, pielieto tiem afīnu pārveidošanas:
• projekcija,
• pagrieziens,
• atspoguļojums,
• mēroga mainīšana,
• spilgtuma un kontrasta mainīšana.
Saglabājot informāciju par nelieliem zīmējuma fragmentiem un pārveidošanas koeficientus, var atjaunot zīmējumu bez ievērojamiem kvalitātes zudumiem.
Fraktāļu algoritms ir ļoti sarežģīts, prasa daudz resursu, bet ļauj sasniegt lielus saspiešanas koeficientus, strādājot ar fotoattēliem. JPEG (un tā modifikācijas) ir viens no jaunākajiem (pirmais standarts parādījās 1991.g.) un labākajiem algoritmiem pilnkrāsu attēliem. Tas sadala attēlu kvadrātos 8×8, kuriem pielieto matemātiskas metodes – Furje pārveidošanas. Ievērojami kvalitātes zudumi parādās blakus kontrastam krāsu robežām, kā arī pie lielām saspiešanas koeficienta vērtībām. Rekursīvais jeb viļņu algoritms orientēts uz attēliem ar nepārtrauktām krāsu pārejām. Vilnu saspiešana pielieto Furje pārveidošanas veselam attēlam (nedalot attēlu uz kvadrātiem, kā JPEG), kas paaugstina saspiesta zīmējuma kvalitāti. Failā tiek saglabāta zīmējuma samazināta kopija un koeficientu tabulas, kas ļauj pakāpeniski atjaunot attēlu, katrā solī uzlabojot tā kvalitāti.
3. Attēlu saspiešanas algoritmi un formāti.
Pēc datu glabāšanas veida grafiskus formātus var sadalīt divās lielās grupās:
• rastra grafika,
• vektorgrafika.
Rastra grafikas attēls ir divdimensiju masīvs ir elementiem – pikseļiem. Savukārt, ir vairāki dažādi formāti pikseļu glabāšanai. Piemēram, grafikā ar paleti katram pikselim atbilst viens skaitlis – krāsas numurs paletē, bet RGB (red-greem-blue) sistēmā katram pikselim atbilst trīs skaitļi – sarkanas, zaļas un zilas krāsas intensitātes. Rastra attēli var izmantot dažādas krāsu sistēmas, kā arī saturēt dažāda rakstura papildu informāciju par dažādiem krāsu modeļiem, kanāliem, slāņiem, vektoriem, animāciju utt.
Vektorgrafikas attēls sastāv no standarta objektiem (līnijām, taisnstūriem utt.); katru objektu nosaka tā pamatpunktu koordinātes, līnijas un tonēšanas krāsas un stili, speciāli efekti. Dažādi vektorgrafikas formāti izmanto atšķirīgus kodēšanas principus, un bieži var būt nesavietojami.
Bet arī vienā formātā saglabātie zīmējumi var būt ļoti atšķirīgi:
• attēli ar nelielu krāsu skaitu un lieliem apgabaliem, aizpildītiem ar vienu krāsu (piemēram, diagrammas, shēmas),
• attēli, kuros ir nepārtrauktas krāsu pārejas, izveidotas ar datora palīdzību (piemēram, prezentācijas),
• fotoattēli utt.
Pielietojot dažādus algoritmus dažādu tipu attēliem, var pārliecināties, ka saspiešanas algoritmu efektivitāte ir stipri atkarīga no tā, kādi dati ir jāarhivē. Ja algoritms pats no sevis ir labs, bet neatbilst konkrētu datu tipam, var gadīties, ka pēc saspiešanas faila izmērs ne tikai nesamazināsies, bet pat kļūs lielāks.
Sākumā zīmējumu saspiešanai izmantoja standarta algoritmus bez zudumiem (Haffmana, RLE, Lempela-Ziva). Vēlāk tika izstrādāti speciālie algoritmi ar zudumiem, paredzēti tieši zīmējumu saspiešanai (JPEG, rekursīvā jeb vilnu saspiešana, fraktāļu saspiešana utt.). Arhivatori ar zudumiem parasti ļauj izvēlēties saspiešanas koeficientu (un, attiecīgi, kvalitātes samazināšanas pakāpi). Arhivēšanas kvalitāti uzskata par teicamu, ja cilvēka acis nevar atšķirt iearhivētu attēlu to no tā oriģināla. Saspiešanas kvalitāte ir laba, ja atšķirību var pamanīt, tikai salīdzinot divus blakus stāvošus attēlus. BMP (Windows Device Independent Mitmap) – rastra grafikas formāts, paredzēts darbam Windows vidē. Iespējama (taču nav ieteicama) RLE-saspiešana.
GIF (Graphics Interchange Format) – formāts izstrādāts 1987.g. rastra attēlu pārraidei datoru tīklos (firmā CompuServe). GIF izmanto Lempela-Ziva saspiešanu (precīzāk – LZW – Lempel, Ziv, Welch).
GIF ir neatkarīgs no aparatūras. Tas ļauj ierakstīt un lasīt attēlu “ik pēc rindas” (Interlaced), pateicoties tam var izvadīt attēlu, nolasot tikai daļu no faila,- protams, ar sliktāku izšķirtspēju. Šīs formāts ļauj saglabāt arī Alpha-kanālu (kas ir atbildīgs par caurspīdīguma efektiem). Vienā GIF-failā var būt vairāki zīmējumi, kuri ielādas pēc kārtas ar noteiktiem starplaikiem (animācija). Galvenais ierobežojums – krāsu skaits līdz 256. JPG – neatkarīgs no aparatūras rastra grafikas formāts; to var izmantot gan IBM PC, gan Macintosh datoros. JPG formātā tiek izmantots saspiešanas algoritms JPEG, kas ļoti labi saspiež zīmējumus ar foto kvalitāti (JPG var būt līdz 500 reizes kompaktāks, kā BMP). Eksistē vairākas JPG formāta modifikācijas. TIF (Tagged Image File Format) – neatkarīgs no aparatūras rastra grafikas formāts; kuru “saprot” praktiski praktiski visas IBM PC un Macintosh grafikas programmas. Ļoti drošs un ērts datu importam izdevniecības sistēmās. Var izmantot visas krāsu modeļus, kā arī dažādus papildu datus. Formātā TIFF paredzēta iespēja saspiest datus, saglabājot tos (JPEG, ZIP, LZW, RLE, Haffmana algoritms). Taču jāievēro, ka veca programmatūra nesaprot saspiestus TIFF. CDR (CorelDRAW Document) – vektorgrafikas formāts. Līrz 7.versijai tas bija nedrošs un slikti savietojams ar ne-Corel programmām, bet mūsdienu versijās vecas problēmas jau atrisinātas. Vektorattēliem un rastra attēliem tiek pielietoti dažādi saspiešanas algoritmi. WMF (Windows Metafile) – vektorgrafikas formāts datu apmaiņai caur Clipboard. WMF saprot visi grafiskie redaktori, strādājoši Windows vidē (bet WMF-failu veidošanai vispiemērotākais ir CorelDRAW). Iespējama RLE-saspiešana.
4. Skaņas saspiešanas algoritmi un formāti
Skaņa pēc savas dabas ir vilni (gausa svārstīšanas), tāpēc skaņu saglabāšanai nepieciešama tās kodēšana (diskretizācija). Parasti skaņu sadala mazos laika sprīžos un katram sprīdim ieraksta svārstīšanas koeficientus – šo procesu sauc par impulsu-kodu modulāciju. Jo lielāka ir modulatora platība, jo vairāk raksturlielumu tas saglabā katram skaņas gabaliņam un jo tuvāk oriģinālam būs ierakstīta skaņa.
Standarta arhivēšanas metodes bez zudumiem parasti nevar dod labu rezultātu skaņas saspiešanā, pat pēc adoptācijas tieši skaņas apstrādei. Tāpēc tika izstrādāti speciāli algoritmi ar zudumiem (MPEG, AAC un citi).
Skaņas saspiešanas algoritmos izmanto šādas metodes:
Paužu saspiešana – grupu saspiešanas (RLE) analogs.
Psihoakustikas metodes – pamatojoties uz cilvēku skaņas uztveršanas īpašībām, aprēķinā laika intervālus diskretizācijai un izmet maznozīmīgu informāciju tā, ka ir grūti pamanīt izmaiņas (kaut gan skaņas kodam paliek ļoti maz kopīgā ar oriģinālu).
Minēsim dažus interesantus skaitļus, kas raksturo cilvēka skaņas uztveršanu.
• Frekvenču diapazons: 20Hz – 20kHz; tas nozīmē, ka ar diskretizācijas frekvenci 40kHz var apstrādāt skaņu bez jūtamiem kvalitātes zudumiem.
• Maksimālā jutīguma diapazons: 2kHz – 4kHz,
• Skaļums – līdz 96 dB;
• Piemēram, frekvencēs ap 1 kHz cilvēks nejūt frekvences izmaiņas līdz 0.3%;
• Skaļuma izmaiņas grūti pamanīt, ja tās nepārsniedz 1 dB;
• Cilvēks nevar pamanīt arī, ja augstās frekvences pazūd uz laiku līdz 2 ms.
• Vispār, cilvēks reāli uztver tikai 10% informācijas skaņas signālā; atlikušas 90% var izmest (tikai jānoskaidro, kāda informācija ir svarīga, un kāda – nevajadzīga).
Nesaspiestas skaņas kvalitāti ciparu formātā nosaka diskretizācijas frekvence un bitu skaits katram sprīdim. Piemēram, ierakstot skaņu kompaktdiskos, izmanto diskretizācijas frekvenci 44,1kHz (kas atbilst skaņas frekvencēm līdz 22kHz – tas pat mazliet pārsniedz cilvēka uztveršanas diapazonu) un bitu skaitu 16, kas nodrošina 216=65536 skaņas līmeņa vērtības. Šādas skaņas pārraidei “reālā laikā” bez saspiešanas nepieciešams pārraides ātrums 44.1*16700 Kbiti/s. Stereo skaņai – divreiz lielāks 1400 Kbiti/s. Saspiešanas algoritmi ļauj ievērojami samazināt informācijas apjomu un kopā ar to nepieciešama ātruma vērtību apmēram 10 reizēs bez ievērojamiem skaņas kvalitātes zudumiem.
Aplūkosim vairākus skaņu formātu piemērus.
VOC (saīsinājums no voice – balss) – izmanto skaņu platēs SoundBlaster.
AU, SND (-law, kompānija Sun/NeXT) – izplatīts internetā formāts, neatkarīgs no aparatūras. Windows neatbalsta šo formātu, bet var izmantot, piemēram, shareware programmu GoldWave.
PMC (Pulse Code Modulatiom) – impulsu kodu modulācija. Faili ar šādu paplašinājumu sastopas ļoti reti, bet PMC princips ir visu skaņas failu pamatā. DPCM un ADPCM – taupīgāki PCM varianti.
WAV (Waveform, firmas Microsoft un IBM) – vienkāršs (tiešs) formāts skaņas informācijas glabāšanai diskrētā veidā; paredzēts darbam Windows vidē.
AIFF (Audio Interchange File Format) un AIFC (compressed) – paredzēts datoriem Macintosh, bet strādāt ar to var arī Windows vidē, izmantojot kādu programmu tipa GoldWave.
MPEG (Moving Pictures Exxperts Group) – tiek izmantota “psihoakustikas” skaņa saspiešana; darbam ar failiem nepieciešama speciāla programmatūra.
RA (Real Audio) – izplatīts formāts skaņas pārraidei Internetā “reālajā laikā”.
5. Video saspiešanas algoritmi un formāti
Video objekti ir, laikam, vislielākie objekti datoros. Piemēram, visizplatītākajām standartam NTSC (raidīšanas kvalitāte) atbilst kadra izmērs 640×480, 24 bitu pikseļi, frekvence 30 kadri sekundē. Tas nozīmē, ka nesaspiestā veidā 1s video aizņem apmēram 30 M atmiņas. Ciparu video saspiešanai izmanto kodekus (codec) – speciālus saspiešanas algoritmus. Ir metodes, kuras samazina krāsu skaitu, kadra izmēru, frekvenci un – kopā ar to arī kvalitāti. Sarežģītākas metodes analizē ne tikai atsevišķus kadrus, bet arī kadru secības, kas ļauj ievērojami saspiest video bez manāmiem kvalitātes zudumiem. Internetā parasti izmanto videoformātus MPEG un QuickTime. MPEG (Motion Picture Experts Group) videofailiem parasti ir paplašinājums MPG. Saspiešanas algoritmā izmanto pareģošanas mehānismu: aktīva kadra saturs tiek izmantots nākošo kadru prognozei. Šādā veidā videofailus nav iespējams rediģēt saspiestā stāvoklī. MPEG nodrošina labus saspiešanas koeficientus gan video, gan audio informācijai (1:50), kā arī augstu arhivēšanas un atarhivēšanas ātrumu (līdz 1.5M/s) bez ievērojamiem kvalitātes zudumiem. Bet, no otrās puses, MPEG-video veidošanai nepieciešama speciāla (un diezgan dārga) aparatūra, kuras iespējas izmanto saspiešanas algoritmi. Formāts QuickTime (firma Apple) atbalsta jebkuras video, audio, animācijas un teksta kombinācijas, pat interaktīvas komandas. Failu paplašinājums – MOV. Datus formātā QuickTime var rediģēt. QuickTime izmanto vairākus saspiešanas algoritmus (Photo-JPEG, Apple Video, MPEG u.c.), pielietojot katru atbilstošā tipa datiem. AVI (Audio/Video Interleaved – firma Microsoft) paredzēts video un audio informācijas glabāšanai un izmantošanai Windows vidē. Video un audio kadri glabājas kopā vienā failā, kas nodrošina to sinhronizāciju. Datu saspiešanai izmanto algoritmus Intel Indeo un Cinepack. Parasti AVI failus “atskaņo” nelielā logā 320×240 ar frekvenci 15 kadri sekundē, bet, izmantojot atbilstošo aparatūru un programmatūru var sasniegt arī pilnekrāna variantu ar 30 kadriem sekundē.