¿Por qué la codificación aritmética puede tener una longitud de palabra de código fraccional?

Answer 1

Debido a que un solo bit de información que completa un carácter codificado podría (en la práctica, casi siempre lo hará) también transportar cierta información sobre el siguiente carácter.

Para mostrar un ejemplo, voy a comenzar con esta respuesta, que describe cómo usar la codificación aritmética para generar un solo carácter de salida. Utiliza una fuente de randoms con 4 resultados, lo que equivale a generar un par de bits al azar; para la codificación aritmética, en su lugar obtendríamos estos bits de un flujo de datos comprimido, pero el algoritmo funciona exactamente de la misma manera.

Di el ejemplo donde la fuente aleatoria produjo 2, 0, 2 (los bits son 1, 0, 0, 0, 1, 0). En este caso, el primer carácter de salida es 9. Pero también tenemos un rango restante, que es [matemática] [\ frac {1} {32}, \ frac {9} {64}) [/ matemática]. En lugar de generar x en [math] [0,1) [/ math] y tomar la parte entera de 17x, podemos generar la segunda x en este intervalo más pequeño. Por lo tanto, se requieren menos bits en promedio.

Para generar el siguiente carácter de salida, expandiríamos el resto por un factor de 17 (para mapearlo en el rango de salida), obteniendo [\ frac {17} {32}, 2 \ frac {25} {64}). Luego, particione repetidamente en partes iguales y use el siguiente bit de origen para elegir qué parte mantener (alta o baja). Siempre que el rango caiga dentro de [matemáticas] [k, k + 1) [/ matemáticas] para algún entero k, genere k y reemplace los límites de rango usando [matemáticas] x \ a 17 (xk) [/ matemáticas] para prepararse para el siguiente salida

El punto aquí es que algunos bits de origen se “comparten” entre dos caracteres de salida, lo que conduce a una longitud de palabra de código promedio fraccional.