Compresión dinámica de Markov

Un codificador aritmético bit a bit como DMC tiene dos componentes: un predictor y un codificador aritmético. El predictor acepta una cadena de entrada de n bits x = x ₁ x ₂ ... x _n y le asigna una probabilidad p ( x ), expresada como el producto de una serie de predicciones, p ( x ₁ ) p ( x ₂ | x ₁ ) p ( x ₃ | x ₁ x ₂ ) ... p ( x _n | x ₁ x ₂ ... x _{n – 1} ). El codificador aritmético mantiene dos números binarios de alta precisión, p _low y p _high , que representan el rango posible para la probabilidad total que el modelo asignaría a todas las cadenas lexicográficamente menores que x , dados los bits de x vistos hasta el momento. El código comprimido para x es p _x , la cadena de bits más corta que representa un número entre p _low y p _high . Siempre es posible encontrar un número en este rango que no sea más de un bit más largo que el límite de Shannon , log ₂  1 / p ( x ). Uno de esos números se puede obtener a partir de p _alto descartando todos los bits finales después del primer bit que difiere de p _bajo .

La compresión procede de la siguiente manera. El rango inicial se establece en p _bajo = 0, p _alto = 1. Para cada bit, el predictor estima p ₀ = p ( x _i = 0 | x ₁ x ₂ ... x _{i – 1} ) y p ₁ = 1 − p ₀ , la probabilidad de un 0 o un 1, respectivamente. El codificador aritmético divide entonces el rango actual, ( p _bajo , p _alto ) en dos partes en proporción a p ₀ y p ₁ . Entonces el subrango correspondiente al siguiente bit x _i se convierte en el nuevo rango.   

Para la descompresión, el predictor realiza una serie idéntica de predicciones, dados los bits descomprimidos hasta el momento. El codificador aritmético realiza una serie idéntica de divisiones de rango, luego selecciona el rango que contiene p _x y genera el bit x _i correspondiente a ese subrango.

En la práctica, no es necesario mantener p _bajo y p _alto en memoria con alta precisión. A medida que el rango se reduce, los bits iniciales de ambos números serán iguales y podrán mostrarse inmediatamente.

El predictor DMC es una tabla que asigna contextos (a nivel de bits) a un par de recuentos, _n₀ y n₁ , que representan _{la cantidad de ceros y unos observados previamente en ese contexto. Así} , predice que el siguiente bit será un 0 con probabilidad _p₀ = n₀ / n = n₀ _/ ( n₀ + n₁ ) y _{un 1} con probabilidad p₁ = 1 ₋ p₀ = n₁ _/ n . Además, cada entrada de _{la tabla tiene un par de punteros a los contextos obtenidos al agregar un 0 o un 1 a la derecha del contexto actual (y posiblemente descartar bits a la izquierda).} Por lo tanto, nunca es necesario consultar el contexto actual en la tabla; basta con mantener un puntero al contexto actual y seguir los enlaces.    

En la implementación original de DMC, la tabla inicial es el conjunto de todos los contextos de longitud entre 8 y 15 bits que comienzan en un límite de byte. El estado inicial es cualquiera de los contextos de 8 bits. Los contadores son números de punto flotante inicializados con una pequeña constante distinta de cero, como 0,2. Los contadores no se inicializan a cero para permitir que se codifiquen valores incluso si no se han visto antes en el contexto actual.

El modelado es el mismo para la compresión y la descompresión. Para cada bit, se calculan p ₀ y p _{1 , el bit} x _i se codifica o decodifica, el modelo se actualiza sumando 1 al contador correspondiente a x _i , y el siguiente contexto se encuentra recorriendo el enlace correspondiente a x _i .

DMC, como se describió anteriormente, es equivalente a un modelo de contexto de orden 1. Sin embargo, es común agregar contextos más largos para mejorar la compresión. Si el contexto actual es A, y el siguiente contexto B descarta bits a la izquierda, entonces DMC puede agregar (clonar) un nuevo contexto C a partir de B. C representa el mismo contexto que A después de agregar un bit a la derecha como con B, pero sin descartar ningún bit a la izquierda. El enlace de A se moverá de B para apuntar a C. Tanto B como C harán la misma predicción, y ambos apuntarán al mismo par de estados siguientes. El recuento total, n = n ₀  + n ₁ para C será igual al recuento n _x para A (para el bit de entrada x ), y ese recuento se restará de B.  

Por ejemplo, supongamos que el estado A representa el contexto 11111. Al ingresar el bit 0, se produce una transición al estado B, que representa el contexto 110, obtenido al descartar 3 bits a la izquierda. En el contexto A, había 4 bits cero y algunos bits uno. En el contexto B, había 3 ceros y 7 unos ( n  =  10), lo que predice p ₁ = 0,7.

C se clona a partir de B. Representa el contexto 111110. Tanto B como C predicen p ₁ = 0,7, y ambos van a los mismos estados siguientes, E y F. El recuento para C es n = 4, igual a n ₀ para A. Esto deja n = 6 para B.

Los estados se clonan justo antes de la transición. En el DMC original, la condición para clonar un estado es que la transición de A a B sea al menos 2, y el conteo para B sea al menos 2 más que eso. (Cuando el segundo umbral es mayor que 0, garantiza que otros estados seguirán transicionando a B después de la clonación). Algunas implementaciones, como hook, permiten establecer estos umbrales como parámetros. En paq8l, estos umbrales aumentan a medida que se usa la memoria para ralentizar la tasa de crecimiento de nuevos estados. En la mayoría de las implementaciones, cuando se agota la memoria, el modelo se descarta y se reinicializa al modelo original de orden 1 bytewise.