Algoritmo de Shannon

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 16 de abril de 2018; las comprobaciones requieren 3 ediciones .

En el campo de la compresión de datos , el código Shannon , llamado así por su creador, Claude Shannon , es un algoritmo de compresión de datos sin pérdidas mediante la construcción de códigos de prefijos basados en un conjunto de caracteres y sus probabilidades (calculadas o medidas). Es subóptimo en el sentido de que no logra las longitudes de código más pequeñas posibles como en la codificación Huffman , y nunca será mejor, pero a veces será igual al código Shannon-Fano .

Este método fue el primero de su tipo, esta técnica se utilizó para probar el teorema de codificación de corrección de errores de Shannon en 1948 en su artículo "Teoría de la comunicación matemática" [1] .

En la codificación de Shannon, los caracteres se ordenan de más probable a menos probable. Se les asignan códigos tomando los primeros dígitos de la descomposición binaria de la probabilidad acumulada . Aquí denota el techo de la función , que se redondea al valor entero más cercano mayor o igual que . $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$

Ejemplo

Esta tabla muestra un ejemplo de codificación Shannon. Puede notar inmediatamente a partir de los códigos finales que es menos óptimo que el método Fano-Shannon .

El primer paso es calcular las probabilidades de cada símbolo. Luego se calcula el número para cada probabilidad. Por ejemplo, para un 2 es igual a tres ( es la mínima potencia de dos −3, por lo tanto es igual a tres). Después de eso, se considera la suma de probabilidades de 0 a i-1 y se convierte a forma binaria. Luego, la parte fraccionaria se trunca a la izquierda al número de caracteres. $yo$ ${\displaystyle 2^{-3}\leq 0.18\leq 2^{-2))$ $yo$ $l_{yo}$

un yo	p(a yo )	yo _	Suma 0 a i-1	Suma sobre p(a i ) bin	Código definitivo
un 1	0.36	2	0.0	0.0000	00
un 2	0.18	3	0.36	0.0101	010
un 3	0.18	3	0.54	0.1000	100
un 4	0.12	cuatro	0.72	0.1011	1011
un 5	0.09	cuatro	0.84	0.1101	1101
un 6	0.07	cuatro	0.93	0.1110	1110

Enlaces

↑ "Una teoría matemática de la comunicación" http://cm.bell-labs.com/cm/ms/what/shannonday/shannon1948.pdf Archivado el 15 de julio de 1998 en Wayback Machine .

métodos de compresión

Teoría

Información	Propio Mutual entropía Entropía condicional Complejidad Redundancia
Unidades	Un poco natural Picar Hartley Fórmula Hartley

sin pérdidas

Compresión de entropía	Sistemas numéricos asimétricos Algoritmo de Huffman Algoritmo de Huffman adaptativo Algoritmo de Shannon-Fano Algoritmo de Shannon Codificación aritmética ( intervalo ) Códigos Golomb Delta código universal Elías fibonacci
Métodos de diccionario	RLE Desinflar LZ ( LZ77/LZ78 LZSS LZW LZWL LZO LZMA LZX LZRW LZJB LZT LZ4 Brotli zestándar )
Otro	RLE CTW BWT MTF ppm DMC

Audio

Teoría	Circunvolución PCM alias Muestreo Teorema de Kotelnikov
Métodos	LPC LAR LSP WLPC CELP ACELP Una ley ley μ ADPCM MDCT Transformada de Fourier modelo psicoacústico
Otro	Compresor de sonido Compresión de voz Codificación de banda

Imágenes

Términos	espacio de color píxel Submuestreo de saturación Artefactos de compresión
Métodos	RLE DPCM fractales ondícula EZW ALCOHOL LP Deberes PCL
Otro	tasa de bits Imagen de prueba estándar PSNR cuantización

Video

Términos	Características del vídeo Cuadro Tipos de cuadros Calidad de video
Métodos	Compensación de movimiento Deberes cuantización ondícula
Otro	Códec de vídeo Tasa de teoría de la distorsión CBR ABR VBR