Passa al contenuto principale

7. Modellazione del contesto (Context Modeling)

7. Modellazione del contesto (Context Modeling)​

Come descritto nella sezione 2, l'albero prefisso (Prefix Tree) utilizzato per codificare un byte letterale (Literal Byte) o un codice di distanza (Distance Code) dipende dal tipo di blocco (Block Type) e dall'ID di contesto (Context ID). Questa sezione specifica come calcolare l'ID di contesto per un particolare letterale e codice di distanza e come codificare la mappa di contesto (Context Map) che mappa una coppia <block type, context ID> all'indice di un codice prefisso nell'array dei codici prefissi letterali e di distanza.

7.1. Modi di contesto e ricerca ID di contesto per i letterali (Context Modes and Context ID Lookup for Literals)​

Il contesto (Context) per codificare il prossimo letterale è definito dagli ultimi due byte nel flusso (p1, p2, dove p1 è il byte più recente), indipendentemente dal fatto che questi byte siano prodotti da meta-blocchi non compressi, riferimenti all'indietro (Backward References), riferimenti al dizionario statico (Static Dictionary References) o da inserimenti letterali (Literal Insertions). All'inizio del flusso, p1 e p2 sono inizializzati a zero.

Esistono quattro metodi, chiamati modi di contesto (Context Modes), per calcolare l'ID di contesto:

  • LSB6: l'ID di contesto è il valore dei sei bit meno significativi di p1.

  • MSB6: l'ID di contesto è il valore dei sei bit più significativi di p1.

  • UTF8: l'ID di contesto è una funzione complessa di p1, p2, ottimizzata per la compressione del testo.

  • Signed: l'ID di contesto è una funzione complessa di p1, p2, ottimizzata per la compressione di sequenze di interi con segno.

L'ID di contesto per i modi di contesto UTF8 e Signed viene calcolato utilizzando le seguenti tabelle di ricerca Lut0, Lut1 e Lut2.

Lut0 :=
  0,  0,  0,  0,  0,  0,  0,  0,  0,  4,  4,  0,  0,  4,  0,  0,
  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,
  8, 12, 16, 12, 12, 20, 12, 16, 24, 28, 12, 12, 32, 12, 36, 12,
 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 32, 32, 24, 40, 28, 12,
 12, 48, 52, 52, 52, 48, 52, 52, 52, 48, 52, 52, 52, 52, 52, 48,
 52, 52, 52, 52, 52, 48, 52, 52, 52, 52, 52, 24, 12, 28, 12, 12,
 12, 56, 60, 60, 60, 56, 60, 60, 60, 56, 60, 60, 60, 60, 60, 56,
 60, 60, 60, 60, 60, 56, 60, 60, 60, 60, 60, 24, 12, 28, 12,  0,
  0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1,
  0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1,
  0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1,
  0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1,
  2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3,
  2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3,
  2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3,
  2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3, 2, 3

Lut1 :=
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
  2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1,
  1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
  2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1,
  1, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
  3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
  2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2

Lut2 :=
  0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
  2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
  2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
  2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
  3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
  3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
  3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
  3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
  4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
  4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
  4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
  4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4,
  5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
  5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
  5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
  6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7

Le lunghezze e i valori di controllo CRC-32 (vedere Appendice C) di ciascuna di queste tabelle come sequenza di byte sono i seguenti:

Table    Length    CRC-32
-----    ------    ------
Lut0     256       0x8e91efb7
Lut1     256       0xd01a32f4
Lut2     256       0x0dd7a0d6

Dato che p1 è l'ultimo byte non compresso e p2 è il penultimo byte non compresso, gli ID di contesto possono essere calcolati come segue:

For LSB6:    Context ID = p1 & 0x3f
For MSB6:    Context ID = p1 >> 2
For UTF8:    Context ID = Lut0[p1] | Lut1[p2]
For Signed:  Context ID = (Lut2[p1] << 3) | Lut2[p2]

Dalle tabelle di ricerca definite sopra e dalle operazioni per calcolare gli ID di contesto, possiamo vedere che gli ID di contesto per i letterali sono nell'intervallo 0..63.

I modi di contesto LSB6, MSB6, UTF8 e Signed sono indicati dagli interi 0, 1, 2, 3.

Un modo di contesto è definito per ogni tipo di blocco letterale e sono memorizzati in un array consecutivo di bit nell'header del meta-blocco, sempre due bit per tipo di blocco.

7.2. ID di contesto per le distanze (Context ID for Distances)​

