Utilizzando l'algoritmo RLE, codificare la sequenza di caratteri BBBBBBACCCABBBBBB

Scrivi il risultato come codici esadecimali (ogni carattere è codificato come un byte, rappresentato da due cifre esadecimali). Verificare il risultato utilizzando il programma RLE.

Decodificare la sequenza impacchettata utilizzando l'algoritmo RLE (sono forniti codici esadecimali): 01 4D 8E 41 01 4D 8E 4116. Utilizzare la tabella ASCII per determinare i caratteri in base al loro codice esadecimale. Nella tabella sopra, la prima riga contiene la prima cifra del codice del carattere esadecimale e la seconda riga contiene la seconda. Ad esempio, il carattere "&" ha il codice esadecimale 2616.

Determina il numero di byte nella sequenza originale e decompressa e calcola il rapporto di compressione: controlla il risultato ottenuto in paragrafo precedente, utilizzando il programma RLE. Suggerisci due modi per controllare. Costruisci sequenze che vengono compresse dall'algoritmo RLE esattamente 2 volte, 4 volte, 5 volte. Controlla le tue risposte con il programma RLE. Pensa a tre sequenze che non possono essere compresse utilizzando l'algoritmo RLE: Usando il programma RLE, applica la compressione RLE ai seguenti file e trova il rapporto di compressione per ciascuno di essi: Spiega i risultati ottenuti nel paragrafo precedente:

Perché non riesco a comprimere le immagini in formato JPEG? perché per due disegni in formato BMP gli stessi rapporti di compressione delle dimensioni secondo l'algoritmo RLE sono così diversi? Suggerimento: apri questi disegni in qualsiasi visualizzatore.

Stimare il rapporto di compressione massimo ottenibile utilizzando la variante da manuale dell'algoritmo RLE. In che caso si può ottenere?
Stimare il rapporto di compressione utilizzando l'algoritmo RLE nel caso peggiore. Descrivi questo caso peggiore.

• tutorial

Tanto tempo fa, quando ero ancora uno scolaro ingenuo, improvvisamente sono diventato terribilmente curioso: come fanno i dati negli archivi a occupare magicamente meno spazio? Cavalcando il mio fedele dialup, ho iniziato a navigare in Internet in cerca di una risposta, e ho trovato molti articoli con una presentazione abbastanza dettagliata delle informazioni che mi interessavano. Ma nessuno di loro sembrava facile da capire allora: gli elenchi dei codici sembravano lettere cinesi e i tentativi di comprendere una terminologia insolita e varie formule non hanno avuto successo.

Pertanto, lo scopo di questo articolo è quello di dare un'idea degli algoritmi di compressione più semplici a coloro la cui conoscenza ed esperienza non consentono ancora loro di comprendere immediatamente la letteratura più professionale, o il cui profilo è completamente lontano da tali argomenti. Quelli. Parlerò "con le dita" di alcuni degli algoritmi più semplici e fornirò esempi della loro implementazione senza elenchi di codici lunghi un chilometro.

Ti avverto immediatamente che non prenderò in considerazione i dettagli dell'implementazione del processo di codifica e sfumature come la ricerca efficiente delle occorrenze di una stringa. L'articolo toccherà solo gli algoritmi stessi e le modalità di presentazione del risultato del loro lavoro.

RLE - Compattezza dell'uniformità

Algoritmo RLEè probabilmente il più semplice di tutti: la sua essenza sta nella codificazione delle ripetizioni. In altre parole, prendiamo sequenze di elementi identici e le "comprimiamo" in coppie conteggio/valore. Ad esempio, una stringa come "AAAAAAAAABCCCC" potrebbe essere convertita in una voce come "8xA, B, 4xC". Questo è, in generale, tutto ciò che devi sapere sull'algoritmo.

Esempio di attuazione

Supponiamo di avere un insieme di alcuni coefficienti interi che possono assumere valori da 0 a 255. Logicamente, siamo giunti alla conclusione che è ragionevole memorizzare questo insieme come un array di byte:
dati caratteri senza segno = ( 0, 0, 0, 0, 0, 0, 4, 2, 0, 4, 4, 4, 4, 4, 4, 4, 80, 80, 80, 80, 0, 2, 2 , 2, 2, 255, 255, 255, 255, 255, 0, 0);

Per molti, sarà molto più familiare vedere questi dati come un dump esadecimale:
0000: 00 00 00 00 00 00 04 02 00 04 04 04 04 04 04 04
0010: 50 50 50 50 00 02 02 02 02 FF FF FF FF 00 00

Riflettendoci, abbiamo deciso che sarebbe stato utile comprimere in qualche modo tali set per risparmiare spazio. Per fare ciò, le abbiamo analizzate e individuato uno schema: molto spesso ci sono sottosequenze costituite dagli stessi elementi. Naturalmente, RLE è perfetto per questo!

