Data compression · Compression de données
Why compress data
- Data takes up space to store and time to send.
- Compression makes a file smaller so it is cheaper to save and faster to share.
- There are two kinds: lossless and lossy.
Pourquoi compresser les données
- Les données prennent de l'espace pour être stockées et du temps pour être envoyées.
- La compression rend un fichier plus petit afin qu'il soit moins cher à sauvegarder et plus rapide à partager.
- Il y a deux types : sans perte et avec perte.
Lossless compression
- Lossless makes a file smaller but keeps every bit of the data.
- When you open the file, you get back the exact original.
- It works by finding patterns and writing them in a shorter way.
Compression sans perte
- La compression sans perte réduit un fichier tout en conservant chaque bit des données.
- Lorsque vous ouvrez le fichier, vous récupérez l'original exact.
- Elle fonctionne en trouvant des motifs et en les écrivant de manière plus courte.
Original: AAAAAAAA-BBB
Shorter: 8A-3B (8 A's, then 3 B's)
Open it: AAAAAAAA-BBB (exactly the same again)
Lossy compression
- Lossy makes a file much smaller by throwing away some data.
- It drops details that people can barely see or hear.
- You cannot get the exact original back — but it is "close enough".
Compression avec perte
- La compression avec perte réduit considérablement un fichier en jetant certaines données.
- Elle élimine les détails que les gens peuvent à peine voir ou entendre.
- Vous ne pouvez pas récupérer l'original exact — mais c'est "assez proche".
Photo (large) --lossy--> Photo (small)
A few colors and fine details are gone,
but your eye hardly notices.
The trade-off: size vs quality
- Lossless keeps full quality, but the file stays larger.
- Lossy gives a much smaller file, but quality goes down a little.
- You choose based on what matters more: perfect data or small size.
Le compromis : taille vs qualité
- Sans perte conserve une qualité totale, mais le fichier reste plus grand.
- Avec perte donne un fichier beaucoup plus petit, mais la qualité diminue un peu.
- Vous choisissez selon ce qui importe le plus : données parfaites ou petite taille.
When to use each
- Use lossless when every detail must be exact.
- Use lossy when a small drop in quality is fine and small size matters.
Quand utiliser chacun
- Utilisez sans perte lorsque chaque détail doit être exact.
- Utilisez avec perte lorsqu'une légère baisse de qualité est acceptable et qu'une petite taille est importante.
Lossless: text, code, a .zip file, a spreadsheet
Lossy: photos (JPEG), music (MP3), video
Key idea
- Compression trades size against quality (or against work to undo it).
- Lossless = smaller and perfect; lossy = much smaller but not exact.
- Good engineers pick the right kind for the job.
Idée clé
- La compression échange la taille contre la qualité (ou contre le travail nécessaire pour l'inverser).
- Sans perte = plus petit et parfait ; avec perte = beaucoup plus petit mais pas exact.
- De bons ingénieurs choisissent le bon type pour la tâche.
Run-length encoding
- Run-length encoding (RLE) is a simple lossless method.
- A run is a stretch of the same character repeated. RLE stores a count instead of the repeats.
- We will store each run as a pair
[character, count]inside a list.
Codage par longueur de run
- Le codage par longueur de run (RLE) est une méthode simple sans perte.
- Un run est une série de caractères identiques répétés. RLE stocke un compteur au lieu des répétitions.
- Nous stockerons chaque run sous forme de paire
[character, count]dans une liste.
"AAAB" -> [["A", 3], ["B", 1]] (3 A's, then 1 B)
[["A", 3], ["B", 1]] -> "AAAB" (decode it back — exact again)
Common mistakes
- Lossless compression can be reversed exactly; lossy throws away detail.
- More compression can mean lower quality.
Erreurs courantes
- La compression sans perte peut être inversée exactement ; avec perte jette des détails.
- Plus de compression peut signifier une qualité inférieure.
Now you try
- Build RLE yourself: an encoder, a decoder, and a length helper.
- Each task checks your function on several inputs. Press Check answer.
À vous maintenant
- Créez RLE vous-même : un encodeur, un décodeur et un utilitaire de longueur.
- Chaque tâche vérifie votre fonction sur plusieurs entrées. Appuyez sur Vérifier la réponse.
Lossless compression · Compression sans perte
Run-length encoding replaces a run of repeats with count + symbol. · Le codage par longueur de run remplace une série de répétitions par compteur + symbole.
Write encode(text) for run-length encoding. Return a list of [character, count] pairs, one per run of repeats. Example: encode("AAAB") → [['A', 3], ['B', 1]]. For the empty string return []. · Écrivez encode(text) pour l'encodage par longueur de course (run-length encoding). Retournez une liste de paires [character, count], une par série de répétitions. Exemple : encode("AAAB") → [['A', 3], ['B', 1]]. Pour la chaîne vide, retournez [].
Click Run to see the output here. · Cliquez sur Exécuter pour voir le résultat ici.
Write decode(pairs) that reverses the encoder: given a list of [character, count] pairs, rebuild the original string. Example: decode([['A', 3], ['B', 1]]) → 'AAAB'. For [] return · rendement ''. · Écrivez decode(pairs) qui inverse l'encodeur : étant donné une liste de [character, count] paires, reconstruisez la chaîne originale. Exemple : decode([['A', 3], ['B', 1]]) → 'AAAB'. Pour [], retournez ''.
Click Run to see the output here. · Cliquez sur Exécuter pour voir le résultat ici.
Without decoding, write original_length(pairs) that returns how many characters the original text had — just add up the counts. Example: original_length([['A', 3], ['B', 1]]) → 4. · Sans décoder, écrivez original_length(pairs) qui retourne combien de caractères avait le texte original — ajoutez simplement les compteurs. Exemple : original_length([['A', 3], ['B', 1]]) → 4.
Click Run to see the output here. · Cliquez sur Exécuter pour voir le résultat ici.