Algoritmul lui Shannon

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 16 aprilie 2018; verificările necesită 3 modificări .

În domeniul compresiei datelor , codul Shannon , numit după creatorul său, Claude Shannon , este un algoritm de compresie a datelor fără pierderi , prin construirea de coduri de prefix pe baza unui set de caractere și a probabilităților acestora (calculate sau măsurate). Este suboptim în sensul că nu atinge cele mai mici lungimi posibile de cod ca în codarea Huffman și nu va fi niciodată mai bună, dar uneori egală cu codul Shannon-Fano .

Această metodă a fost prima de acest gen, această tehnică a fost folosită pentru a demonstra teorema de codare a lui Shannon de corectare a erorilor în 1948 în lucrarea sa „Teoria comunicării matematice” [1] .

În codarea Shannon, caracterele sunt ordonate de la cel mai probabil la cel mai puțin probabil. Li se atribuie coduri prin preluarea primelor cifre din descompunerea binară a probabilității cumulate . Aici desemnează plafonul funcției , care se rotunjește la cea mai apropiată valoare întreagă mai mare sau egală cu . $l_{i}=\left\lceil -\log _{2}p_{i}\right\rceil$ $\sum \limits _{k=1}^{i-1}p_{k)$ $\left\lceil x\right\rceil$ $X$ $X$

Exemplu

Acest tabel prezintă un exemplu de codificare Shannon. Puteți observa imediat din codurile finale că este mai puțin optim decât metoda Fano-Shannon .

Primul pas este de a calcula probabilitățile fiecărui simbol. Apoi se calculează numărul pentru fiecare probabilitate. De exemplu, pentru un 2 este egal cu trei ( este puterea minimă a doi -3, prin urmare este egal cu trei). După aceea, suma probabilităților de la 0 la i-1 este considerată și convertită în formă binară. Apoi partea fracțională este trunchiată în stânga la numărul de caractere. $l$ $2^{-3}\leq 0,18\leq 2^{-2)$ $l$ $l_{i}$

un i	p(a i )	eu _	Suma 0 la i-1	Suma peste p(a i ) bin	Cod final
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	patru	0,72	0,1011	1011
un 5	0,09	patru	0,84	0,1101	1101
a 6	0,07	patru	0,93	0,1110	1110

Link -uri

↑ „A Mathematical Theory of Communication” http://cm.bell-labs.com/cm/ms/what/shannonday/shannon1948.pdf Arhivat la 15 iulie 1998 la Wayback Machine

Metode de compresie

Teorie

informație	propriu Reciproc Entropie Entropia condiționată Complexitate Redundanţă
Unități	Pic Nat Ciuguli Hartley Formula Hartley

Fara pierderi

Compresie entropică	Sisteme numerice asimetrice Algoritmul Huffman Algoritmul adaptiv Huffman Algoritmul Shannon-Fano algoritmul lui Shannon Codare aritmetică ( Interval ) Codurile Golomb Delta Cod universal Elias Fibonacci
Dicţionar Methods	RLE Dezumfla LZ ( LZ77/LZ78 LZSS LZW LZWL LZO LZMA LZX LZRW LZJB LZT LZ4 Brotli zstandard )
Alte	RLE CTW BWT MTF PPM DMC

Audio

Teorie	Convoluţie PCM Alianta Prelevarea de probe teorema lui Kotelnikov
Metode	LPC LAR LSP WLPC CELP ACELP O lege μ-legea ADPCM MDCT transformata Fourier Model psihoacustic
Alte	Compresor audio Compresia vorbirii Codarea benzii

Imagini

Termeni	spațiu de culoare Pixel Subeșantionarea de saturație Artefacte de compresie
Metode	RLE DPCM fractal wavelet EZW SPIHT LP PrEP PCL
Alte	Rata de biți Imagine de testare standard PSNR Cuantizarea

Video

Termeni	Caracteristicile video Cadru Tipuri de cadre Calitate video
Metode	Compensarea mișcării PrEP Cuantizarea wavelet
Alte	Codec video Teoria distorsiunii ratei CBR ABR VBR