Prediction by Partial Matching (algoritmo de compresión)

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 emita 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).