Codifichiamo i nostri dati utilizzando le nuove conoscenze ottenute: 6x0, 4, 2, 0, 7x4, 4x80, 0, 4x2, 5x255, 2x0.

È ora di presentare in qualche modo il nostro risultato in un formato compatibile con il computer. Per fare ciò, nel flusso di dati, dobbiamo in qualche modo separare i singoli byte dalle stringhe codificate. Poiché l'intero intervallo di valori di byte viene utilizzato dai nostri dati, non sarà possibile semplicemente allocare intervalli di valori ​​per i nostri scopi.

Ci sono almeno due vie d'uscita da questa situazione:

1. Come indicatore di una catena compressa, seleziona un valore di byte e, in caso di collisione con dati reali, esegui l'escape. Ad esempio, se utilizziamo il valore 255 per scopi "ufficiali", quando questo valore viene rilevato nei dati di input, dovremo scrivere "255, 255" e utilizzare un massimo di 254 dopo l'indicatore.
2. Strutturare i dati codificati, indicando il numero di singoli elementi non solo ripetuti, ma anche successivi. Quindi sapremo in anticipo dove sono i dati.

Il primo metodo nel nostro caso non sembra efficace, quindi, forse, ricorreremo al secondo.

Quindi ora abbiamo due tipi di sequenze: stringhe di singoli elementi (come "4, 2, 0") e stringhe di elementi identici (come "0, 0, 0, 0, 0, 0"). Assegniamo un bit nei byte "servizio" per il tipo sequenza: 0 - elementi singoli, 1 - identici. Prendi per questo, diciamo, il bit più significativo di un byte.

Nei restanti 7 bit memorizzeremo le lunghezze delle sequenze, ad es. la lunghezza massima della sequenza codificata è di 127 byte. Potremmo allocare, diciamo, due byte per scopi di servizio, ma nel nostro caso sequenze così lunghe sono estremamente rare, quindi è più facile ed economico suddividerle semplicemente in sequenze più brevi.

Si scopre che nel flusso di output scriveremo prima la lunghezza della sequenza, quindi un valore ripetuto o una catena di elementi non ripetuti della lunghezza specificata.

La prima cosa che dovrebbe attirare la tua attenzione è che in questa situazione abbiamo un paio di valori inutilizzati. Non possono esserci sequenze di lunghezza zero, quindi possiamo aumentare lunghezza massima fino a 128 byte, sottraendo uno dalla lunghezza durante la codifica e aggiungendolo durante la decodifica. Quindi possiamo codificare lunghezze da 1 a 128 invece di lunghezze da 0 a 127.

La seconda cosa da notare è che non ci sono sequenze di elementi identici di lunghezza unitaria. Pertanto, durante la codifica, ne sottrarremo un'altra dalla lunghezza di tali sequenze, aumentando così la loro lunghezza massima a 129 (la lunghezza massima di una catena di singoli elementi è ancora 128). Quelli. catene di elementi identici possono avere una lunghezza da 2 a 129.

Codifichiamo di nuovo i nostri dati, ma ora in una forma comprensibile al computer. Scriveremo i byte di servizio come , dove T è il tipo di sequenza e L è la lunghezza. Prenderemo subito in considerazione che scriviamo le lunghezze in una forma modificata: a T=0 sottraiamo uno da L, a T=1 - due.

0, , 4, 2, 0, , 4, , 80, , 0, , 2, , 255, , 0

Proviamo a decodificare il nostro risultato:

• . T=1, quindi il byte successivo verrà ripetuto L+2 (4+2) volte: 0, 0, 0, 0, 0, 0.
• . T=0, quindi leggi semplicemente L+1 (2+1) byte: 4, 2, 0.
• . T=1, ripeti il ​​byte successivo 5+2 volte: 4, 4, 4, 4, 4, 4, 4.
• . T=1, ripeti il ​​byte successivo 2+2 volte: 80, 80, 80, 80.
• . T=0, leggi 0+1 byte: 0.
• . T=1, ripetere il byte 2+2 volte: 2, 2, 2, 2.
• . T=1, ripetere il byte 3+2 volte: 255, 255, 255, 255, 255.
• . T=1, ripetere il byte 0+2 volte: 0, 0.

E adesso ultimo passo: memorizza il risultato come un array di byte. Ad esempio, una coppia racchiusa in un byte sarebbe simile a questa:

Di conseguenza, otteniamo quanto segue:
0000: 84 00 02 04 02 00 85 04 82 80 00 00 82 02 83 FF
0010: 80 00

In un modo così semplice, questo esempio dei dati di input, abbiamo ottenuto 18 byte su 32. Non un brutto risultato, soprattutto considerando che può essere molto migliore su catene più lunghe.

Possibili miglioramenti

