Codificación de entropía

Esquema de compresión de datos sin pérdida

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érdida 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érdida debe tener una longitud de código esperada mayor o igual a la entropía de la fuente. ^[1]

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 , donde es el número de símbolos en una palabra de código, es la función de codificación, es el número de símbolos utilizados para crear códigos de salida y es la probabilidad del símbolo de fuente. Una codificación de entropía intenta acercarse a este límite inferior. ${\displaystyle \operatorname {E} _{x\sim P}[\ell (d(x))]\geq \operatorname {E} _{x\sim P}[-\log _{b}(P(x))]}$ ${\displaystyle \ell }$ ${\displaystyle d}$ ${\displaystyle b}$ ${\displaystyle P}$

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 . ^[2] Si las características de entropía aproximadas de un flujo de datos se conocen de antemano (especialmente para la compresión de señales ), puede resultar ú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 ).

Desde 2014, los compresores de datos han comenzado a utilizar la familia de técnicas de codificación de entropía de sistemas numerales asimétricos , que permite combinar la relación de compresión de la codificación aritmética con un coste de procesamiento similar a la codificación de Huffman .

La entropía como medida de similitud

Además de utilizar la codificación de entropía como una forma de comprimir datos digitales, también se puede utilizar un codificador de entropía para medir la cantidad de similitud entre flujos de datos y clases de datos ya existentes. Esto se hace generando un codificador/compresor de entropía para cada clase de datos; luego, los datos desconocidos se clasifican alimentando los datos sin comprimir a cada compresor y viendo qué compresor produce la mayor compresión. El codificador con la mejor compresión es probablemente el codificador entrenado con los datos que eran más similares a los datos desconocidos.

Véase también

• Codificación aritmética
• Sistemas de numeración asimétricos (SNA)
• Codificación aritmética binaria adaptativa al contexto (CABAC)
• Codificación de Huffman
• Codificación de rango

Referencias

1. Duda, Jarek; Tahboub, Khalid; Gadgil, Neeraj J.; Delp, Edward J. (mayo de 2015). "El uso de sistemas numéricos asimétricos como un reemplazo preciso para la codificación de Huffman". Simposio de codificación de imágenes (PCS) de 2015. págs. 65–69. doi :10.1109/PCS.2015.7170048. ISBN 978-1-4799-7783-3.S2CID20260346  .​
2. Huffman, David (1952). "Un método para la construcción de códigos de redundancia mínima". Actas del IRE . 40 (9). Instituto de Ingenieros Eléctricos y Electrónicos (IEEE): 1098–1101. doi :10.1109/jrproc.1952.273898. ISSN  0096-8390.

Enlaces externos

• 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, incluida la codificación Huffman y la codificación aritmética .
• Codificación fuente, por T. Wiegand y H. Schwarz (2011).