Mezcla de contexto

Se nos proporciona un conjunto de predicciones.${\textstyle P_ {i} (1) = n_ {1i}/n_ {i}}$, dónde${\textstyle n_ {i} = n_ {0i} + n_ {1i}}$, y${\displaystyle n_{0i}}$y${\displaystyle n_{1i}}$son los recuentos de bits 0 y 1 respectivamente para el${\displaystyle i}$Modelo 'th. Las probabilidades se calculan mediante la suma ponderada de los recuentos de 0 y 1:

• ${\textstyle S_{0}=\sum _{i}w_{i}n_{0i}}$
• ${\textstyle S_{1}=\sum _{i}w_{i}n_{1i}}$
• ${\textstyle S=S_{0}+S_{1}}$
• ${\textstyle P(0)={\frac {S_{0}}{S}}}$
• ${\textstyle P(1)={\frac {S_{1}}{S}}}$

Los pesos${\displaystyle w_{i}}$son inicialmente iguales y siempre suman 1. Bajo las condiciones iniciales, cada modelo se pondera en proporción a la evidencia. Luego, las ponderaciones se ajustan para favorecer a los modelos más precisos. Supongamos que se nos da que el bit real que se predice es${\displaystyle y}$(0 o 1). Entonces el ajuste de peso es: ^{[ 3 ]}$${\displaystyle w_{i}\leftarrow \max[0,w_{i}+(yP(1)){\frac {Sn_{1i}-S_{1}n_{i}}{S_{0}S_{1}}}]}$$La compresión se puede mejorar mediante la limitación.${\textstyle n_{i}}$para que la ponderación del modelo esté mejor equilibrada. En PAQ6, cada vez que se incrementa uno de los contadores de bits, la parte del otro contador que excede 2 se reduce a la mitad. Por ejemplo, después de la secuencia 000000001, los contadores irían desde${\textstyle (n_ {0},n_ {1}) = (8,0)}$a${\textstyle (5,1)}$.

Dejar${\displaystyle P_{i}(1)}$ser la predicción por el ${\displaystyle i}$El modelo indica que el siguiente bit será un 1. Luego, la predicción final.${\displaystyle P(1)}$se calcula:

• ${\displaystyle x_{i}={\text{estiramiento}}(P_{i}(1))}$
• ${\textstyle P(1)={\text{aplastar}}(\sum _{i}w_{i}x_{i})}$

dónde${\displaystyle P(1)}$es la probabilidad de que el siguiente bit sea un 1,${\displaystyle P_{i}(1)}$es la probabilidad estimada por el ${\displaystyle i}$el modelo y

• ${\displaystyle {\text{estiramiento}}(x)=\ln(x/(1-x))}$
• ${\displaystyle {\text{aplastar}}(x)={\text{estirar}}^{-1}(x)=1/(1+e^{-x})}$

Tras cada predicción, el modelo se actualiza ajustando las ponderaciones para minimizar el coste de codificación.

• ${\displaystyle w_{i}\leftarrow w_{i}+\eta x_{i}(yP(1))}$

dónde${\displaystyle \eta }$es la tasa de aprendizaje (normalmente de 0,002 a 0,01),${\displaystyle y}$es el bit previsto, y (${\displaystyle yP(1)}$) es el error de predicción.

Todas las versiones que se muestran a continuación utilizan la mezcla logística, salvo que se indique lo contrario.

• Todas las versiones de PAQ (Matt Mahoney, Serge Osnach, Alexander Ratushnyak, Przemysław Skibiński, Jan Ondrus y otros)PAQAR y las versiones anteriores a PAQ7 utilizaban mezcla lineal. Las versiones posteriores utilizaban mezcla logística.
• Todas las versiones de LPAQ (Matt Mahoney, Alexander Ratushnyak).
• ZPAQ (Matt Mahoney).
• WinRK 3.0.3 (Malcolm Taylor) en modo PWCM de máxima compresiónLa versión 3.0.2 se basaba en la mezcla lineal.
• NanoZip (Sami Runsas) en modo de compresión máxima (opción -cc).
• xwrt 3.2 (Przemysław Skibiński) en modo de compresión máxima (opciones -i10 a -i14)como parte del backend de un codificador de diccionario.
• Los algoritmos cmm1 a cmm4, M1 y M1X2 (Christopher Mattern) utilizan un número reducido de contextos para lograr alta velocidad. M1 y M1X2 emplean un algoritmo genético para seleccionar dos contextos enmascarados por bits en una pasada de optimización independiente.
• ccm (Christian Martelock).
• bit (Osman Turan).
• espinilla, espinilla2, tc y px (Ilia Muraviev).
• enc (Serge Osnach) prueba varios métodos basados ​​en PPM y mezcla de contexto (lineal) y elige el mejor.
• fpaq2 (Nania Francesco Antonio) utilizando promedio ponderado fijo para alta velocidad.
• cmix (Byron Knoll) combina muchos modelos y actualmente ocupa el primer lugar en el benchmark Large Text Compression, ^{[ 4 ]} así como en el corpus Silesia ^{[ 5 ]} y ha superado la entrada ganadora del Hutter Prize aunque no es elegible debido a que utiliza demasiada memoria.