L'efficienza di un algoritmo dipende non solo dall'algoritmo stesso, ma anche da come viene implementato. Pertanto, per dati diversi è possibile sviluppare diverse varianti di codifica e presentazione di dati codificati. Ad esempio, quando si codificano le immagini, è possibile creare catene di lunghezza variabile: allocare un bit per indicare una catena lunga e, se è impostato su uno, memorizzare anche la lunghezza nel byte successivo. In questo modo sacrifichiamo la lunghezza delle catene corte (65 elementi invece di 129), ma d'altra parte rendiamo possibile codificare catene lunghe fino a 16385 elementi (2 14 + 2) con soli tre byte!

È possibile ottenere ulteriore efficienza utilizzando tecniche di codifica euristica. Ad esempio, codifichiamo a modo nostro la seguente catena: "ABBA". Otteniamo " , A, , B, , A" - cioè Abbiamo trasformato 4 byte in 6, gonfiato i dati originali fino a una volta e mezza! E più sequenze eterogenee alternate sono così brevi, più dati ridondanti. Se teniamo conto di questo, potremmo codificare il risultato come ", A, B, B, A" - spenderemmo solo un byte in più.

LZ77 - brevità nella ripetizione

LZ77 è uno degli algoritmi più semplici e conosciuti della famiglia LZ. Prende il nome dai suoi creatori: Abraham Lempel (Abraham l empel) e Jacob Ziv (Jacob Z iv). I numeri 77 nel titolo significano 1977, in cui è stato pubblicato un articolo che descrive questo algoritmo.

L'idea principale è codificare sequenze identiche di elementi. Cioè, se una catena di elementi si verifica più di una volta nei dati di input, tutte le sue occorrenze successive possono essere sostituite da "collegamenti" alla sua prima istanza.

Come il resto degli algoritmi di questa famiglia della famiglia, LZ77 utilizza un dizionario che memorizza le sequenze incontrate in precedenza. Per fare ciò, applica il principio del cosiddetto. " finestra scorrevole': l'area sempre prima della posizione di codifica corrente all'interno della quale possiamo indirizzare i collegamenti. Questa finestra è il dizionario dinamico per questo algoritmo- ogni elemento in esso contenuto corrisponde a due attributi: posizione nella finestra e lunghezza. Anche se in senso fisico, questo è solo un pezzo di memoria che abbiamo già codificato.

Esempio di attuazione

Proviamo a codificare qualcosa ora. Generiamo una stringa adatta per questo (mi scuso in anticipo per la sua assurdità):

"La compressione e il la decompressione lascia un'impressione. Ha ha ha ha ha!"

Ecco come apparirà in memoria (codifica ANSI):
0000: 54 68 65 20 63 6F 6D 70 72 65 73 73 69 6F 6E 20 La compressione
0010: 61 6E 64 20 74 68 65 20 64 65 63 6F 6D 70 72 65 e la decompressione
0020: 73 73 69 6F 6E 20 6C 65 61 76 65 20 61 6E 20 69 ssion lasciare un i
0030: 6D 70 72 65 73 73 69 6F 6E 2E 20 48 61 68 61 68 Ahahah
0040: 61 68 61 68 61 21 ahaha!

Non abbiamo ancora deciso la dimensione della finestra, ma saremo d'accordo sovradimensionato stringa codificata. Proviamo a trovare tutte le stringhe di caratteri ripetute. Una stringa è una sequenza di caratteri più lunga di uno. Se la catena fa parte di una catena ripetuta più lunga, la ignoreremo.

“La compressione e t de leave[an] i . Ah!"

Per maggiore chiarezza, osserviamo il diagramma, dove possiamo vedere la corrispondenza delle sequenze ripetute e le loro prime occorrenze:

Forse l'unico punto poco chiaro qui è la sequenza "Hahahahaha!", perché la stringa di caratteri "ahahaha" corrisponde alla stringa corta "ah". Ma non c'è niente di insolito qui, abbiamo usato un trucco che consente all'algoritmo di funzionare a volte come l'RLE descritto in precedenza.

Il fatto è che durante il disimballaggio, leggeremo il numero di caratteri specificato dal dizionario. E poiché l'intera sequenza è periodica, cioè i dati in esso contenuti vengono ripetuti con un certo punto, e i simboli del primo periodo saranno subito prima della posizione di disimballaggio, quindi possiamo ricreare l'intera catena da essi, semplicemente copiando i simboli del periodo precedente nel successivo.

Ho risolto. Ora sostituiamo le ripetizioni trovate con i riferimenti al dizionario. Scriveremo il collegamento nel formato , dove P è la posizione della prima occorrenza della stringa nella stringa, L è la sua lunghezza.

“La compressione e t de lasciare i . Ah!"

Ma non dimenticare che abbiamo a che fare con una finestra scorrevole. Per una migliore comprensione, in modo che i collegamenti non dipendano dalle dimensioni della finestra, sostituiremo le posizioni assolute con la differenza tra esse e la posizione di codifica corrente.

“La compressione e t de lasciare i . Ah!"

