Metodo di codifica semplice ( CODIFICA DELLA LUNGHEZZA DI ESECUZIONE), che viene utilizzato con successo dagli archivisti popolari.
Questo metodo si basa sul conteggio della lunghezza dei caratteri ripetuti in una riga e sulla scrittura di informazioni come il numero di caratteri e il carattere ripetuto stesso in un file compresso invece di una sequenza di questi caratteri. Ad esempio, c'è una stringa come " AAAAABBCCCCADDDEEL". Sarà confezionato in una sequenza come" 5A3B3CADDEEL". Come puoi vedere dall'esempio, una sequenza di 5 lettere" A "è stata compressa in due caratteri" 5 "e" A ", e le sequenze" DD "," EE "," L "non erano affatto impacchettate , poiché non c'è alcun vantaggio dalla sostituzione di questi caratteri con una sequenza di tipo "lunghezza" + "lettera".
Quando si realizza l'impacchettamento di un file utilizzando questo metodo, sorgono le seguenti difficoltà: come l'unpacker distinguerà le informazioni di controllo dal file compresso dai dati decompressi. Ad esempio, come nel caso discusso sopra, l'unpacker distinguerà il carattere di controllo "5" da un carattere decompresso con lo stesso codice? Ci sono due opzioni per risolvere questo problema:
(IO)... Trova un simbolo che si incontra meno degli altri o che non compare affatto nel file compresso e utilizzalo come controllo. Chiamiamolo prefisso per comodità nella seguente spiegazione. Ora la sequenza "AAAA" dal packer verrà convertita in un prefisso (8 bit), "A" (8 bit), numero (8 bit), ovvero 5 byte verranno sostituiti da tre. Se viene rilevato un bit con un codice prefisso nel file sorgente durante il confezionamento, nel file risultante vengono scritti due byte con un codice prefisso e con questo segno l'unpacker determinerà dove il prefisso è un simbolo e dove si trova informazioni di controllo. Sono possibili modifiche a questo metodo, ad esempio:
1. Codificare la quantità non in otto bit, ma tre, quattro e così via, che aumenterà la percentuale di impacchettamento, ma allo stesso tempo limiterà la lunghezza massima dei caratteri ripetuti che possono essere compressi nel caso di codifica a tre bit (da 3 a 10, ovvero . 000 = 3, ..., 111 = 10) e se la lunghezza è superiore a 10 caratteri, comprimere dieci caratteri ciascuno.
2. Una seconda modifica è possibile, quando il numero di caratteri ripetuti è codificato non da otto bit, ma da tre bit, e la lunghezza dei caratteri ripetuti è limitata dal numero pari a 265. Si pone il problema di come codificare 256 lunghezze diverse in 3 bit. Si scopre che è possibile, ma solo nell'intervallo da 3 a 9, se la lunghezza dei caratteri ripetuti è superiore a 9, vengono scritti tre bit "111" in codice binario, che è uguale a "7". Ciò significa che la vera lunghezza della sequenza è nel byte successivo (8 bit sono allocati per lunghezze da 10 a 256 caratteri).
Ecco alcuni esempi:
Abbiamo sequenze:
a) "AAAABBBBBBBBBBCCAAAAAAAAAAAAAAA"
b) "CBBBBBBBBBBEEEEEEEEEEE"
Impacchettali:
1.Utilizzare il metodo RLE (codifica run-length - pacchetto di byte ripetuti).
a) Prendiamo un prefisso uguale a "D", otteniamo:
RE, RE, LA, 5, RE, SI, 10, DO, RE, LA, 15.Percentuale di compressione = 12 byte / 32 byte = 37,5%
In un file compresso, il primo byte è il byte del prefisso, in modo che l'unpacker sappia quale byte è un prefisso.
b) Prendi un prefisso uguale ad "A", anche se in realtà il packer non lo farà, poiché non ci sono molti caratteri in questa sequenza, quindi l'archivator prenderà un carattere inutilizzato come prefisso.
Sequenza confezionata:
"A", "C", "A", "B", 10, "A", "E", 10, "A", "A"Percentuale di compressione = 10 byte / 22 byte = 45,5%
2. Ora impacchettiamo le stesse righe per la modifica 1 del metodo RLE con gli stessi valori di prefisso per analizzare l'efficienza.
"D", "D", "A", 2, "D", "B", 7,
8 bit 8 bit 8 bit 3 bit 8 bit 8 bit 3 bit"RE", "LA", 7, "RE", "LA", 2
8 bit 8 bit 3 bit 8 bit 8 bit 3 bitPercentuale di compressione = 84 bit / (22 * 8) bit = 32,8%
"A", "C", "A", "B", 7, "A", "E", 7, "A", "A"
8 bit 8 bit 8 bit 8 bit 4 bit 8 bit 8 bit 3 bit 8 bit 8 bitPercentuale di compressione = 70 bit / (22 * 8) bit = 39,8%
3. Ora controlliamo l'efficacia dell'ultima modifica:
a) Sequenza compatta:
"D", "D", "A", 2, "D", "B", 7, 0
8 bit 8 bit 8 bit 3 bit 8 bit 8 bit 3 bit 8 bit"RE", "LA", 7, 5
8 bit 8 bit 3 bit 8 bitPercentuale di compressione = 81 bit / (32 * 8) bit = 31,6%
b) Sequenza compatta:
"A", "C", "A", "B", 7, 0, "A", "E"
8 bit 8 bit 8 bit 8 bit 3 bit 8 bit 8 bit 8 bit7, 0, "LA", "LA"
3 bit 8 bit 8 bit 8 bitPercentuale di compressione = 86 bit / (22 * 8) bit = 48,9%
Da questi esempi si può vedere che a seconda del contenuto dei dati compressi, l'uno o l'altro algoritmo è efficace, quindi, per scegliere quale algoritmo è più efficace, è necessario verificarli su diversi tipi di file.
(ii)... La seconda opzione per registrare le informazioni di controllo per l'unpacker è la seguente: se si incontra un singolo carattere nel testo, viene scritto un bit di controllo nel file di output, che è uguale a uno e questo carattere stesso. Se viene rilevata una sequenza di byte ripetuti, ad esempio "AAAAAA", l'informazione compressa sarà simile a questa: 0 (1 bit), byte A (8 bit), numero (3-8 bit);
Facciamo un esempio per chiarezza. Per questo prendiamo le sequenze degli esempi precedenti.
1) Il numero di byte ripetuti è codificato in 8 bit.
a) 0, "A", 5, 0, "B", 10, 1, "C", 1, "C", 0, "A", 15
1b. 8b. 8b. 1b. 8b. 8b. 1b. 8b. 1b. 8b. 1b. 8b. 8b.Percentuale di compressione = 71 bit / 256 bit = 27,7%
b) 1, "C", 0, "B", 10, 0, "E", 10, 1, "A"
1b. 8b. 1b. 8b. 8b. 1b. 8b. 8b. 1b. 8b.Percentuale di compressione = 52 bit / 176 bit = 29,5%
2) Ora prendiamo 3 bit per codificare il numero di byte ripetuti, in cui puoi codificare valori da 2 a 8 (0 - 6), se la lunghezza della sequenza ripetuta è maggiore, allora questi tre bit contengono "111 " (7-decimal) e la lunghezza reale è nel byte successivo (lunghezza da 9 a 264).
a) 0, "A", 3, 0, "B", 7, 1, 0, "C", 0, 0, "A", 7, 6
1b. 8b. 3b. 1b. 8b. 3b. 8b. 1b. 8b. 3b. 1b. 8b. 3b. 8b.Percentuale di compressione = 64 bit / 256 bit = 20,3%
b) 1, "C", 0, "B", 7, 1, 0, "E", 7, 1, 1, "LA"
1b. 8b. 1b. 8b. 3b. 8b. 1b. 8b. 3b. 8b. 1b. 8b.Percentuale di compressione = 58 bit / 176 bit = 33%
Se la grandezza è codificata in 4 bit (2..16), allora
1, "C", 0, "B", 8, 0, "E", 8, 1, "LA"
1b. 8b. 1b. 8b. 4b. 1b. 8b. 4b. 1b. 8b.Percentuale di compressione = 44 bit / 176 bit = 25%
Come puoi vedere dagli esempi, la seconda opzione di impacchettamento è più efficiente, poiché comprime le sequenze che iniziano con due caratteri, che di solito sono la stragrande maggioranza. La prima opzione racchiudeva le sequenze che iniziavano con tre caratteri.
Classificazione di base degli algoritmi di compressione reversibile
Esistono molte pratiche di compressione senza perdita di dati che generalmente hanno un'efficienza diversa per i diversi tipi di dati e per le diverse dimensioni. Tuttavia, questi metodi si basano su tre principali schemi di compressione classici:
Codifica della serie di sequenze (RLE);
Metodi di compressione statistica;
Metodi di compressione del dizionario (euristico).
Compressione per codifica in serie: algoritmo RLE
L'approccio semplice e l'algoritmo più famosi per comprimere le informazioni in modo reversibile è Run Length Encoding (RLE). L'essenza dei metodi di questo approccio consiste nel sostituire stringhe o serie di byte ripetuti o le loro sequenze con un byte di codifica e un contatore del numero delle loro ripetizioni. Il problema con tutti i metodi analoghi è determinare il modo in cui l'algoritmo di decompressione potrebbe distinguere le serie codificate nel flusso di byte risultante dalle altre, le sequenze di byte non codificate. La soluzione al problema si ottiene solitamente mettendo dei segni all'inizio delle stringhe codificate. Tali etichette possono essere, ad esempio, valori di bit caratteristici nel primo byte di un'esecuzione codificata, valori del primo byte di un'esecuzione codificata, ecc. Questi metodi, di regola, sono abbastanza efficaci per comprimere immagini grafiche raster (BMP, PCX, TIF, GIF), perché questi ultimi contengono molte lunghe serie di sequenze ripetute di byte. Lo svantaggio del metodo RLE è il rapporto di compressione piuttosto basso o il costo di codificare file con un numero ridotto di serie e, peggio ancora, con un numero ridotto di byte ripetuti in una serie.
L'algoritmo RLE si basa sull'idea di rilevare sequenze di dati ripetute e di sostituirle con una struttura più semplice, che specifica il codice dei dati e la velocità di ripetizione. Ad esempio, supponiamo che ti venga fornita una sequenza di dati soggetta a compressione: 1 1 1 1 2 2 3 4 4 4 ... L'algoritmo RLE propone di sostituirlo con la seguente struttura: 1 4 2 2 3 1 4 3 dove il primo numero di ogni coppia di numeri è il codice dati e il secondo è la frequenza di ripetizione. Se viene allocato 1 byte per memorizzare ogni elemento di dati della sequenza di input, l'intera sequenza occuperà 10 byte di memoria, mentre la sequenza di output (versione compressa) occuperà 8 byte di memoria. È chiaro che l'algoritmo RLE fornirà un migliore effetto di compressione quando la lunghezza della sequenza di dati ripetitiva è maggiore. Nel caso dell'esempio precedente, se la sequenza di input è simile a questa: 1 1 1 1 1 1 3 4 4 4, il rapporto di compressione sarà del 60%. A questo proposito, la maggiore efficienza dell'algoritmo RLE si ottiene durante la compressione dei dati grafici (soprattutto per le immagini monocromatiche).
Algoritmi euristici (dizionario) compression (LZ, LZW) cerca nel file le righe che si ripetono e costruisce un dizionario di frasi che sono già state incontrate. Di solito, tali algoritmi hanno un numero di parametri specifici (dimensione del buffer, lunghezza massima della frase, ecc.), La cui selezione dipende dall'esperienza dell'autore dell'opera e questi parametri sono selezionati in modo tale da ottenere il rapporto ottimale tra il tempo di funzionamento dell'algoritmo, il rapporto di compressione e l'elenco dei file che si restringono bene.
Algoritmi statistici(Huffman, Shannon-Fano, aritmetica) Gli algoritmi statistici utilizzano un modello di dati statistici e la qualità della compressione delle informazioni dipende direttamente da quanto è buono questo modello. Prendere in considerazione le proprietà statistiche dei dati nel caso più semplice significa utilizzare codici non uniformi per la codifica: i simboli frequenti sono codificati in codici brevi e raramente - in codici lunghi. Cioè, tali algoritmi richiedono la conoscenza delle probabilità di comparsa dei caratteri nell'immagine, una stima della quale può essere, nel caso semplice, la frequenza di comparsa dei caratteri nei dati di input. In genere, queste probabilità sono sconosciute. Lo scopo della codifica è convertire il flusso di input in un flusso di bit di lunghezza minima, che si ottiene riducendo l'entropia (caos) del flusso di input tenendo conto delle frequenze dei simboli.
La lunghezza del codice che rappresenta i caratteri dell'alfabeto del flusso deve essere proporzionale alla quantità di informazioni nel flusso di input e la lunghezza dei simboli del flusso in bit non può essere un multiplo di 8 o addirittura variabile. Se è nota la distribuzione di probabilità delle frequenze di occorrenza dei simboli dall'alfabeto del flusso di input, è possibile costruire un modello di codifica ottimale. Tuttavia, a causa dell'esistenza di un numero enorme di formati di file diversi, l'attività diventa molto più complicata. la distribuzione di frequenza dei simboli di dati non è nota in anticipo. In questo caso vengono utilizzati due approcci.
Primo consiste nel visualizzare il flusso di input e costruire una codifica basata sulle statistiche raccolte (questo richiede due passaggi attraverso il file - uno per visualizzare e raccogliere informazioni statistiche, il secondo per la codifica, il che limita in qualche modo la portata di tali algoritmi, perché, quindi, elimina la possibilità di una codifica "al volo" in un solo passaggio, utilizzata nei sistemi di telecomunicazione, dove a volte la quantità di dati non è nota e la loro ritrasmissione o analisi può richiedere tempi irragionevolmente lunghi). In tal caso, lo schema statistico della codifica utilizzata viene scritto nel flusso di output. Questa tecnica è nota come codifica statica di Huffman. Una tabella dei simboli viene trasferita con il file compresso. Tali algoritmi sono abbastanza buoni per comprimere la maggior parte dei file, ma è necessario un ulteriore trasferimento della tabella di frequenza dei simboli, nonché la necessità di due passaggi del file sorgente per raccogliere statistiche e comprimere.
Metodo due- metodo di codifica adattivo. Il suo principio è cambiare lo schema di codifica a seconda della natura dei cambiamenti nel flusso di input. Adattivo: iniziano a lavorare con una tabella iniziale fissa di frequenze dei simboli (di solito tutti i simboli sono inizialmente ugualmente probabili) e nel processo questa tabella cambia a seconda dei simboli che si trovano nel file. Vantaggi: algoritmo a passaggio singolo, non ha bisogno di trasferire una tabella di frequenze dei simboli, comprime un'ampia classe di file in modo abbastanza efficiente. Questo approccio ha un algoritmo a passaggio singolo e non richiede la memorizzazione di informazioni sulla codifica utilizzata in una forma esplicita. La codifica adattiva può fornire un rapporto di compressione più elevato rispetto alla codifica statica, poiché i cambiamenti nelle frequenze del flusso di input vengono presi in considerazione in modo più completo. Questa tecnica è nota come codifica dinamica di Huffman.
In quest'ottica, gli algoritmi statistici possono essere suddivisi in tre classi:
1. Non adattivo: utilizzano probabilità di simboli fisse e predeterminate. La tabella delle probabilità dei simboli non viene trasmessa con il file, poiché è nota in anticipo. Svantaggio: area di utilizzo ristretta per una tabella di frequenza specifica, per la quale si ottiene un rapporto di compressione accettabile.
2. Semi-adattivo: viene creata una tabella di frequenza dei simboli per ciascun file e il file viene compresso in base ad esso. Una tabella dei simboli viene trasferita con il file compresso. Tali algoritmi sono abbastanza buoni per comprimere la maggior parte dei file, ma è necessario un ulteriore trasferimento della tabella di frequenza dei simboli, nonché la necessità di due passaggi del file sorgente per raccogliere statistiche e comprimere.
3. Adattivo: iniziano a lavorare con una tabella iniziale fissa di frequenze dei simboli (di solito tutti i simboli sono inizialmente ugualmente probabili) e nel processo di lavoro questa tabella cambia a seconda dei simboli che si trovano nel file. Vantaggi: algoritmo a passaggio singolo, non ha bisogno di trasferire una tabella di frequenze dei simboli, comprime un'ampia classe di file in modo abbastanza efficiente.
L'algoritmo di Huffman si basa sull'idea della codifica in gruppi di bit. Innanzitutto, viene eseguita un'analisi di frequenza della sequenza di dati di input, ovvero viene impostata la frequenza di occorrenza di ciascun simbolo trovato in essa. Successivamente, i simboli vengono ordinati in base alla frequenza decrescente di occorrenza.
L'idea di base è la seguente: più spesso un carattere si verifica, meno bit è codificato. Il risultato della codifica viene inserito nel dizionario richiesto per la decodifica. Diamo un'occhiata a un semplice esempio per illustrare come funziona l'algoritmo di Huffman.
Nella codifica Huffman statica, i simboli di input (stringhe di bit di diversa lunghezza) sono associati a stringhe di bit e anche a lunghezza variabile - i loro codici. La lunghezza del codice di ogni simbolo è presa proporzionale al logaritmo binario della sua frequenza, presa con il segno opposto. E l'insieme comune di tutti i diversi simboli incontrati costituisce l'alfabeto del torrente. Questa codifica è un prefisso, il che semplifica la decodifica nel flusso dei risultati, perché, con la codifica del prefisso, il codice di qualsiasi carattere non è un prefisso del codice di qualsiasi altro carattere: l'alfabeto è unico.
Anche 10-15 anni fa, gli archivi venivano utilizzati principalmente per risparmiare spazio sui dischi rigidi e per inserire la massima quantità di dati su un floppy disk. Tuttavia, i tempi sono cambiati. Nessuno ha utilizzato floppy disk come mezzo per trasferire e archiviare informazioni da molto tempo e il costo delle unità è diventato così basso che nessuno pensa nemmeno a comprimere i dati per risparmiare spazio. Inoltre, i volumi di dati sono diventati così grandi che archiviarli e rimuoverli dall'archiviazione per risparmiare spazio è semplicemente impraticabile, poiché richiede molto tempo. Oggi, infatti, la quantità di dati sui drive degli utenti si misura in terabyte. Ora immagina quanto tempo ci vorrà per archiviare un terabyte di dati. Ci vorranno non una o anche due ore, ma almeno 10-12 ore, cioè il computer dovrà essere lasciato acceso tutta la notte.
Sembrerebbe che gli archivisti oggi debbano gradualmente perdere la loro rilevanza. Ma non succede niente del genere. La stragrande maggioranza degli utenti, tra gli altri programmi, ha installato gli archivi o utilizza l'archiviatore integrato nel sistema operativo Windows (non consideriamo altri sistemi operativi in questa pubblicazione).
Il fatto è che lo scopo degli archivi è cambiato. Oggi vengono utilizzati principalmente per caricare dati sul Web. La maggior parte dei driver sui siti Web dei produttori sono disposti in archivi e anche la maggior parte dei programmi su varie risorse sono archiviati. A proposito, l'utente stesso, prima di caricare qualsiasi dato sulla rete (ad esempio, su risorse di condivisione di file), comprime i dati in un archivio.
Per quanto riguarda il mercato russo, i nostri archivi più comuni sono tre: WinRAR, WinZip e 7-Zip, presentati in entrambe le versioni a 32 e 64 bit. Li confronteremo in questo articolo. Tuttavia, prima esamineremo brevemente alcuni aspetti teorici del lavoro degli archivisti.
Algoritmi di compressione delle informazioni
L'essenza di qualsiasi algoritmo di compressione delle informazioni consiste nel fatto che mediante una qualche trasformazione dell'insieme iniziale di bit di informazione, all'uscita, si ottiene un certo insieme di dimensioni inferiori. Inoltre, tutti gli algoritmi di conversione dei dati possono essere suddivisi condizionatamente in due classi: reversibili e irreversibili.
Per algoritmo di compressione irreversibile delle informazioni si intende una tale trasformazione della sequenza di bit originale in cui la sequenza di output di dimensioni inferiori non consente di ricostruire accuratamente la sequenza di input. Vengono utilizzati algoritmi di compressione irreversibili, ad esempio, in relazione a dati grafici, video e audio, e questo porta sempre a una perdita della loro qualità. Naturalmente, gli algoritmi di compressione dei dati irreversibili non vengono utilizzati negli archivi e quindi non li prenderemo in considerazione in futuro.
Gli algoritmi di compressione dei dati reversibili consentono di ricostruire con precisione la sequenza di dati originale dalla sequenza compressa. Sono questi algoritmi che vengono utilizzati negli archivi. Le caratteristiche comuni di tutti gli algoritmi di compressione sono il rapporto di compressione (il rapporto tra i volumi della sequenza di dati originale e compresso), il tasso di compressione (il tempo necessario per archiviare una certa quantità di dati) e la qualità di compressione (il valore che mostra quanto viene compressa la sequenza di dati applicandovi la ricompressione secondo lo stesso o un diverso algoritmo).
La teoria della compressione delle informazioni, nota anche come teoria della codifica economica dell'informazione discreta, è una branca piuttosto complessa della scienza matematica. Naturalmente, la presentazione anche delle sue basi va ben oltre lo scopo di questo articolo, e quindi prenderemo in considerazione solo superficialmente vari algoritmi di compressione delle informazioni senza entrare nei dettagli. Inoltre, oggi sono stati sviluppati molti algoritmi di compressione dei dati e anche la loro considerazione è inclusa nel nostro compito. Pertanto, parleremo solo a livello qualitativo di diversi algoritmi che consentono di avere un'idea generale dei metodi di compressione delle informazioni.
Algoritmo RLE
Uno dei metodi di compressione delle informazioni più antichi e semplici è l'algoritmo RLE (Run Length Encoding), ovvero un algoritmo per la codifica di una serie di sequenze. Questo metodo è molto semplice da implementare ed è uno degli algoritmi di archiviazione, e la sua essenza è sostituire una serie (gruppo) di byte ripetuti con un byte di codifica e un contatore del numero delle loro ripetizioni. Cioè, un gruppo di byte identici verrà sostituito da una coppia:<счетчик повторений, значение>, che riduce la ridondanza dei dati.
In questo algoritmo il contatore è indicato da quelli nei due bit superiori del byte letto. Ad esempio, se i primi due bit sono 11, allora i restanti 6 bit vengono assegnati a un contatore, che può assumere valori da 1 a 64. Di conseguenza, con soli due byte si può determinare una serie di 64 byte ripetuti, che è, compresso 32 volte.
Esiste un'altra variante dell'implementazione di questo algoritmo, quando l'attributo counter è 1 nel primo byte del contatore. In questo caso il contatore può assumere un valore massimo di 127, e quindi il rapporto di compressione massimo sarà 64.
È chiaro che l'algoritmo RLE è efficace solo quando è presente un numero elevato di gruppi lunghi di byte identici. Se i byte non vengono ripetuti, l'utilizzo del metodo RLE aumenta la dimensione del file.
RLE è generalmente molto efficace per comprimere grafica bitmap (BMP, PCX, TIF, GIF) perché contiene molte lunghe serie di sequenze di byte ripetitive.
Limitazione dell'alfabeto delle informazioni
Un altro metodo abbastanza semplice per comprimere le informazioni può essere chiamato limitazione dell'alfabeto delle informazioni. Immediatamente, notiamo che un tale algoritmo non è stato implementato nella pratica, ma la presentazione di questo metodo aiuterà a comprendere meglio il metodo dei codici a lunghezza variabile.
In quanto segue, sotto l'alfabeto delle informazioni, si intende l'insieme di caratteri utilizzati per codificare la sequenza delle informazioni. Ad esempio, supponiamo che ci sia un messaggio di testo. Per codificare ogni lettera di questo messaggio viene utilizzata una tabella ASCII di 256 caratteri. In questo caso vengono allocati esattamente 8 bit (1 byte) per la codifica di ciascun carattere. In questo caso, l'alfabeto delle informazioni è composto da tutti i 256 caratteri della tabella di codifica ASCII.
È chiaro che non tutti i 256 caratteri della tabella ASCII possono essere utilizzati nel messaggio di testo originale. Ad esempio, se stiamo parlando di un messaggio di testo in russo, in cui non ci sono numeri, sono sufficienti 64 caratteri (33 lettere minuscole e 31 lettere maiuscole). Se aggiungi segni di punteggiatura, segni di paragrafo e nuove righe a questo, diventa chiaro che il numero di caratteri non supererà 100. In questo caso, puoi usare la codifica dei caratteri non a 8, ma a 7 bit, che ti consente di ottenere un tabella di 128 caratteri. Cioè, limitiamo in qualche modo l'alfabeto delle informazioni, grazie al quale possiamo ridurre la profondità di bit di ciascun carattere da collocare. Puoi andare oltre: determinare con precisione il numero di caratteri utilizzati in un messaggio di testo. Se, ad esempio, risulta che nel messaggio sono coinvolti solo 30 caratteri (inclusi i caratteri di nuova riga), è possibile utilizzare una tabella di codifica a 5 bit contenente 32 caratteri, quindi il rapporto di compressione del messaggio di testo diventerà ancora maggiore . In effetti, se il messaggio originale utilizza la codifica dei caratteri a 8 bit e quello compresso utilizza la codifica a 5 bit, il rapporto di compressione sarà 8/5.
Nonostante l'apparente semplicità del metodo per limitare l'alfabeto, in pratica non viene utilizzato. Il punto è che il metodo descritto non consente di decodificare correttamente il messaggio originale senza trasferire informazioni aggiuntive. Infatti, senza conoscere le tabelle di codifica utilizzate per comprimere le informazioni, è impossibile decodificarle. Cioè, insieme alla sequenza di informazioni codificate, è necessario trasmettere tabelle di codifica. È chiaro che in questo caso il vantaggio derivante dall'utilizzo di un alfabeto limitato è ridotto a zero.
Il metodo dell'alfabeto delimitato presenta anche altri svantaggi. Se il messaggio informativo originale contiene un numero elevato di caratteri diversi, non sarà possibile ridurre la capacità delle cifre dei caratteri dell'alfabeto e questo metodo semplicemente non funzionerà. Supponiamo, ad esempio, che il messaggio di dati originale contenga 129 caratteri di un alfabeto di 256 caratteri. In questo caso non sarà possibile utilizzare la codifica dei caratteri a 7 bit, poiché 7 bit consentiranno solo la codifica di 128 caratteri. Pertanto, per 129 caratteri, dovrai ripristinare la stessa codifica a 8 bit dell'alfabeto di 256 caratteri originale.
Codici a lunghezza variabile
Uno dei principali inconvenienti dell'ipotetico metodo di limitazione dell'alfabeto che abbiamo considerato è che utilizza un codice uniforme quando tutti i simboli dell'alfabeto delle informazioni hanno la stessa lunghezza (8, 7 bit o meno). Sarebbe più logico utilizzare un tale sistema di codifica in cui la lunghezza del codice carattere dipende dalla frequenza della sua occorrenza nel messaggio informativo. Cioè, se nel messaggio informativo originale alcuni caratteri si trovano più spesso di altri, è ottimale utilizzare codici brevi per loro e, per quelli rari, più lunghi.
Come esempio ipotetico, considera il seguente messaggio informativo: "Incidente aereo" che contiene 14 caratteri. Supponiamo di avere un alfabeto di 14 caratteri che ci permette di codificare questo messaggio. Se viene utilizzato un codice uniforme, sono necessari 4 bit per ogni carattere dell'alfabeto (una lunghezza del codice di 4 bit consentirà di formare 16 caratteri). Tuttavia, è facile vedere che nel nostro messaggio informativo il simbolo "a" compare cinque volte, il simbolo "t" - due volte e il resto dei simboli - una volta. Se per il carattere "a" usiamo un codice con una lunghezza di 2 bit, per il carattere "t" - una lunghezza di 3 bit e per i caratteri rimanenti - una lunghezza di 4 bit, allora possiamo sicuramente risparmiare denaro. È solo necessario capire come esattamente costruire codici di lunghezza variabile e come esattamente la lunghezza del codice dovrebbe dipendere dalla frequenza di comparsa del simbolo nel messaggio informativo.
Se tutti i caratteri inseriscono il messaggio informativo con la stessa frequenza (altrettanto probabile), allora con un alfabeto informativo di N caratteri, per codificare ciascun carattere, esattamente log 2 n morso. In effetti, questo è il caso di un codice uniforme.
Se i simboli hanno diverse probabilità di occorrenza in un messaggio informativo, allora, secondo la teoria di K. Shannon, un simbolo con una probabilità di occorrenza pari a p è ottimale e, cosa particolarmente importante, è teoricamente ammissibile associare un codice di lunghezza –log 2 P... Tornando al nostro esempio con il messaggio informativo "incidente aereo" e considerando che la probabilità della comparsa del simbolo "a" (p (a)) è 5/14, la probabilità della comparsa del simbolo "t" è 2 /14, e la probabilità della comparsa di tutti gli altri simboli è 1 / 14, otteniamo che: per il carattere "a" la lunghezza ottimale del codice è –log 2 (5/14) = 1,48 bit; per il simbolo "t" - –log 2 (2/14) = 2,8 bit, e per tutti gli altri simboli è –log 2 (1/14) = 3,8. Poiché nel nostro caso la lunghezza del codice può avere solo un valore intero, allora, arrotondando, otteniamo che per il carattere "a" è ottimale utilizzare un codice con una lunghezza di 2 bit, per il carattere "t" - una lunghezza di 3 bit, e per il resto - una lunghezza di 4 bit.
Calcoliamo il rapporto di compressione quando si utilizza questa codifica. Se fosse utilizzato un codice uniforme basato su un alfabeto di 14 caratteri, sarebbero necessari 56 bit per codificare la parola "incidente aereo". Quando si utilizzano codici a lunghezza variabile, sono necessari 5 × 2 bit + 2 × 3 bit + 7 × 4 bit = 44 bit, quindi il rapporto di compressione è 1,27.
Ora diamo un'occhiata agli algoritmi per ottenere codici a lunghezza variabile.
Codifica prefisso
Il metodo più semplice per ottenere codici a lunghezza variabile è la cosiddetta codifica del prefisso, che consente di ottenere codici a lunghezza intera. La caratteristica principale dei codici prefisso è che all'interno di ciascuno dei loro sistemi, i codici più brevi non coincidono con l'inizio (prefisso) dei codici più lunghi. È questa proprietà dei codici prefisso che rende molto facile decodificare le informazioni.
Spieghiamo questa proprietà dei codici prefisso con un esempio specifico. Sia un sistema di tre prefissi: (0, 10, 11). Come puoi vedere, il codice più corto 0 non coincide con l'inizio dei codici più lunghi 10 e 11. Lascia che il codice 0 specifichi il carattere "a", codice 10 - il carattere "m" e il codice 11 - il carattere " P". Quindi la parola "frame" viene codificata con la sequenza 110100. Proviamo a decodificare questa sequenza. Poiché il primo bit è 1, il primo carattere può essere solo "m" o "p" ed è determinato dal valore del secondo bit. Poiché il secondo bit è 1, il primo carattere è "p". Il terzo bit è 0 e corrisponde in modo univoco al carattere "a". Il quarto bit è 1, ovvero devi guardare il valore del bit successivo, che è 0, quindi il terzo carattere è "m". L'ultimo bit è 0, che corrisponde in modo univoco al carattere "a". Pertanto, la proprietà dei codici prefisso che i codici più brevi non possono coincidere con l'inizio dei codici più lunghi consente di decodificare in modo univoco un messaggio informativo codificato con codici di prefisso a lunghezza variabile.
I codici dei prefissi sono generalmente ottenuti costruendo alberi di codice (per un sistema binario). Ciascun nodo interno di un tale albero binario ha due archi in uscita, con un arco corrispondente al carattere binario "0" e l'altro - "1". Per chiarezza, possiamo concordare che il bordo sinistro dovrebbe essere associato al simbolo "0" e il bordo destro - il simbolo "1".
Poiché non possono esserci cicli nell'albero, puoi sempre creare un singolo percorso dal nodo radice al nodo foglia. Se i bordi dell'albero sono numerati, allora ciascuno di questi percorsi corrisponde a una sequenza binaria unica. L'insieme di tutte queste sequenze formerà un sistema di codice prefisso.
Per l'esempio considerato di un sistema di tre codici di prefisso: (0, 10, 11), che definiscono i simboli "a", "m" e "p", l'albero dei codici è mostrato in Fig. uno.
Riso. 1. Albero del codice per il sistema
di tre prefissi: (0, 10, 11)
La comodità della rappresentazione ad albero dei codici prefisso risiede nel fatto che è la struttura ad albero che consente di generare codici di lunghezza variabile che soddisfano la condizione principale dei codici prefisso, cioè la condizione che i codici più brevi non coincidano con l'inizio di codici più lunghi.
Finora, abbiamo esaminato solo l'idea di codici di prefisso a lunghezza variabile. Per quanto riguarda gli algoritmi per ottenere i codici dei prefissi, ce ne sono parecchi, ma i più famosi sono due metodi: Shannon-Fano e Huffman.
Algoritmo di Shannon-Fano
Questo algoritmo per ottenere codici prefisso è stato proposto indipendentemente da R. Fano e K. Shannon, consiste nel seguente. Nella prima fase, tutti i simboli della sequenza di informazioni originale sono ordinati con probabilità decrescente o crescente della loro comparsa (frequenza della loro comparsa), dopodiché la riga ordinata di simboli è divisa in due parti in un punto in modo che in ciascuna di loro la somma delle frequenze simbolo è approssimativamente la stessa. Come dimostrazione, considera la parola già familiare a noi "Incidente aereo" .
Se i simboli che compongono una data parola sono ordinati in ordine decrescente della loro frequenza di occorrenza, allora otteniamo la seguente sequenza: (a (5), t (2), in (1) e (1), a ( 1), c (1), p (1), o (1), f (1)) (tra parentesi è indicata la frequenza di ripetizione del simbolo nella parola). Successivamente, dobbiamo dividere questa sequenza in due parti in modo che in ciascuna di esse la somma delle frequenze dei simboli sia approssimativamente la stessa (per quanto possibile). È chiaro che la sezione passerà tra i simboli "t" e "b", per cui si formano due sequenze: (a (5), t (2)) e (in (1) e (1 ), a (1), c (1), p (1), o (1), φ (1)). Inoltre, le somme della frequenza di ripetizione dei simboli nella prima e nella seconda sequenza saranno le stesse e uguali a 7.
Nella prima fase della divisione di una sequenza di caratteri, otteniamo la prima cifra del codice di ciascun carattere. La regola è semplice: per quei caratteri che compaiono nella sequenza a sinistra, il codice inizierà con "0" e per quelli a destra - con "1".
In particolare, la sequenza (a (5), m (2)) si dividerà in due caratteri distinti: a (5) e m (2) (non ci sono altre divisioni). Quindi la seconda cifra del codice per il simbolo "a" è "0" e per il simbolo "t" - "1". Poiché, a seguito della divisione della sequenza, abbiamo ricevuto singoli elementi, non sono più divisi e per il simbolo "a" otteniamo il codice 00 e per il simbolo "t" - il codice 01.
La sequenza (in (1), u (1), a (1), c (1), p (1), o (1), f (1)) può essere divisa in sequenze (in (1), e (1), k (1)) e (c (1), p (1), o (1), φ (1)), o su (in (1), u (1), k (1) ), (c (1)) e (p (1), o (1), (1)).
Nel primo caso, le somme dei tassi di ripetizione dei simboli nella prima e nella seconda sequenza saranno rispettivamente 3 e 4, e nel secondo caso rispettivamente 4 e 3. Per motivi di chiarezza, utilizzeremo la prima opzione.
Per i caratteri della nuova sequenza risultante (in (1), e (1), a (1)) (questa è la sequenza a sinistra), le prime due cifre del codice saranno 10, e per la sequenza (c ( 1), p (1), o (1 ), φ (1)) - 11.
Nel nostro esempio (Fig. 2 e 3) si ottiene il seguente sistema di codici prefisso: "a" - 00, "t" - 01, "b" - 100, "u" - 1010, "k" - 1011, " c" - 1100, "p" - 1101, "o" - 1110, "f" - 1111. Come puoi vedere, i codici più brevi non sono l'inizio di codici più lunghi, ovvero la proprietà principale dei codici prefisso è soddisfatta.
Riso. 2. Dimostrazione dell'algoritmo di Shannon-Fano
Riso. 3. Albero del codice per la parola "incidente aereo"
nell'algoritmo di Shannon-Fano
Algoritmo di Huffman
L'algoritmo di Huffman è un altro algoritmo per ottenere codici di prefisso di lunghezza variabile. A differenza dell'algoritmo di Shannon-Fano, che prevede la costruzione dell'albero di codifica dall'alto verso il basso, questo algoritmo implica la costruzione dell'albero di codifica in ordine inverso, cioè dal basso verso l'alto (dai nodi foglia alla radice nodo).
Nella prima fase, come nell'algoritmo di Shannon-Fano, la sequenza originale di caratteri è ordinata in ordine decrescente della frequenza di ripetizione dei caratteri (elementi di sequenza). Per l'esempio sopra con la parola "Incidente aereo" otteniamo la seguente sequenza ordinata di elementi: (a (5), t (2), in (1), u (1), k (1), c (1), p (1), o (1), (1 )).
Inoltre, gli ultimi due elementi della sequenza vengono sostituiti con un nuovo elemento S1, al quale viene assegnata una ripetibilità pari alla somma della ripetibilità degli elementi originari. Quindi, gli elementi della sequenza vengono nuovamente ordinati in base alla loro ripetibilità. Nel nostro caso, gli ultimi due elementi o (1) e φ (1) sono sostituiti dall'elemento S1 (2) e la nuova sequenza ordinata assumerà la forma: (a (5), m (2), S1 ( 2), in (1) , u (1), k (1), c (1), p (1)).
Continuando questa procedura di sostituzione degli ultimi due elementi della sequenza con un nuovo elemento a totale ripetibilità e successivo riordinamento della sequenza in accordo con la ripetibilità degli elementi, si arriva ad una situazione in cui nella sequenza rimane un solo elemento ( figura 4).
Riso. 4. Dimostrazione dell'algoritmo di Huffman
usando l'esempio della parola "incidente aereo"
Contemporaneamente alla sostituzione degli elementi e al riordinamento della sequenza, viene costruito un albero di codice binario. L'algoritmo di costruzione dell'albero è molto semplice: l'operazione di combinazione (sostituzione) di due elementi della sequenza genera un nuovo nodo nell'albero del codice. Cioè, se si osserva l'albero dal basso verso l'alto, i bordi dell'albero del codice provengono sempre dagli elementi sostituiti e convergono in un nuovo elemento nodo corrispondente all'elemento sequenza ottenuto per sostituzione (Fig. 5). In questo caso, al bordo sinistro dell'albero del codice può essere assegnato il valore "0" e quello destro - "1". Questi valori serviranno ulteriormente come elementi del codice del prefisso.
Riso. 5. Costruire un albero del codice
nell'algoritmo di Huffman
(sostituendo gli elementi "o" e "f"
nuovo elemento S1)
Completa l'albero dei codici di Huffman per una parola "Incidente aereo" , mostrato in Fig. 6.
Riso. 6. Albero del codice completo per la parola "incidente aereo"
costruito dall'algoritmo di Huffman
Camminando lungo i bordi dell'albero dei codici dall'alto verso il basso, è facile ottenere codici prefisso per tutti i simboli del nostro alfabeto informativo:
Se ora provi a scrivere una parola "Incidente aereo" nella codifica Huffman, otteniamo la sequenza a 41 bit 0 1101 11000 0 11001 0 111 0 1010 111 1011 1000 1001 0. È interessante notare che quando si utilizzano i codici del prefisso Shannon-Fano, si ottiene anche una sequenza a 41 bit per la parola "incidente aereo". Cioè, in un esempio specifico, l'efficienza di codifica di Huffman e Shannon-Fano è la stessa. Ma se teniamo conto che l'alfabeto delle informazioni reali è di 256 caratteri (e non 14, come nel nostro esempio) e le sequenze di informazioni reali sono file di qualsiasi contenuto e lunghezza, allora sorge la domanda sul codice del prefisso ottimale, cioè, un codice che permette di ottenere la lunghezza minima della sequenza di output.
Si può dimostrare che il sistema di codici ottenuto utilizzando l'algoritmo di Huffman è il migliore tra tutti i possibili sistemi di codici prefissi, nel senso che la lunghezza della sequenza di informazioni codificate risultante è minima. Cioè, l'algoritmo di Huffman è ottimale.
Il principale svantaggio dell'algoritmo di Huffman è la complessità del processo di costruzione di un sistema di codici. Tuttavia, è l'algoritmo ottimale di Huffman che è l'algoritmo di generazione del codice a lunghezza variabile più comune ed è incorporato nella maggior parte delle utilità di compressione e archiviazione delle informazioni.
Codifica aritmetica
Come abbiamo già notato, secondo il criterio di Shannon, il codice ottimo è quello in cui viene allocato un codice di lunghezza –log 2 per ogni carattere P morso. E se, ad esempio, la probabilità di un certo carattere è 0,2, la lunghezza ottimale del suo codice sarà –log 2 0,2 = 2,3 bit. È chiaro che i codici prefisso non possono fornire una tale lunghezza del codice e quindi non sono ottimali. In generale, la lunghezza del codice determinata dal criterio di Shannon è solo un limite teorico. L'unica domanda è quale metodo di codifica consente di avvicinarsi il più possibile a questo limite teorico. I codici di prefisso a lunghezza variabile sono efficienti e abbastanza facili da implementare, ma esistono metodi di codifica più efficienti, in particolare un algoritmo di codifica aritmetica.
L'idea alla base della codifica aritmetica è che invece di codificare i singoli caratteri, il codice viene assegnato simultaneamente all'intera sequenza di informazioni. È ovvio che la lunghezza del codice per un singolo carattere potrebbe non essere un numero intero. Ecco perché questo metodo di codifica è molto più efficiente della codifica del prefisso ed è più coerente con il criterio di Shannon.
L'idea alla base dell'algoritmo di codifica aritmetica è la seguente. Come in tutti i metodi di codifica considerati in precedenza, ogni simbolo della sequenza di informazioni originale è caratterizzato dalla sua probabilità. Alla sequenza originale non codificata viene assegnato un semiintervallo)
