Codificación de entropía

Esquema de compresión de datos sin pérdidas

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 acercarse al límite inferior declarado por el teorema de codificación 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. a la entropía de la fuente. ^[1]

Más precisamente, el teorema de codificación fuente establece que para cualquier distribución fuente, la longitud esperada del código satisface , donde es el número de símbolos en una palabra código, es la función de codificación, es el número de símbolos utilizados para generar códigos de salida y es la probabilidad. del símbolo 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 entrópica 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 ), un código estático más simple puede resultar útil. 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 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 numéricos asimétricos , que permite combinar la relación de compresión de la codificación aritmética con un costo 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 más similares a los datos desconocidos.

Ver también

• Codificación aritmética
• Sistemas de numeración asimétricos (ANS)
• Codificación aritmética binaria adaptativa al contexto (CABAC)
• Codificación 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 de 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. S2CID  20260346.
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 de Huffman y la codificación aritmética .
• Codificación fuente, de T. Wiegand y H. Schwarz (2011).