2. Panoramica della rappresentazione compressa (Compressed Representation Overview)
2. Panoramica della rappresentazione compressa (Compressed Representation Overview)
Un set di dati compressi (Compressed Data Set) è costituito da un header e una serie di meta-blocchi (Meta-blocks). Ogni meta-blocco comprime una sequenza di byte di input. L'header contiene la dimensione dei dati non compressi, se nota in anticipo, altrimenti contiene zero. Pertanto, è legale avere un flusso compresso con zero byte di header.
Un meta-blocco è costituito da un header del meta-blocco (Meta-block Header) e dati del meta-blocco (Meta-block Data). L'header del meta-blocco descrive come deve essere interpretata la parte dati. Contiene la dimensione della parte dati, insieme a due bit per segnalare se i dati sono non compressi o se si tratta dell'ultimo meta-blocco. L'interpretazione dei dati del meta-blocco dipende da questi bit.
La dimensione non compressa di un meta-blocco può essere zero. Ad esempio, un meta-blocco vuoto può essere inviato dopo un precedente meta-blocco di tipo non compresso o semplicemente per segnalare la fine dei dati.
Esistono tre diversi tipi di meta-blocchi:
Meta-blocchi compressi (Compressed meta-blocks): Questi meta-blocchi contengono dati codificati con prefisso LZ77 (LZ77 Prefix-Coded Data). Ogni meta-blocco compresso è diviso in una sezione di codici prefissi (Prefix Code Section) e una sezione dati (Data Section). La sezione di codici prefissi contiene i codici prefissi da utilizzare nella sezione dati. La sezione dati contiene una sequenza di riferimenti all'indietro LZ77 (LZ77 Backward References), letterali (Literals) e riferimenti al dizionario statico (Static Dictionary References). Ogni riferimento all'indietro LZ77 è una coppia ⟨length, distance⟩, dove length denota il numero di byte da copiare e distance denota quanti byte indietro nel flusso di dati non compressi iniziare a copiare. Una distance di 1 significa che l'ultimo byte deve essere copiato distance volte. Una distance può anche essere tradotta in una posizione nel dizionario statico. I riferimenti al dizionario statico sono riferimenti all'indietro gestiti in modo speciale; vedere la sezione 8 per i dettagli. I letterali e i riferimenti all'indietro sono memorizzati nella stessa struttura dati, chiamata codice di lunghezza di inserimento e copia (Insert-and-Copy Length Code). In questo modo, un valore determina la lunghezza di inserimento (Insert Length), che è il numero di letterali che seguono immediatamente il codice, e la lunghezza di copia (Copy Length), che è la lunghezza del successivo riferimento all'indietro. La distanza del riferimento all'indietro è determinata dal successivo codice di distanza (Distance Code). L'ultimo codice di lunghezza di inserimento e copia può avere una lunghezza di copia di 0; in questo caso, gli ultimi simboli nei dati sono valori letterali.
Meta-blocchi non compressi (Uncompressed meta-blocks): Questi meta-blocchi contengono dati non compressi (Uncompressed Data).
Meta-blocchi di meta-dati (Meta-data meta-blocks): Questi meta-blocchi sono riservati per uso futuro. Vengono saltati dal decodificatore. Questo documento non definisce il formato di questi meta-blocchi. Le applicazioni possono definire tali formati se necessario.
La struttura del meta-blocco compresso è la seguente:
-
Un tipo di blocco (Block Type) e un conteggio di blocchi (Block Count) per ciascuna delle tre categorie di letterali, lunghezze di inserimento e copia, e distanze. Il tipo di blocco ha un piccolo valore intero e identifica un insieme di codici prefissi da utilizzare per i valori di conteggio di blocchi successivi. Il conteggio di blocchi è un numero di simboli per i quali vengono utilizzati i codici prefissi e i modelli di contesto (Context Models) nel tipo di blocco corrente.
-
Un codice prefisso per i tipi di blocchi per i letterali (
BTYPE-L). -
Un codice prefisso per i conteggi di blocchi per i letterali (
BLEN-L). -
Un codice prefisso per i tipi di blocchi per le lunghezze di inserimento e copia (
BTYPE-I). -
Un codice prefisso per i conteggi di blocchi per le lunghezze di inserimento e copia (
BLEN-I). -
Un codice prefisso per i tipi di blocchi per le distanze (
BTYPE-D). -
Un codice prefisso per i conteggi di blocchi per le distanze (
BLEN-D). -
Eventualmente, un parametro di distanza
NPOSTFIXeNDIRECT(se il meta-blocco è il primo, sono impostati a 0; altrimenti possono essere impostati su qualsiasi valore non negativo, vedere la sezione 4). -
Numero di tipi di blocchi letterali
NBLTYPES-Le numero di modalità di contestoCMODE(seNBLTYPES-Lè 0, viene interpretato come 1). -
Per ciascuno dei
NBLTYPES-Ltipi di blocchi letterali:- Una modalità di contesto (zero, uno o due) per i letterali.
- Eventualmente, una mappa di contesto letterale (Literal Context Map) (se
NBLTYPES-Lè 1, la mappa di contesto non deve essere codificata; in tal caso, l'ID di contesto è sempre 0).
-
Numero di tipi di blocchi di inserimento e copia
NBLTYPES-I(se è 0, viene interpretato come 1). -
Eventualmente, una mappa di contesto di inserimento e copia (Insert-and-Copy Context Map) (se
NBLTYPES-Iè 1, la mappa di contesto non deve essere codificata; in tal caso, l'ID di contesto è sempre 0). -
Numero di tipi di blocchi di distanza
NBLTYPES-D(se è 0, viene interpretato come 1). -
Eventualmente, una mappa di contesto di distanza (Distance Context Map) (se
NBLTYPES-Dè 1, la mappa di contesto non deve essere codificata; in tal caso, l'ID di contesto è sempre 0). -
Una sequenza di codici prefissi per i letterali, il cui numero è uguale a
NBLTYPES-Lmoltiplicato per il numero di ID di contesto diversi (al massimo 64 per ogni tipo di blocco letterale). Questi codici vengono utilizzati per i letterali nei comandi successivi. -
Una sequenza di codici prefissi per le lunghezze di inserimento e copia, il cui numero è uguale a
NBLTYPES-Imoltiplicato per il numero di ID di contesto diversi (al massimo 256 per ogni tipo di blocco di inserimento e copia). Questi codici vengono utilizzati per i comandi successivi. -
Una sequenza di codici prefissi per le distanze, il cui numero è uguale a
NBLTYPES-Dmoltiplicato per il numero di ID di contesto diversi (4 per ogni tipo di blocco di distanza). Questi codici vengono utilizzati per le distanze nei comandi successivi. -
Flusso di dati (Data Stream) con comandi di cambio di blocco (Block-Switch Commands), letterali, lunghezze di inserimento e copia, e distanze.
La struttura dei blocchi (Block Structure) aiuta la compressione partizionando l'input in distribuzioni di alfabeto separate (Alphabet Distributions) con i tipi di blocchi. I tipi di blocchi per i letterali e le distanze possono essere ulteriormente partizionati in distribuzioni diverse utilizzando contesti. Le mappe di contesto per tipo di blocco controllano quale codice prefisso viene utilizzato con contesti diversi.
L'intuizione dietro il cambio di blocco (Block Switching) è che diverse regioni dell'input sono probabilmente caratterizzate da statistiche diverse (ad esempio, HTML rispetto a JavaScript in una pagina Web). Può esserci più di un tipo di blocco in un particolare meta-blocco per ogni categoria (letterali, lunghezze di inserimento e copia, e distanze), quindi il cambio di blocco può essere utilizzato per adattare le distribuzioni dei codici prefissi senza avviare un nuovo meta-blocco. Ogni tipo di blocco può avere più distribuzioni di codici prefissi per i letterali e le distanze basate sulla modellazione del contesto (Context Modeling).
Fonte (Source): RFC 7932, Section 2
Testo ufficiale (Official Text): https://www.rfc-editor.org/rfc/rfc7932.txt