Transformee de Burrows-Wheeler

Transformee de Burrows-Wheeler

Transformée de Burrows-Wheeler

Page d'aide sur l'homonymie Pour les articles homonymes, voir BWT.

La transformée de Burrows-Wheeler, couramment appelée BWT (pour Burrows-Wheeler Transform) est une technique utilisée en compression de données. Elle fut inventée par Michael Burrows et David Wheeler. Cette technique fut rendue publique en 1994, à la suite de travaux précédents de Wheeler en 1983. Il ne s'agit pas à proprement parler d'un algorithme de compression, car aucune réduction de taille n'est effectuée, au contraire (voir ci-dessous), mais bien d'une méthode de réorganisation des données : les probabilités pour que des caractères identiques initialement éloignés les uns des autres se retrouvent côte à côte sont alors augmentées. Cette technique n'est pas très utilisée, mais l'on peut cependant remarquer qu'elle est présente dans le format bzip2 qui est actuellement l'un des formats offrant un des meilleurs taux de compression.

Sommaire

Fonctionnement

Comme nous l'avons dit, la transformée de Burrows-Wheeler ne compresse pas les données, elle se contente de les réorganiser de manière à obtenir un plus gros taux de compression.

Tout d'abord, la chaîne de caractères à coder doit être copiée dans un tableau carré en décalant la chaîne d'un caractère vers la droite à chaque nouvelle ligne. Ces lignes sont ensuite classées par ordre alphabétique. Nous savons que, grâce au décalage, chaque dernière lettre de chaque ligne précède la première lettre de la même ligne, sauf pour la ligne originale dont on notera la position. De plus, comme les lignes sont rangées par ordre alphabétique, on peut retrouver la première colonne du tableau grâce à la dernière colonne.

Prenons un exemple : supposons que la chaîne à coder soit « TEXTUEL ». On réalise tout d'abord le tableau. La première lettre est marquée ici en rouge pour améliorer la lecture du tableau.

Chaîne

T E X T U E L
L T E X T U E
E L T E X T U
U E L T E X T
T U E L T E X
X T U E L T E
E X T U E L T

Puis l'on classe ces chaînes par ordre alphabétique :

Chaîne            Position

E L T E X T U     1
E X T U E L T     2
L T E X T U E     3
T E X T U E L     4 <- position du texte original
T U E L T E X     5
U E L T E X T     6
X T U E L T E     7

Le texte codé est alors constitué de la dernière colonne précédée de la position du texte original, soit : « 4UTELXTE ». La position du texte original sert au décodage.

Cette transformation n'apporte aucun gain de compression immédiat, au contraire, car il est nécessaire de transmettre des informations supplémentaires pour le décodage. Cependant, pour un texte relativement long en langage naturel, qui contient plusieurs fois les mêmes mots, le texte codé comportera de nombreuses répétitions de caractères. Ainsi, Burrows et Wheeler recommandent d'utiliser ensuite un algorithme de type MTF qui, de par les répétitions de caractères, génèrera beaucoup de 0. Ceci assure avec un algorithme de type codage de Huffman un quotient de compression élevé.

Le décodage consiste à reconstruire le tableau complet à partir de sa dernière colonne (texte codé « UTELXTE ») à partir de laquelle on reconstruit la colonne « suivante », c’est-à-dire, par rotation, la première, dont on sait qu’elle est dans l’ordre alphabétique (« EELTTUX »). On colle alors la dernière colonne juste avant cette première colonne, puis on classe dans l’ordre alphabétique les paires obtenues pour construire les deux premières colonnes. On répète ensuite cette opération jusqu’à constituer le tableau complet dans lequel on retrouve le texte original par son numéro de ligne :

Initiation Tri Collage Tri Collage Tri
      U
      T
      E
      L
      X
      T
      E
      E
      E
      L
      T
      T
      U
      X
     UE
     TE
     EL
     LT
     XT
     TU
     EX
     EL
     EX
     LT
     TE
     TU
     UE
     XT
    UEL
    TEX
    ELT
    LTE
    XTU
    TUE
    EXT
    ELT
    EXT
    LTE
    TEX
    TUE
    UEL
    XTU
