Sujet
Les algorithmes évoqués ci-dessous sont utilisés pour la compression de données sans perte d'information, par exemple pour les Fax et les fichiers mp3. II s'agit de créer des systèmes de codage/décodage (le plus important étant le décodage) en essayant de diminuer au maximum l'encombrement mémoire.
Partie A : Une approche
- Le système universel ASCII permet le codage de caractères en utilisant, pour chaque caractère, un code formé de huit chiffres valant 0 ou 1 . On dit que les caractères sont codés en binaire sur huit bits correspondant à 8 cases contenant chacune 0 ou 1. Par exemple, la lettre E peut être codée par : 01000101.
Il s'agit d'un codage binaire sur 8 bits correspondant à :
Le codage d'un mot s'obtient en juxtaposant les codes des lettres qui le composent.
a. En utilisant le système ASCII, combien de bits sont nécessaires pour coder le mot : DECADE ?
b. En considérant qu'une page contient en moyenne 3000 caractères, combien de pages peut-on coder en ASCII à l'aide d'un Mégabit (1 Mégabit \(=10^{6}\) bits) ?
2. On veut maintenant coder uniquement les 26 lettres de l'alphabet. Peut-on employer un codage n'utilisant que 4 bits par caractère ? 5 bits par caractère ?
Partie B : Un nouveau codage
Pour diminuer le nombre de bits nécessaires pour coder un texte, on considère une nouvelle approche dans laquelle la longueur du code peut varier d'un caractère à l'autre. On présente d'abord la méthode sur un petit alphabet dans lequel on n'utilise plus que les lettres A, B, C, D, E. Dans cet alphabet, les fréquences d'apparition des lettres sont : A : \(25 \% ; \mathrm{B}: 4 \% ; \mathrm{C}: 12 \% ; \mathrm{D}: 14 \% ; \mathrm{E}: 45 \%\). Le codage de ces lettres est : A : \(10 ; \mathrm{B}: 1110 ; \mathrm{C}: 1111 ; \mathrm{D}: 110 ; \mathrm{E}: 0\). On rappelle que le codage d'un mot s'obtient en juxtaposant les codes des lettres qui le composent.
3. Coder DECADE.
4. Décoder 101111111101100.
5. Expliquer pourquoi le code fourni est toujours «sans ambigüité au décodage» (si un codage représente effectivement un texte, on ne peut pas se tromper en le décodant).
6. Pour coder un texte composé d'un million de ces cinq lettres, combien faut-il utiliser de bits par caractère en moyenne (donner un résultat au centième) ?
Partie C : Génération d'un code
Désormais, il s'agit de créer des codes « sans ambigüité au décodage » dans lesquels les codages des caractères ont des longueurs variables. Pour obtenir ces codes, à partir des fréquences d'apparition des caractères, on construit des arbres binaires, que nous nommons ici \(H\)-arbres. Les règles de construction de ces arbres sont les suivantes :
- Positionnement de départ : Les lettres sont rangées de gauche à droite par fréquence croissante ; en cas d'égalité on utilise l'ordre alphabétique. Chaque lettre est associée à un point appelé « nœud ».
Aucun corrigé disponible pour cet exercice dans la source APMEP.