3. Rappresentazione compressa dei codici prefissi (Compressed Representation of Prefix Codes)

3.1. Introduzione alla codifica prefissa (Introduction to Prefix Coding)

La codifica prefissa (Prefix Coding) rappresenta i simboli di un alfabeto noto a priori mediante sequenze di bit (Codes), un codice per ogni simbolo, in modo tale che simboli diversi possano essere rappresentati da sequenze di bit di lunghezze diverse, ma un parser possa sempre analizzare una stringa codificata in modo non ambiguo simbolo per simbolo.

Definiamo un codice prefisso in termini di albero binario (Binary Tree) in cui i due archi discendenti da ogni nodo non foglia (Non-leaf Node) sono etichettati 0 e 1, e in cui i nodi foglia (Leaf Nodes) corrispondono uno a uno con (sono etichettati con) i simboli dell'alfabeto. Il codice per un simbolo è la sequenza di 0 e 1 sugli archi che portano dalla radice alla foglia etichettata con quel simbolo. Ad esempio:

           /\              Symbol    Code
          0  1             ------    ----
         /    \                A     00
        /\     B               B     1
       0  1                    C     011
      /    \                   D     010
     A     /\
          0  1
         /    \
        D      C

Un parser può decodificare il prossimo simbolo dal flusso compresso percorrendo l'albero dalla radice, ad ogni passo scegliendo l'arco corrispondente al prossimo bit di dati compressi.

Dato un alfabeto con frequenze di simboli note, l'algoritmo di Huffman (Huffman Algorithm) consente la costruzione di un codice prefisso ottimale (uno che rappresenta stringhe con quelle frequenze di simboli utilizzando il minor numero di bit di tutti i codici prefissi possibili per quell'alfabeto). Tale codice prefisso è chiamato codice di Huffman (Huffman Code). (Vedere [HUFFMAN] per ulteriori informazioni sui codici di Huffman.)

Nel formato brotli, si noti che i codici prefissi per i vari alfabeti non devono superare determinate lunghezze di codice massime. Questo vincolo complica l'algoritmo per calcolare le lunghezze di codice dalle frequenze di simboli. Ancora una volta, vedere [HUFFMAN] per i dettagli.

3.2. Uso della codifica prefissa nel formato Brotli (Use of Prefix Coding in the Brotli Format)

I codici prefissi utilizzati per ciascun alfabeto nel formato brotli sono codici prefissi canonici (Canonical Prefix Codes), che hanno due regole aggiuntive:

Tutti i codici di una data lunghezza di bit hanno valori lessicograficamente consecutivi, nello stesso ordine dei simboli che rappresentano.
I codici più corti precedono lessicograficamente i codici più lunghi.

Potremmo ricodificare l'esempio sopra per seguire questa regola come segue, assumendo che l'ordine dell'alfabeto sia ABCD:

Symbol  Code
------  ----
A       10
B       0
C       110
D       111

Cioè, 0 precede 10, che precede 11x, e 110 e 111 sono lessicograficamente consecutivi.

Data questa regola, possiamo definire il codice prefisso canonico per un alfabeto semplicemente fornendo le lunghezze di bit dei codici per ogni simbolo dell'alfabeto in ordine; questo è sufficiente per determinare i codici effettivi. Nel nostro esempio, il codice è completamente definito dalla sequenza di lunghezze di bit (2, 1, 3, 3). Il seguente algoritmo genera i codici come interi, destinati a essere letti dal bit più significativo al meno significativo. Le lunghezze di codice sono inizialmente in tree[I].Len; i codici sono prodotti in tree[I].Code.

1) Contare il numero di codici per ogni lunghezza di codice.
   Sia bl_count[N] il numero di codici di lunghezza N, N >= 1.

2) Trovare il valore numerico del codice più piccolo per ogni
   lunghezza di codice:

   code = 0;
   bl_count[0] = 0;
   for (bits = 1; bits <= MAX_BITS; bits++) {
      code = (code + bl_count[bits-1]) << 1;
      next_code[bits] = code;
   }