Collage Tri Collage Tri Collage Tri
   UELT
   TEXT
   ELTE
   LTEX
   XTUE
   TUEL
   EXTU
   ELTE
   EXTU
   LTEX
   TEXT
   TUEL
   UELT
   XTUE
  UELTE
  TEXTU
  ELTEX
  LTEXT
  XTUEL
  TUELT
  EXTUE
  ELTEX
  EXTUE
  LTEXT
  TEXTU
  TUELT
  UELTE
  XTUEL
 UELTEX
 TEXTUE
 ELTEXT
 LTEXTU
 XTUELT
 TUELTE
 EXTUEL
 ELTEXT
 EXTUEL
 LTEXTU
 TEXTUE
 TUELTE
 UELTEX
 XTUELT
Collage Tri Sélection
UELTEXT
TEXTUEL
ELTEXTU
LTEXTUE
XTUELTE
TUELTEX
EXTUELT
ELTEXTU
EXTUELT
LTEXTUE
TEXTUEL
TUELTEX
UELTEXT
XTUELTE
   1
   2
   3
<- 4
   5
   6
   7

On retrouve bien le texte original à la ligne dont le numéro avait été transmis avec le texte codé.

Voir aussi

Articles connexes

Références

  1. Michael Burrows, D. J. Wheeler: "A block-sorting lossless data compression algorithm", 10th May 1994, Digital SRC Research Report 124.
  • Portail de l’informatique Portail de l’informatique
Ce document provient de « Transform%C3%A9e de Burrows-Wheeler ».

Wikimedia Foundation. 2010.

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

Игры ⚽ Нужно сделать НИР?

Regardez d'autres dictionnaires:

  • Transformée de burrows-wheeler — Pour les articles homonymes, voir BWT. La transformée de Burrows Wheeler, couramment appelée BWT (pour Burrows Wheeler Transform) est une technique utilisée en compression de données. Elle fut inventée par Michael Burrows et David Wheeler. Cette… …   Wikipédia en Français

  • Transformée de Burrows-Wheeler — Pour les articles homonymes, voir BWT. La transformée de Burrows Wheeler, couramment appelée BWT (pour anglais : Burrows Wheeler Transform) est une technique utilisée en compression de données. Elle fut inventée par Michael Burrows et David… …   Wikipédia en Français

  • Transformation de Burrows-Wheeler — Transformée de Burrows Wheeler Pour les articles homonymes, voir BWT. La transformée de Burrows Wheeler, couramment appelée BWT (pour Burrows Wheeler Transform) est une technique utilisée en compression de données. Elle fut inventée par Michael… …   Wikipédia en Français

  • Wheeler — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Wheeler peut désigner : Patronyme Wheeler est un nom de famille notamment porté par : Anne Wheeler, (1946 ), réalisatrice, scénariste,… …   Wikipédia en Français

  • Transformation de Burrow-Wheeler — Transformée de Burrows Wheeler Pour les articles homonymes, voir BWT. La transformée de Burrows Wheeler, couramment appelée BWT (pour Burrows Wheeler Transform) est une technique utilisée en compression de données. Elle fut inventée par Michael… …   Wikipédia en Français

  • Michael Burrows — Naissance 1963 Nationalité  Royaume Uni Profession Programmeur …   Wikipédia en Français

  • David John Wheeler — David Wheeler Pour les articles homonymes, voir Wheeler. David John Wheeler Naissance 9 février 1927 Birmingham Décès 13 décembre  …   Wikipédia en Français

  • David Wheeler — Pour les articles homonymes, voir Wheeler. David John Wheeler Naissance 9 février 1927 Birmingham Décès 13 décembre 2004 …   Wikipédia en Français

  • Compression de données — La compression de données ou codage de source est l opération informatique qui consiste à transformer une suite de bits A en une suite de bits B plus courte, contenant les mêmes informations, en utilisant un algorithme particulier. Il s agit d… …   Wikipédia en Français

  • Compression De Données — La compression de données est l opération informatique qui consiste à transformer une suite de bits A en une suite de bits B plus courte, et qui contient les mêmes informations, en utilisant un algorithme particulier. La décompression est l… …   Wikipédia en Français

Share the article and excerpts

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