Codes Sans Préfixes


  1. INTRODUCTION
  2. DECODAGE SANS AMBIGUITE
    1. Définition
    2. Longueur fixe
    3. Longueur variable
    4. Illustration / exemple
  3. PROPRIETE PREFIXE
    1. Définition
    2. Inégalité de KRAFT
    3. Démonstration
    4. Algorithme
  4. ARBRE DE HUFFMAN
  5. NOTION D'AMBIGUITE DE DECOUPAGE EN MOTS PAR LE CODE MORSE
  6. CODE UTF-8 et CODE DE FIBONACCI
  7. BIBLIOGRAPHIE

1- Introduction


Le but de cet article consistera à expliquer au mieux dans un premier temps, ce que c'est un code sans préfixe. Nous pourrons ensuite expliquer son intérêt notamment dans le milieu informatique. Et enfin, éventuellement présenter un programme qui permet de générer un code sans préfixe pourvu que l'alphabet et les longueurs des mots donnés le permettent.

2- Décodage sans Ambiguité


La première qualité que doit avoir un code est de pouvoir etre decodé, cela étant une évidence mais pas toujours une operation triviale. Si on suppose que le code est une fonction bijective, qui transforme le message source en message qui est transmis par un canal;

  • pour un message source a1...an, chaine sur un alphabet source quelconque,
  • et pour un alphabet de code C,
  • appelons F la fonction de codage.

On a alors le message codé :

c1...cn = f(a1)...f(an)    avec ci ∈ V+ pour tout i.  

Le code en tant qu'ensemble des mots de codes, est l'image de la fonction de codage F. Le fait que F soit bijective ne suffit cépendant pas pour que le message puisse être decodé sans ambiguité par le recepteur.

Exemple : 
S={A,...,Z} par les entiers C={0,...,25} en base 10 :
f(A)=0, f(B)=1,..., f(J)=9, f(K)=10, f(L)=11, ..., f(Z)=25
le mot de code 1209 par exemple peut correspondre à differents messages :
par exemple : BUJ ou MAJ ou BCAJ.

A travers cet exemple, on voit qu'il est donc nécessaire d'ajouter des contraintes sur le code pour qu'un message quelconque puisse être dechiffré sans ambiguité.

2-1 Definition :

Un code C sur un alphabet V est non ambigu ( on dit parfois uniquement déchiffrable) si, pour tout :

x = x1 ... xn ∈ V+, il existe au plus une séquence c = c1 ... cm ∈ C+ 
telle que :
c1 ... cm = x1 ... xn
Toute séquence de mots de code ne correspond qu'à un seul message-source.
2-2 Longueur Fixe :
Définition :

Pour tout code C d'un alphabet quelconque, C est de Longueur Fixe si tous ses mots de code sont de même longueur :

l1 = l2 = ... = li  , i étant le nombre de mots dans C  
Proprieté : Tout code dont tous les mots sont de même longueur possede la proprieté préfixe (péfixe à voir dans la suite).
2-3 Longueur Variable:
Définition :

Pour tout code C d'un alphabet quelconque, C est de Longueur Variable si ses mots de code sont de longueurs differentes :

soit i et u,  deux mots de code dans C, alors 
l(i) != l(u)
NB: Deux mots de code peuvent avoir la même longueur.
2-4 Exemple / Illustration :

Un codage de longueur variable peut-il faire mieux qu'un codage de longueur fixe?

Pour répondre à cette question nous allons illustré avec un exemple.

Exemple : 
Pour le codage d'un fichier contenant 100.000 caractères seulement 6 caractères apparaissent et on a la fréquence de chacun de ces 6 caractères (en millier)
a b cdef
fréquence (en millier) 4513121695
mot de code de long. fixe 000001010011100101
mot de code de long. Variable 010110011111011100
Dans cet exemple, avec le codage de mot de longueur fixe on aura besoin de 3 bits pour chaque caractère : 3 * 100.000 = 300.000 ( au total on aura besoin de 300.000 bits). Avec le codage de mot de longueur variable :
(45 * 1 + 13 * 3 + 12 * 3 + 16 * 3 + 9 * 4 + 5 * 4) = 224
donc au total on aura besoin de 224.000 bits.

Conclusion : avec avec le codage de longueur variable on a fait une optimisation de 25%, donc on peut faire nettement mieux avec le codage de longueur variable, en attribuant aux caractères plus fréquents des mots de code plus courts, et aux caracteres moins fréquents des mots de code plus longs .

