La predicción por coincidencia parcial ( PPM ) es una técnica de compresión de datos estadística adaptativa basada en el modelado y la predicción del contexto . Los modelos PPM utilizan un conjunto de símbolos anteriores en el flujo de símbolos sin comprimir para predecir el siguiente símbolo en el flujo. Los algoritmos PPM también se pueden utilizar para agrupar datos en grupos previstos en el análisis de conglomerados .
Las predicciones se reducen generalmente a clasificaciones de símbolos [ aclaración necesaria ] . Cada símbolo (una letra, un bit o cualquier otra cantidad de datos) se clasifica antes de comprimirlo, y el sistema de clasificación determina la palabra de código correspondiente (y, por lo tanto, la tasa de compresión). En muchos algoritmos de compresión, la clasificación es equivalente a la estimación de la función de masa de probabilidad. Dadas las letras anteriores (o un contexto dado), a cada símbolo se le asigna una probabilidad. Por ejemplo, en la codificación aritmética, los símbolos se clasifican según sus probabilidades de aparecer después de los símbolos anteriores, y toda la secuencia se comprime en una única fracción que se calcula de acuerdo con estas probabilidades.
El número de símbolos anteriores, n , determina el orden del modelo PPM, que se denota como PPM( n ). También existen variantes ilimitadas en las que el contexto no tiene limitaciones de longitud y se denotan como PPM* . Si no se puede hacer ninguna predicción en función de los n símbolos de contexto, se intenta una predicción con n − 1 símbolos. Este proceso se repite hasta que se encuentra una coincidencia o no quedan más símbolos en el contexto. En ese punto, se realiza una predicción fija.
Gran parte del trabajo de optimización de un modelo PPM consiste en gestionar entradas que aún no se han producido en el flujo de entrada. La forma obvia de gestionarlas es crear un símbolo "nunca visto" que active la secuencia de escape [ aclaración necesaria ] . Pero, ¿qué probabilidad se debe asignar a un símbolo que nunca se ha visto? Esto se denomina problema de frecuencia cero. Una variante utiliza el estimador de Laplace , que asigna al símbolo "nunca visto" un pseudoconteo fijo de uno. Una variante denominada PPMd incrementa el pseudoconteo del símbolo "nunca visto" cada vez que se utiliza dicho símbolo. (En otras palabras, PPMd estima la probabilidad de un nuevo símbolo como la relación entre el número de símbolos únicos y el número total de símbolos observados).
Las implementaciones de compresión PPM varían mucho en otros detalles. La selección de símbolos real generalmente se registra mediante codificación aritmética , aunque también es posible utilizar la codificación Huffman o incluso algún tipo de técnica de codificación de diccionario . El modelo subyacente utilizado en la mayoría de los algoritmos PPM también se puede ampliar para predecir múltiples símbolos. También es posible utilizar modelos no Markovianos para reemplazar o complementar el modelado Markoviano. El tamaño del símbolo suele ser estático, normalmente un solo byte, lo que facilita el manejo genérico de cualquier formato de archivo.
Se pueden encontrar investigaciones publicadas sobre esta familia de algoritmos que se remontan a mediados de la década de 1980. Las implementaciones de software no fueron populares hasta principios de la década de 1990 porque los algoritmos PPM requieren una cantidad significativa de RAM . Las implementaciones recientes de PPM se encuentran entre los programas de compresión sin pérdida de mejor rendimiento para texto en lenguaje natural .
PPMd es una implementación de dominio público de PPMII (PPM con herencia de información) de Dmitry Shkarin que ha sufrido varias revisiones incompatibles. [1] Se utiliza en formato de archivo RAR de forma predeterminada. También está disponible en los formatos de archivo 7z y zip .
Los intentos de mejorar los algoritmos PPM condujeron a la serie PAQ de algoritmos de compresión de datos.
Un algoritmo PPM, en lugar de usarse para la compresión, se utiliza para aumentar la eficiencia de la entrada del usuario en el programa de método de entrada alternativo Dasher .