Compression de données/Transformée de Burrows-Wheeler

La transformée de Burrows-Wheeler, couramment désignée par le sigle BWT (pour "Burrows-Wheeler Transform") est un prétraitement utilisé en compression de données.
Inventée par Michael Burrows et David Wheeler, elle a été publiée en 1994, à la suite de travaux précédents de Wheeler en 1983.
Il ne s'agit pas d'un algorithme de compression, car aucune réduction de taille n'est effectuée.
Il s'agit d'une méthode de réorganisation des données : la probabilité que des caractères identiques initialement éloignés les uns des autres se retrouvent côte à côte dans le résultat est accrue.
La technique est à la base de l'algorithme de compression bzip2 qui est actuellement l'un de ceux offrant un des meilleurs taux de compression. Elle est aussi très utilisée en génomique, par exemple pour les problèmes d'alignement de lectures courtes issues des nouvelles technologies de séquençage d'ADN (ou d'ARN) ou pour des problèmes de comptage de mots (détection de répétitions).
Fonctionnement.
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
 E X T U E L
 L E X T U E
 E L E X T U
 U E L E X T
 T U E L E X
 X T U E L E
 E X T U E L 
Puis l'on classe ces chaînes par ordre alphabétique :
 Chaîne Position
 E L E X T U 1
 E X T U E L 2
 L E X T U E 3
 E X T U E L 4 ← position du texte original
 T U E L E X 5
 U E L E X T 6
 X T U E L 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.
Utilisation en compression.
La transformation de Burrows et Wheeler n'apporte aucun gain de compression. Au contraire même, car il est nécessaire de transmettre la position du texte original pour le décodage.
Cependant, on observe que la transformée de textes relativement longs comportent de nombreuses répétitions contiguës de caractères car ils contiennent un nombre élevé de fois les mêmes mots. 
Cela provient du fait que la transformée de Burrows et Wheeler revient à trier les caractères par ordre alphabétique, puis à chaque fois écrire le caractère qui précédait dans le texte original. Vu qu'elle est construite par rotation, la dernière colonne est composée des caractères précédant. Un exemple flagrant est la transformation de « TEXTUELTEXTUEL » qui donne : « 7UUTTEELLXXTTEE ».
À des fins de compression donc, on utilise un algorithme de type MTF sur cette transformée. Les répétitions de caractères produiront beaucoup de zéros. Un codage de Huffman sur un tel résultat permet d'obtenir un taux élevé de compression.
Décodage.
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 couples de lettres obtenus 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 donné par son numéro de ligne :
On retrouve bien le texte original à la ligne dont le numéro avait été transmis avec le texte codé.
Vu que la chaîne transformée est constituée des caractères qui précèdent dans l'ordre alphabétique. Une autre manière d'appréhender ce décodage consiste à trier par ordre alphabétique et prendre à chaque fois le suivant dans la chaîne transformée.
etc.

Agrodatabase/21 - Prontuaire culture - Données/Ail

Agrodatabase/21 - Prontuaire culture - Données/Oignons

Agrodatabase/21 - Prontuaire culture - Données/Tomates

Agrodatabase/21 - Prontuaire culture - Données/Poivrons

Agrodatabase/21 - Prontuaire culture - Données/Aubergines

Agrodatabase/21 - Prontuaire culture - Données/Concombres

Agrodatabase/21 - Prontuaire culture - Données/Courgettes

Agrodatabase/21 - Prontuaire culture - Données/Melons

Agrodatabase/21 - Prontuaire culture - Données/Potirons

Agrodatabase/21 - Prontuaire culture - Données/Pastèques

Agrodatabase/21 - Prontuaire culture - Données/Chayote

Agrodatabase/21 - Prontuaire culture - Données/Brocolis

Agrodatabase/21 - Prontuaire culture - Données/Choux fleurs

Agrodatabase/21 - Prontuaire culture - Données/Choux pommés

Agrodatabase/21 - Prontuaire culture - Données/Choux de Chine

Agrodatabase/21 - Prontuaire culture - Données/Laitue

Agrodatabase/21 - Prontuaire culture - Données/Chicorée

Agrodatabase/21 - Prontuaire culture - Données/Épinards

Agrodatabase/21 - Prontuaire culture - Données/Feuilles de bettes

Agrodatabase/21 - Prontuaire culture - Données/Céleri

Agrodatabase/21 - Prontuaire culture - Données/Asperges

Agrodatabase/21 - Prontuaire culture - Données/Artichauts

Auto-éditer un wikilivre/Auto-référencer/Description du projet

Informatique
Algorithme
Pathologie/Anatomie pathologique/Macroscopie

La macroscopie est l'étude des prélèvements et des pièces opératoires à l’œil nu. 
Elle a pour but de mettre en évidence des anomalies morphologiques macroscopiques.
L'examen macroscopique peut être celui des pièces opératoires (pathologie chirurgicale) ou des cadavres (autopsie).

Pathologie/Anatomie pathologique/Microscopie

En anatomie pathologique, la microscopie est l'étude microscopique des tissus et des tumeurs à des fins diagnostiques. 
Son but est d'identifier des anomalies microscopiques.
= Théorie cellulaire =
La s'est développé au début du 19e siècle. 
Une théorie cellulaire des processus pathologiques a émergé à partir du début du 19e siècle avec des auteurs comme :
La description microscopique des maladies et des tumeurs humaines s'est ensuite étendue tout le 19e et 20e siècle.
= Galerie =

Pathologie/Anatomie pathologique/Anomalies microscopiques

Les anomalies microscopiques sont des anomalies morphologiques détectables au microscope.

Pathologie/Anatomie pathologique/Pathologie tumorale

La pathologie tumorale est l'étude des tumeurs dans un but diagnostique ou pronostique.

Pathologie/Anatomie pathologique/Description des tumeurs

La description des tumeurs
Comment décrire une tumeur ?
Macroscopie :
Examen microscopique :

Compression de données/Codage par répétition

Les algorithmes de codage par répétition permettent la compression des répétitions successives du même caractère, ou d'une même séquence de caractères.
Ici un caractère est à prendre au sens large, représentant une donnée de taille déterminée, pouvant être un octet pour un fichier, un pixel pour une image, un nombre dans un tableau...
Différents algorithmes de codage par répétition existent :

Compression de données/Taux de compression