Häviötön pakkaus

Häviötön tiedonpakkaus on datapakkausalgoritmien  luokka (video, ääni, grafiikka, digitaalisessa muodossa esitetyt asiakirjat, ohjelmointikielillä ja konekoodeilla olevat ohjelmat ja monet muut datatyypit), joita käyttämällä koodattu data voidaan rekonstruoida yksiselitteisesti lähimpään bittiin , pikseliin , vokseliin jne. Tässä tapauksessa alkuperäiset tiedot palautetaan kokonaan pakatusta tilasta. Tämäntyyppinen pakkaus eroaa pohjimmiltaan häviöisestä tietojen pakkaamisesta . Jokaiselle digitaaliselle informaatiotyypille on yleensä optimaaliset häviöttömät pakkausalgoritmit.

Häviötöntä tietojen pakkausta käytetään monissa sovelluksissa. Sitä käytetään esimerkiksi kaikissa tiedostoarkistoissa . Sitä käytetään myös komponenttina häviöisessä pakkauksessa.

Häviötöntä pakkausta käytetään, kun pakatun tiedon identiteetti alkuperäiseen on tärkeää. Yleinen esimerkki ovat suoritettavat tiedostot ja lähdekoodi. Jotkut grafiikkatiedostomuodot (kuten PNG ) käyttävät vain häviötöntä pakkausta, kun taas toiset ( TIFF , FLIF tai GIF ) voivat käyttää sekä häviöllistä että häviötöntä pakkausta.

Pakkaus ja kombinatoriikka

Lause on helppo todistaa.

Jos N > 0, ei ole häviötöntä pakkausalgoritmia, joka:

  1. Mikä tahansa tiedosto, joka on enintään N tavua, joko säilyttää saman pituuden tai pienentää sitä.
  2. Pienentää tiettyä tiedostoa, jonka pituus on enintään N , vähintään yhdellä tavulla.

Todiste. Yleisyyttä menettämättä voidaan olettaa, että tiedosto A , jonka pituus on täsmälleen N , on pienentynyt . Merkitään aakkoset muodossa . Harkitsemme sarjaa . Tässä lähdetiedostojoukossa, vaikka niitä ei ole enempää kuin . Siksidekompressiofunktio on epäselvä , ristiriita . Lause on todistettu.

Tämä lause ei kuitenkaan varjoa häviötöntä pakkausta. Tosiasia on, että mitä tahansa pakkausalgoritmia voidaan muokata niin, että se lisää kokoa enintään 1 bitillä: jos algoritmi on pienentänyt tiedostoa, kirjoitamme "1", sitten pakattu sekvenssi, jos se on kasvanut, kirjoitamme " 0”, sitten alkuperäinen.

Joten kokoonpuristumattomat fragmentit eivät johda arkiston hallitsemattomaan "turvotukseen". "Oikeat" tiedostot, joiden pituus on N , ovat paljon pienempiä kuin (he sanovat, että tiedoilla on alhainen informaatioentropia ) - esimerkiksi on epätodennäköistä, että kirjainyhdistelmä "ujo" esiintyisi merkityksellisessä tekstissä, ja digitoidussa äänessä taso ei voi hypätä 0:sta 100 prosenttiin. Lisäksi tietyntyyppisten tietojen (teksti, grafiikka, ääni jne.) algoritmien erikoistumisesta johtuen on mahdollista saavuttaa korkea pakkaus: esimerkiksi arkistoissa käytetyt yleisalgoritmit pakkaavat ääntä noin kolmas (1,5 kertaa), kun taas FLAC  on 2,5 kertaa. Useimmista erikoisalgoritmeista ei ole juurikaan hyötyä "vieraille" tiedostotyypeille: esimerkiksi tekstille suunniteltu algoritmi pakkaa audiodataa huonosti.

Häviötön pakkausmenetelmä

Yleisesti ottaen häviöttömän pakkaamisen merkitys on seuraava: alkuperäisestä tiedosta löytyy jokin kuvio ja tämä kuvio huomioon ottaen generoidaan toinen sekvenssi, joka kuvaa täysin alkuperäistä. Esimerkiksi koodataksemme binäärisekvenssejä, joissa on useita nollia ja vähän ykkösiä, voimme käyttää seuraavaa korvausta:

00 → 0 01 → 10 10 → 110 11 → 111

Tässä tapauksessa kuusitoista bittiä

00 01 00 00 11 10 00 00

muunnetaan kolmetoista bitiksi

0 10 0 0 111 110 0 0

Tällainen korvaus on etuliitekoodi , eli sillä on seuraava ominaisuus: jos kirjoitamme pakatun merkkijonon ilman välilyöntejä, voimme silti laittaa siihen välilyöntejä - ja siten palauttaa alkuperäisen sekvenssin. Tunnetuin etuliitekoodi on Huffman-koodi .

Useimmat häviöttömät pakkausalgoritmit toimivat kahdessa vaiheessa: ensimmäinen luo tilastollisen mallin saapuville tiedoille, toinen bittikartoittaa saapuvat tiedot käyttämällä mallia "todennäköisyyspohjaisen" (eli usein esiintyvän) datan tuottamiseen, jota käytetään useammin kuin "epätodennäköistä" dataa..

Tilastolliset algoritmimallit tekstille (tai tekstipohjaiselle binääritiedolle, kuten suoritettaville tiedostoille) sisältävät:

Koodausalgoritmit luomalla bittijaksoja:

Häviöttömät pakkausmenetelmät

Katso täydellinen luettelo kohdasta Luokka:Tietojen pakkaus

Monikäyttöinen

Äänen pakkaus

Grafiikkapakkaus

Videon pakkaus

Tekstin pakkaus

Esimerkkejä algoritmeista

Esimerkkejä formaateista ja niiden toteutuksista

Katso myös

Muistiinpanot

  1. ↑ TIFF v6 -spesifikaatio (downlink) . Käyttöpäivä: 18. joulukuuta 2010. Arkistoitu alkuperäisestä 3. heinäkuuta 2012. 

Linkit

 Puristusmenetelmät _
Teoria
Tiedot
Yksiköt
Häviötön
Entropian pakkaus
Sanakirjamenetelmät
muu
Audio
Teoria
menetelmät
muu
Kuvat
Ehdot
menetelmät
muu
Video
Ehdot
menetelmät
muu