Codificación aritmética
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 12 de marzo de 2013; las comprobaciones requieren 30 ediciones .La codificación aritmética es uno de los algoritmos de compresión de entropía .
A diferencia del algoritmo de Huffman , no tiene una correspondencia dura y constante entre los caracteres de entrada y los grupos de bits en el flujo de salida. Esto le da al algoritmo más flexibilidad para representar frecuencias de caracteres fraccionarios.
Por regla general, supera al algoritmo de Huffman en términos de eficiencia de compresión, le permite comprimir datos con una entropía inferior a 1 bit por carácter codificado, pero algunas versiones tienen restricciones de patente de IBM . [una]
Características
Proporciona una relación de compresión casi óptima en términos de estimación de entropía de codificación de Shannon. Se requiere casi un bit para cada símbolo, donde está la entropía informativa de la fuente.
A diferencia del algoritmo de Huffman , el método de codificación aritmética muestra una alta eficiencia para intervalos fraccionarios no uniformes de la distribución de probabilidad de los símbolos codificados. Sin embargo, en el caso de una distribución equiprobable de caracteres, por ejemplo, para una cadena de bits 010101…0101 de longitud s , el método de codificación aritmética se aproxima al código de prefijo Huffman e incluso puede tardar un bit más. [2]
Cómo funciona
Que haya un cierto alfabeto, así como datos sobre la frecuencia de uso de los caracteres (opcional). Luego considere el segmento de línea de 0 a 1 en la línea de coordenadas.
Llamemos a este segmento trabajando. Dispongamos los puntos en él de tal manera que las longitudes de los segmentos formados sean iguales a la frecuencia de uso del símbolo, y cada uno de esos segmentos corresponderá a un símbolo.
Ahora tomemos un símbolo de la secuencia y busquemos un segmento para él entre los recién formados, ahora el segmento para este símbolo ha comenzado a funcionar. Dividámoslo de la misma manera que dividimos el segmento de 0 a 1. Realicemos esta operación para una cierta cantidad de caracteres consecutivos. Luego elegimos cualquier número del segmento de trabajo. Los bits de este número, junto con la longitud de su registro de bits, son el resultado de la codificación aritmética de los símbolos de flujo utilizados.
Un ejemplo de cómo funciona el método de codificación aritmética
Modelo probabilístico
Usando el método de codificación aritmética, se puede lograr una representación casi óptima para un conjunto dado de símbolos y sus probabilidades (de acuerdo con la teoría de codificación de entropía fuente de Shannon, la representación óptima tenderá a ser −log 2 P bits por símbolo cuya probabilidad es P ). Los algoritmos de compresión de datos que utilizan el método de codificación aritmética en su trabajo, antes de la codificación directa, forman un modelo de datos de entrada basado en características cuantitativas o estadísticas, así como cualquier información adicional que se encuentre en la secuencia codificada de repeticiones o patrones -cualquier información adicional que permita para aclarar la probabilidad de aparición del símbolo P en el proceso de codificación. Obviamente, cuanto más exactamente se determine o prediga la probabilidad del símbolo, mayor será la eficiencia de compresión.
Considere el caso más simple de un modelo estático para codificar información proveniente de un sistema de procesamiento de señales. Los tipos de señales y sus correspondientes probabilidades se distribuyen de la siguiente manera:
- 60% de probabilidad de un valor de señal neutral o NEUTRO.
- 20% de probabilidad de un valor de señal positivo, o POSITIVO.
- 10% de probabilidad de un valor de señal negativo o NEGATIVO.
- 10% de probabilidad de una señal de fin de secuencia o FIN DE DATOS.
La aparición del último símbolo para el decodificador significa que toda la secuencia se ha decodificado con éxito (como enfoque alternativo, pero no necesariamente con más éxito, se puede utilizar un algoritmo de bloque de longitud fija) .
También cabe señalar que cualquier conjunto de símbolos puede ser considerado como el alfabeto del modelo probabilístico del método, en función de las características del problema a resolver. Los enfoques más heurísticos , utilizando el esquema básico del método de codificación aritmética, aplican modelos dinámicos o adaptativos . La idea de estos métodos es refinar la probabilidad del carácter codificado teniendo en cuenta la probabilidad del contexto anterior o futuro (es decir, la probabilidad de que ocurra el carácter codificado después de un cierto número k-ésimo de caracteres a la izquierda o a la derecha, donde k es el orden del contexto).
Codificación de mensajes
Tomemos como ejemplo la siguiente secuencia:
FIN DE DATOS NEUTRO NEGATIVO
Primero, dividamos el segmento de 0 a 1 según las frecuencias de las señales. Partiremos el segmento en el orden indicado arriba: NEUTRO - de 0 a 0,6; NEGATIVO - de 0,6 a 0,8; FIN DE DATOS - de 0,8 a 1.
Ahora comencemos a codificar desde el primer carácter. El primer carácter - NEUTRO corresponde a un segmento de 0 a 0,6. Dividamos este segmento de la misma manera que el segmento de 0 a 1.
Codifiquemos el segundo carácter - NEGATIVO. En el segmento de 0 a 0,6, corresponde al segmento de 0,48 a 0,54. Dividamos este segmento de la misma manera que el segmento de 0 a 1.
Codifiquemos el tercer carácter: FIN DE DATOS. En el segmento de 0,48 a 0,54, corresponde al segmento de 0,534 a 0,54.
Dado que este fue el último carácter, la codificación está completa. El mensaje codificado es un segmento de 0,534 a 0,54 o cualquier número del mismo, por ejemplo, 0,538.
Decodificación de mensajes
Supongamos que necesitamos decodificar un mensaje utilizando el método de codificación aritmética según el modelo descrito anteriormente. El mensaje codificado está representado por el valor fraccionario 0,538 (por simplicidad, se utiliza la representación decimal de la fracción en lugar de la base binaria). Se supone que el mensaje codificado contiene exactamente tantos caracteres en el número considerado como sea necesario para restaurar de forma única los datos originales.
El estado inicial del proceso de decodificación coincide con el proceso de codificación y se considera el intervalo [0,1). Basado en el modelo probabilístico conocido, el valor fraccionario 0.538 cae dentro del intervalo [0, 0.6). Esto le permite determinar el primer carácter que eligió el codificador, por lo que su valor se emite como el primer carácter del mensaje decodificado.
Notas
- ↑ La historia del desarrollo de la teoría de la compresión de la información Copia de archivo del 28 de diciembre de 2010 en Wayback Machine / Compression.ru, Sarmin Alexey, 10 de marzo de 2011
- ↑ Dra. Boletín de compresión de datos de Dobb Archivado el 11 de diciembre de 2017 en Wayback Machine , 13 de agosto de 2001
Enlaces
| métodos de compresión | |||||||
|---|---|---|---|---|---|---|---|
| Teoría |
| ||||||
| sin pérdidas |
| ||||||
| Audio |
| ||||||
| Imágenes |
| ||||||
| Video |
| ||||||