La compresión dinámica de Markov ( DMC ) es un algoritmo de compresión de datos sin pérdidas desarrollado por Gordon Cormack y Nigel Horspool . [1] Utiliza 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 está ampliamente implementado. Algunas implementaciones recientes incluyen el gancho de programas de compresión experimental de Nania Francesco Antonio, ocamydde Frank Schwellinger, y como submodelo en paq8l de Matt Mahoney. Estos se basan en la implementación de 1993 en C por 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 algoritmos de mezcla de contextos como PAQ en que solo hay un contexto por predicción. A continuación, el bit predicho se codifica 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 ) pags ( x 3 | x 1 x 2 ) ... pags ( x norte | x 1 x 2 ... x n –1 ). El codificador aritmético mantiene dos números binarios de alta precisión, p bajo y p alto , que representan el rango posible para la probabilidad total de 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 px , la cadena de bits más corta que representa un número entre p bajo y p alto . Siempre es posible encontrar un número en este rango no más de un bit más largo que elLímite de Shannon , log 2 1 / p ( x'). Uno de esos números se puede obtener de p alto eliminando 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 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. El codificador aritmético luego divide el rango actual ( p bajo , p alto ) en dos partes en proporción a p 0 y p1 . Luego, el subrango correspondiente al siguiente bit x i se convierte en el nuevo rango.
Para la descompresión, el predictor hace 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 con alta precisión. A medida que el rango se estrecha, los bits iniciales de ambos números serán los mismos y se pueden generar de inmediato.