El algoritmo Prediction by Partial Matching (en español Predicción por Coincidencia Parcial) o PPM es una técnica adaptativa estadística de compresión de datos basada en el modelo de contexto y predicción. Los modelos PPM usan un conjunto de símbolos previos en el flujo de símbolos no comprimidos para predecir el siguiente símbolo en dicho flujo.

Funcionamiento

Las predicciones se reducen normalmente a rankings de símbolos. El número de símbolos previos, n, determina el orden del modelo PPM que se denota con PPM(n). También existen variantes donde el contexto no tiene limitaciones de longitud y se denotan como PPM*. Si no se puede realizar una predicción basada en todos los n símbolos del contexto, se realiza una predicción con sólo n-1 símbolos. Este proceso se repite hasta que se alcanza una coincidencia o no quedan más símbolos en el contexto. Es en ese punto donde se realiza la predicción. Este proceso es el inverso del seguido en los algoritmos de compresión DMC que se construyen sobre un modelo de orden cero (Ver Cadena de Márkov).

Optimización

La mayoría del trabajo de optimizar un modelo PPM está en manejar las entradas que no hayan aparecido en el flujo de entrada. La manera obvia es creando un símbolo "nunca antes visto" que lancé una secuencia de escape. Pero, ¿qué probabilidad debe ser asignada a un símbolo que nunca haya sido visto?. Esta cuestión se conoce como el problema de frecuencia cero. Una variante asigna el símbolo "nunca antes visto" a un seudo contador de aciertos de uno. La variante conocida como PPM-D incrementa dicho contador del símbolo "nunca antes visto" cada vez que se usa dicho símbolo. (Dicho de otra forma, PPM-D estima la probabilidad de un nuevo símbolo como la proporción entre el número de símbolos únicos y en número total de símbolos observados).

Implementación

Las implementaciones de los modelos PPM varían notablemente en otros detalles. La selección del símbolo actual se guarda usando la codificación aritmética, aunque se puede usa la codificación Huffman o incluso algún tipo de codificación por diccionario. El modelo PPM puede extender para predecir múltiples símbolos. También es posible usar o añadir modelados diferentes a los de Márkov. El tamaño del símbolo es normalmente estático, típicamente un único byte, lo que lo hace génerico y fácil para el manejo de cualquier formato de fichero.

Situación actual

Se han publicado investigaciones referentes a esta familia de algoritmos desde mediados de los años 1980. Sin embargo, las implementaciones via software no fueron populares hasta mediados de los años 1990 debido a la alta necesidad de recursos de memoria volátil. Las implementaciones más recientes de PPM se encuentran entre los mejores sistemas de compresión sin pérdida de texto en lenguaje natural.

Referencias

• T. Bell, J. Cleary, and I. Witten (University of Waikato, New Zealand)(1984) Data compression using adaptive coding and partial string matching. IEEE Transactions on Communications, Vol. 32 (4), p. 396-402.
• A. Moffat (1990) Implementing the PPM data compression scheme. IEEE Transactions on Communications, Vol. 38 (11), p. 1917-1921.
• J. Cleary, W. Teahan, and I. Witten (1995) Unbounded length contexts for PPM. In J.A. Storer and M. Cohn, editors, Proceedings DCC-95. IEEE Computer Society Press.
• C. Bloom (unknown) Resolviendo los problemas del modelado de contexto.
• W. Teahan (unknown) Estimación de probabilidad para el PPM.

Enlaces externos

• Lista de manuales de algoritmos de compresión sin pérdida incluyendo los PPM(en español)
• Lista de recursos, tutoriales y fuentes de PPM (en inglés)
• Sitio de compresores PPM con benchmarks (en inglés)
• BICOM, un compresor biyectivo PPM (en inglés)