• Tutorial

Tanto tempo fa, quando ero ancora uno scolaretto ingenuo, improvvisamente sono diventato terribilmente curioso: come fanno i dati negli archivi a occupare magicamente meno spazio? Appollaiato il mio fedele dial-up, ho iniziato a navigare in Internet alla ricerca di una risposta, e ho trovato molti articoli con una presentazione abbastanza dettagliata delle informazioni che mi interessavano. Ma nessuno di loro mi sembrava facile da capire: gli elenchi di codici sembravano essere alfabetizzazione cinese e i tentativi di comprendere la terminologia insolita e varie formule non avevano successo.

Pertanto, lo scopo di questo articolo è dare un'idea degli algoritmi di compressione più semplici a coloro che, per conoscenza ed esperienza, non consentono ancora loro di comprendere immediatamente la letteratura più professionale, o il cui profilo è lontano da argomenti simili. Quelli. Ti parlerò sulle mie dita di alcuni degli algoritmi più semplici e fornirò esempi della loro implementazione senza elenchi di codici chilometrici.

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

RLE - uniformità compatta

L'algoritmo RLE è probabilmente il più semplice di tutti: la sua essenza è codificare le ripetizioni. In altre parole, prendiamo sequenze di elementi identici e le "comprimiamo" in coppie quantità/valore. Ad esempio, una stringa come "AAAAAAAABCCCC" potrebbe essere convertita in una stringa come "8 × A, B, 4 × C". Questo è, in generale, tutto ciò che c'è da sapere sull'algoritmo.

Esempio di implementazione

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 char 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 sotto forma di 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 FF 00 00

Dopo un po' di riflessione, abbiamo deciso che sarebbe stato utile comprimere in qualche modo tali set per risparmiare spazio. Per farlo li abbiamo analizzati e individuato uno schema: molto spesso ci sono sottosequenze costituite dagli stessi elementi. Naturalmente, RLE è utile per questo!

Codifichiamo i nostri dati utilizzando le conoscenze appena acquisite: 6 × 0, 4, 2, 0, 7 × 4, 4 × 80, 0, 4 × 2, 5 × 255, 2 × 0.

È tempo di presentare in qualche modo il nostro risultato in una forma comprensibile al 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 allocare semplicemente alcun intervallo di valori per i nostri scopi.

Ci sono almeno due modi per uscire da questa situazione:

1. Selezionare un valore di byte come indicatore della catena compressa e, in caso di collisione con dati reali, eseguirne l'escape. Ad esempio, se utilizziamo il valore 255 per scopi di "servizio", quando incontriamo questo valore nei dati di input, dovremo scrivere "255, 255" e dopo l'indicatore utilizzare un massimo di 254.
2. Strutturare i dati codificati, specificando il numero non solo per i ripetuti, ma anche per ulteriori singoli elementi successivi. Allora sapremo in anticipo dove si trovano i dati.

Il primo metodo nel nostro caso non sembra essere efficace, quindi, forse, faremo ricorso 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 di sequenza: 0 - elementi singoli, 1 - identico. Prendiamo 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 per le esigenze di servizio, diciamo, due byte, ma nel nostro caso sequenze così lunghe sono estremamente rare, quindi è più semplice 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 ci possono essere sequenze di lunghezza zero, quindi possiamo aumentare la lunghezza massima a 128 byte sottraendo uno dalla lunghezza durante la codifica e aggiungendone uno durante la decodifica. Pertanto, possiamo codificare lunghezze da 1 a 128 invece di lunghezze da 0 a 127.

