Codificación de entropía

En teoría de la información , una codificación de entropía (o codificación de entropía ) es cualquier método de compresión de datos sin pérdidas que intenta aproximarse al límite inferior declarado por el teorema de codificación de fuente de Shannon , que establece que cualquier método de compresión de datos sin pérdidas debe tener una longitud de código esperada mayor o igual que la entropía de la fuente. ^{[ 1 ] [ 2 ]}

Más precisamente, el teorema de codificación de fuente establece que para cualquier distribución de fuente, la longitud de código esperada satisface${\displaystyle \operatorname {E} _{x\sim P}[\ell (d(x))]\geq \operatorname {E} _{x\sim P}[-\log _{b}(P(x))]}$, dónde${\displaystyle \ell }$es la función que especifica el número de símbolos en una palabra clave,${\displaystyle d}$es la función de codificación,${\displaystyle b}$es el número de símbolos utilizados para generar códigos de salida y${\displaystyle P}$es la probabilidad del símbolo fuente. Una codificación de entropía intenta aproximarse a este límite inferior. ^{[ 2 ] [ 3 ]}

Dos de las técnicas de codificación de entropía más comunes son la codificación de Huffman y la codificación aritmética . ^{[ 4 ] [ 5 ]} Si se conocen de antemano las características aproximadas de entropía de un flujo de datos (especialmente para la compresión de señales ), puede ser útil un código estático más simple. Estos códigos estáticos incluyen códigos universales (como la codificación gamma de Elias o la codificación de Fibonacci ) y códigos de Golomb (como la codificación unaria o la codificación de Rice ). ^{[ 5 ]}

Desde 2014, los compresores de datos han comenzado a utilizar la familia de técnicas de codificación de entropía de sistemas numéricos asimétricos (ANS), que permite combinar la relación de compresión de la codificación aritmética con un costo de procesamiento similar al de la codificación Huffman . ^{[ 6 ] [ 1 ]} ANS ha sido adoptado por compresores desarrollados por Facebook ( Zstandard ), Apple ( LZFSE ) y Google (Draco), entre otros. ^{[ 6 ]}

La codificación entrópica aprovecha el hecho de que algunos símbolos aparecen con mayor frecuencia que otros. Cuando las probabilidades de los símbolos son desiguales, algunos resultados son más predecibles, y esta predictibilidad puede utilizarse para representar los datos con menos bits. Por el contrario, cuando todos los símbolos tienen la misma probabilidad, cada símbolo contiene la máxima cantidad de información posible y no es posible la compresión. ^{[ 3 ] [ 2 ]}

Cuando la compresión no es posible: Una secuencia de lanzamientos de monedas independientes y justas, donde cara y cruz ocurren con una probabilidad de 0,5 cada una, tiene una entropía de 1 bit por símbolo, exactamente el costo de almacenar un dígito binario. Dado que cada símbolo ya ocupa el mínimo espacio posible, no hay redundancia que aprovechar, y ningún método de codificación de entropía puede reducir aún más el tamaño promedio de los datos. El mismo principio se aplica a alfabetos más grandes: los símbolos ternarios independientes (0, 1, 2), cada uno con una probabilidad de 1/3, tienen una entropía de aproximadamente 1,585 bits por símbolo, el máximo para un alfabeto de tres símbolos, y son igualmente incompresibles. ^{[ 3 ] [ 2 ]}

Cuando es posible la compresión: si la misma fuente binaria produce unos con una probabilidad de 0,9 y ceros con una probabilidad de 0,1, la entropía se reduce a aproximadamente 0,469 bits por símbolo. Esto está muy por debajo del coste de almacenamiento de 1 bit, porque la predominancia de los unos hace que cada símbolo sea parcialmente predecible. Un codificador de entropía, como la codificación aritmética, puede aprovechar esta previsibilidad para lograr una relación de compresión de aproximadamente 2,1:1 asignando códigos más cortos al símbolo más común. ^{[ 3 ] [ 5 ]}

Ejemplo práctico: El texto en inglés tiene un alfabeto de aproximadamente 27 caracteres (26 letras más un espacio). Si todos los caracteres aparecieran con la misma frecuencia, cada uno requeriría unos 4,75 bits. Sin embargo, debido a que las frecuencias de las letras son muy desiguales (la 'e' aparece mucho más a menudo que la 'z') y las letras no son independientes (la 'u' casi siempre sigue a la 'q'), la entropía real del inglés se ha estimado en aproximadamente 1,0 a 1,5 bits por carácter. Esta gran diferencia es lo que hace que el texto en inglés sea altamente compresible. ^{[ 7 ] [ 3 ]}

Además de utilizar la codificación de entropía para comprimir datos digitales, un codificador de entropía también puede emplearse para medir la similitud entre flujos de datos y clases de datos ya existentes. Esto se logra generando un codificador/compresor de entropía para cada clase de datos; los datos desconocidos se clasifican introduciendo los datos sin comprimir en cada compresor y observando cuál ofrece la mayor compresión. El codificador con la mejor compresión es probablemente el que se entrenó con los datos más similares a los datos desconocidos. ^{[ 8 ]} Este enfoque se basa en el concepto de distancia de compresión normalizada , una métrica de similitud universal y sin parámetros, basada en la compresión, que se aproxima a la distancia de información normalizada , que no se puede calcular . ^{[ 8 ] [ 9 ]}

• Codificación aritmética
• Sistemas numéricos asimétricos (SNA)
• Codificación aritmética binaria adaptativa al contexto (CABAC)
• Codificación de Huffman
• Distancia de compresión normalizada
• Codificación de rango
• Teorema de codificación de fuente

• El libro "Teoría de la información, inferencia y algoritmos de aprendizaje" , de David MacKay (2003), ofrece una introducción a la teoría de Shannon y la compresión de datos, incluyendo la codificación de Huffman y la codificación aritmética .
• Codificación de código fuente , por T. Wiegand y H. Schwarz (2011).