15.4 Modelos con memoria

• En muchos casos la probabilidad de un símbolo depende de los símbolos vecinos (también llamados contexto). Cuando esto ocurre se dice que el modelo posee memoria (recuerda el contexto) [2].
• La ventaja de tener en cuenta el contexto es que las probabilidades pueden calcularse con mayor precisión (asignando probabilidades más altas) y por tanto se decrementa el número de bits necesarios para representar las secuencias comprimidas.
• En los Apéndices 39.46, 39.41 y 39.45 encontraremos ejemplos de modelos con memoria.

Compresor

Sea C[i] la secuencia de los i últimos símbolos codificados y sea p(s|C[i]) la probabilidad de que ocurra el símbolo s tras C[i]. Sea k el orden de predicción (el número máximo de símbolos recordados).

1. Crear un modelo vacío (excepto por el símbolo ESC) para cada posible contexto donde i ≥ 0 y un modelo no vacío para i = -1.
2. Mientras existan símbolos que codificar:
   1. s ← siguiente símbolo.
   2. i ← k (excepto en la primera iteración donde i ← 0).
   3. Mientras p(s|C[i]) = 0 (s es la primera vez que aparece tras c[i]):
      1. Codificar ESC según p(ESC|C[i]).
      2. Añadir s al contexto para C[i].
      3. i ← i - 1.
   4. Codificar s según p(s|C[i]). Todos los símbolos que estaban en contextos de orden mayor que i deben ser excluidos del contexto actual ya que es seguro que s no es ninguno de ellos.
   5. Actualizar p(s|C[i]).

Ejemplo

• r = 256 es el tamaño del alfabeto fuente.
• El contexto C[-1] tiene asociado un modelo probabilístico M[C[-1]] de orden 0 no adaptativo y no vacío, en el que además aparece el símbolo especial EOF (End Of File). Por tanto, este modelo contiene r + 1 símbolos y su contenido es

  M[C[-1]] = {0,1 1,1  a,1 b,1  255,1 ESC,1 EOF,1},

  donde cada par a,b denota el símbolo a y su probabilidad b, medida como un número de ocurrencias.

• El contexto C[0] tiene asociado un modelo probabilístico de orden 0 adaptativo e inicialmente vacío, que contiene sólo el símbolo ESC. Su contenido es, por tanto

  M[C[0]] = {ESC,1}.

• En este ejemplo (por simplicidad), el orden máximo de predicción es k = 1 (se recuerda a lo sumo el símbolo anterior). Por tanto, existen otros r contextos de orden 0 adaptativos e inicialmente vacíos, iguales al anteriormente descrito y que contienen sólo el símbolo ESC.
• Durante la codificación del símbolo a ocurre lo siguiente:
  1. s ← a.
  2. i ← 0.
  3. p(a|C[0]) = 0 (el contexto contiene sólo el ESC).
  4. Codificamos un ESC aunque no se genera ningún bit de código porque su probabilidad es 1.
  5. Añadimos a al modelo M[C[0]].
  6. Hacemos i ←-1.
  7. p(a|C[-1])≠0.
  8. Codificamos a según p(a|C[-1]) = 1∕(r + 1).
• Durante la codificación del segundo símbolo (b):
  1. s ← b.
  2. i ← 1.
  3. p(b|C[1]) = 0 porque C[1] = a y M[a] contiene inicialmente sólo el símbolo ESC.
  4. Codificamos un ESC y no se genera ningún bit de código porque su probabilidad es 1.
  5. Añadimos b al modelo M(a).
  6. Hacemos i ← 0.
  7. p(b|C[0]) = 0 porque M[C[0]] contiene sólo el símbolo ESC y el símbolo a.
  8. Codificamos un ESC, pero ahora se generan 1∕2 bits de datos. Se incrementa su recuento.
  9. Añadimos b al modelo M[C[0]]. Ahora M[C[0]] = {ESC,4 a,1 b,1}.
  10. Hacemos i ←-1.
  11. p(b|C[-1])≠0.
  12. Codificamos b según p(b|C[-1]) = 1∕r. Nótese que debe excluirse el símbolo a para calcular la probabilidad del símbolo b porque el símbolo a ya aparece en el contexto M[C[0]].

Descompresor

1. Idem al paso 1 del compresor.
2. Mientras existan símbolos que descodificar:
   1. i ← k.
   2. Mientras el símbolo descodificado sea ESC:
      1. i ← i - 1.
   3. Descodificar s según p(s|c[i]).
   4. Actualizar p(s|c[i]).
   5. Mientras i < k:
      1. i ← i + 1.
      2. Añadir s al contexto para c[i].