Shannonin algoritmi

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 16. huhtikuuta 2018 tarkistetusta versiosta . tarkastukset vaativat 3 muokkausta .

Tietojen pakkaamisen alalla Shannon-koodi , joka on nimetty sen luojan Claude Shannonin mukaan, on häviötön tietojen pakkausalgoritmi , joka muodostaa etuliitekoodeja, jotka perustuvat merkkijoukkoon ja niiden todennäköisyyksiin (laskettu tai mitattu). Se ei ole optimaalinen siinä mielessä, että se ei saavuta pienintä mahdollista koodin pituutta, kuten Huffman-koodauksessa , eikä se ole koskaan parempi, mutta joskus sama kuin Shannon-Fano- koodi .

Tämä menetelmä oli ensimmäinen laatuaan, tätä tekniikkaa käytettiin todistamaan Shannonin virheenkorjaava koodauslause vuonna 1948 hänen artikkelissaan "Mathematical Communication Theory" [1] .

Shannon-koodauksessa merkit on järjestetty todennäköisimmästä epätodennäköisimpään. Heille annetaan koodit ottamalla kumulatiivisen todennäköisyyden binäärihajotelman ensimmäiset numerot . Tässä tarkoittaa funktion kattoa , joka pyöristyy lähimpään kokonaisarvoon, joka on suurempi tai yhtä suuri kuin . $l_{i}=\left\lceil -\log _{2}p_{i}\right\rceil$ ${\displaystyle \sum \limits _{k=1}^{i-1}p_{k))$ $\left\lceil x\right\rceil$ $x$ $x$

Esimerkki

Tässä taulukossa on esimerkki Shannon-koodauksesta. Voit heti huomata lopullisista koodeista, että se on vähemmän optimaalinen kuin Fano-Shannon -menetelmä .

Ensimmäinen askel on laskea kunkin symbolin todennäköisyydet. Sitten lasketaan kunkin todennäköisyyden luku. Esimerkiksi 2 : lle se on yhtä kuin kolme ( on kahden −3:n minimiteho, joten se on yhtä suuri kuin kolme). Tämän jälkeen otetaan huomioon todennäköisyyksien summa 0 :sta i-1 :een ja muunnetaan binäärimuotoon. Sitten murto-osa katkaistaan vasemmalla merkkien lukumäärään. $l$ ${\displaystyle 2^{-3}\leq 0,18\leq 2^{-2))$ $l$ $l_{i}$

a i	p(a i )	l i	Summa 0 - i-1	Summa yli p(a i ) bin	Lopullinen koodi
a 1	0,36	2	0,0	0.0000	00
a 2	0,18	3	0,36	0,0101	010
a 3	0,18	3	0,54	0,1000	100
a 4	0.12	neljä	0,72	0,1011	1011
a 5	0.09	neljä	0,84	0,1101	1101
a 6	0,07	neljä	0,93	0,1110	1110

Linkit

↑ "A Mathematical Theory of Communication" http://cm.bell-labs.com/cm/ms/what/shannonday/shannon1948.pdf Arkistoitu 15. heinäkuuta 1998 Wayback Machinessa

Puristusmenetelmät _

Teoria

Tiedot	Oma Keskinäinen Haje Ehdollinen entropia Monimutkaisuus Redundanssi
Yksiköt	Bitti Nat Napostella Hartley Hartleyn kaava

Häviötön

Entropian pakkaus	Epäsymmetriset lukujärjestelmät Huffmanin algoritmi Mukautuva Huffman-algoritmi Shannon-Fano-algoritmi Shannonin algoritmi Aritmeettinen koodaus ( intervalli ) Golomb koodit Delta Universaali koodi Elias fibonacci
Sanakirjamenetelmät	RLE Tyhjennä LZ ( LZ77/LZ78 LZSS LZW LZWL LZO LZMA LZX LZRW LZJB LZT LZ4 Brotli zstandardi )
Muut	RLE CTW BWT MTF PPM DMC

Audio

Teoria	Convolution PCM Aliasing Näytteenotto Kotelnikovin lause
menetelmät	LPC LAR LSP WLPC CELP ACELP Laki μ-laki ADPCM MDCT Fourier-muunnos Psykoakustinen malli
Muut	Äänen kompressori Puheen pakkaus Band koodaus

Kuvat

Ehdot	väriavaruutta Pikseli Saturaatio-alinäytteenotto Pakkausesineet
menetelmät	RLE DPCM fraktaali aallokko EZW SPIHT LP PrEP PCL
Muut	Bittinopeus Normaali testikuva PSNR Kvantisointi

Video

Ehdot	Videon ominaisuudet Kehys Kehystyypit Videon laatu
menetelmät	Liikekompensointi PrEP Kvantisointi aallokko
Muut	Videokoodekki Nopeuden vääristymisteoria CBR ABR VBR