Codage de Levenshtein

Codage de Levenshtein

Le codage de Levenshtein est un codage entropique inventé par Vladimir Levenshtein en 1968 et utilisé essentiellement en compression de données.

Le code de Levenshtein produit est un code préfixe et universel.

Sommaire

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 :

  1. le codage du nombre de récursions de l'algorithme avec un codage unaire ;
  2. 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

Représentation des premiers entiers naturels (zéro compris) avec un codage de Levenshtein
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


Voir aussi

Articles connexes


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Codage de Levenshtein de Wikipédia en français (auteurs)

Игры ⚽ Поможем сделать НИР

Regardez d'autres dictionnaires:

  • Codage entropique — Le codage entropique (ou codage statistique à longueur variable) est une méthode de codage de source sans pertes, dont le but est de transformer la représentation d une source de données pour sa compression et/ou sa transmission sur un canal de… …   Wikipédia en Français

  • Codage delta — Pour les articles homonymes, voir Code Delta (émission de télévision). Le codage delta ou codage delta d Elias est un codage entropique inventé par Peter Elias et utilisé essentiellement en compression de données. Le code delta produit est un… …   Wikipédia en Français

  • Codage gamma — Le codage gamma ou codage gamma d Elias est un codage entropique inventé par Peter Elias et utilisé essentiellement en compression de données. Le code gamma produit est un code préfixe et universel. Sommaire 1 Principe 2 Codage des entiers… …   Wikipédia en Français

  • Codage omega — Le codage omega ou codage omega d Elias est un codage entropique inventé par Peter Elias et utilisé essentiellement en compression de données. Le code omega produit est un code préfixe et universel. Sommaire 1 Principe 1.1 Codage 1.2 Décodage …   Wikipédia en Français

  • Codage de Huffman — Le codage de Huffman est un algorithme de compression de données sans perte élaboré par David Albert Huffman, lors de sa thèse de doctorat au MIT. L algorithme a été publié en 1952 dans l article A Method for the Construction of Minimum… …   Wikipédia en Français

  • Codage de Rice — Le codage de Rice, codage de Golomb Rice ou GPO2 (pour Golomb power of 2) est un codage entropique inventé par Robert F. Rice et James R. Plaunt en 1971 et utilisé essentiellement en compression de données. Le code produit est un code préfixe.… …   Wikipédia en Français

  • Codage binaire tronqué — Le codage binaire tronqué est un codage entropique utilisé essentiellement en compression de données et s appuyant sur la base 2. Il est plus généralement utilisé pour coder de façon efficace en termes de longueur, un alphabet dont la taille n… …   Wikipédia en Français

  • Codage de Shannon-Fano — Le codage de Shannon Fano est un algorithme de compression de données sans perte élaboré par Robert Fano à partir d une idée de Claude Shannon. Il s agit d un codage entropique produisant un code préfixe très similaire à un code de Huffman, bien… …   Wikipédia en Français

  • Codage de Fibonacci — Le codage de Fibonacci est un codage entropique utilisé essentiellement en compression de données. Il utilise les nombres de la suite de Fibonacci, dont les termes ont la particularité d être composés de la somme des deux termes consécutifs… …   Wikipédia en Français

  • Codage zeta — Le codage zeta ou codage de Boldi Vigna est un codage entropique inventé par Paolo Boldi et Sebastiano Vigna en 2003 et utilisé essentiellement en compression de graphes. Le code zeta produit est un code préfixe et universel. Sommaire 1 Principe… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”