3- Propriété Préfixe


On dit qu’un code C sur un alphabet V a la propriété du préfixe (on dit parfois qu’il est instantané, ou irréductible) si et seulement si pour tout couple de mots de code distincts (c1, c2) , c2 n’est pas préfixe de c1.
Exemple : 
a = 101000, b = 01, c = 1010 ; ce code n’est pas sans préfixe car b n’est pas un préfixe de a mais c est un préfixe de a .
par contre, a = 101, b = 0, c = 11 est un code sans préfixe.
Grâce à la propriété préfixe, on peut déchiffrer les mots d’un tel code dès la fin de la réception du mot (instantanéité), ce qui n’est pas toujours le cas pour les codes uniquement déchiffrables (codes ambigüs) comme on l’a illustré précedemment sur l’exemple du codage des lettres de l’alphabet.

NB : tout code préfixe est non-ambigu, cépendant la reciprocité n'est pas toujours le cas car il existe des codes non-ambigus qui ne sont pas préfixes.
3-1 Inégalité de KRAFT :

La contrainte de déchiffrabilité implique une longueur minimale aux mots de code. Le théorème de KRAFT donne une condition nécessaire et suffisante sur la longueur des mots de code pour assurer l'existence d'un code sans préfixe
3-2 Démonstration :
Supposons tout d'abord qu'il existe un code instantané D-aire dont les longueurs de mots de code sont : 
l1 , l1 , . . . , lN
Soit L := max li + 1 .
Considérons la construction de l'arbre de codage correspondant Tcode consistant à élaguer Tcomplet, l'arbre D-aire de profondeur L.
Supposons tout d'abord qu'il existe un code instantané D-aire dont les longueurs de mots de code sont : 
l1 , l1 , . . . , lN
Soit L := max li + 1 .
Considérons la construction de l'arbre de codage correspondant Tcode consistant à élaguer Tcomplet, l'arbre D-aire de profondeur L.
En raison de la condition «instantané», aucun noeud correspondant à un mot de code ne peut être au-dessous d'un autre noeud correspondant à un autre mot de code. Par conséquent, chaque noeud correspondant à un mot de code élague son propre sous-arbre de Tcomplet. En examinant le ième mot de code et en appliquant la propriété :
Dans l'arbre n-aire complet de profondeur d (d>=0), chaque noeud à la profondeur l 0<=l<=d couvre exactement n^(d-l) feuilles.
À li , (qui est < L), Tcode a, pour ce noeud uniquement, D^(L-li) feuilles de moins que Tcomplet
En considérant maintenant tout le code, Tcode a :
feuilles de moins que Tcomplet 
Toutefois, au plus D^L feuilles peuvent être retirées, étant donné que Tcomplet a précisément D^L feuilles. Par conséquent :
 c'est-à-dire 
En outre, dans le cas où le code considéré est complet, tous les noeuds correspondent à un mot de code; donc tous les sous-arbres correspondants dans  Tcomplet ont été «élagués», et, par conséquent, les D^L feuilles de Tcomplet  ont été retirées. Ceci signifie que
 c'est-à-dire 
3-3 Exemples :

Discutez de la possibilité de trouver un code de préfixe avec des longueurs de mots de code 1, 2, 3, 3.

les longueurs des mots de code satisfaisant l'inégalité de Kraft, il est possible de trouver un code de préfixe avec ces longueurs de mot

OBSERVATION

L'inégalité de Kraft peut être mal utilisée si ses revendications ne sont pas étudiées avec soin. Nous soulignons ici ce que le théorème peut et ne peut pas faire.
1 - L'inégalité de Kraft définit les exigences sur la longueur d'un code de préfixe .Si les longueurs ne satisfont pas l'inégalité de Kraft, nous savons qu'il n'y a aucune chance de trouver un code de préfixe avec ces longueurs. 
2 - L'inégalité de Kraft ne nous dit pas comment construire un code de préfixe, ni la forme du code. Il est donc possible de trouver des codes de préfixe sous différentes formes et un code de préfixe peut être transformé en un autre en échangeant la position des 0 et des 1. 
Si (0, 10, 110, 111) est un code de préfixe, alors (1, 01, 001, 000) 
3 - L'inégalité de Kraft peut indiquer qu'un code donné n'est pas un code de préfixe, mais il ne peut pas être utilisé pour décider si un code donné est un code de préfixe. 
4 - L'inégalité de Kraft peut nous dire si les longueurs d'un code de préfixe peut être raccourcie, mais elle ne peut pas modifier les longueurs. 
Par exemple, considérons les deux codes :
(0, 10, 110, 1111) et (0, 10, 110, 111). Les longueurs des deux codes satisfont l'inégalité de Kraft.
Les longueurs 1, 2, 3, 4 du premier code donnent
Les longueurs 1, 2, 3, 3 du deuxième code donnent
L'inégalité de Kraft devient égalité lorsque le code ne peut pas être raccourci.
3-3 Algorithme de Génération de Codes Sans Préfixe :

