Scarica la lezione, gli esercizi e le soluzioni (PDF)
SCUOLAGRAM · INFORMATICA
La compressione senza perdita con RLE
Informatica · Scuola secondaria di primo grado · Proposta per seconda/terza
In breve
La codifica RLE descrive una sequenza di simboli uguali indicando quanti sono e quale simbolo si ripete. Con regole chiare possiamo ricostruire esattamente il punto di partenza: per questo è una codifica senza perdita. Non accorcia però ogni sequenza. Lo scopriremo con lettere, carta e una piccola immagine a quadretti, senza computer.
Il problema: devo davvero scriverli tutti?
Immagina di dettare a un compagno questa fila: BBBBBBBB. Potresti leggere otto volte la lettera B. Oppure potresti dire «otto B». Il messaggio è più breve e il compagno può riscrivere proprio la fila iniziale.
L’idea della run-length encoding, abbreviata in RLE, è questa: descrivere i gruppi di simboli uguali consecutivi, invece di ripetere tutti i simboli. Run significa qui una sequenza ininterrotta dello stesso simbolo; length è la sua lunghezza. Non basta che due lettere siano uguali: per appartenere allo stesso gruppo devono stare una accanto all’altra. In BBNNBB i due gruppi di B rimangono separati, perché fra loro ci sono delle N. [1, §7.2; 2, «Lossless compression»]
Comprimere senza perdita non significa cancellare una parte del disegno e sperare che non si noti. Significa rappresentare gli stessi dati in un altro modo, dal quale si possa tornare esattamente a quelli iniziali. Nel nostro esercizio, anche una sola casella ricostruita diversamente segnala un errore. [1, §7.2.1; 2, «Lossless compression»]
Le regole del nostro laboratorio
Useremo solo B = bianco e N = nero. Sono anche etichette: non serve distinguere colori. Ogni gruppo consecutivo diventa numero + lettera, per esempio 4B. Il numero conta quante volte ripetere quella lettera. Si legge e si scrive da sinistra verso destra. I gruppi sono separati da uno spazio: 4B 2N.
È una notazione didattica scelta per questa lezione, non l’unico formato RLE e non un formato di file da aprire con un programma. Il destinatario deve conoscere le stesse regole del mittente.
Parole da ricordare: codificare = passare alla descrizione RLE; decodificare = ricostruire la sequenza; senza perdita = ritrovare gli stessi dati.
Quando la descrizione è davvero più corta?
Prima codifico, poi ricostruisco
Partiamo da BBBBNNNBB. I gruppi sono quattro B, tre N, due B. Scriviamo quindi 4B 3N 2B. Per decodificare facciamo il percorso inverso: scriviamo quattro B, poi tre N, poi due B. Otteniamo di nuovo BBBBNNNBB. L’ordine dei gruppi conta: mettere insieme tutte le B produrrebbe un’altra sequenza.
Il nostro metro: caratteri, non byte
Per fare confronti facili, contiamo solo lettere e cifre. Gli spazi che separano i gruppi non si contano. Anche nell’originale si contano solo le lettere. In 12B ci sono tre caratteri: la cifra 1, la cifra 2 e la lettera B. Il numero dodici non occupa un unico carattere.
| Sequenza di partenza | Codifica RLE | Caratteri prima → dopo |
|---|---|---|
BBBBBBBB |
8B |
8 → 2 |
BBBBNNNBB |
4B 3N 2B |
9 → 6 |
BNBNBNBN |
1B 1N 1B 1N 1B 1N 1B 1N |
8 → 16 |
BBBBBBBBBBBB |
12B |
12 → 3 |
La fila alternata diventa più lunga! Ogni lettera richiede anche una cifra che dice «una volta». Senza perdita e più corto non sono sinonimi: la fila si ricostruisce comunque, ma in quel caso la nostra RLE non conviene. Con gruppi lunghi, invece, il conteggio può essere vantaggioso.
Questo è un confronto in un modello di caratteri. Non stiamo misurando i byte di un vero file: in un file reale contano anche il modo di memorizzare numeri, simboli, separatori e informazioni sul formato. Non possiamo dire che un’immagine sul disco occuperà un certo numero di byte solo contando i nostri segni sulla carta. [1, §7.2.2]
Prova guidata
NNNBBBBN diventa 3N 4B 1N. I caratteri passano da 8 a 6: due in meno. Decodifica i tre gruppi e confronta una lettera alla volta con la fila iniziale. Per questa prova, la ricostruzione esatta è il controllo decisivo.
Domanda da discutere: due file che contengono la stessa immagine devono per forza avere la stessa dimensione? Non necessariamente: il modo di rappresentare e memorizzare i dati può essere diverso. Il nostro laboratorio mostra soltanto un piccolo modello di questa idea.
Laboratorio su carta · Un messaggio a quadretti
Occorrente: questa scheda, una matita e un foglio per coprire il disegno. Nessuno schermo o account.
Un’immagine digitale può essere descritta come una griglia di piccoli elementi, i pixel. Qui ne usiamo un modello su carta: 8 colonne e 5 righe, una B o una N per casella. Non studiamo densità di stampa o qualità delle fotografie.
Regola aggiuntiva: leggi ogni riga da sinistra a destra, procedendo dall’alto in basso. Codifica le righe separatamente: a ogni riga riparti da capo, senza unire i gruppi fra righe. Scrivi il numero della riga fuori dalla codifica.
| Riga | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| 1 | B | B | N | N | N | N | B | B |
| 2 | B | N | N | B | B | N | N | B |
| 3 | N | N | B | N | N | B | N | N |
| 4 | B | N | N | B | B | N | N | B |
| 5 | B | B | N | N | N | N | B | B |
- Codifica ciascuna delle cinque righe su un foglio separato. Non consegnare il disegno a chi deve ricostruirlo.
- A coppie: chi riceve conosce dimensioni e regole, ma copre la figura originale. Ricostruisce le righe nella griglia vuota qui sotto usando solo la codifica. Poi scoprite l’originale e confrontate ogni posizione. Da soli: coprite l’originale e fate lo stesso controllo.
- Per ogni riga, la somma dei conteggi deve dare 8. Basta questo a garantire che il disegno sia giusto? Spiegate.
- Contate lettere e cifre nella codifica completa e confrontatele con le 40 lettere iniziali. Gli spazi, i numeri di riga e le informazioni sulle dimensioni sono esclusi dal nostro confronto, da entrambe le parti. Questa immagine conviene in RLE?
| Riga | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| 1 | ||||||||
| 2 | ||||||||
| 3 | ||||||||
| 4 | ||||||||
| 5 |
Sfida breve: progettate un’altra griglia 8×5 che usi meno caratteri in RLE. Conservate originale e codifica per controllare la ricostruzione. Potete usare lettere senza colorare le caselle.
Mettiti alla prova
Nome ____________________ Classe ______ Data __________
Usa sempre le regole della lezione: gruppi massimi di lettere uguali consecutive, numero prima della lettera, B/N come soli simboli. Per il confronto conta cifre e lettere; non contare gli spazi.
1 · Codifica
Trasforma in RLE: a) BBBBNNBB; b) NNNNNN; c) BNBN.
Risposte:
2 · Decodifica
Ricostruisci: a) 2N 3B 1N; b) 1B 4N 2B. Non scambiare l’ordine dei gruppi.
Risposte:
3 · Conviene oppure no?
Per ciascuna fila scrivi la codifica, conta i caratteri prima e dopo e concludi: più corta, uguale oppure più lunga.
a) BBNNBBNN b) BBBBBBBBNNNN c) BNBNBN
4 · Caccia all’errore
Per BBBBNNBB una compagna propone 6B 2N. La somma delle quantità è giusta. La codifica è corretta? Decodificala e spiega che cosa non torna.
5 · Conta anche le cifre
Una fila contiene dodici N consecutive. Qual è la codifica? Quanti caratteri ha? Di quanti caratteri è più corta della fila originale, secondo il nostro modello?
6 · Spiega con parole tue
«Se la codifica si allunga, non è più senza perdita». Sei d’accordo? Usa BNBN come controesempio oppure come prova. Perché dai nostri conteggi non possiamo ricavare i byte di un vero file?
Soluzioni commentate · Esercizi
Da distribuire dopo il lavoro. Le risposte spiegano il procedimento, non soltanto il risultato.
1 · Codifica
a) 4B 2N 2B. Ci sono due gruppi distinti di B; unirli cambierebbe l’ordine dei simboli. b) 6N: l’intera fila è un unico gruppo. c) 1B 1N 1B 1N: anche un gruppo di una sola lettera richiede il suo conteggio.
2 · Decodifica
a) NNBBBN: due N, tre B, una N, per sei lettere in tutto. b) BNNNNBB: una B, quattro N, due B, per sette lettere. I totali aiutano a controllare che non manchino lettere, ma va verificato anche il loro ordine.
3 · Conviene oppure no?
| Caso | Codifica | Prima → dopo | Conclusione |
|---|---|---|---|
| a | 2B 2N 2B 2N |
8 → 8 | Uguale |
| b | 8B 4N |
12 → 4 | Più corta di 8 caratteri |
| c | 1B 1N 1B 1N 1B 1N |
6 → 12 | Più lunga di 6 caratteri |
Nel caso a, ciascun gruppo di due lettere diventa una cifra e una lettera: non c’è risparmio. Nel caso b i gruppi lunghi permettono di risparmiare. Nel caso c ogni gruppo contiene una sola lettera, ma richiede due caratteri per essere descritto.
4 · Caccia all’errore
6B 2N si decodifica in BBBBBBNN, che è diverso da BBBBNNBB. La lunghezza totale, otto, è giusta in entrambi i casi, ma non basta: nella proposta le ultime due B sono state spostate. La codifica corretta è 4B 2N 2B. Un controllo completo confronta ogni posizione, non solo la somma dei conteggi.
5 · Conta anche le cifre
La codifica è 12N: 3 caratteri, non 2. Rispetto alle dodici lettere originali si usano 9 caratteri in meno. Scrivere un numero con due cifre ha un costo diverso dallo scrivere un numero con una sola cifra, nel modello adottato.
6 · Spiega con parole tue
Non sono d’accordo: BNBN diventa 1B 1N 1B 1N, che ha otto caratteri invece di quattro, ma si ricostruisce esattamente in BNBN. «Senza perdita» riguarda la ricostruzione, non la convenienza. Inoltre abbiamo ignorato spazi e informazioni sul formato e non abbiamo scelto una memorizzazione binaria: i nostri caratteri contati non danno direttamente la dimensione reale di un file in byte.
Soluzioni del laboratorio e guida per chi insegna
La tessera è un motivo astratto: conta ricostruire le posizioni, non riconoscere un oggetto.
| Riga | Codifica | Caratteri |
|---|---|---|
| 1 | 2B 4N 2B |
6 |
| 2 | 1B 2N 2B 2N 1B |
10 |
| 3 | 2N 1B 2N 1B 2N |
10 |
| 4 | 1B 2N 2B 2N 1B |
10 |
| 5 | 2B 4N 2B |
6 |
Totale iniziale: 40 lettere; totale RLE: 42 caratteri. La descrizione si allunga di 2 caratteri: non conviene in questo modello, pur essendo senza perdita. Ogni riga somma a 8, ma il totale non controlla l’ordine: occorre confrontare le singole caselle.
Per la sfida sono possibili molte risposte. Un esempio è una griglia con ogni riga BBBBNNNN: ogni riga diventa 4B 4N, quindi 4 caratteri per riga e 20 in tutto, contro 40. La decodifica restituisce esattamente cinque righe uguali all’originale.
Prerequisiti: contare, seguire una sequenza da sinistra a destra e orientarsi tra righe e colonne; non è richiesta programmazione.
Obiettivi osservabili
Al termine del lavoro l’alunno sa individuare gruppi consecutivi, codificarli e decodificarli; controlla la ricostruzione; confronta lunghezze usando una regola dichiarata; distingue ricostruzione senza perdita e riduzione di lunghezza.
Una possibile ora di lezione
5 minuti: dettatura della fila iniziale e raccolta di proposte. 10 minuti: regole, esempio guidato e differenza fra caratteri e byte. 20 minuti: laboratorio a coppie o individuale. 15 minuti: esercizi selezionati. 10 minuti: confronto, correzione e risposta di uscita: «Quando la nostra RLE non conviene?» Tempi proposti, da adattare dopo la prova in classe.
Accessibilità e osservazione
Non richiedere la percezione del colore: le lettere B/N sono sempre sufficienti. Consentire una striscia di carta per seguire una riga alla volta, lettura ad alta voce dei gruppi, risposta dettata a un compagno e tempi aggiuntivi. Per iniziare, limitarsi a quattro caselle per riga; mantenere poi la stessa regola. Valutare separatamente comprensione e rapidità di scrittura.
Osservare quattro aspetti: individua i gruppi; rispetta l’ordine; ricostruisce la fila; giustifica il confronto. Un errore di calcolo e un errore di regola non sono la stessa difficoltà. Non usare la sola lunghezza finale come prova di correttezza.
Fonti e precisazioni
I riferimenti numerati richiamati nella spiegazione riguardano i principi tecnici. Esempi B/N, disegno, esercizi e soluzioni sono elaborazioni originali di questa lezione; non sono esercizi riprodotti dalle fonti.
[1] University of Canterbury · Computer Science Field Guide
«7.2. Run length encoding»
https://www.csfieldguide.org.nz/en/chapters/coding-compression/run-length-encoding/
- §7.2, introduzione, paragrafo che inizia «In run length encoding, we replace each row…»: gruppi di pixel consecutivi dello stesso colore. La fonte usa conteggi alternati iniziando dal bianco; la nostra notazione numero+lettera è diversa ed esplicita il simbolo.
- §7.2.1, «Converting run length encoding back to the original representation», incipit «Just to ensure that we can reverse…»: ricostruzione della rappresentazione iniziale.
- §7.2.2, «Analysing run length encoding», paragrafo «One simple way to consider this…» e riquadro «Run length encoding representation in practice»: confronto didattico dei caratteri distinto dalla rappresentazione effettiva in bit. La fonte conta anche le virgole; qui non usiamo virgole e non contiamo gli spazi.
- §7.2, riquadro «The PBM file format», paragrafo «The second line specifies the width…»: esempio di formato che dichiara larghezza e altezza. Non è un’affermazione che ogni RLE usi lo stesso header.
[2] BBC Bitesize · Computer Science, Cambridge OCR
«Units and data representation — Compression»
https://www.bbc.co.uk/bitesize/guides/zfspfcw/revision/10
- «Lossless compression», paragrafo «With lossless compression…»: riduzione senza eliminare dati.
- Nella stessa sezione, paragrafi «One method of lossless compression is run length encoding (RLE)» e «RLE looks for the runs…»: RLE come metodo senza perdita, individuazione delle ripetizioni consecutive e registrazione di dato e quantità.
Sono due fonti editorialmente indipendenti: una risorsa universitaria e un servizio didattico della BBC. Sostengono il principio di RLE e la ricostruibilità, non l’esatta notazione del nostro laboratorio. L’espansione delle sequenze alternate è verificata direttamente con le regole e i conteggi dichiarati nella lezione.
Confini da non oltrepassare: nessuna equivalenza automatica fra caratteri e byte; nessuna garanzia che RLE accorci qualsiasi sequenza; nessuna affermazione generale sul funzionamento di tutti i PDF, ZIP o formati immagine. La proposta non richiede account, connessione, fotografie personali o condivisioni pubbliche.
Revisione docente: APERTA. Prova in classe: APERTA.