Il contesto (Context) per codificare un codice di distanza è definito dalla lunghezza di copia (Copy Length) corrispondente alla distanza. Gli ID di contesto sono 0, 1, 2 e 3 per lunghezze di copia 2, 3, 4 e più di 4, rispettivamente.

7.3. Codifica della mappa di contesto (Encoding of the Context Map)​

Esistono due mappe di contesto (Context Maps), una per i letterali e una per le distanze. La dimensione della mappa di contesto è 64 * NBLTYPESL per i letterali e 4 * NBLTYPESD per le distanze. Ogni valore nella mappa di contesto è un intero tra 0 e 255, che indica l'indice del codice prefisso da utilizzare quando si codifica il prossimo letterale o distanza.

Le mappe di contesto sono matrici bidimensionali, codificate come array unidimensionali:

CMAPL[0..(64 * NBLTYPESL - 1)]
CMAPD[0..(4 * NBLTYPESD - 1)]

L'indice del codice prefisso per codificare un codice letterale o di distanza con tipo di blocco BTYPE_x e ID di contesto CIDx è:

index of literal prefix code = CMAPL[64 * BTYPE_L + CIDL]
index of distance prefix code = CMAPD[4 * BTYPE_D + CIDD]

I valori della mappa di contesto sono codificati con la combinazione di codifica a lunghezza variabile (Run Length Encoding) per valori zero e codifica prefissa. Sia RLEMAX il numero di codici a lunghezza variabile e NTREES il valore massimo nella mappa di contesto più uno. NTREES deve essere uguale al numero di valori diversi nella mappa di contesto; in altre parole, i valori diversi nella mappa di contesto devono essere l'intervallo [0..NTREES-1]. L'alfabeto del codice prefisso ha i seguenti RLEMAX + NTREES simboli:

0: valore zero
1: ripeti uno zero 2-3 volte, leggi 1 bit per la lunghezza di ripetizione
2: ripeti uno zero 4-7 volte, leggi 2 bit per la lunghezza di ripetizione
...
RLEMAX: ripeti uno zero (1 << RLEMAX) a (1 << (RLEMAX+1))-1 volte,
        leggi RLEMAX bit per la lunghezza di ripetizione
RLEMAX + 1: valore 1
...
RLEMAX + NTREES - 1: valore NTREES - 1

Se RLEMAX = 0, la codifica a lunghezza variabile non viene utilizzata e i simboli dell'alfabeto sono direttamente i valori nella mappa di contesto. Possiamo ora definire il formato della mappa di contesto (lo stesso formato è utilizzato per le mappe di contesto letterali e di distanza):

1..5 bit: RLEMAX, 0 è codificato con un bit 0, e i valori 1..16
          sono codificati con il pattern di bit xxxx1 (quindi 01001 è 5)

Codice prefisso con dimensione dell'alfabeto NTREES + RLEMAX

Valori di dimensione della mappa di contesto codificati con il codice
prefisso sopra e la codifica a lunghezza variabile per valori zero.
Se una lunghezza variabile comporterebbe più lunghezze in totale della
dimensione della mappa di contesto, allora il flusso dovrebbe essere
rifiutato come non valido.

1 bit:  bit IMTF, se impostato, eseguiamo una trasformazione inversa
        move-to-front (Inverse Move-to-Front Transform) sui valori
        nella mappa di contesto per ottenere gli indici dei codici
        prefissi.

Si noti che RLEMAX può essere più grande del valore necessario per rappresentare la sequenza più lunga di valori zero. Inoltre, il valore NTREES è codificato subito prima della mappa di contesto come descritto nella sezione 9.2.

Definiamo la trasformazione inversa move-to-front (Inverse Move-to-Front Transform) utilizzata in questa specifica con la seguente funzione in linguaggio C:

void InverseMoveToFrontTransform(uint8_t* v, int v_len) {
   uint8_t mtf[256];
   int i;
   for (i = 0; i < 256; ++i) {
      mtf[i] = (uint8_t)i;
   }
   for (i = 0; i < v_len; ++i) {
      uint8_t index = v[i];
      uint8_t value = mtf[index];
      v[i] = value;
      for (; index; --index) {
         mtf[index] = mtf[index - 1];
      }
      mtf[0] = value;
   }
}

Si noti che la trasformazione inversa move-to-front non produrrà valori al di fuori dell'intervallo [0..NTREES-1].

Fonte (Source): RFC 7932, Section 7
Testo ufficiale (Official Text): https://www.rfc-editor.org/rfc/rfc7932.txt

Ultimo aggiornamento il