Datu kompresija kļūst arvien aktuālāka

 

Optimālu datu kompresijas metožu izstrāde patlaban ir viens no galvenajiem faktoriem, kas veicina informācijas tehnoloģiju attīstību. Bez šīm metodēm tādi plaši lietoti komerciāli produkti kā DVD, videofoni, digitālās fotokameras, bezvadu internets, skaņas un video pārraide internetā kļūtu virtuāli neiespējami.

 

Datu saspiešanas loma mūsdienās

Efektīva datu kompresija patlaban ir galvenais informācijas glabāšanas un pārraides metožu attīstības pamatnosacījums. Sakaru kanālu caurlaides spēja ir daudz dārgāks resurss nekā datu glabāšanas resursi, tādēļ aktuāla ir datu saspiešana pirms pārraidīšanas, kas ļauj pārraidīt vairāk datu laika vienībā. Datu saspiešanas algoritmi veidoti tādējādi, ka tiek kodēta izejošā informācija un dekodēta pienākošā informācija. Izmantojot multimediju datu saspiešanu, samazinās nepieciešamais datu joslas platums un aizkaves datu pārraidē.

Arī gandrīz katrs datorlietotājs ir saskāries ar datu kompresijas programmām, kas palīdz risināt datora cietā diska pārpildīšanās problēmu, kā arī palīdz datu nesējā – disketē vai zibatmiņā – ierakstīt vairāk informācijas. Ir izveidotas daudzas datu kompresijas programmas, vairāk pazīstamās ir WinZip, WinRar, mazāk zināmās – Stacker un Doublespace.

 

Datu kodēšanas veidi

Informācijas apstrādes un pārraides teorētiskos aspektus pēta informācijas teorija jeb informātika. Informāciju kā jebkuru reāli eksistējošu lielumu var mērīt un izteikt tās apjomu ar informācijas mērvienībām. Faktiski informācijas saspiešana ir viens no informācijas kodēšanas mērķiem, tāpat kā kļūdu korekcija un kriptogrāfija.

Datu saspiešanas kodi iedalās kodos bez informācijas zudumiem un kodos ar informācijas zudumiem. Izmantojot metodi, kas kodē informāciju bez zudumiem, iespējama pilnīgi precīza datu dekodēšana, un ar šo metodi var kodēt jebkuru informāciju. Kodēšanas metodēm ar zaudējumiem ir lielāks datu saspiešanas koeficients, taču dekodētie dati atšķiras no izejas datiem. Datu saspiešanu ar zaudējumiem pārsvarā izmanto grafisko (JPEG), skaņas (MP3) un video (MPEG) datu kodēšanai, tas ir, tādos gadījumos, kad dekodēto datu atšķirība no oriģinālajiem datiem nav pamanāma vai būtiska, bet datu saspiešana ar zaudējumiem daudzkārt samazina pārraidāmo datu apjomu.

Bezzudumu datu saspiešanu lieto teksta dokumentu, izpildāmo failu, augstas kvalitātes audio un grafisko datņu kodēšanai. Algoritmi, kas kodē informāciju bez zudumiem, parasti veido īsākus kodus biežāk lietojamiem simboliem, bet garākus – retāk lietojamiem simboliem (piemēram, ar Hafmaņa metodi). Metodes trūkums ir tas, ka lai iegūtu lielāku datu saspiešanas koeficientu, nākas izmantot ievērojamus atmiņas daudzumus.

 

Populārākie saspiesto datu formāti

Viens no galvenajiem datu saspiešanas mērķiem ir saspiest audio/video signālu līdz datu joslas platumam, kurš interneta pieslēgumam un CD-ROM lasīšanas ātrumam ir apmēram 1,5 Mbps. Pazīstamākie kompresētu attēlu datu formāti ir JPG (Joint Photographic Experts Group), GIF (Graphics Interchange Format), populārākie kompresētu videodatu formāti ir MPEG (Moving Picture Group), AVI (Audio Video Interleave), populārākais kompresētu audiodatu formāts – MP3.