La seconda cosa che si può notare è che non ci sono sequenze di elementi identici di lunghezza unitaria. Pertanto, ne sottraiamo uno in più dal valore della lunghezza di tali sequenze durante la codifica, aumentando così la loro lunghezza massima a 129 (la lunghezza massima di una catena di singoli elementi è sempre pari a 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 overhead come, dove T è il tipo della sequenza e L è la lunghezza. Prenderemo subito in considerazione che scriviamo le lunghezze in una forma modificata: a T = 0 sottraiamo uno da L e a T = 1 - due.

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

Proviamo a decodificare il nostro risultato:

• ... T = 1, il che significa che il byte successivo verrà ripetuto L + 2 (4 + 2) volte: 0, 0, 0, 0, 0, 0.
• ... T = 0, quindi leggiamo solo L + 1 (2 + 1) byte: 4, 2, 0.
• ... T = 1, ripetiamo il byte successivo 5 + 2 volte: 4, 4, 4, 4, 4, 4, 4.
• ... T = 1, ripetiamo il byte successivo 2 + 2 volte: 80, 80, 80, 80.
• ... T = 0, leggi 0 + 1 byte: 0.
• ... T = 1, ripeti byte 2 + 2 volte: 2, 2, 2, 2.
• ... T = 1, ripetiamo il byte 3 + 2 volte: 255, 255, 255, 255, 255.
• ... T = 1, ripetiamo il byte 0 + 2 volte: 0, 0.

E ora l'ultimo passaggio: salva il risultato come array di byte. Ad esempio, una coppia compressa in byte avrà il seguente aspetto:

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 modo così semplice, per questo esempio di dati di input, abbiamo ottenuto 18 byte su 32. Non un brutto risultato, soprattutto considerando che su catene più lunghe può risultare molto migliore.

Possibili miglioramenti

L'efficienza di un algoritmo dipende non solo dall'algoritmo stesso, ma anche dal modo in cui viene implementato. Pertanto, per dati diversi, è possibile sviluppare diverse varianti della codifica e della rappresentazione dei dati codificati. Ad esempio, quando si codificano immagini, è possibile creare catene di lunghezza variabile: allocare un bit per l'indicazione di una catena lunga e, se è impostato su uno, memorizzare anche la lunghezza nel byte successivo. Quindi sacrifichiamo la lunghezza delle catene corte (65 elementi invece di 129), ma d'altro canto diamo la possibilità di codificare catene lunghe fino a 16385 elementi (2 14 + 2) con soli tre byte!

È possibile ottenere un'efficienza aggiuntiva mediante l'uso di tecniche di codifica euristica. Ad esempio, codifichiamo a nostro modo la seguente stringa: "ABBA". Otteniamo ", A,, B,, A" - cioè Abbiamo trasformato 4 byte in 6, gonfiato i dati originali fino a una volta e mezza! E più brevi sequenze alternate di diversi tipi, più dati ridondanti. Se teniamo conto di questo, sarebbe possibile codificare il risultato come ", A, B, B, A" - avremmo speso 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 Ziva (Jacob Z IV). I numeri 77 nel titolo significano 1977, in cui è stato pubblicato un articolo che descrive questo algoritmo.

L'idea di base è quella di codificare le stesse sequenze di elementi. Cioè, se una catena di elementi si verifica più di una volta nei dati di input, tutte le successive occorrenze di essa possono essere sostituite con "collegamenti" alla sua prima istanza.

Come il resto degli algoritmi in questa famiglia della famiglia, LZ77 utilizza un dizionario che memorizza le sequenze incontrate in precedenza. Per questo, 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 è un dizionario dinamico per questo algoritmo: ogni elemento in essa contenuto corrisponde a due attributi: posizione nella finestra e lunghezza. Anche se in senso fisico, è solo un pezzo di memoria che abbiamo già codificato.

Esempio di implementazione

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

“La compressione e la decompressione lasciano 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 pressione. ahahah
0040: 61 68 61 68 61 21 ahaha!

Non abbiamo ancora deciso la dimensione della finestra, ma concorderemo che è maggiore della dimensione della stringa codificata. Proviamo a trovare tutte le stringhe di caratteri ripetute. Considereremo una catena come una sequenza di simboli con una lunghezza maggiore di uno. Se la catena fa parte di una catena ripetuta più lunga, la ignoreremo.

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

Per maggiore chiarezza, osserviamo il diagramma dove sono visibili le corrispondenze delle sequenze ripetute e le loro prime occorrenze:

Forse l'unico punto poco chiaro qui sarà la sequenza "Hahahahaha!" Ma non c'è niente di insolito qui, abbiamo usato un trucco che consente all'algoritmo di comportarsi a volte come l'RLE precedentemente descritto.

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

Con questo risolto. Ora sostituiamo i duplicati trovati con i collegamenti al dizionario. Scriveremo il collegamento nel formato, dove P è la posizione della prima occorrenza della catena nella stringa, L è la sua lunghezza.

“La compressione e t de leave i. Ahah!"

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

“La compressione e t de leave i. Ahah!"

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

È il momento di decidere la dimensione della finestra e la lunghezza massima della frase codificata. Poiché si tratta di testo, raramente ci saranno sequenze ripetitive particolarmente lunghe. Quindi assegniamo per la loro lunghezza, diciamo, 4 bit: per noi è sufficiente un limite di 15 caratteri alla volta.

Ma la dimensione della finestra dipende già da quanto profondamente cercheremo catene identiche. Poiché si tratta di testi piccoli, sarebbe giusto integrare il numero di bit che stiamo utilizzando a due byte: indirizzeremo collegamenti nell'intervallo di 4096 byte, utilizzando 12 bit per questo.

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

Quindi, presentiamo il nostro testo codificato con questi emendamenti:

“La compressione e t de leave i. Ahah!"

Ora, di nuovo, dobbiamo separare in qualche modo le catene compresse dal resto dei dati. Il modo più comune è riutilizzare la struttura e specificare direttamente dove si trovano i dati compressi e dove no. Per fare ciò, divideremo i dati codificati in gruppi di otto elementi (simboli o collegamenti), e prima di ciascuno di questi gruppi inseriremo un byte, dove ogni bit corrisponde al tipo dell'elemento: 0 per un simbolo e 1 per un collegamento.

Ci dividiamo in gruppi:

• "Il comp"
• "Resione"
• "E t de"
• "Lasciare"
• "IO. Ahah"

Composizione dei gruppi:

“(0.0.0.0.0.0.0.0) La comp (0.0.0.0.0.0.0.0) ression (0.0.0.0.0.1 , 0,0) e t de (1,0,0,0,0,0,1 ,0) lasciare (0,1,0,0,0,0,0,1) i. Ah (0)! "

Quindi, se durante l'unpacking incontriamo il bit 0, allora leggiamo semplicemente il carattere nel flusso di output, se il bit 1, leggiamo il collegamento e per riferimento leggiamo la sequenza dal dizionario.

Ora tutto ciò che dobbiamo fare è raggruppare il risultato in un array di byte. Siamo d'accordo che usiamo bit e byte nell'ordine più significativo. Vediamo come i collegamenti sono compressi in byte usando un esempio:

Di conseguenza, il nostro flusso compresso sarà simile a questo:

0000: 00 54 68 65 20 63 6f 6d 70 00 72 65 73 73 69 6f #Il comp # ressio
0010: 6e 20 04 61 6e 64 20 74 01 31 64 65 82 01 5a 6c n #and t ## de ### l
0020: 65 61 76 65 01 b1 20 41 69 02 97 2e 20 48 61 68 gronda ## # i ##. ahah
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 i vantaggi della codifica euristica, si consideri il seguente esempio:

“Il lungo gooooong. Loooooower legato. "

Troviamo sequenze solo per la parola "loooooower":

“Il lungo gooooong. Erano legati".

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

“Il lungo gooooong. L'essere vincolato. "

Allora spenderemmo un byte in meno.

Invece di una conclusione

Nonostante la loro semplicità e un'efficienza apparentemente non troppo elevata, questi algoritmi sono ancora ampiamente utilizzati in varie aree 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 presentati in questo modo aiuti qualcuno a capire le basi e iniziare a guardare verso cose più serie.

La codifica run-length (RLE) o ripetizione della codifica è un semplice algoritmo di compressione dei dati che opera con serie di dati, ovvero sequenze in cui lo stesso carattere si verifica più volte di seguito. Durante la codifica, una stringa di caratteri identici che costituisce una serie viene sostituita da una stringa che contiene il carattere ripetuto stesso e il numero di volte che viene ripetuto.

Caratteristiche dell'algoritmo RLE:

Rapporti di compressione: Prima opzione: 32, 2, 0,5. Seconda opzione: 64, 3, 128/129. (Probabilità migliore, media, peggiore). Classe di immagine: L'algoritmo si concentra su immagini con un numero ridotto di colori: grafica aziendale e scientifica. Simmetria: Circa uno.

Caratteristiche: Gli aspetti positivi dell'algoritmo, forse, possono essere attribuiti solo al fatto che non richiede memoria aggiuntiva durante l'archiviazione e l'annullamento dell'archiviazione e funziona anche rapidamente. Una caratteristica interessante della codifica di gruppo è che il grado di archiviazione per alcune immagini può essere notevolmente aumentato semplicemente cambiando l'ordine dei colori nella tavolozza dell'immagine.

La prima versione dell'algoritmo

Questo algoritmo è estremamente semplice da implementare. Run Length Encoding (RLE) è uno degli algoritmi più antichi e semplici per l'archiviazione della grafica. L'immagine al suo interno (come in diversi algoritmi descritti di seguito) viene inserita in una stringa di byte lungo le linee raster. La compressione stessa in RLE avviene per il fatto che nell'immagine originale sono presenti stringhe degli stessi byte. Sostituendoli con coppie<contatore di ripetizioni, valore> riduce la ridondanza dei dati.

L'algoritmo è progettato per la grafica aziendale: immagini con ampie aree di colori ripetuti. Non è raro che un file diventi più grande per questo semplice algoritmo. Può essere facilmente ottenuto applicando la codifica batch alle fotografie a colori elaborate. Per ingrandire l'immagine due volte, deve essere applicato a un'immagine in cui i valori di tutti i pixel sono maggiori del 11000000 binario e non vengono ripetuti a coppie di fila.

La seconda variante dell'algoritmo

La seconda variante di questo algoritmo ha un rapporto di archiviazione massimo più alto e meno aumenta la dimensione del file originale.

29. Algoritmo di compressione lzw

L'algoritmo ha preso il nome dalle prime lettere dei nomi dei suoi sviluppatori - Lempel, Ziv e bene.

L'algoritmo LZW si basa sull'idea di espandere l'alfabeto, che consente di utilizzare caratteri aggiuntivi per rappresentare stringhe di caratteri ordinari. Utilizzando, ad esempio, invece di codici ASCII a 8 bit a 9 bit, si ottengono ulteriori 256 caratteri. Il funzionamento del compressore si riduce alla costruzione di una tabella composta da righe e dai relativi codici. L'algoritmo di compressione si riduce a quanto segue: il programma legge il carattere successivo e lo aggiunge alla riga. Se la riga è già presente nella tabella, la lettura continua, in caso contrario la riga indicata viene aggiunta alla tabella delle righe. Più righe doppie ci sono, più i dati verranno compressi. Tornando all'esempio telefonico, possiamo, usando un'analogia molto semplificata, dire che comprimendo il record 233 34 44 con il metodo LZW, arriveremo all'introduzione di nuove linee - 333 e 444 e, esprimendole con caratteri aggiuntivi, saremo in grado di ridurre la lunghezza del record.

Caratteristiche dell'algoritmo LZW:Rapporti di compressione: Circa 1000, 4, 5/7 (probabilità migliore, media, peggiore). La compressione di 1000 volte si ottiene solo su immagini a un colore in multipli di circa 7 MB. Classe di immagine: si concentra su LZW per immagini generate al computer a 8 bit. Comprime a causa delle stesse catene secondarie nel flusso. Simmetria: Quasi simmetrico, supponendo un'implementazione ottimale della ricerca di una riga in una tabella.

Caratteristiche: La situazione in cui l'algoritmo ingrandisce l'immagine è estremamente rara. LZW è universale: sono le sue varianti che vengono utilizzate negli archivi ordinari.

Il processo di compressione sembra abbastanza semplice. Leggiamo in sequenza i caratteri del flusso di input e controlliamo se c'è una tale riga nella tabella delle righe che abbiamo creato. Se c'è una riga, allora leggiamo il carattere successivo e, se non c'è nessuna riga, inseriamo il codice per la riga trovata precedente nel flusso, inseriamo la riga nella tabella e ricominciamo la ricerca.

La particolarità di LZW è che per la decompressione non è necessario salvare la tabella delle stringhe in un file per la decompressione. L'algoritmo è strutturato in modo tale da poter ricostruire la tabella delle stringhe utilizzando solo un flusso di codici.

Un'immagine tipica scattata con una fotocamera digitale ha una risoluzione di circa 3000x2000, ad es. circa 6 megapixel; il colore è in genere 24 bit per pixel. Pertanto, il volume dei dati iniziali è di circa 17 megabyte. Per i dispositivi di input di immagini professionali, la dimensione del raster risultante può essere significativamente maggiore e la profondità del colore - fino a 48 bit per pixel ("Grafica raster hardware moderna"). Di conseguenza, la dimensione di un'immagine può essere superiore a 200 megabyte. Pertanto, gli algoritmi compressione immagini, o, in altre parole, algoritmi che riducono la quantità di dati che rappresentano un'immagine.

Esistono due classi principali di algoritmi:

1. A è chiamato un algoritmo compressione senza perdite(compressione senza perdita di dati inglese), se esiste un algoritmo A -1 (inverso ad A) tale che per qualsiasi immagine I A (I) = I 1 e A -1 (I 1) = I. L'immagine I è definita come un insieme di valori degli attributi dei pixel; dopo aver applicato l'algoritmo A a I, otteniamo il set di dati I 1. La compressione senza perdita viene utilizzata in formati di immagini grafiche come: GIF, PCX, PNG, TGA, TIFF 1 In generale, questo formato supporta anche la compressione con perdita., molti formati proprietari di produttori di fotocamere digitali, ecc.);
2. A è chiamato un algoritmo compressione con perdita(Compressione con perdita di dati inglese), se non fornisce la possibilità di ripristinare accuratamente l'immagine originale. Un algoritmo che è accoppiato con A, che fornisce un recupero approssimativo, sarà indicato come A *: per un'immagine IA (I) = I 1, A * (I 1) = I 2 e l'immagine ricostruita risultante I 2 non necessariamente coincide esattamente con I. La coppia A, A * è selezionata in modo da fornire rapporti di compressione elevati e tuttavia mantenere la qualità visiva, ad es. ottenere una minima differenza di percezione tra io e io 2. La compressione con perdita viene utilizzata nei seguenti formati di immagine: JPEG, JPEG2000, ecc.