Ora dobbiamo solo sottrarre P dalla posizione di codifica corrente per ottenere la posizione assoluta nella stringa.

È ora di decidere la dimensione della finestra e la lunghezza massima della frase codificata. Poiché si tratta di testo, è raro che vi siano sequenze ripetute particolarmente lunghe. Quindi allochiamo, diciamo, 4 bit per la loro lunghezza: un limite di 15 caratteri alla volta è abbastanza per noi.

Ma la dimensione della finestra dipende già da quanto in profondità cercheremo le stesse catene. Dal momento che abbiamo a che fare con testi piccoli, sarà giusto integrare a due byte il numero di bit che utilizziamo: indirizzeremo i collegamenti in un intervallo di 4096 byte, utilizzando 12 bit per questo.

Sappiamo per esperienza con RLE che non tutti i valori possono essere utilizzati. Ovviamente, il collegamento può avere un valore minimo di 1, quindi, per tornare nell'intervallo 1..4096, dobbiamo sottrarre uno dal collegamento durante la codifica e aggiungerlo durante la decodifica. Lo stesso con le lunghezze delle sequenze: invece di 0..15 useremo l'intervallo 2..17, poiché non lavoriamo con lunghezze zero e i singoli caratteri non sono sequenze.

Quindi, immaginiamo il nostro testo codificato, tenendo conto di questi emendamenti:

“La compressione e t de lasciare i . Ah!"

Ora, ancora una volta, abbiamo bisogno di separare in qualche modo le catene compresse dal resto dei dati. Il modo più comune è utilizzare nuovamente la struttura e indicare direttamente dove i dati sono compressi e dove non lo sono. Per fare ciò, divideremo i dati codificati in gruppi di otto elementi (caratteri o link), e prima di ciascuno di questi gruppi inseriremo un byte, dove ogni bit corrisponde al tipo di elemento: 0 per un carattere e 1 per un collegamento.

Ci dividiamo in gruppi:

• "Il Comp"
• "remissione"
• "e t de"
• "partire"
• "io. ah"

Gruppi di compilazione:

"(0,0,0,0,0,0,0,0) La comp(0,0,0,0,0,0,0,0) ressione (0,0,0,0,0,1 ,0,0) e t de(1,0,0,0,0,0,1,0) leave (0,1,0,0,0,0,0,1) i . Ah(0)!"

Pertanto, se incontriamo il bit 0 durante la decompressione, leggiamo semplicemente il carattere nel flusso di output, se il bit è 1, leggiamo il collegamento e, per riferimento, leggiamo la sequenza dal dizionario.

Ora non ci resta che raggruppare il risultato in un array di byte. Siamo d'accordo sul fatto che utilizziamo bit e byte in ordine dall'alto al basso. Vediamo come i collegamenti sono impacchettati in byte usando un esempio:

Di conseguenza, il nostro flusso compresso sarà simile al seguente:

0000:00 54 68 65 20 63 6f 6d 70 00 72 65 73 73 69 6f #La comp#ressio
0010: 6e 20 04 61 6e 64 20 74 01 31 64 65 82 01 5a 6c n #e t##de###l
0020: 65 61 76 65 01 b1 20 41 69 02 97 2e 20 48 61 68 eave## #i##. Ah
0030: 00 15 00 21 00 00 00 00 00 00 00 00 00 00 00 00 ###!

Possibili miglioramenti

In linea di principio, tutto ciò che è stato descritto per RLE sarà vero qui. In particolare, per dimostrare l'utilità dell'approccio euristico nella codificazione, si consideri il seguente esempio:

"Il lungo goooooong. Il più basso legato."

Troviamo sequenze solo per la parola "looooooower":

"Il lungo goooooong. Il wer legato."

Per codificare un tale risultato, abbiamo bisogno di quattro byte per collegamento. Tuttavia, sarebbe più economico farlo:

"Il lungo goooooong. Io ero legato."

Quindi spenderemmo un byte in meno.

Invece di una conclusione

Nonostante la loro semplicità e, sembrerebbe, non eccessiva efficienza, questi algoritmi sono ancora ampiamente utilizzati in vari ambiti della sfera IT.

Il loro vantaggio è la semplicità e la velocità e algoritmi più complessi ed efficienti possono essere basati sui loro principi e sulle loro combinazioni.

Spero che l'essenza di questi algoritmi espressi in questo modo aiuterà qualcuno a capire le basi e iniziare a guardare a cose più serie.

Anche 10-15 anni fa, gli archiviatori venivano utilizzati principalmente per risparmiare spazio sui dischi rigidi e per inserire la maggior parte dei dati su un floppy disk. Tuttavia, i tempi sono cambiati. Nessuno utilizza da molto tempo i floppy disk come mezzo per trasferire e archiviare informazioni 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 annullarne l'archiviazione per risparmiare spazio semplicemente non è pratico, perché richiede molto tempo. Ebbene, in effetti, oggi la quantità di dati sui dischi degli utenti si misura in terabyte. Ora immagina quanto tempo ci vorrebbe per archiviare un terabyte di dati. Non ci vorranno una o anche due ore, ma almeno 10-12 ore, ovvero il computer dovrà essere lasciato acceso tutta la notte.