Arī datora multivides aprīkojums jeb aparatūras un programmatūras komplekts, ar kuru var apstrādāt informāciju multividē, piemēram, CD/DVD atskaņotājs/rakstītājs, skaņas karte, ir savā ziņā kompresētu datņu veidotājs un patērētājs. Multivides sistēmās tiek veidota, apstrādāta, glabāta, prezentēta vai pārraidīta gan no laika neatkarīga informācija (teksts, vektorgrafika, rastra grafika), gan no laika atkarīga informācija (audiodati, videodati, animācijas, interaktīvas spēles tīmekļa vidē).

Datu apjoma piemēri dažiem informācijas veidiem

Lapa ar tekstu (A4 formāts)                               5 KB

Rastra attēls (BMP formāts, 3072x2048 px)           1,12 MB

Audiodati (44,1 KHz)                                          88,2 KB sekundē

Videodati (320x240 px, 30 kadru sekundē)            6,5 MB sekundē

 

Datu saspiešanas metožu īsa vēsture

Semjuela Morzes 1838. gadā izveidotā Morzes ābece ir viens no pirmajiem datu saspiešanas (kodēšanas) piemēriem, jo tekstos angļu valodā visbiežāk sastopamie burti e un t tika kodēti ar īsāku kodu – e ar vienu īso signālu, t – ar vienu garo signālu.

Mūsdienās pazīstamās informācijas saspiešanas metodes tika izveidotas reizē ar informācijas teorijas izstrādi 1940. gadu beigās. Pirmo pasaulē pazīstamo digitālo signālu kompresijas algoritmu, kas balstījās uz atsevišķu teksta bloku sastopamības varbūtību, 1949. gadā neatkarīgi viens no otra izstrādāja Klods Šenons un Roberts Fano. Optimālāku metodi datu saspiešanai, kas bija kompromiss starp datu saspiešanu un kļūdu korekciju, izstrādāja Deivids Hafmanis 1951. gadā.

1970. gadu vidū, kad kļuva aktuāla teksta failu saspiešana pārsūtīšanai internetā, tika izstrādāti vairāki algoritmi, kuros atkārtoti izmantoja Hafmana informācijas kodēšanas metodes. 1977. gadā Abrahams Lempels un Jakobs Zivs realizēja ideju par atsauču un frāžu vārdnīcu izmantošanu kodēšanā. Viņu darbu turpināja Terijs Velčs, izstrādājot LZW (nosaukums veidots no autoru uzvārdu pirmajiem burtiem) datu saspiešanas algoritmu, kuru izmantoja daudzās datu kompresijas sistēmās, piemēram, programmā PKZIP, patlaban – algoritmos LZ77 un LZ78. Lempela–Ziva Velča algoritmā atkārtotu vārdu vietā ievieto atsauces uz sākotnējo vārdu, metodes priekšrocība ir tā, ka nav jāpārsūta kodējuma tabula kopā ar datiem.

1980. gadu beigās līdz ar digitālo attēlu popularitātes pieaugumu tika izstrādāti arī standarti attēlu saspiešanai. 1990. gadu sākumā attēlu saspiešanā sāka plaši lietot datu kompresijas metodes ar zudumiem. Patlaban attēlu saspiešanas standartos iekļautas tādas datu saspiešanas metodes kā FAXCCITT3, GIF, JPEG, BMP, TIFF u. c. Pēdējos 15 gados Hafmaņa kodēšanas metode tiek aizstāta ar aritmētisko (Aritmetic coding) kodēšanu, kuras būtība ir aizstāt ienākošo simbolu plūsmu ar īpašu kodu, kas ir liels decimāldaļskaitlis. Aritmētiskajā kodēšanā viss ziņojums tiek aprakstīts ar vienu reālu skaitli intervālā [0,1), kur katra zīme aiz komata attēlo vienu simbolu. Joprojām lieto arī it kā triviālo datu saspiešanas metodi, piemēram, BMP tipa failos, kur bieži sastopamās apakšvirknes aizstāj ar īsāku kodu, atkārtotus simbolus aizstāj ar simbola kodu un skaitli, cik reižu pēc kārtas šis simbols atkārtojas.