Questa lezione si concentra sulla compressione senza perdita di dati, necessaria nei casi in cui le informazioni sono state ottenute a un costo elevato (ad esempio, immagini mediche o immagini satellitari) o in altri casi in cui anche la minima distorsione è indesiderabile.

13.2. La non esistenza di un algoritmo perfetto

Come già accennato nel paragrafo precedente, l'immagine I è considerata come un insieme (sequenza) di valori degli attributi dei pixel. In quanto segue in questa lezione, tutti gli algoritmi e le affermazioni si riferiscono sia a immagini che a sequenze arbitrarie, i cui elementi possono assumere un numero finito di valori.

Dichiarazione 13.2.1... Non esiste un algoritmo per comprimere senza perdita di dati qualsiasi set di dati.

Ci sono 2 N sequenze di N bit di dimensione (considerare un bit come il vettore minimo di informazioni). Sia un algoritmo A tale che, dove | I | - volume dati (lunghezza della sequenza). Sia M = max M k, allora M< N . Существует 2 1 + 2 2 + ... + 2 M последовательностей длины, меньшей или равной M . Но 2 1 +2 2 + ... + 2 M = 2 M + 1 -2< 2 N ... Contraddizione.

Segue dall'affermazione che ha senso sviluppare algoritmi che comprimono in modo efficiente una certa classe di immagini; allo stesso tempo, per questi algoritmi ci saranno sempre immagini per le quali non forniranno la compressione.