Sembrerebbe che oggi gli archivisti dovrebbero perdere gradualmente la loro rilevanza. Ma non succede niente del genere. La stragrande maggioranza degli utenti, tra gli altri programmi, ha degli archiviatori installati o utilizza un archiviatore integrato nel sistema operativo Windows (in questa pubblicazione non vengono presi in considerazione altri sistemi operativi).

Il fatto è che la nomina degli archivisti è cambiata. Oggi vengono utilizzati principalmente per inviare 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 vengono archiviati. A proposito, l'utente stesso, prima di caricare qualsiasi dato sulla rete (ad esempio, su risorse di condivisione file), impacchetta i dati in un archivio.

Riguardo mercato russo, quindi abbiamo i tre archiviatori più comuni: WinRAR, WinZip e 7-Zip, presentati in entrambe le versioni a 32 e 64 bit. Sono loro che confronteremo in questo articolo. Tuttavia, prima, diamo una rapida occhiata ad alcuni aspetti teorici lavoro di archiviazione.

Algoritmi di compressione delle informazioni

L'essenza di qualsiasi algoritmo di compressione delle informazioni è ottenere, mediante una qualche trasformazione dell'insieme iniziale di bit di informazione, all'uscita un certo insieme più piccola. Inoltre, tutti gli algoritmi di trasformazione dei dati possono essere suddivisi condizionatamente in due classi: reversibili e irreversibili.

Per algoritmo di compressione delle informazioni irreversibile si intende una tale trasformazione della sequenza di bit originale, in cui la sequenza di output di dimensioni inferiori non consente il ripristino esatto della sequenza di input. Vengono utilizzati algoritmi di compressione irreversibile, ad esempio, in relazione a dati grafici, video e audio, e questo porta sempre ad una perdita della loro qualità. Naturalmente, negli archivi non vengono utilizzati algoritmi per la compressione irreversibile dei dati e quindi non li considereremo ulteriormente.

Gli algoritmi di compressione dei dati reversibili consentono di ripristinare esattamente la sequenza di dati originale dalla sequenza compressa. Sono questi algoritmi che vengono utilizzati negli archivi. Caratteristiche generali di tutti gli algoritmi di compressione sono il rapporto di compressione (il rapporto tra i volumi della sequenza di dati originale e quello compresso), il tasso di compressione (il tempo impiegato per archiviare una certa quantità di dati) e la qualità di compressione (un valore che mostra quanto sia forte la sequenza di dati viene compresso applicando la ricompressione secondo questo o qualche altro algoritmo).

La teoria della compressione dell'informazione, 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 considereremo 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 fa parte del nostro compito. Pertanto, parleremo solo a livello qualitativo di diversi algoritmi che ci 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 l'algoritmo per la codifica di 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 per il 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 segno del contatore è quello dei primi due bit del byte letto. Ad esempio, se i primi due bit sono 11, i restanti 6 bit vengono allocati al contatore, che può assumere valori da 1 a 64. Di conseguenza, è possibile definire una serie di 64 byte ripetuti con soli due byte, che è, compresso di 32 volte.

Esiste un'altra implementazione di questo algoritmo, quando il segno del contatore è 1 nel primo byte del contatore. In questo caso, il contatore può prendere valore massimo, pari a 127 - e quindi il rapporto di compressione massimo sarà pari a 64.

È chiaro che l'algoritmo RLE è efficiente solo quando è presente un numero elevato di gruppi lunghi di byte identici. Se i byte non vengono ripetuti, l'utilizzo del metodo RLE comporta un aumento della dimensione del file.

Il metodo RLE è generalmente molto efficiente per la compressione di grafica bitmap (BMP, PCX, TIF, GIF) perché contengono serie molto lunghe di sequenze di byte ripetute.

Limitazione dell'alfabeto delle informazioni

Un altro modo abbastanza semplice per comprimere le informazioni può essere chiamato vincolo alfabeto informativo. Notiamo subito che in pratica tale algoritmo non è implementato, ma la presentazione di questo metodo aiuterà a comprendere meglio il metodo dei codici a lunghezza variabile.