Mūsdienu datu kompresijas metodes tekstu saspiež apmēram trīs reizes, digitālos attēlus saspiež divas reizes, digitālos attēlus ar zudumiem saspiež apmēram 20 reižu. Biežāk lietotie bezzudumu saspiesto datu tipi ir ZIP, BZIP un RAR.

 

Hafmaņa izgudrojums - atspēriens kompresijas algoritmu attīstībā

Šķiet, ka vislielākā un ilglaicīgākā ietekme uz datu kompresijas algoritmu attīstību ir bijusi Deivida Hafmana (David Huffman) datu saspiešanas metodei – Hafmaņa kodēšanai (Huffman Coding Procedure). Pirmoreiz šīs metodes apraksts publicēts 1952. gadā.

Deivids Hafmans dzimis 1925. gadā Ohaio štatā ASV. 18 gadu vecumā viņš ieguvis bakalaura izglītību Ohaio valsts universitātē. Hafmans dienējis armijā, vadījis radara apkalpošanu, pēc Otrā pasaules kara bijis atmīnētājs Ķīnas un Japānas jūrās. Pēc dienesta ieguvis gan maģistra grādu Ohaio universitātē, gan doktora grādu Masačūsetsas Tehnoloģiskajā Institūtā (MIT). Kopš 1953. gada Hafmans strādājis MIT, bet kopš 1967. gada pēc Otrā pasaules kara Kalifornijas universitātē Santakrūzā.

Deividam Hafmanam ir lieli nopelni ne tikai datu saspiešanas teorijas izstrādē un pētījumos, bet arī elektronikā. Universitātē viņš nodarbojās ar akadēmisko programmu veidošanu, lasījis lekciju ciklus informācijas teorijā un signālu analīzē līdz pat 1994. gadam. Par ieguldījumu zinātnē Deividam Hafmanam piešķirti daudzi apbalvojumi. Hafmans nav patentējis savu izgudrojumu – datu kodēšanas ideju, jo, pēc viņa vārdiem, darba rezultāts esot studenti. (My products are my students). Miris 1999. gadā 74 gadu vecumā.

Hafmana kodēšanas idejas būtība ir kodēt tekstā biežāk sastopamos simbolus ar mazāku bitu skaitu, retāk satopamos – ar lielāku bitu skaitu. Hafmaņa algoritms kodē tekstu divos piegājienos – pirmajā tiek sastādīta simbolu biežuma tabula un ģenerēti kodi, otrajā – kodēts teksts. Pirmoreiz šīs datu saspiešanas metodes apraksts tika publicēts 1952. gadā, un šī metode kļuva par bāzi daudziem pētījumiem datu apstrādē. Hafmana kodēšanas principi tika izmantoti komerciālās programmās, piemēram, PKZIP un LHA, kā arī JPEG algoritmā grafisko attēlu saspiešanai. Arī mūsdienās tā nav zaudējusi savu nozīmi, jo Hafmana algoritms (parasti saistībā arī ar citiem algoritmiem) tiek lietots ikdienā katru reizi, kad tiek arhivēti faili, skatītas fotogrāfijas vai filmas datorā, tiek sūtīts fakss, lietoti modemi, datortīkli, digitālā televīzija vai notiek mūzikas klausīšanās.

 

Algorego – cerība datu kompresijas algoritmu attīstībā

Vērienīgi pieaugot datu apjomam, maz palīdz tradicionālie risinājumi – papildu diski informācijas glabāšanai vai datu arhivēšana. Latvijas Universitātes Matemātikas un informātikas Institūta zinātnieki  izveidojuši apvienību Algorego (agrākais nosaukums – Smart Image Solutins), kas izstrādājusi inovatīvu datu arhivēšanas sistēmu.

Tā ļauj saspiest datus apmēram 40 reižu, kā arī ātri manipulēt ar kompresētajiem datiem. Sistēmas arhitektūra ļauj ieekonomēt ievērojamus līdzekļus datu glabāšanas un ekspluatācijas gaitā. Sīkāk ar šo izstrādni var iepazīties interneta vietnē http://www.algorego.com/. Ļoti gribētos, ka arī Latvijas zinātnieku veikums būtu nozīmīgs ieguldījums informātikas zinātnes un mūsdienīgu tehnoloģisko produktu attīstībā.     

Velta MIKA