DMC (algoritmo de compresión)
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 10 de enero de 2018; las comprobaciones requieren
10 ediciones .
DMC ( compresión dinámica de Markov , compresión dinámica de Markov [1] ) es un algoritmo de compresión de datos sin pérdidas desarrollado por Gordon Cormack y Nigel Horspool [2] . El método se construye de manera similar al método PPM : el algoritmo en sí mismo es un predictor (calcula las probabilidades de los símbolos), y un codificador de entropía realiza la compresión directa . A diferencia de PPM, el método DMC generalmente funciona a nivel de bits, mientras que PPM funciona a nivel de bytes. DMC proporciona niveles de compresión y velocidad de procesamiento comparables a PPM, pero requiere más memoria y no es tan común como PPM. Algunas de las implementaciones modernas son: el compresor de gancho de Nania Francesco Antonio, el compresor ocamyd de Frank Schwellinger, y DMC se usa como uno de los modelos en el compresor paq8l de Matt Mahoney . Todos los compresores enumerados se basan en la implementación C original de 1993 de Gordon Cormack.
Algoritmo
DMC predice y codifica un bit por paso lógico de operación. Se diferencia de PPM en que trabaja a nivel de bits, no de bytes. La diferencia con los métodos de mezcla de contexto (como PAQ ) es que DMC construye y usa un solo modelo fuente. La compresión directa se realiza mediante codificación aritmética .
Modelo
El modelo de origen predice el siguiente bit en función del contexto actual. El modelo se puede representar como un gráfico, cada nodo del cual contiene dos contadores: n 0 y n 1 , donde n 0 es un contador de bits con un valor de 0, y n 1 es un contador de bits con un valor de 1. Uno de los nodos es siempre el actual. Uno de los contadores en el nodo actual se incrementa cuando se encuentra un bit con el valor correspondiente en los datos originales. El nodo también tiene dos bordes que lo conectan con otros nodos o consigo mismo. Uno de los bordes se usa cuando ocurre 0 en los datos de origen, el otro cuando ocurre 1. En el caso más simple, el modelo consta de un solo nodo que se refiere a sí mismo. En esta configuración, el modelo solo puede leer la relación entre el número de bits con un valor de 0 y el número de bits con un valor de 1 en los datos originales. Cuando hay más de un nodo en el modelo, al procesar el siguiente bit, puede ocurrir una transición a otro nodo, así como la formación de un nuevo nodo.
El siguiente bit se predice calculando las probabilidades para 0 usando la fórmula p 0 = n 0 / n = n 0 /( n 0 + n 1 ) y, en consecuencia, para 1 usando la fórmula p 1 = 1 − p 0 = n 1 / n . Así, cada nodo encarna un estado separado del modelo, en el que hace diferentes predicciones. El contexto en el modelo DMC no se recuerda explícitamente, pero el modelo lo tiene en cuenta como resultado de las transiciones entre los nodos del gráfico de estado.
La simulación se realiza de la misma forma tanto para la compresión como para la descompresión.
Notas
- ↑ Vatolin D. Métodos de compresión de datos. El dispositivo de archivadores, compresión de imagen y video.. - M. : Dialog-MEPhI, 1993. - P. 9. - ISBN 5-86404-170-x .
- ↑ Gordon Cormack y Nigel Horspool, "Compresión de datos mediante modelado dinámico de Markov", Computer Journal 30:6 (diciembre de 1987)