13.3. Algoritmi di codifica della lunghezza delle ripetizioni (RLE)

Questo tipo di algoritmi (algoritmi di codifica della lunghezza di ripetizione 2 Un altro nome si trova spesso in letteratura: la codifica di gruppo.(RLE 3 inglese Codifica della lunghezza della corsa)) si basa sul principio più semplice: sostituiremo gruppi ripetuti di elementi della sequenza originale con una coppia (quantità, elemento) o solo con una quantità.

RLE - livello di bit

Considereremo i dati originali a livello di una sequenza di bit; ad esempio, rappresentando un'immagine in bianco e nero. Di solito ci sono diversi 0 o 1 in una riga e puoi ricordare solo il numero di cifre identiche consecutive. Quelli. sequenza 0000 11111 000 11111111111 corrisponde a un insieme di numeri di numeri di ripetizioni 4 5 3 11. Sorge la seguente sfumatura: anche i numeri che indicano il numero di ripetizioni devono essere codificati in bit. Possiamo supporre che ogni numero di ripetizioni vari da 0 a 7 (cioè può essere codificato con esattamente tre bit), quindi la sequenza 11111111111 può essere confrontata con i numeri 7 0 4, cioè 7 uno, 0 zeri, 4 uno. Ad esempio, una sequenza di 21 unità, 21 zeri, 3 unità e 7 zeri è codificata in questo modo: 111 000 111 000 111 111 000 111 000 111 011 111 , cioè. dalla sequenza originale, che ha una lunghezza di 51 bit, è stata ottenuta una sequenza di una lunghezza di 36 bit.

