Codificación de entropía

Este artículo incluye una lista de referencias , lecturas relacionadas o enlaces externos , pero sus fuentes siguen sin estar claras porque carece de citas en línea . Ayude a mejorar este artículo introduciendo citas más precisas. ( Diciembre de 2013 ) ( Obtenga información sobre cómo y cuándo eliminar este mensaje de plantilla )

En la teoría de la información, una codificación de entropía es un esquema de compresión de datos sin pérdidas que es independiente de las características específicas del medio.

Uno de los principales tipos de codificación de entropía crea y asigna un código único sin prefijo a cada símbolo único que aparece en la entrada. ^[1] Estos codificadores de entropía luego comprimen los datos reemplazando cada símbolo de entrada de longitud fija con la correspondiente palabra de código de salida sin prefijo de longitud variable. La longitud de cada palabra de código es aproximadamente proporcional al logaritmo negativo de la probabilidad de aparición de esa palabra de código. Por lo tanto, los símbolos más comunes utilizan los códigos más cortos. ^[2]

De acuerdo con el teorema de codificación de fuente de Shannon , la longitud de código óptima para un símbolo es , donde es el número de símbolos utilizados para hacer códigos de salida y es la probabilidad del símbolo de entrada.${\displaystyle -log_{b}(P)}$${\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 . ^[3] 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 ser útil. Estos códigos estáticos incluyen códigos universales (como la codificación gamma de Elias o la codificación de Fibonacci ) y los 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 Asymmetric Numeral Systems , 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 usar la codificación de entropía como una forma de comprimir datos digitales, también se puede usar 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 compresión más alta. El codificador con la mejor compresión es probablemente el codificador entrenado en los datos que eran más similares a los datos desconocidos.

Ver también

• Codificación aritmética
• Sistemas numéricos asimétricos
• Codificación CABAC
• Codificación de Huffman
• Codificación de rango

Referencias

1. "Educación - codificación de entropía" . www.pcs-ip.eu . Consultado el 13 de octubre de 2020 .
2. "¿Qué es la codificación de entropía | IGI Global" . www.igi-global.com . Consultado el 13 de octubre de 2020 .
3. Huffman, David (1952). "Un método para la construcción de códigos de redundancia mínima". Actas de la IRE . Instituto de Ingenieros Eléctricos y Electrónicos (IEEE). 40 (9): 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 de fuentes , por T. Wiegand y H. Schwarz (2011).