La compresión dinámica de Markov ( DMC ) es un algoritmo de compresión de datos sin pérdida desarrollado por Gordon Cormack y Nigel Horspool . [1] Utiliza una codificación aritmética predictiva similar a la predicción por coincidencia parcial (PPM), excepto que la entrada se predice un bit a la vez (en lugar de un byte a la vez). DMC tiene una buena relación de compresión y una velocidad moderada, similar a PPM, pero requiere algo más de memoria y no se implementa ampliamente. Algunas implementaciones recientes incluyen los programas de compresión experimental hook de Nania Francesco Antonio, ocamyd de Frank Schwellinger y como submodelo en paq8l de Matt Mahoney. Estos se basan en la implementación de 1993 en C de Gordon Cormack.
DMC predice y codifica un bit a la vez. Se diferencia de PPM en que codifica bits en lugar de bytes, y de los algoritmos de mezcla de contextos como PAQ en que solo hay un contexto por predicción. El bit predicho se codifica luego mediante codificación aritmética .
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 1 x 2 ... x n y le asigna una probabilidad p ( x ), expresada como un producto de una serie de predicciones, p ( x 1 ) p ( x 2 | x 1 ) p ( x 3 | x 1 x 2 ) ... p ( x n | x 1 x 2 ... 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 ahora. 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 2 1 / p ( x ). Uno de esos números se puede obtener a partir de p high eliminando todos los bits posteriores al primer bit que difiere de p low .
La compresión se lleva a cabo de la siguiente manera. El rango inicial se establece en p low = 0, p high = 1. Para cada bit, el predictor estima p 0 = p ( x i = 0 | x 1 x 2 ... x i –1 ) y p 1 = 1 − p 0 , la probabilidad de un 0 o un 1, respectivamente. A continuación, el codificador aritmético divide el rango actual, ( p low , p high ) en dos partes en proporción a p 0 y p 1 . A continuación, 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 la memoria para lograr una alta precisión. A medida que el rango se estrecha, los bits iniciales de ambos números serán los mismos y se podrán imprimir de inmediato.
El predictor DMC es una tabla que asigna contextos (bit a bit) a un par de conteos, n 0 y n 1 , que representan la cantidad de ceros y unos observados previamente en este contexto. Por lo tanto, predice que el siguiente bit será un 0 con probabilidad p 0 = n 0 / n = n 0 / ( n 0 + n 1 ) y 1 con probabilidad p 1 = 1 − p 0 = n 1 / 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 eliminar bits a la izquierda). Por lo tanto, nunca es necesario buscar el contexto actual en la tabla; es suficiente 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 de 8 a 15 bits que comienzan en un límite de byte. El estado inicial es cualquiera de los contextos de 8 bits. Los conteos son números de punto flotante inicializados en una pequeña constante distinta de cero, como 0,2. Los conteos no se inicializan en cero para permitir que se codifiquen los 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 0 y p 1 , se codifica o decodifica el bit x i , se actualiza el modelo sumando 1 al recuento correspondiente a x i , y se encuentra el siguiente contexto recorriendo el enlace correspondiente a x i .
El DMC descrito anteriormente es equivalente a un modelo de contexto de orden 1. Sin embargo, es normal agregar contextos más largos para mejorar la compresión. Si el contexto actual es A y el siguiente contexto B eliminaría bits de la izquierda, entonces el 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 eliminar ningún bit a la izquierda. El enlace de A se moverá de B para apuntar a C. B y C harán la misma predicción y ambos apuntarán al mismo par de estados siguientes. El recuento total, n = n 0 + n 1 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. En el bit de entrada 0, se pasa al estado B que representa el contexto 110, obtenido al eliminar 3 bits de la izquierda. En el contexto A, ha habido 4 bits cero y una cierta cantidad de bits uno. En el contexto B, ha habido 3 ceros y 7 unos ( n = 10), lo que predice p 1 = 0,7.
C se clona de B. Representa el contexto 111110. Tanto B como C predicen p 1 = 0,7 y ambos pasan a los mismos estados siguientes, E y F. El recuento para C es n = 4, igual a n 0 para A. Esto deja n = 6 para B.
Los estados se clonan justo antes de realizar la transición a ellos. En el DMC original, la condición para clonar un estado es cuando la transición de A a B es al menos 2, y el recuento para B es al menos 2 más que eso. (Cuando el segundo umbral es mayor que 0, garantiza que otros estados seguirán realizando la transición a B después de la clonación). Algunas implementaciones como hook permiten que estos umbrales se establezcan como parámetros. En paq8l, estos umbrales aumentan a medida que se utiliza la memoria para reducir 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 de nuevo al modelo original de orden 1 byte por byte.
La página reproducirá audio cuando se cargue)