Généralités
La compression est une opération qui consiste à réduire la taille occupée par les données numériques, audio ou audio-visuelles. Son principe général consiste à éliminer les informations redondantes et non significatives des données. La problématique de la compression résulte de la taille limitée de la bande passante du réseau Internet qui n'était pas conçu à la base pour recevoir un flot incessant d'image, de données audio visuels et de communications téléphoniques. Les critères d'évolution des méthodes de compression sont:
- La qualité de la reconstitution de la donnée source
- Le taux de compression.
- La rapidité du codeur/décodeur (codec).
Les problèmes liés à la compression
Le contrôle de débit
A débit constant, il peut y avoir un risque de débordement si une crise de fluidité intervient dans le réseau.
A débit variable, il peut y avoir un risque de conflit entre le codeur et le décodeur.
Les pertes dans le réseau
La perte de certaines données comme les en-têtes peuvent avoir des conséquences grammatiques sur le comportement du décodeur.
Run Lenght Encoding : RLE
C'est le plus simple des algorithmes de compression, il consiste à quantifier un seuil S0 fixé.
Exemple
Soit le texte source (P) suivant: [AAAAALBBCCCCDE] taille de (p)=14
- Fixons le seuil S0=3, on aura compress_P=[A(5)LBBC(4)DE]
taille[compress_P] = 9.
Taux de compression = [taille(P)-taille(compress_p)]/taille(P)
Taux de compression = (14-9)/14 = 35% - Fixons Seuil: S0=2
On aura compress_P = [A(5)LB(2)C(4)DE].
Taille[compress_P] = 9
Taux de compression = 35%
Exercice:
Décompressez [C(p)], Si C(P)=[00010(00101)01011(0011)10010(00100)10101(00011)11010(00100)]
Solution:
P = [B(5)K(3)R(4)U(3)Z(4)]
P = [BBBBKKKKKKKRRRUUUZZZZ]
Taux de compression = (23-10)/23 = 13/23 = 56,5%
Compression de HUFFMAN
C'est un algorithme de codage utilisé pour la compression des données (caractères, mots) son principe:
- Connaitre la taille totale du volume des données
- Affecter des codes inversement proportionnels à la fréquence des caractères contenus dans les données (haute fréquence implique codage souple)
Exemple
Texte source:
T : [aaakea befafm afakfk kfkede mdakfm]
taille(T) = 30
Fréquence:
a = 8/30 = 27%
k = 6/30 = 20%
e = 4/30 = 13%
b = 1/30 = 3,3%
f = 6/30 = 20%
m = 3/30 = 10%
d = 2/30 = 6,66%
On classe par fréquence croissante:
Compression de HUFFMAN pour les caractères
Soit le texte à compresser: T = [COMMENT_ÇA_MARCHE]
On ava supposer que les caractères de T sont données en ACII, méthode de HUFFMAN:
- On classe les caractères par fréquence décroissante
- On divise la liste ainsi obtenue en 2 sous groupes S1 et S2 dont la somme des fréquences internes respectives:
Application:
|
Caractères |
Apparitions |
Fréquences |
|
c |
2 |
11,6% |
|
O |
1 |
5,88% |
|
M |
3 |
17,64% |
|
E |
2 |
11,76% |
|
N |
1 |
5,88% |
|
T |
1 |
5,88% |
|
_ |
2 |
11,76% |
|
A |
2 |
11,75% |
|
R |
1 |
5,88% |
|
H |
1 |
5,88% |
|
Ç |
1 |
5,88% |
- Construisons une partition en 2 variables:
Le caractère à plus haute fréquence (M) n'a pas le plus petit codage, car il n'a pas été initialisé dans le sous groupe de moindre poids.
M = [COMMENT_ÇA_MARCHE]
Taux de compression de M:
Chaque caractère codé en ASCII occupe 8 bits.
Chaque caractère du texte source a la taille suivante:
|
X |
& |
Taille unitaire |
Taille totale |
|
X1 |
C |
1 |
2 |
|
X2 |
O |
4 |
4 |
|
X3 |
M |
1 |
3 |
|
X4 |
E |
2 |
4 |
|
X5 |
N |
4 |
4 |
|
X6 |
T |
4 |
4 |
|
X7 |
_ |
2 |
4 |
|
X8 |
Ç |
4 |
4 |
|
X9 |
A |
3 |
6 |
|
X10 |
R |
4 |
4 |
|
X11 |
H |
4 |
4 |
Taille (en binaire) du texte source 17x8=136bits
Concours d'entrée aux grandes écoles
Probatoire A-ABI 2021 Epreuve de littérature ou de culture générale