4. Entropy Encoding (Codifica dell'entropia)

Il formato Zstandard utilizza due tipi di codifica dell'entropia: FSE e codifica di Huffman. Huffman viene utilizzato per comprimere i letterali (Literals), mentre FSE viene utilizzato per tutti gli altri simboli (Literals_Length_Code, Match_Length_Code e codici di offset) e per comprimere gli header Huffman.

4.1 FSE (Entropia a Stati Finiti)

FSE, abbreviazione di Finite State Entropy (Entropia a Stati Finiti), è un codec di entropia basato su [ANS]. La codifica/decodifica FSE coinvolge uno stato (State) che viene trasportato tra i simboli, quindi la decodifica deve essere eseguita nella direzione opposta rispetto alla codifica. Pertanto, tutti i flussi di bit FSE (Bitstreams) vengono letti dalla fine all'inizio. Si noti che l'ordine dei bit nel flusso non è invertito; vengono semplicemente letti nell'ordine inverso rispetto a quello in cui sono stati scritti.

Per ulteriori dettagli su FSE, vedere "FiniteStateEntropy" [FSE].

La decodifica FSE coinvolge una tabella di decodifica (Decoding Table) che ha una dimensione in potenza di 2 e contiene tre elementi: Symbol (Simbolo), Num_Bits (Numero di bit) e Baseline (Linea di base). Il logaritmo in base 2 della dimensione della tabella è il suo Accuracy_Log (Log di precisione). Un valore di stato FSE rappresenta un indice in questa tabella.

Per ottenere il valore di stato iniziale, consumare Accuracy_Log bit dal flusso come valore little-endian. Il simbolo successivo nel flusso è il Symbol indicato nella tabella per quello stato. Per ottenere il valore di stato successivo, il decoder dovrebbe consumare Num_Bits bit dal flusso come valore little-endian e aggiungerlo a Baseline.

4.1.1 FSE Table Description (Descrizione della tabella FSE)

Per decodificare i flussi FSE, è necessario costruire la tabella di decodifica. Il formato Zstandard codifica le descrizioni delle tabelle FSE come descritto qui.

Una tabella di distribuzione FSE (Distribution Table) descrive le probabilità di tutti i simboli da 0 all'ultimo presente (incluso) su una scala normalizzata di (1 << Accuracy_Log). Si noti che devono esserci due o più simboli con probabilità diversa da zero.

Un flusso di bit viene letto in avanti, in modo little-endian. Non è necessario conoscerne la dimensione esatta, poiché la dimensione sarà scoperta e riportata dal processo di decodifica. Il flusso di bit inizia riportando su quale scala opera. Se low4bits designa i 4 bit più bassi del primo byte, allora Accuracy_Log = low4bits + 5.

Questo è seguito da ciascun valore di simbolo, da 0 all'ultimo presente. Il numero di bit utilizzati da ciascun campo è variabile e dipende da:

Probabilità rimanenti + 1 : Ad esempio, presumendo un Accuracy_Log di 8 e presumendo che siano già stati distribuiti 100 punti di probabilità, il decoder può leggere qualsiasi valore da 0 a (256 - 100 + 1) == 157, incluso. Pertanto, deve leggere log₂(157) == 8 bit.

Valore decodificato : I valori piccoli usano 1 bit in meno. Ad esempio, presumendo che i valori da 0 a 157, inclusi, siano possibili, rimangono 255 - 157 = 98 valori in un campo di 8 bit. I primi 98 valori (quindi da 0 a 97) usano solo 7 bit, e i valori da 98 a 157 usano 8 bit. Questo è ottenuto attraverso lo schema nella tabella 20:

+============+===============+===========+
| Value Read | Value Decoded | Bits Used |
+============+===============+===========+
|   0 - 97   |     0 - 97    |     7     |
+------------+---------------+-----------+
|  98 - 127  |    98 - 127   |     8     |
+------------+---------------+-----------+
| 128 - 225  |     0 - 97    |     7     |
+------------+---------------+-----------+
| 226 - 255  |   128 - 157   |     8     |
+------------+---------------+-----------+

Tabella 20: Valori decodificati

Le probabilità dei simboli vengono lette una per una, in ordine. La probabilità è ottenuta dal valore decodificato (Value Decoded) usando la formula P = Value - 1. Questo significa che il valore 0 diventa la probabilità negativa -1. Questa è una probabilità speciale che significa "minore di 1". Il suo effetto sulla tabella di distribuzione è descritto di seguito. Ai fini del calcolo dei punti di probabilità totali allocati, conta come 1.

Quando un simbolo ha una probabilità di zero, è seguito da un flag di ripetizione (Repeat Flag) di 2 bit. Questo flag di ripetizione indica quante probabilità di zero seguono quella corrente. Fornisce un numero che va da 0 a 3. Se è un 3, segue un altro flag di ripetizione di 2 bit, e così via.

Quando l'ultimo simbolo raggiunge un totale cumulativo di (1 << Accuracy_Log), la decodifica è completa. Se l'ultimo simbolo fa superare il totale cumulativo (1 << Accuracy_Log), la distribuzione è considerata corrotta.

Infine, il decoder può determinare quanti byte sono stati utilizzati in questo processo e quanti simboli sono presenti. Il flusso di bit consuma un numero intero di byte. Qualsiasi bit rimanente nell'ultimo byte è semplicemente inutilizzato.

Il contesto in cui la tabella deve essere utilizzata specifica un numero atteso di simboli. Quel numero atteso di simboli non supera mai 256. Se il numero di simboli decodificati non è uguale a quello atteso, l'header dovrebbe essere considerato corrotto.

La distribuzione delle probabilità normalizzate è sufficiente per creare una tabella di decodifica unica. La tabella ha una dimensione di (1 << Accuracy_Log). Ogni cella descrive il simbolo decodificato e le istruzioni per ottenere lo stato successivo.

I simboli vengono scansionati nel loro ordine naturale per le probabilità "minore di 1" come descritto sopra. Ai simboli con questa probabilità viene assegnata una singola cella, partendo dalla fine della tabella e retrocedendo. Questi simboli definiscono un reset completo dello stato (Full State Reset), leggendo Accuracy_Log bit.

Tutti i simboli rimanenti vengono allocati nel loro ordine naturale. Partendo dal simbolo 0 e dalla posizione di tabella 0, ogni simbolo riceve tante celle quante la sua probabilità. L'allocazione delle celle è distribuita, non lineare; ogni posizione successiva segue questa regola:

position += (tableSize >> 1) + (tableSize >> 3) + 3;
position &= tableSize - 1;

Una posizione viene saltata se è già occupata da un simbolo con probabilità "minore di 1". La posizione non si resetta tra i simboli; itera semplicemente attraverso ogni posizione nella tabella, passando al simbolo successivo quando sono stati allocati abbastanza stati a quello corrente.

Il risultato è una lista di valori di stato. Ogni stato decodificherà il simbolo corrente.

Per ottenere il Number_of_Bits e la Baseline richiesti per lo stato successivo, è prima necessario ordinare tutti gli stati nel loro ordine naturale. Gli stati inferiori avranno bisogno di 1 bit in più rispetto a quelli superiori. Il processo viene ripetuto per ogni simbolo.

Ad esempio, presumendo che un simbolo abbia una probabilità di 5, riceve cinque valori di stato. Gli stati vengono ordinati in ordine naturale. La potenza di 2 successiva è 8. Lo spazio delle probabilità è diviso in 8 parti uguali. Presumendo che l'Accuracy_Log sia 7, questo definisce 128 stati, e ogni quota (divisa per 8) ha una dimensione di 16. Per raggiungere 8, 8 - 5 = 3 stati più bassi conteranno "doppio", raddoppiando il numero di quote (larghezza 32), richiedendo 1 bit in più nel processo.

La Baseline viene assegnata partendo dagli stati superiori che usano meno bit, procedendo naturalmente, quindi riprendendo dal primo stato, ognuno prendendo la sua larghezza allocata dalla Baseline.

+----------------+-------+-------+--------+------+-------+
|  state order   |   0   |   1   |   2    |  3   |   4   |
+----------------+-------+-------+--------+------+-------+
|     width      |   32  |   32  |   32   |  16  |   16  |
+----------------+-------+-------+--------+------+-------+
| Number_of_Bits |   5   |   5   |   5    |  4   |   4   |
+----------------+-------+-------+--------+------+-------+
|  range number  |   2   |   4   |   6    |  0   |   1   |
+----------------+-------+-------+--------+------+-------+
|    Baseline    |   32  |   64  |   96   |  0   |   16  |
+----------------+-------+-------+--------+------+-------+
|     range      | 32-63 | 64-95 | 96-127 | 0-15 | 16-31 |
+----------------+-------+-------+--------+------+-------+

Tabella 21: Assegnazioni Baseline

Lo stato successivo è determinato dallo stato corrente leggendo il Number_of_Bits richiesto e aggiungendo la Baseline specificata.

Vedere l'Appendice A per i risultati di questo processo applicati alle distribuzioni predefinite.

4.2 Huffman Coding (Codifica di Huffman)

I flussi codificati Huffman di Zstandard vengono letti all'indietro, simili ai flussi di bit FSE. Pertanto, per trovare l'inizio del flusso di bit, è necessario conoscere l'offset dell'ultimo byte del flusso codificato Huffman.

Dopo aver scritto l'ultimo bit contenente informazioni, il compressore scrive un singolo bit 1 e quindi riempie il resto del byte con bit 0. L'ultimo byte del flusso di bit compresso non può essere 0 per questo motivo.

Durante la decompressione, l'ultimo byte contenente il riempimento è il primo byte da leggere. Il decompressore deve saltare fino a 7 bit di riempimento 0 così come il primo bit 1 che si verifica. Successivamente, inizia la parte utile del flusso di bit.

Il flusso di bit contiene simboli codificati Huffman in ordine little-endian, con i codici definiti dal metodo seguente.

4.2.1 Huffman Tree Description (Descrizione dell'albero di Huffman)

La codifica a prefisso (Prefix Coding) rappresenta i simboli da un alfabeto noto a priori mediante sequenze di bit (parole di codice), una parola di 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 inequivocabile, simbolo per simbolo.

Dato un alfabeto con frequenze di simboli note, l'algoritmo di Huffman consente la costruzione di un codice a prefisso ottimale utilizzando il minor numero di bit di tutti i possibili codici a prefisso per quell'alfabeto.

Il codice a prefisso non deve superare una lunghezza massima del codice. Più bit migliorano la precisione ma producono una dimensione dell'header maggiore e richiedono più memoria o operazioni di decodifica più complesse. Questa specifica limita la lunghezza massima del codice a 11 bit.

Tutti i valori letterali da zero (incluso) all'ultimo presente (escluso) sono rappresentati da Weight (Peso) con valori da 0 a Max_Number_of_Bits. La trasformazione da Weight a Number_of_Bits segue questo pseudocodice:

if Weight == 0:
    Number_of_Bits = 0
else:
    Number_of_Bits = Max_Number_of_Bits + 1 - Weight

Il Weight dell'ultimo simbolo è dedotto da quelli precedentemente decodificati, completando alla potenza di 2 più vicina. Questa potenza di 2 fornisce Max_Number_of_Bits, la profondità dell'albero corrente.

(Continuazione con tabelle 22-26 e dettagli della codifica Huffman)

---