In quanto segue, per alfabeto informativo si intende l'insieme dei simboli utilizzati per codificare la sequenza informativa. Ad esempio, supponiamo che ci sia un messaggio di testo. Ogni lettera di questo messaggio è codificata utilizzando una tabella ASCII composta da 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 noi stiamo parlando per un SMS in russo che non contenga numeri, sono sufficienti 64 caratteri (33 minuscole e 31 maiuscole). Se aggiungiamo a questi segni di punteggiatura, segni di paragrafo e segni di nuova riga, diventa chiaro che il numero di caratteri non supererà 100. In questo caso, puoi utilizzare la codifica dei caratteri non a 8, ma a 7 bit, che ti consente di ottenere una tabella di 128 caratteri. Cioè, noi, per così dire, limitiamo l'alfabeto informativo, grazie al quale possiamo ridurre la profondità di bit di ogni carattere raccolto. Puoi andare oltre, per determinare con precisione il numero di caratteri utilizzati in un messaggio di testo. Se, ad esempio, si scopre che nel messaggio vengono utilizzati solo 30 caratteri (compresi i newline), è possibile utilizzare una tabella di codifica a 5 bit contenente 32 caratteri e quindi il rapporto di compressione del messaggio di testo diventerà ancora maggiore. Infatti, se nel messaggio originale viene utilizzata la codifica dei caratteri a 8 bit e nel messaggio compresso viene utilizzata la codifica dei caratteri a 5 bit, il rapporto di compressione sarà 8/5.

Nonostante l'apparente semplicità del metodo di limitazione dell'alfabeto, in pratica non viene utilizzato. Il fatto è che il metodo descritto non consente di decodificare correttamente il messaggio originale senza trasmettere 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 guadagno derivante dall'utilizzo di un alfabeto limitato si riduce a zero.

Il metodo dell'alfabeto limitato presenta anche altri svantaggi. Se il messaggio informativo originale contiene un numero elevato di caratteri diversi, non sarà possibile ridurre la profondità di bit della rappresentazione dei caratteri alfabetici e questo metodo semplicemente non funzionerà. Si supponga, ad esempio, che il messaggio informativo 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 codificheranno solo 128 caratteri. Pertanto, per 129 caratteri, dovrai utilizzare la stessa codifica a 8 bit dell'alfabeto originale a 256 caratteri.

Codici a lunghezza variabile

Uno dei principali svantaggi dell'ipotetico metodo di restrizione dell'alfabeto che abbiamo considerato è che utilizza un codice uniforme quando tutti i caratteri 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 del carattere dipende dalla frequenza della sua occorrenza nel messaggio informativo. Cioè, se nel messaggio informativo originale alcuni caratteri si verificano più spesso di altri, è ottimale per l'uso codici brevi, e per quelli rari, quelli più lunghi.

Come esempio ipotetico, si consideri 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 formerà 16 caratteri). Tuttavia, è facile vedere che nel nostro messaggio informativo il simbolo "a" ricorre cinque volte, il simbolo "t" - due volte e il resto dei simboli - una volta. Se per il simbolo "a" utilizziamo un codice di 2 bit, per il simbolo "t" - 3 bit e per il resto dei caratteri - 4 bit, allora possiamo sicuramente salvare. È solo necessario capire come costruire esattamente codici a lunghezza variabile e come esattamente la lunghezza del codice dovrebbe dipendere dalla frequenza del simbolo nel messaggio informativo.

Se tutti i caratteri sono inclusi nel messaggio informativo con la stessa frequenza (equiprobabile), quindi con un alfabeto informativo di N caratteri, ogni carattere dovrà essere codificato esattamente log 2 N morso. In realtà, questo è un caso di codice uniforme.

Se i simboli hanno diverse probabilità di apparire nel messaggio informativo, allora, secondo la teoria di K. Shannon, il simbolo, la cui probabilità è uguale a p, è ottimo e, cosa particolarmente importante, è teoricamente possibile associare un codice di lunghezza -log 2 p. Tornando al nostro esempio con il messaggio informativo "air crash" e dato che la probabilità della comparsa del carattere "a" (p(a)) è 5/14, la probabilità della comparsa del carattere "t" è 2 /14, e la probabilità che si verifichino tutti gli altri caratteri è 1/14, otteniamo che: per il carattere "a", la lunghezza ottimale del codice è -log 2 (5/14) = 1,48 bit; per il carattere "t" - -log 2 (2/14) = 2,8 bit e per tutti gli altri caratteri è -log 2 (1/14) = 3,8. Poiché nel nostro caso la lunghezza del codice può avere solo un valore intero, allora, arrotondando per eccesso, otteniamo che per il simbolo “a” è ottimale utilizzare un codice di 2 bit, per il simbolo “t” - 3 bit, e per il resto - 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, saranno richiesti 5×2 bit + 2×3 bit + 7×4 bit = 44 bit, ovvero il rapporto di compressione sarà 1,27.

Consideriamo ora gli algoritmi per ottenere codici a lunghezza variabile.

codifica del prefisso

Più metodo semplice ottenere codici di lunghezza variabile è la cosiddetta codifica del prefisso, che permette di ricevere codici di lunghezza intera. caratteristica principale i codici prefissi stanno nel fatto 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 prefissi che semplifica la decodifica delle informazioni.