3) Assegnare valori numerici a tutti i codici, utilizzando valori
   consecutivi per tutti i codici della stessa lunghezza con i
   valori di base determinati al passo 2. I codici che non vengono
   mai utilizzati (che hanno una lunghezza di bit zero) non devono
   essere assegnati a un valore.

   for (n = 0; n <= max_code; n++) {
      len = tree[n].Len;
      if (len != 0) {
         tree[n].Code = next_code[len];
         next_code[len]++;
      }
   }

Esempio:

Consideriamo l'alfabeto ABCDEFGH, con lunghezze di bit (3, 3, 3, 3, 3, 2, 4, 4). Dopo il passo 1, abbiamo:

N      bl_count[N]
-      -----------
2      1
3      5
4      2

Il passo 2 calcola i seguenti valori next_code:

N      next_code[N]
-      ------------
1      0
2      0
3      2
4      14

Il passo 3 produce i seguenti valori di codice:

Symbol Length   Code
------ ------   ----
A       3       010
B       3       011
C       3       100
D       3       101
E       3       110
F       2       00
G       4       1110
H       4       1111

3.3. Dimensioni dell'alfabeto (Alphabet Sizes)

I codici prefissi sono utilizzati per scopi diversi nel formato brotli, e ogni scopo ha una dimensione di alfabeto diversa. Per i codici letterali (Literal Codes), la dimensione dell'alfabeto è 256. Per i codici di lunghezza di inserimento e copia (Insert-and-Copy Length Codes), la dimensione dell'alfabeto è 704. Per i codici di conteggio blocchi (Block Count Codes), la dimensione dell'alfabeto è 26. Per i codici di distanza (Distance Codes), i codici di tipo blocco (Block Type Codes) e i codici prefissi utilizzati nella compressione della mappa di contesto, la dimensione dell'alfabeto è dinamica ed è basata sui parametri definiti nelle sezioni successive. La seguente tabella riassume le dimensioni dell'alfabeto per i vari codici prefissi e le sezioni di questo documento in cui sono definiti.

+-----------------+-------------------------+------------+
| Prefix Code     | Alphabet Size           | Definition |
+-----------------+-------------------------+------------+
| literal         | 256                     |            |
+-----------------+-------------------------+------------+
| distance        | 16 + NDIRECT +          | Section 4  |
|                 | (48 << NPOSTFIX)        |            |
+-----------------+-------------------------+------------+
| insert-and-copy | 704                     | Section 5  |
| length          |                         |            |
+-----------------+-------------------------+------------+
| block count     | 26                      | Section 6  |
+-----------------+-------------------------+------------+
| block type      | NBLTYPESx + 2,          | Section 6  |
|                 | (where x is I, L, or D) |            |
+-----------------+-------------------------+------------+
| context map     | NTREESx + RLEMAXx       | Section 7  |
|                 | (where x is L or D)     |            |
+-----------------+-------------------------+------------+

3.4. Codici prefissi semplici (Simple Prefix Codes)

I primi due bit della rappresentazione compressa di ogni codice prefisso distinguono tra codici prefissi semplici e complessi. Se questo valore è 1, allora segue un codice prefisso semplice (Simple Prefix Code) come descritto in questa sezione. Altrimenti, segue un codice prefisso complesso (Complex Prefix Code) come descritto nella sezione 3.5.

Un codice prefisso semplice può avere fino a quattro simboli con lunghezza di codice non zero. Il formato del codice prefisso semplice è il seguente:

bits: valore di 1 indica un codice prefisso semplice
bits: NSYM - 1, dove NSYM = numero di simboli codificati

NSYM simboli, ciascuno codificato utilizzando ALPHABET_BITS bit

bit:  tree-select, presente solo per NSYM = 4

