La transformación de Burrows-Wheeler ( BWT , también llamada compresión de clasificación de bloques ) reorganiza una cadena de caracteres en series de caracteres similares. Esto es útil para la compresión, ya que tiende a ser fácil comprimir una cadena que tiene series de caracteres repetidos mediante técnicas como la transformación de movimiento al frente y la codificación de longitud de serie . Más importante aún, la transformación es reversible , sin necesidad de almacenar ningún dato adicional excepto la posición del primer carácter original. El BWT es, por lo tanto, un método "gratuito" para mejorar la eficiencia de los algoritmos de compresión de texto, que solo cuesta algunos cálculos adicionales. La transformada de Burrows-Wheeler es un algoritmose utiliza para preparar datos para su uso con técnicas de compresión de datos como bzip2 . Fue inventado por Michael Burrows y David Wheeler en 1994 mientras Burrows trabajaba en el Centro de Investigación de Sistemas DEC en Palo Alto , California. Se basa en una transformación inédita descubierta por Wheeler en 1983. El algoritmo se puede implementar de manera eficiente utilizando una matriz de sufijos , alcanzando así una complejidad de tiempo lineal. [1]
Cuando el BWT transforma una cadena de caracteres , la transformación permuta el orden de los caracteres. Si la cadena original tenía varias subcadenas que ocurrían con frecuencia, la cadena transformada tendrá varios lugares donde un solo carácter se repite varias veces seguidas.
La salida es más fácil de comprimir porque tiene muchos caracteres repetidos. En este ejemplo, la cadena transformada contiene seis series de caracteres idénticos: XX, SS, PP, .., IIy III, que juntos forman 13 de los 44 caracteres.
La transformación se realiza ordenando todos los cambios circulares de un texto en orden lexicográfico y extrayendo la última columna y el índice de la cadena original en el conjunto de permutaciones ordenadas de S.
Dada una cadena de entrada (paso 1 en la tabla a continuación), gírela N veces (paso 2), donde está la longitud de la cadena considerando también el símbolo que representa el inicio de la cadena y el rojo | carácter que representa el puntero ' EOF '; estas rotaciones, o desplazamientos circulares, se clasifican lexicográficamente (paso 3). El resultado de la fase de codificación es la última columna después del paso 3 y el índice (basado en 0) de la fila que contiene la cadena original , en este caso .S = ^BANANA|N = 8S^L = BNN^AA|AISI = 7
El siguiente pseudocódigo brinda una forma simple (aunque ineficiente) de calcular el BWT y su inversa. Asume que la cadena de entrada scontiene un carácter especial 'EOF' que es el último carácter y no aparece en ninguna otra parte del texto.