Nous présentons ici une capture du programme qui permet de générer un code sans préfixe ainsi son arbre correspondant pourvu que l'alphabet et les longueurs des mots donnés le permettent.
Ce programme est écrit dans le langage OCAML.
programme qui genère un code sans préfixe s'il existe à partir des longueurs des mots de code

4- Arbre de Huffman


L'arbre de Huffman est un objet permettant de représenter facilement tous les codes qui ont la propriété du préfixe, et cette représentation facilite grandement leur manipulation. On donne ici les définitions dans le cas binaire, mais elles sont généralisables pour des codes d'arité quelconque. On appelle arbre de Huffman un arbre binaire tel que tout sous -arbre a soit 0 soit 2 fils (il est localement complet). Dans ce dernier cas , on assigne le symbole "1" à l'arete reliant la racine locale au fils droit et "0" au fils gauche.
A chaque feuille d'un arbre de Huffman, on peut associer un mot de {0,1}+ : c'est la chaîne des symboles marquant les arêtes d'un chemin depuis la racine jusqu'à la feuille.
Le maximum sur l'ensemble des longueurs des mots d'un arbre de Huffman est appelé hauteur de cet arbre. On appelle Code de Huffman l'ensemble des mots correspondant aux chemins d'un arbre de Huffman; la hauteur de cet arbre est appelée aussi hauteur du code C

Arbre de hufffman
4-1 Répresentation des codes sans préfixes

L'introduction des arbres de Huffman est justifiée par la propriété suivante, qui assure que tous les codes sans préfixes (instantanés) pourront être manipulés avec de tels arbres

*) Propriété : Un code de Huffman possède la propriété du préfixe.
Preuve : Si un mot de code C1 est préfixe de C2, alors le chemin représentant C1 dans l'arbre de Huffman est inclus dans le chemin représentant C2. Comme C1 et C2 sont, par définition, associés à des feuilles de l'arbre. Il n'existe donc pas deux mots différents dont l'un est le préfixe de l'autre, et le code de Huffman a la propriété du préfixe.

5- Notion d'ambiguté du découpage du code morse


La notion d'ambiguité du découpage du code morse

A : 01	        U : 001
B : 1000	V : 0001
C : 1010	W : 011
D : 100	        X : 1001
E : 0		Y : 1011
F : 0010	Z : 1100
G : 110
H : 0000	1 : 01111
I : 00		2 : 00111
J : 0111	3 : 00011
K : 101	        4 : 00001
L : 0100	5 : 00000
M : 11		6 : 10000
N : 10		7 : 11000
O : 111	        8 : 11100
P : 0110	9 : 11110
Q : 1101	0 : 11111
R : 010
S : 000
T : 1

Voilà ce que donne le code morse si on utilisait un code binaire dans lequel 0 représenterait le "ti" (le point) et 1 représenterait le "taah" (la barre). Plusieurs méthodes s'offrent à nous pour montrer que le code est sans préfixe :
1ère méthode : Montrer qu'il existe un mot qui est préfixe d'un autre. 
Dans ce cas, prenons 2 mots du code : par exemple 0 (pour encoder "E") et 01 (pour encoder "A"). On voit très clairement que 0 est préfixe de 01. Le code n'est donc pas sans préfixe.
2ème méthode : Montrer que l'on ne peut pas décoder le message dès que l'on atteint la fin du mot :
Prenons le mot "0000000001" , Il peut être lu comme EEEEEEEEET ou bien EEEEEEEIT et d'autres encore.
Le fait qu'on puisse lire le message de plusieurs manières nous permet de dire que le code n'est pas instantané. Il serait intéressant de demander de combien de manière on peut lire "0000000001". Si vous voulez devenir un monstre de la combinatoire, faites l'exercice. Pour les plus courageux, faites un programme qui prend en entrée une chaîne de caractères, composée de 0 et 1, et renvoie le nombre de manières différentes de lire le mot dans le code morse.
3ème méthode : En appliquant l'inégalité de Kraft, on obtient :
L'inégalité ne se réalise pas, le code n'est donc pas instantané ce qui implique que le code n'est pas sans préfixe.

