Codage de Levenshtein
Cet article ne cite pas suffisamment ses sources ().
Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références ».
En pratique : Quelles sources sont attendues ? Comment ajouter mes sources ?
Le codage de Levenshtein est un codage entropique inventé par Vladimir Levenshtein en 1968 et utilisé essentiellement en compression de données[1].
Le code de Levenshtein produit est un code préfixe et universel.
Principe
Le codage de Levenshtein permet de coder tous les entiers naturels (zéro compris — ce qui le distingue des codes d'Elias), sans qu'il y ait besoin de connaitre au préalable l'intervalle des valeurs à coder (contrairement, par exemple, au codage binaire de taille fixe, qui ne permet de coder que des nombres inférieurs à une borne supérieure fixée à l'avance).
Pour cela, le codage de Levenshtein se fait en deux étapes :
- le codage du nombre de récursions de l'algorithme avec un codage unaire ;
- le codage récursif de la valeur.
Le codage récursif consiste à représenter l'entier en binaire, privé de son bit de poids fort (implicite) et précédé de son nombre de bits (sans compter le bit de poids fort dont il est privé), lui-même codé avec un codage récursif — la récursion s'arrêtant lorsque le nombre est nul.
Longueur du code
Un code de Levenshtein est toujours exactement un bit plus long que le code omega équivalent. À la différence de ce dernier, il permet cependant de coder les entiers relatifs sans transformation intermédiaire.
Exemples
Décimal | Binaire | Code omega | Code de Levenshtein |
---|---|---|---|
0 | 0 | Impossible | 0 |
1 | 1 | 0 | 10 |
2 | 10 | 10 0 | 110 0 |
3 | 11 | 11 0 | 110 1 |
4 | 100 | 10 100 0 | 1110 0 00 |
5 | 101 | 10 101 0 | 1110 0 01 |
Notes et références
- ↑ (ru) Vladimir Levenshtein, « On the redundancy and delay of separable codes for the natural numbers » [« ОБ ИЗБЫТОЧНОСТИ И ЗАМЕДЛЕНИИ РАЗДЕЛИМОГО КОДИРОВАНИЯ НАТУРАЛЬНЫХ ЧИСЕЛ »], Problems of Cybernetics, vol. 20, , p. 173–179 (lire en ligne [PDF])
Voir aussi
- Codage omega
- Codage entropique
- Compression de données
v · m Techniques de compression de données | |||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Sans perte |
| ||||||||||||||
Avec pertes |
|
- Portail de l’informatique