Predicción mediante coincidencia parcial

La predicción por coincidencia parcial ( PPM ) es una técnica adaptativa de compresión de datos estadísticos 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 dicho flujo. Los algoritmos PPM también pueden utilizarse para agrupar datos en grupos predichos en el análisis de clústeres .

Las predicciones suelen reducirse a clasificaciones de símbolos . Cada símbolo (una letra, un bit o cualquier otra cantidad de datos) se clasifica antes de su compresión, y el sistema de clasificación determina la palabra clave 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 una función de probabilidad. Dadas las letras anteriores (o un contexto), a cada símbolo se le asigna una probabilidad. Por ejemplo, en la codificación aritmética, los símbolos se clasifican según su probabilidad de aparecer después de los símbolos anteriores, y toda la secuencia se comprime en una sola fracción que se calcula de acuerdo con estas probabilidades.

El número de símbolos previos, n , determina el orden del modelo PPM, que se denota como PPM( n ). También existen variantes sin límite de longitud, donde el contexto no tiene restricciones, que se denotan como PPM* . Si no se puede realizar ninguna predicción con los n símbolos del 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 momento, se realiza una predicción fija.

Gran parte del trabajo de optimización de un modelo PPM consiste en gestionar las entradas que no han aparecido previamente en el flujo de entrada. La forma obvia de hacerlo es crear un símbolo "nunca visto" que active la secuencia de escape . Pero, ¿qué probabilidad se debe asignar a un símbolo que nunca se ha visto? Esto se conoce como el problema de la frecuencia cero . Una variante utiliza el estimador de Laplace , que asigna al símbolo "nunca visto" un pseudoconteo fijo de uno. Otra variante, denominada PPMd, incrementa el pseudoconteo del símbolo "nunca visto" cada vez que se utiliza. (En otras palabras, PPMd estima la probabilidad de un nuevo símbolo como la proporció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 considerablemente en otros detalles. La selección de símbolos se registra generalmente 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 por diccionario . El modelo subyacente utilizado en la mayoría de los algoritmos PPM también puede extenderse para predecir múltiples símbolos. Asimismo, es posible utilizar modelos no markovianos para reemplazar o complementar los modelos markovianos. El tamaño del símbolo suele ser estático, normalmente de 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 desde mediados de la década de 1980. Las implementaciones de software no se popularizaron hasta principios de la década de 1990 debido a que los algoritmos PPM requieren una cantidad considerable 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 por defecto en formato de archivo RAR . También está disponible en formatos de archivo 7z y zip .

Los intentos por mejorar los algoritmos PPM dieron lugar a la serie PAQ de algoritmos de compresión de datos.

En el programa Dasher , que utiliza un método de entrada alternativo, el algoritmo PPM, en lugar de utilizarse para la compresión, se emplea para aumentar la eficiencia de la entrada del usuario .

• Modelo de lenguaje
• n -grama

• Cleary, J.; Witten, I. (abril de 1984). "Compresión de datos mediante codificación adaptativa y coincidencia parcial de cadenas". IEEE Trans. Commun. 32 (4): 396– 402. CiteSeerX 10.1.1.14.4305 . doi : 10.1109/TCOM.1984.1096090 . 
• Moffat, A. (noviembre de 1990). "Implementación del esquema de compresión de datos PPM". IEEE Trans. Commun. 38 (11): 1917– 1921. CiteSeerX 10.1.1.120.8728 . doi : 10.1109/26.61469 . 
• Cleary, JG; Teahan, WJ; Witten, IH (1997). "Contextos de longitud ilimitada para PPM" . The Computer Journal . 40 (2_and_3). Oxford, Inglaterra: Oxford University Press: 67–75 . doi : 10.1093/comjnl/40.2_and_3.67 . ISSN 0010-4620 . 
• C. Bloom, Resolviendo los problemas del modelado de contexto .
• WJ Teahan, Estimación de probabilidad para PPM , Fuente original de archive.org .
• Schürmann, T.; Grassberger, P. (septiembre de 1996). "Estimación de entropía de secuencias de símbolos". Caos . 6 (3): 414– 427. arXiv : cond-mat/0203436 . Bibcode : 1996Caos...6..414S . doi : 10.1063/1.166191 . PMID 12780271 . S2CID 10090433 .