compresión de Burrows-Wheeler

La transformación de Burrows–Wheeler (BWT del inglés Burrows–Wheeler transform, también conocida como compresión por ordenación de bloques), es un algoritmo usado en técnicas de compresión de datos como en bzip2. Fue inventado por Michael Burrows y David Wheeler en 1994 mientras trabajaban en el en Palo Alto, California.​ Se basa en una transformación previamente descubierta por Wheeler que no se encuentra publicada. Cuando se transforma una cadena de caracteres mediante la BWT, ninguno de sus caracteres cambia de valor. La transformación permuta el orden de los caracteres. Si la cadena original contiene muchas subcadenas que aparecen a menudo, entonces la cadena transformada contendrá múltiples posiciones en las que un mismo carácter esté repetido varias veces en una fila. Esto es útil para la compresión, ya que tiende a ser fácil comprimir una cadena que contiene secuencias de caracteres repetidos con técnicas como y run-length encoding. Por ejemplo: La salida es más fácil de comprimir ya que tiene muchos caracteres repetidos.De hecho, en la cadena transformada, aparece un total de seis secuencias de caracteres idénticos: XX,SS,PP,..,II,yIII, que juntos representan 13 de los 44 caracteres.