Il valore di ALPHABET_BITS dipende dall'alfabeto del codice prefisso: è il più piccolo numero di bit che può rappresentare tutti i simboli nell'alfabeto. Ad esempio, per l'alfabeto dei byte letterali, ALPHABET_BITS è 8. Il valore di ciascuno dei NSYM simboli sopra è il valore del valore intero di larghezza ALPHABET_BITS. Se il valore intero è maggiore o uguale alla dimensione dell'alfabeto, o il valore è identico a un valore precedente, allora il flusso dovrebbe essere rifiutato come non valido.

Si noti che i NSYM simboli potrebbero non essere presentati in ordine ordinato. I codici prefissi della stessa lunghezza di bit devono essere assegnati ai simboli in ordine ordinato.

Le lunghezze di codice (non zero) dei simboli possono essere ricostruite come segue:

se NSYM = 1, la lunghezza del codice per l'unico simbolo è zero -- quando si codifica questo simbolo nel flusso di dati compressi utilizzando questo codice prefisso, non vengono emessi bit effettivi. Allo stesso modo, quando si decodifica un simbolo utilizzando questo codice prefisso, non vengono letti bit e viene restituito l'unico simbolo.
se NSYM = 2, entrambi i simboli hanno lunghezza di codice 1.
se NSYM = 3, le lunghezze di codice per i simboli sono 1, 2, 2 nell'ordine in cui appaiono nella rappresentazione del codice prefisso semplice.
se NSYM = 4, le lunghezze di codice (nell'ordine dei simboli decodificati) dipendono dal bit tree-select: 2, 2, 2, 2 (bit tree-select 0), o 1, 2, 3, 3 (bit tree-select 1).

3.5. Codici prefissi complessi (Complex Prefix Codes)

Un codice prefisso complesso (Complex Prefix Code) è un codice prefisso canonico, definito dalla sequenza di lunghezze di codice, come discusso nella sezione 3.2. Per una compattezza ancora maggiore, le sequenze di lunghezze di codice stesse sono compresse utilizzando un codice prefisso. L'alfabeto per le lunghezze di codice è il seguente:

 0..15: Rappresentano lunghezze di codice da 0..15
    16: Copiare la lunghezza di codice non zero precedente 3..6 volte.
        I prossimi 2 bit indicano la lunghezza di ripetizione
              (0 = 3, ... , 3 = 6)
        Se questa è la prima lunghezza di codice, o tutte le
        lunghezze di codice precedenti sono zero, una lunghezza
        di codice di 8 viene ripetuta 3..6 volte.
        Un codice di lunghezza di codice ripetuto di 16 modifica il
        conteggio di ripetizione del precedente come segue:
           repeat count = (4 * (repeat count - 2)) +
                          (3..6 sui prossimi 2 bit)
        Esempio: Codici 7, 16 (+2 bit 11), 16 (+2 bit 10)
                 si espanderanno a 22 lunghezze di codice di 7
                 (1 + 4 * (6 - 2) + 5)
    17: Ripetere una lunghezza di codice di 0 per 3..10 volte.
        I prossimi 3 bit indicano la lunghezza di ripetizione
              (0 = 3, ... , 7 = 10)
        Un codice di lunghezza di codice ripetuto di 17 modifica il
        conteggio di ripetizione del precedente come segue:
           repeat count = (8 * (repeat count - 2)) +
                          (3..10 sui prossimi 3 bit)

Si noti che un codice di 16 che segue immediatamente un 16 precedente modifica il conteggio di ripetizione precedente, che diventa il nuovo conteggio di ripetizione. Lo stesso vale per un 17 che segue un 17. È possibile una sequenza di tre o più codici 16 di fila o tre o più codici 17 di fila, modificando il conteggio ogni volta. Viene utilizzato solo il conteggio di ripetizione finale. La modifica si applica solo se segue lo stesso codice. Una ripetizione di 16 non modifica un conteggio di 17 immediatamente precedente né viceversa.

Una lunghezza di codice di 0 indica che il simbolo corrispondente nell'alfabeto non si verificherà nei dati compressi e non dovrebbe partecipare all'algoritmo di costruzione del codice prefisso dato in precedenza. Un codice prefisso complesso deve avere almeno due lunghezze di codice non zero.

Le lunghezze di bit del codice prefisso sull'alfabeto di lunghezza di codice sono compresse con il seguente codice a lunghezza variabile (Variable-Length Code) (come appare nei dati compressi, dove i bit sono analizzati da destra a sinistra):

Symbol   Code
------   ----
        00
      0111
       011
        10
        01
      1111

Possiamo ora definire il formato del codice prefisso complesso come segue:

2 bit: HSKIP, il numero di lunghezze di codice saltate, può avere valori di 0, 2 o 3. Le lunghezze saltate sono considerate zero. (Un HSKIP di 1 indica un codice prefisso semplice.)
Lunghezze di codice per i simboli nell'alfabeto di lunghezza di codice dato appena sopra, nell'ordine: 1, 2, 3, 4, 0, 5, 17, 6, 16, 7, 8, 9, 10, 11, 12, 13, 14, 15. Se HSKIP è 2, allora le lunghezze di codice per i simboli 1 e 2 sono zero, e la prima lunghezza di codice è per il simbolo 3. Se HSKIP è 3, allora la lunghezza di codice per il simbolo 3 è anche zero, e la prima lunghezza di codice è per il simbolo 4.

Le lunghezze di codice dei simboli di lunghezza di codice sono comprese tra 0 e 5, e sono rappresentate con 2..4 bit secondo il codice a lunghezza variabile sopra. Una lunghezza di codice di 0 significa che il simbolo di lunghezza di codice corrispondente non viene utilizzato.

Se HSKIP è 2 o 3, un numero rispettivo di lunghezze di codice iniziali sono zeri impliciti e non sono presenti nella sequenza di lunghezza di codice sopra.

Se ci sono almeno due lunghezze di codice non zero, tutte le lunghezze di codice zero finali sono omesse, cioè l'ultima lunghezza di codice nella sequenza deve essere non zero. In questo caso, la somma di (32 >> code length) su tutte le lunghezze di codice non zero deve essere uguale a 32.

Se le lunghezze sono state lette per l'intero alfabeto di lunghezza di codice e c'era solo una lunghezza di codice non zero, allora il codice prefisso ha un simbolo il cui codice ha lunghezza zero. In questo caso, quel simbolo non produce bit emessi dal compressore e nessun bit consumato dal decompressore. Quel singolo simbolo viene restituito immediatamente quando questo codice viene decodificato. Un esempio di dove ciò si verifica è se l'intero codice da rappresentare ha simboli di lunghezza 8. Ad esempio, un codice letterale che rappresenta tutti i valori letterali con uguale probabilità. In questo caso, il simbolo singolo è 16, che ripete la lunghezza precedente. La lunghezza precedente è considerata 8 prima che vengano lette tutte le lunghezze di codice di lunghezza di codice.
Sequenza di simboli di lunghezza di codice, che è al massimo la dimensione dell'alfabeto, codificata utilizzando il codice prefisso di lunghezza di codice. Qualsiasi 0 o 17 finale deve essere omesso, cioè l'ultimo simbolo di lunghezza di codice codificato deve essere tra 1 e 16. La somma di (32768 >> code length) su tutte le lunghezze di codice non zero nell'alfabeto, incluse quelle codificate utilizzando il/i codice/i di ripetizione di 16, deve essere uguale a 32768. Se il numero di volte per ripetere la lunghezza precedente o ripetere una lunghezza zero comporterebbe più lunghezze in totale del numero di simboli nell'alfabeto, allora il flusso dovrebbe essere rifiutato come non valido.

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