Arhivēšanas algoritmi

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.

• arhivēšanas algoritmi bez zudumiem (iespējama atarhivēšana bez izmaiņām),

Kriptogrāfijā izmanto tikai arhivēšanu bez zudumiem. Otras grupas algoritmus var pielietot skaņas, zīmējumu un video saspiešanai.

Arhivēšanai bez zudumiem parasti izmanto vienu no trim algoritmiem:

• 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;

5) simbolu kods binārajā sistēmā ir ceļš no grafa virsotnes līdz šim simbolam:

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).

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:

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 8x8, 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.