|
Les
principaux pionniers de la compression de données furent sans doute C.
Shannon et R. M. Fano. Ils démontrèrent que l'on pouvait coder un message en
utilisant la probabilité d'apparition d'un symbole ainsi que la base 2. Ils
ont établi 3 propriétés qui permettent de compresser un message : · Chaque code (ou presque) a un nombre de
bits différent. · Le code correspondant à un symbole dont la
probabilité d'apparition dans le message est faible sera codé avec plus de
bits, le code dont le symbole respectif a une plus grande probabilité
d'apparaître aura un nombre de bits moins élevé. · Même si les codes ont des longueurs
différentes, cela ne doit pas empêcher de pouvoir les décoder de façon
distincte. L’algorithme
de Shannon Fano se décompose en différentes étapes : · Dresser une table triée par ordre croissant
des fréquences d'apparition des symboles. · Diviser cette table en deux parties. La
somme des fréquences de la première partie devant être le plus égal possible
à la somme des fréquences de la deuxième partie. · Affecter le chiffre binaire 0 à la moitié
supérieure, la moitié inférieure prenant le chiffre binaire 1. · Répéter les opérations 2 et 3 aux deux
parties, jusqu'à ce que chaque symbole ne représente plus qu'une partie de la
table. |