Spieghiamo questa proprietà dei codici prefissi con un esempio specifico. Sia un sistema di tre codici di prefisso: (0, 10, 11). Come puoi vedere, il codice più breve 0 non coincide con l'inizio dei codici più lunghi 10 e 11. Lascia che il codice 0 specifichi il carattere "a", il codice 10 il carattere "m" e il codice 11 il carattere "p". Quindi la parola "frame" viene codificata dalla sequenza 110100. Proviamo a decodificare questa sequenza. Poiché il primo bit è un 1, il primo carattere può essere solo "m" o "p" ed è determinato dal valore del secondo bit. Poiché il secondo bit è un 1, il primo carattere è "p". Il terzo bit è 0 e corrisponde in modo univoco al carattere "a". Il quarto bit è 1, cioè 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 prefissi, che consiste nel fatto che codici più brevi non possono coincidere con l'inizio di codici più lunghi, consente di decodificare in modo univoco un messaggio informativo codificato con codici prefissi di lunghezza variabile.

I codici di prefisso sono generalmente ottenuti costruendo codice (per sistema binario) alberi. Ogni nodo interno di un tale albero binario ha due bordi in uscita, con un bordo corrispondente al simbolo binario "0" e l'altro - "1". Per certezza, possiamo essere d'accordo sul fatto che al bordo sinistro dovrebbe essere assegnato il simbolo "0" e al bordo destro il simbolo "1".

Poiché non possono esserci cicli in un albero, può esserci sempre un solo percorso dal nodo radice al nodo foglia. Se i bordi dell'albero sono numerati, allora ciascuno di questi percorsi corrisponde a una sequenza binaria univoca. L'insieme di tutte queste sequenze formerà un sistema di codici di prefisso.

Per l'esempio considerato di un sistema di tre codici prefissi: (0, 10, 11), che definiscono i simboli "a", "m" e "p", l'albero dei codici è mostrato in Fig. uno.

Riso. 1. Albero dei codici per il sistema
di tre prefissi: (0, 10, 11)

La comodità della rappresentazione ad albero dei codici prefissi sta nel fatto che è la struttura ad albero che permette di formare codici di lunghezza variabile che soddisfano la condizione principale dei codici prefissi, cioè la condizione che i codici più brevi non coincidano con l'inizio di codici più lunghi.

Finora, abbiamo considerato solo l'idea di codici prefissi a lunghezza variabile. Per quanto riguarda gli algoritmi per ottenere i codici dei prefissi, possono essere sviluppati parecchio, ma i più famosi sono due metodi: Shannon-Fano e Huffman.

Algoritmo di Shannon-Fano

Questo algoritmo per ottenere i codici di prefisso è stato proposto indipendentemente da R. Fano e K. Shannon, è il seguente. Nella prima fase, tutti i simboli della sequenza di informazioni iniziale sono ordinati secondo probabilità decrescenti o crescenti della loro occorrenza (frequenze della loro occorrenza), dopodiché la serie ordinata di simboli in un punto è divisa in due parti in modo che in ciascuna di esse la somma delle frequenze dei simboli è approssimativamente la stessa. A titolo di dimostrazione, considera la parola già familiare "incidente aereo" .

