La compression sans perte permet la reconstitution exacte des données d'origine lors de la décompression.
C'est celle utilisée pour les fichiers de données.
Les algorithmes tels que Lempel-Ziv ou le codage RLE consistent à remplacer des suites de bits utilisées plusieurs fois dans un même fichier.
Dans l'algorithme de codage de Huffman plus la suite de bits est utilisée souvent, plus la suite qui la remplacera sera courte.
Les algorithmes tels que la transformée de Burrows-Wheeler sont utilisés avec un algorithme de compression.
De tels algorithmes modifient l'ordre des bits de manière à augmenter l'efficacité de l'algorithme de compression, mais sans compresser par eux-mêmes.
Codage par répétition.
Codage RLE.
Les lettres RLE signifient "run-length encoding".
Il s'agit d'un mode de compression parmi les plus simples : toute suite de bits ou de caractères identiques est remplacée par un couple (nombre d'occurrences ; bit ou caractère répété).
Exemple : codice_1 donne : codice_2, ce qui est beaucoup plus court.
Voir le chapitre « Run-length encoding » qui détaille l'algorithme.
Compression CCITT.
C'est une compression d'images utilisée par les télécopieurs (ou "fax"), standardisée par des recommandations de l'Union internationale des télécommunications (UIT, anciennement appelée CCITT).
Elle est de type RLE : on code les suites horizontales de pixels blancs et de pixels noirs ; et peut-être bidirectionnelle (on déduit une ligne de la précédente).
Il existe plusieurs types de compressions (« groupes ») suivant l'algorithme utilisé et le nombre de couleurs du document (monochrome, niveau de gris, couleur).
Deux compressions existent, celle du Groupe 3 (recommandation ITU T.4) et celle du Groupe 4 (recommandation ITU T.6), utilisées pour les fax :
Ceci est théorique : en pratique, il faudra transmettre plus de symboles, mais envoyer une page blanche est tout de même beaucoup plus rapide avec le Groupe 4 qu'avec le Groupe 3.
Codage entropique.
Voir le chapitre « Codage entropique » pour plus de détails.
Codage de Huffman.
L'idée qui préside au codage de Huffman est voisine de celle utilisée dans le code Morse : coder ce qui est fréquent sur peu de place, et coder en revanche sur des séquences plus longues ce qui revient rarement (entropie). En morse le « e », lettre très fréquente, est codé par un simple point, le plus bref de tous les signes.
L'originalité de David A. Huffman est qu'il fournit un "procédé d'agrégation objectif" permettant de constituer son code dès lors qu'on possède les statistiques d'utilisation de chaque caractère.
Le Macintosh d'Apple codait les textes dans un système inspiré de Huffman : les 15 lettres les plus fréquentes (dans la langue utilisée) étaient codées sur , et la 16 combinaison était un code d'échappement indiquant que la lettre était codée en ASCII sur les suivants. Ce système permettait une compression des textes voisine en moyenne de 30 % à une époque où la mémoire était extrêmement chère par rapport aux prix actuels (compter un facteur 1000).
Le défaut du codage Huffman est qu'il doit connaître la fréquence des caractères utilisés dans un fichier avant de choisir les codes optimaux.
Et il doit donc lire tout le fichier avant de comprimer.
Une autre conséquence est que pour décomprimer il faut connaître les codes et donc la table, qui est ajoutée devant le fichier, aussi bien pour transmettre que stocker, ce qui diminue la compression, surtout pour les petits fichiers.
Ce problème est éliminé par le codage Huffman adaptatif, qui modifie sa table au fil des choses.
Et peut donc démarrer avec une table de base.
En principe il commence avec les caractères à même probabilité.
Voir le chapitre « Codage de Huffman » qui détaille l'algorithme.
Code Baudot.
Le code Baudot est un exemple de compression concret, simple et représentatif.
Ce code utilise une base de 5 bits pour coder les caractères alors que la table des caractères, étalée sur 6 bits, contient formula_1 éléments.
Cette dernière est séparée en deux jeux de formula_2 éléments et deux caractères "Inversion Lettres" (code 31) et "Inversion Chiffres" (code 27) permettent de commuter entre les deux ensembles.
Si les caractères étaient utilisés de manière aléatoire, ce système n'aurait aucun intérêt et entraînerait même un surplus de données avec une moyenne de formula_3 bits par caractère.
Cependant, les lettres sont codées sur le premier jeu de caractère tandis que les chiffres et caractères spéciaux sur le second.
Or la nature des caractères utilisés n'est pas aléatoire.
En effet, lorsque l'on écrit un texte cohérent, les chiffres sont séparés des lettres et les ponctuations sont rares.
Ainsi, on écrira :
 "le prix moyen d'une encyclopédie est de 112,45 euros" (52 caractères)

(formula_4 bits)
Alors qu'il est peu probable que l'on ait à taper :
 "1e pr1 m0yen d'une en5yc10p3d1 e5t 2 cent12,45 eur0s" (52 caractères)