L'idea alla base di questo metodo viene utilizzata durante l'invio di fax.

RLE - Livello byte

Supponiamo che l'input sia un'immagine in scala di grigi, dove 1 byte è assegnato al valore dell'intensità dei pixel. È chiaro che, rispetto a un raster in bianco e nero, l'aspettativa di una lunga stringa di bit identici è notevolmente ridotta.

Divideremo il flusso di input in byte (lettere) e codificheremo le lettere ripetute a coppie (numero, lettera).

Quelli. AABBBCDAA codifica (2A) (3B) (1C) (1D) (2A). Tuttavia, potrebbero esserci lunghi segmenti di dati in cui nulla viene ripetuto e codifichiamo ogni lettera in una coppia (numero, lettera).

Supponiamo di avere un numero fisso (lettera) M (da 0 a 255). Quindi una singola lettera può essere codificata da sola, - output = S, e se ci sono più lettere o, quindi output = CS, dove C> M, e C - M è il numero di lettere consecutive S. Ad esempio, daremo solo l'algoritmo di decodifica.

// M - limite fisso // legge i caratteri in sequenza dal flusso di input // in - input - sequenza compressa // out - output - sequenza non compressa while (in.Read (c)) (if (c> M) (// contatore di casi n = c - M; in.Read (c); for (i = 0; i< n; i++) out.Write(c); } else // случай просто символа out.Write(c); } Listato 13.1. Algoritmo di decodifica RLE - Livello di byte

Il numero M è solitamente 127. Più spesso viene utilizzata una modifica di questo algoritmo, dove il segno del contatore è la presenza di unità nei 2 bit più significativi del carattere letto. I restanti 6 bit sono il valore del contatore.

Questa modifica di questo algoritmo viene utilizzata nel formato PCX. Tuttavia, le modifiche di questo algoritmo sono raramente utilizzate da sole, poiché la sottoclasse di sequenze su cui questo algoritmo è efficace è relativamente ristretta. Le modifiche dell'algoritmo vengono utilizzate come una delle fasi della pipeline di compressione (ad esempio, nel formato JPEG,