6- Code de Fibonacci

Code de Fibo : 
2 pour 1 : 11 3 pour 2 : 011 4 pour 3 : 0011 4 pour 4 : 1011 5 pour 5 : 00011 5 pour 6 : 10011 5 pour 7 : 01011 6 pour 8 : 000011 6 pour 9 : 100011 6 pour 10 : 010011 11 : 001011 12 : 101011 13 : 0000011 14 : 1000011 15 : 0100011 …

Le code de Fibonacci est un code préfixe qui code les entiers naturels. La suite de Fibonacci est définie comme :

Avec

et

Pour coder un entier dans le code de Fibonacci, il faut tout d'abord décomposer l'entier avec les entiers de la suite de Fibonacci, c'est-à-dire 1,2,3,5,8,13 … (il n'existe pas qu'une seule décomposition)

Prenons l'entier 61

61 = 34 + 21 + 3 + 2 + 1 (il peut également se décomposer en 55 + 5 + 1)

Faisons un tableau de 2 lignes avec la première ligne compléter avec la suite de Fibonacci dans l'ordre croissant.

1 2 3 5 8 13 21 34 55
1 1 1 0 0 0 1 1 0

Et compléter la deuxième ligne avec un 0 dans la colonne si le nombre ne fait pas partie de la décomposition et 1 s'il en fait partie.

Ce n'est pas encore un mot de Fibonacci.

En recopiant la deuxième ligne on obtient 11100011

Dès lors qu'on voit deux "1" successifs, il y a une modification à faire. Il faut en effet changer 11 par 001.

Dans notre exemple :

11100011 → 10010011
11100011 → 100100001
On obtient 10010001, on y ajoute un 1 à la fin du mot ce qui donne : 100100011 et on obtient un mot dans le code de Fibonacci. Ce qui est intéressant avec le code de Fibonnacci, c'est que le mot se termine forcément par 11. En effet, si la décomposition contient 2 termes qui se suivent dans la suite de Fibonacci, alors, ils peuvent être remplacé par le suivant. Par exemple : 3 + 5 peuvent être remplacé par 8, 8 + 5 par 13 etc … Ce qui fait que dans le code de Fibonacci, on ne retrouvera jamais deux "1" de suite sauf à la fin d'un entier. Le double "1" agit comme un séparateur dans le code. On peut conclure que le code de Fibonnacci est un code sans préfixe.
Ce qui est intéressant dans le code de Fibonnacci, c'est aussi le fait que l'on peut coder tous les entiers.
Essayons de prouver que pour un mot quelconque du mot, on peut trouver un successeur.
Soit k un mot du code et W1 W2 W3...Wn  les lettres du mot.
On ajoute 1 à k.
Si W1=0 alors W1=1, et on applique la conversion expliqué au-dessus.
Dans le cas où W1=1, alors W1=0 et W1=1 (à noter que W2 ne peut pas être égale à 0 car deux 1 ne peuvent pas se succéder sauf pour coder l'entier 1) et on applique la conversion expliquée plus haut
On a donc prouvé que pour chaque entier, on pouvait avoir un successeur.

Conclusion


Nous avons vu et constaté à travers cet article, que le codage / décodage n'est pas une opération triviale dans tous les cas. Reconstituer sans ambiguité le message source en découpant la suite selon les blocs dont elle est constituée requiert une forme particulière du code.
C'est là que les codes préfixes ont tout leur sens, leur utilisation permet un décodage instantané du message source, il est ainsi possible de les représenter par des arbres (l'arbre de Huffman en particulier).
L'utilisation de l'algorithme de Huffman permet de construire l'arbre de Huffman sans connaitre assez d'informations sur les algorithmes de construction des arbres.

7- Bibliographie

[1] Théorie des codes, 2ème édition Dunod.


1 Cliquer pour recommander cet article