Se i simboli che compongono parola data, ordinati in ordine decrescente rispetto alla frequenza della loro occorrenza, otteniamo la seguente sequenza: (a(5), m(2), v(1), u(1), k(1), c(1), p(1), o (1), f(1)) (tra parentesi è indicata la frequenza di ripetizione di un simbolo in una 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 "c", per cui si formano due successioni: (a (5), t (2)) e (in (1), u (1 ), k (1), c(1), p(1), o(1), φ(1)). Inoltre, le somme delle frequenze di ripetizione dei simboli nella prima e nella seconda sequenza saranno le stesse e pari a 7.

Al primo passaggio della divisione di una sequenza di caratteri, otteniamo la prima cifra del codice di ogni carattere. La regola qui è semplice: per quei caratteri che si trovano 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 separati: a(5) e m(2) (non ci sono altre opzioni di divisione). Quindi la seconda cifra del codice per il simbolo "a" è "0" e per il simbolo "t" - "1". Dal momento che, come risultato della divisione della sequenza, abbiamo ottenuto singoli elementi, allora non sono più divisibili e per il simbolo "a" otteniamo il codice 00, e per il simbolo "t" - il codice 01.

La sequenza (in(1), u(1), k(1), c(1), p(1), o(1), f(1)) può essere suddivisa in sequenze (in(1), u( 1), k(1)) e (c(1), p(1), o(1), φ(1)), o su (v(1), u(1), k(1) ), (c(1)) e (p(1), o(1), φ(1)).

Nel primo caso, la somma delle frequenze dei simboli nella prima e nella seconda sequenza sarà rispettivamente 3 e 4, e nel secondo caso, 4 e 3, rispettivamente. Per certezza, utilizziamo la prima opzione.

Per i caratteri della nuova sequenza risultante (v(1), u(1), k(1)) (questa è la sequenza a sinistra), le prime due cifre del codice saranno 10, e per la sequenza (c( 1), p(1), o(1 ), f(1)) - 11.

Nel nostro esempio (Fig. 2 e 3) si ottiene il seguente sistema di codici prefissi: "a" - 00, "t" - 01, "c" - 100, "i" - 1010, "k" - 1011, "s" - 1100, "r" - 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 prefissi di lunghezza variabile. A differenza dell'algoritmo Shannon-Fano, che prevede la costruzione albero del codice dall'alto verso il basso, questo algoritmo prevede la creazione di un albero di codice ordine inverso, ovvero dal basso verso l'alto (dai nodi foglia al nodo radice).

Nella prima fase, come nell'algoritmo di Shannon-Fano, la sequenza iniziale di simboli è ordinata in ordine decrescente della frequenza di ripetizione dei simboli (elementi della sequenza). Per l'esempio discusso in precedenza con la parola "incidente aereo" otteniamo la seguente sequenza ordinata di elementi: (a(5), m(2), b(1), u(1), k(1), c(1), p(1), o(1), f(1 )).

Successivamente, gli ultimi due elementi della sequenza vengono sostituiti da un nuovo elemento S1, a cui viene assegnata una ricorrenza pari alla somma delle ricorrenze elementi iniziali. Quindi viene eseguito un nuovo ordinamento degli elementi della sequenza in base alla loro ricorrenza. Nel nostro caso, gli ultimi due elementi o(1) e f(1) sono sostituiti dall'elemento S1(2), e la sequenza appena ordinata assumerà la forma: (a(5), m(2), S1( 2), c(1), u(1), k(1), c(1), p(1)).

Continuando questa procedura di sostituzione di due ultimi elementi sequenza a un nuovo elemento con ripetibilità totale e successivo riordinamento della sequenza in base alla ripetibilità degli elementi, arriveremo a una situazione in cui nella sequenza rimane un solo elemento (Fig. 4).

Riso. 4. Dimostrazione dell'algoritmo di Huffman
sull'esempio della parola "incidente aereo"

Contemporaneamente alla sostituzione degli elementi e al riordinamento della sequenza, viene costruito un albero binario di codice. L'algoritmo per costruire un albero è molto semplice: l'operazione di combinazione (sostituzione) di due elementi di una sequenza genera un nuovo elemento nodo sull'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 della sequenza ottenuta per sostituzione (Fig. 5). In questo caso, al bordo sinistro dell'albero del codice può essere assegnato il valore "0" e al bordo destro - "1". Questi valori serviranno in seguito come elementi codice prefisso.

Riso. 5. Costruire un albero del codice
nell'algoritmo di Huffman
(sostituendo gli elementi "o" e "f"
nuovo elemento S1)

L'albero del codice Huffman completo per una parola "incidente aereo" mostrato in fig. 6.

Riso. 6. Albero del codice completo per la parola "incidente aereo",
costruito secondo l'algoritmo di Huffman

Camminando lungo i bordi dell'albero dei codici dall'alto verso il basso, è facile ottenere i codici prefissi per tutti i caratteri del nostro alfabeto informativo:

Ora se provi a scrivere una parola "incidente aereo" nella codifica di Huffman, otteniamo una 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, otteniamo 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 il vero alfabeto delle informazioni è 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, ovvero , il codice che consente di ottenere la lunghezza minima della sequenza di output.

Si può dimostrare che il sistema di codice 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 di Huffman ottimale che è l'algoritmo di generazione di codice a lunghezza variabile più comune ed è incorporato nella maggior parte delle utilità per la compressione e l'archiviazione delle informazioni.

Codifica aritmetica

Come abbiamo già notato, secondo il criterio di Shannon, il codice ottimo è quello in cui viene assegnato un codice di lunghezza –log 2 per ogni carattere. p morso. E se, ad esempio, la probabilità di un determinato carattere è 0,2, la lunghezza ottimale del suo codice sarà -log 2 0,2 ​​= 2,3 bit. È chiaro che i codici prefissi non possono fornire una tale lunghezza di 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 ti permetta di avvicinarti il ​​più possibile a questo limite teorico. I codici prefissi a lunghezza variabile sono efficienti e abbastanza facili da implementare, ma ce ne sono di più modi efficaci codifica, in particolare l'algoritmo di codifica aritmetica.

L'idea della codifica aritmetica è che invece di codificare i singoli caratteri, il codice viene assegnato contemporaneamente all'intera sequenza di informazioni. Allo stesso tempo, è 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 dell'algoritmo di codifica aritmetica è la seguente. Come in tutti i metodi di codifica precedentemente considerati, ogni simbolo della sequenza di informazioni originale è caratterizzato dalla sua probabilità. Alla sequenza originale non codificata viene assegnato un semiintervallo)