Tietojen pakkaus
Tietojen pakkaus on algoritminen (yleensä palautuva) datamuunnos , joka suoritetaan niiden käyttämän määrän vähentämiseksi. Sitä käytetään tallennus- ja tiedonsiirtolaitteiden järkevämpään käyttöön . Synonyymit - tietojen pakkaus , pakkaus , pakkauskoodaus , lähdekoodaus . Käänteistä menettelyä kutsutaan tietojen palauttamiseksi (dekompressio, purku).
Pakkaaminen perustuu alkuperäisen tiedon sisältämän redundanssin poistamiseen. Yksinkertaisin esimerkki redundanssista on katkelmien toistaminen tekstissä (esimerkiksi luonnollisen tai konekielen sanat). Tällainen redundanssi eliminoidaan yleensä korvaamalla toistuva sekvenssi viittauksella jo koodattuun fragmenttiin sen pituuden osoittamalla. Toisenlainen redundanssi johtuu siitä, että jotkin pakattavan datan arvot esiintyvät useammin kuin toiset. Tietomäärän vähentäminen saavutetaan korvaamalla usein esiintyvät tiedot lyhyillä koodisanoilla ja harvinaiset pitkillä ( entropiakoodaus ). Tietojen, joilla ei ole redundanssin ominaisuutta (esimerkiksi satunnainen signaali tai valkoinen kohina , salatut viestit), pakkaaminen on pohjimmiltaan mahdotonta ilman häviötä.
Häviöttömän pakkauksen avulla voit palauttaa alkuperäisen viestin kokonaan, koska se ei vähennä siinä olevan tiedon määrää pituuden lyhenemisestä huolimatta. Tällainen mahdollisuus syntyy vain, jos todennäköisyyksien jakauma sanomajoukolla ei ole yhtenäinen, esimerkiksi osa edellisessä koodauksessa teoreettisesti mahdollisista viesteistä ei toteudu käytännössä.
Tietojen pakkaamisen periaatteet
Minkä tahansa pakkausmenetelmän ytimessä on tietolähdemalli tai tarkemmin sanottuna redundanssimalli . Toisin sanoen tietojen pakkaamisessa käytetään jonkin verran ennakkotietoa siitä, millaista dataa pakataan. Ilman tällaista tietoa lähteestä on mahdotonta tehdä mitään oletuksia muunnoksesta, joka pienentäisi viestin kokoa. Redundanssimalli voi olla staattinen, muuttumaton koko pakatun viestin osalta tai rakennettu tai parametroitu pakkaus- (ja palautus)vaiheessa. Menetelmiä, jotka mahdollistavat informaatioredundanssimallin muuttamisen syöttödataan perustuen, kutsutaan adaptiivisiksi. Ei-adaptiiviset ovat yleensä erittäin erikoistuneita algoritmeja, joita käytetään käsittelemään tietoja, joilla on hyvin määritellyt ja muuttumattomat ominaisuudet. Suurin osa riittävän yleismaailmallisista algoritmeista on jossain määrin mukautuvia.
Kaikki tietojen pakkausmenetelmät on jaettu kahteen pääluokkaan:
Häviötöntä pakkausta käytettäessä on mahdollista palauttaa alkuperäiset tiedot kokonaan, kun taas häviöllisen pakkauksen avulla voit palauttaa tiedot vääristymin, jotka ovat yleensä merkityksettömiä palautettujen tietojen jatkokäytön kannalta. Häviötöntä pakkausta käytetään yleensä tekstitietojen, tietokoneohjelmien siirtämiseen ja tallentamiseen, harvemmin - ääni- ja videodatan , digitaalisten valokuvien jne. äänenvoimakkuuden vähentämiseen tapauksissa, joissa vääristymiä ei voida hyväksyä tai ei-toivottuja. Häviöllistä pakkausta, joka on paljon tehokkaampaa kuin häviötöntä pakkausta, käytetään tyypillisesti vähentämään äänen, videon ja digitaalisten valokuvien määrää tapauksissa, joissa pienentäminen on ensisijaista eikä alkuperäisen ja palautetun tiedon täyttä vastaavuutta vaadita.
Pakkausalgoritmien ominaisuudet ja niiden soveltuvuus
Puristussuhde
Pakkaussuhde on pakkausalgoritmin pääominaisuus. Se määritellään alkuperäisen pakkaamattoman datan tilavuuden suhteeksi pakatun tiedon tilavuuteen, eli: , jossa k on pakkaussuhde, S o on alkuperäisen datan tilavuus ja S c on pakatut tiedot. Näin ollen, mitä korkeampi pakkaussuhde, sitä tehokkaampi algoritmi. Se pitäisi huomata:
- jos k = 1, niin algoritmi ei pakkaa, eli lähtöviesti on yhtä suuri kuin tulo;
- jos k < 1, niin algoritmi tuottaa suuremman viestin kuin pakkaamaton, eli se tekee "haitallista" työtä.
Tilanne, jossa k < 1, on täysin mahdollinen pakkauksessa. On pohjimmiltaan mahdotonta saada häviötöntä pakkausalgoritmia, joka mahdollisella tiedolla tuottaisi ulostulossa vähemmän tai yhtä pitkiä tietoja. Syynä tälle tosiasialle on se, että koska eri pituisten n bitin viestien määrä on täsmälleen 2 n , erilaisten viestien, joiden pituus on pienempi tai yhtä suuri kuin n (jos on vähintään yksi lyhyempi viesti) määrä on useimmat 2 n . Tämä tarkoittaa, että on mahdotonta kartoittaa yksiselitteisesti kaikkia alkuperäisiä viestejä pakatuksi: joko joillakin alkuperäisillä viesteillä ei ole pakattua esitystä tai useilla alkuperäisillä viesteillä on sama pakattu esitys, jolloin niitä ei voida erottaa. Vaikka pakkausalgoritmi kasvattaa alkuperäisen datan kokoa, on kuitenkin helppo varmistaa, että niiden koko ei taatusti kasva enempää kuin 1 bittiä. Silloin tapahtuu pahimmassakin tapauksessa epätasa-arvoa:
Tämä tehdään seuraavasti: jos pakatun tiedon määrä on pienempi kuin alkuperäisen määrä, palautetaan pakatut tiedot lisäämällä niihin "1", muuten palautetaan alkuperäiset tiedot lisäämällä niihin "0").
Pakkaussuhde voi olla joko vakio (jotkut äänen, kuvien jne. pakkaamiseen käytettävät algoritmit, kuten A-laki , μ-laki , ADPCM , katkaistu lohkokoodaus ) ja muuttuva. Toisessa tapauksessa se voidaan määrittää joko kullekin tietylle viestille tai arvioida joidenkin kriteerien mukaan:
- keskiarvo (yleensä jollekin testitietojoukolle);
- maksimi (parhaan pakkauksen tapaus);
- minimaalinen (pahin pakkaustapaus);
tai joku muu. Tässä tapauksessa häviöllinen pakkaussuhde riippuu voimakkaasti sallitusta pakkausvirheestä tai laadusta , joka yleensä toimii algoritmin parametrina. Yleisessä tapauksessa vain häviölliset tiedonpakkausmenetelmät voivat tarjota vakiopakkaussuhteen.
Häviöiden sallittavuus
Pääkriteeri pakkausalgoritmien erottamiseksi toisistaan on yllä kuvattujen häviöiden olemassaolo tai puuttuminen. Yleensä häviöttömät pakkausalgoritmit ovat universaaleja siinä mielessä, että niiden käyttö on varmasti mahdollista kaikentyyppisille tiedoille, kun taas häviöllisen pakkauksen käyttömahdollisuus on perusteltava. Joillekin tietotyypeille vääristymät eivät ole periaatteessa sallittuja. Heidän keskuudessaan
- symboliset tiedot, joiden muuttuminen johtaa väistämättä niiden semantiikan muutokseen: ohjelmat ja niiden lähdetekstit, binääritaulukot jne.;
- tärkeitä tietoja, joiden muutokset voivat johtaa kriittisiin virheisiin: esimerkiksi saatu lentokoneiden, avaruusalusten jne. lääketieteellisistä mittauslaitteista tai ohjauslaitteista;
- välitiedot, jotka on toistuvasti pakattu ja palautettu graafisten, ääni- ja videotietojen monivaiheisen käsittelyn aikana.
Algoritmien järjestelmävaatimukset
Eri algoritmit voivat vaatia eri määriä resursseja siitä tietokonejärjestelmästä, jossa ne on toteutettu:
- RAM (välitiedoille);
- pysyvä muisti (ohjelmakoodin ja vakioiden alla);
- prosessorin aika.
Yleensä nämä vaatimukset riippuvat algoritmin monimutkaisuudesta ja "älykkyydestä". Yleinen trendi on seuraava: mitä tehokkaampi ja monipuolisempi algoritmi, sitä suurempia vaatimuksia se asettaa laskentaresursseille. Tietyissä tapauksissa yksinkertaiset ja kompaktit algoritmit voivat kuitenkin toimia yhtä hyvin kuin monimutkaiset ja yleismaailmalliset algoritmit. Järjestelmävaatimukset määräävät niiden kuluttajaominaisuudet: mitä vähemmän vaativa algoritmi, sitä yksinkertaisempi ja siten kompaktimpi, luotettavampi ja halvempi järjestelmä voidaan toteuttaa.
Koska pakkaus- ja palautusalgoritmit toimivat pareittain, järjestelmävaatimusten suhteella niihin on merkitystä. Usein on mahdollista monimutkaistamalla yhtä algoritmia merkittävästi yksinkertaistaa toista. Eli kolme vaihtoehtoa on mahdollista:
Pakkausalgoritmi vaatii enemmän laskentaresursseja kuin palautusalgoritmi. Tämä on yleisin suhde, tyypillinen tapauksiin, joissa kerran pakattua tietoa käytetään toistuvasti. Esimerkkinä digitaaliset ääni- ja videosoittimet. Pakkaus- ja palautusalgoritmit vaativat suunnilleen yhtä suuret laskentaresurssit. Hyväksyttävin vaihtoehto viestintälinjoille, kun pakkaus ja palautus tapahtuu kerran sen kahdessa päässä (esimerkiksi digitaalisessa puhelussa). Pakkausalgoritmi on huomattavasti vähemmän vaativa kuin palautusalgoritmi. Tämä tilanne on tyypillinen tapauksille, joissa pakkausprosessi toteutetaan yksinkertaisella, usein kannettavalla laitteella, jolle käytettävissä olevien resurssien määrä on erittäin kriittinen, esimerkiksi avaruusalus tai laaja hajautettu anturiverkko. Se voi myös olla dataa, joka on purettava erittäin pienessä osassa tapauksia, kuten CCTV-materiaalia.Tuntemattomat tietojen pakkausalgoritmit
Tuntemattoman muodon tietojen pakkaamiseen on kaksi päätapaa:
- Jokaisessa pakkausalgoritmin vaiheessa seuraava pakattava merkki joko sijoitetaan pakkaavan kooderin lähtöpuskuriin sellaisenaan (erityisellä lipulla, joka osoittaa, että sitä ei pakattu), tai useiden pakattavien merkkien ryhmä korvataan linkillä. ryhmään jo koodattuja merkkejä, jotka vastaavat sitä. Koska tällä tavalla pakattujen tietojen palautus on erittäin nopeaa, tätä lähestymistapaa käytetään usein itsepurkavien ohjelmien luomiseen.
- Jokaisesta pakattavasta merkkijonosta kerätään tilastot sen esiintymisestä koodatussa datassa kerran tai kullakin ajanhetkellä. Näiden tilastojen perusteella lasketaan seuraavan koodatun merkin (tai merkkijonon) arvon todennäköisyys. Sitten käytetään jonkinlaista entropiakoodausta , kuten aritmeettista koodausta tai Huffman-koodausta , edustamaan usein esiintyviä sekvenssejä lyhyissä koodisanoissa ja harvoin esiintyviä pidemmissä koodisanoissa.
Katso myös
- Arkisto (tietokonetiede)
- Luettelo algoritmeista
- Entropiakoodaus
- Tiedon teoria
- Todennäköisyysteoria
- Tilastot
Kirjallisuus
- D. Vatolin, A. Ratushnyak, M. Smirnov, V. Yukin. Tietojen pakkausmenetelmät. Arkistointien järjestely, kuvan ja videon pakkaus. - Dialogue-MEPhI, 2002. - S. 384. - ISBN 5-86404-170-X . 3000 kappaletta
- D. Salomon. Tietojen, kuvien ja äänen pakkaus. - M .: Technosfera, 2004. - S. 368. - ISBN 5-94836-027-X . 3000 kappaletta
Linkit
| Puristusmenetelmät _ | |||||||
|---|---|---|---|---|---|---|---|
| Teoria |
| ||||||
| Häviötön |
| ||||||
| Audio |
| ||||||
| Kuvat |
| ||||||
| Video |
| ||||||