La transformada de Burrows-Wheeler ( BWT , también llamada compresión por ordenamiento de bloques ) reorganiza una cadena de caracteres en secuencias de caracteres similares. Esto es útil para la compresión, ya que tiende a ser fácil comprimir una cadena que tiene secuencias de caracteres repetidos mediante técnicas como la transformada de movimiento al frente y la codificación por longitud de secuencia . 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. La BWT es, por 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 algoritmo utilizado 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 temporal lineal. [1]
Cuando BWT transforma una cadena de caracteres , la transformación permuta el orden de los caracteres. Si la cadena original tenía varias subcadenas que se repetían con frecuencia, la cadena transformada tendrá varios lugares en los que un mismo carácter se repite varias veces seguidas.
Por ejemplo:
La salida es más fácil de comprimir porque tiene muchos caracteres repetidos. En este ejemplo, la cadena transformada contiene seis secuencias de caracteres idénticos: XX, SS, PP, .., IIy III, que juntas forman 13 de los 44 caracteres.
La transformación se realiza ordenando todos los desplazamientos 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 siguiente), rótela N veces (paso 2), donde es la longitud de la cadena considerando también el carácter rojo que representa el inicio de la cadena y el carácter rojo que representa el puntero ' EOF '; estas rotaciones, o desplazamientos circulares, se ordenan luego lexicográficamente (paso 3). La salida 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 = 6
No es necesario utilizar ambos $, ^pero se debe utilizar al menos uno, de lo contrario no podemos invertir la transformación, ya que todas las permutaciones circulares de una cadena tienen la misma transformación de Burrows-Wheeler.
El siguiente pseudocódigo ofrece una forma sencilla (aunque ineficiente) de calcular la BWT y su inversa. Supone que la cadena de entrada scontiene un carácter especial 'EOF', que es el último carácter y no aparece en ningún otro lugar del texto.
función BWT ( cadena s) Crea una tabla, donde las filas son todas las rotaciones posibles de s ordenar filas alfabéticamente regresar (ultima columna de la tabla)
función inversaBWT ( cadena s) crear tabla vacía repetir longitud(es) veces // la primera inserción crea la primera columna Insertar s como una columna de la tabla antes de la primera columna de la tabla Ordenar las filas de la tabla alfabéticamente regresar (fila que termina con el carácter 'EOF')
Para entender por qué esto crea datos más fáciles de comprimir, considere transformar un texto largo en inglés que contenga frecuentemente la palabra "the". Ordenar las rotaciones de este texto agrupará las rotaciones que comiencen con "he", y el último carácter de esa rotación (que también es el carácter antes de "he") generalmente será "t", por lo que el resultado de la transformación contendrá una cantidad de caracteres "t" junto con las excepciones quizás menos comunes (como si contiene "ache") mezcladas. Por lo tanto, se puede ver que el éxito de esta transformación depende de que un valor tenga una alta probabilidad de aparecer antes de una secuencia, por lo que en general necesita muestras bastante largas (al menos unos pocos kilobytes) de datos apropiados (como texto).
Lo notable del BWT no es que genere una salida más fácil de codificar (una clasificación normal haría eso), sino que lo hace de manera reversible , permitiendo que el documento original se vuelva a generar a partir de los datos de la última columna.
La operación inversa se puede entender de esta manera. Tome la tabla final en el algoritmo BWT y borre todas las columnas excepto la última. Con solo esta información, puede reconstruir fácilmente la primera columna. La última columna le indica todos los caracteres del texto, por lo que simplemente ordene estos caracteres alfabéticamente para obtener la primera columna. Luego, la última y la primera columnas (de cada fila) juntas le brindan todos los pares de caracteres sucesivos en el documento, donde los pares se toman cíclicamente de modo que el último y el primer carácter forman un par. Al ordenar la lista de pares, se obtienen la primera y la segunda columna. Continuando de esta manera, puede reconstruir la lista completa. Luego, la fila con el carácter "fin de archivo" al final es el texto original. La inversión del ejemplo anterior se realiza de la siguiente manera:
Una serie de optimizaciones pueden hacer que estos algoritmos se ejecuten de manera más eficiente sin cambiar la salida. No es necesario representar la tabla ni en el codificador ni en el decodificador. En el codificador, cada fila de la tabla se puede representar mediante un único puntero a las cadenas, y la ordenación se puede realizar utilizando los índices. En el decodificador, tampoco es necesario almacenar la tabla y, de hecho, no se necesita ninguna ordenación. En un tiempo proporcional al tamaño del alfabeto y la longitud de la cadena, la cadena decodificada se puede generar un carácter a la vez de derecha a izquierda. Un "carácter" en el algoritmo puede ser un byte, un bit o cualquier otro tamaño conveniente.
También se puede observar que, matemáticamente, la cadena codificada se puede calcular como una simple modificación de la matriz de sufijos , y las matrices de sufijos se pueden calcular con tiempo lineal y memoria. La BWT se puede definir con respecto a la matriz de sufijos SA del texto T como (indexación basada en 1):
[3]
No es necesario tener un carácter 'EOF' real. En su lugar, se puede utilizar un puntero que recuerde dónde estaría el 'EOF' en una cadena si existiera. En este enfoque, la salida de la BWT debe incluir tanto la cadena transformada como el valor final del puntero. La transformación inversa luego la reduce al tamaño original: se le da una cadena y un puntero, y devuelve solo una cadena.
Se puede encontrar una descripción completa de los algoritmos en el artículo de Burrows y Wheeler, o en varias fuentes en línea. [1] Los algoritmos varían un poco según si se utiliza EOF y en qué dirección se realizó la clasificación. De hecho, la formulación original no utilizaba un marcador EOF. [4]
Dado que cualquier rotación de la cadena de entrada dará como resultado la misma cadena transformada, la BWT no se puede invertir sin agregar un marcador EOF al final de la entrada o hacer algo equivalente, lo que permite distinguir la cadena de entrada de todas sus rotaciones. Aumentar el tamaño del alfabeto (agregando el carácter EOF) hace que los pasos de compresión posteriores sean complicados.
Existe una versión biyectiva de la transformación, mediante la cual la cadena transformada identifica de forma única a la original, y las dos tienen la misma longitud y contienen exactamente los mismos caracteres, sólo que en un orden diferente. [5] [6]
La transformación biyectiva se calcula factorizando la entrada en una secuencia no creciente de palabras Lyndon ; dicha factorización existe y es única según el teorema de Chen–Fox–Lyndon [7] y puede encontrarse en tiempo lineal y espacio constante. [8] El algoritmo ordena las rotaciones de todas las palabras; como en la transformación de Burrows–Wheeler, esto produce una secuencia ordenada de n cadenas. La cadena transformada se obtiene entonces eligiendo el carácter final de cada cadena en esta lista ordenada. La única salvedad importante aquí es que las cadenas de diferentes longitudes no se ordenan de la forma habitual; las dos cadenas se repiten para siempre y las repeticiones infinitas se ordenan. Por ejemplo, "ORO" precede a "OR" porque "OROORO..." precede a "OROROR...".
Por ejemplo, el texto " ^ BANANA $ " se transforma en "ANNBAA ^ $ " mediante estos pasos (el carácter $ rojo indica el puntero EOF ) en la cadena original. El carácter EOF no es necesario en la transformación biyectiva, por lo que se omite durante la transformación y se vuelve a agregar a su lugar correspondiente en el archivo.
La cadena se divide en palabras de Lyndon, de modo que las palabras de la secuencia se ordenan de manera decreciente utilizando el método de comparación anterior. (Tenga en cuenta que estamos ordenando " ^ " como caracteres sucesivos). " ^ BANANA" se convierte en ( ^ ) (B) (AN) (AN) (A).
Hasta el último paso, el proceso es idéntico al proceso inverso de Burrows-Wheeler, pero aquí no necesariamente dará rotaciones de una sola secuencia; en cambio, da rotaciones de palabras de Lyndon (que comenzarán a repetirse a medida que continúa el proceso). Aquí, podemos ver (repeticiones de) cuatro palabras de Lyndon distintas: (A), (AN) (dos veces), (B) y ( ^ ). (NANA... no representa una palabra distinta, ya que es un ciclo de ANAN...) En este punto, estas palabras se ordenan en orden inverso: ( ^ ), (B), (AN), (AN), (A). Luego, se concatenan para obtener
La transformación de Burrows-Wheeler puede considerarse un caso especial de esta transformación biyectiva: en lugar de la tradicional introducción de una nueva letra ajena a nuestro alfabeto para indicar el final de la cadena, podemos introducir una nueva letra que precede a todas las letras existentes y que se coloca al principio de la cadena. La cadena completa es ahora una palabra Lyndon y, por lo tanto, al ejecutarla a través del proceso biyectivo se obtendrá un resultado transformado que, al invertirse, devuelve la palabra Lyndon, sin necesidad de volver a ensamblarla al final.
De manera similar, el texto transformado solo diferirá del resultado de BWT en un carácter por cada palabra de Lyndon; por ejemplo, si la entrada se descompone en seis palabras de Lyndon, la salida solo diferirá en seis caracteres. Por ejemplo, al aplicar la transformación biyectiva se obtiene:
La transformación biyectiva incluye ocho series de caracteres idénticos. Estas series son, en orden: XX, II, XX, PP, .., EE, .., y IIII.
En total se utilizan 18 caracteres en estas ejecuciones.
Cuando se edita un texto, su transformada de Burrows-Wheeler cambiará. Salson et al. [9] proponen un algoritmo que deduce la transformada de Burrows-Wheeler de un texto editado a partir de la del texto original, realizando un número limitado de reordenamientos locales en la transformada de Burrows-Wheeler original, lo que puede ser más rápido que construir directamente la transformada de Burrows-Wheeler del texto editado.
Esta implementación de Python sacrifica velocidad por simplicidad: el programa es corto, pero requiere más tiempo del que sería deseable en una implementación práctica. Básicamente, hace lo mismo que la sección de pseudocódigo.
Utilizando los códigos de control STX/ETX para marcar el inicio y el final del texto, y utilizando s[i:] + s[:i]para construir la irotación th de s, la transformada hacia adelante toma el último carácter de cada una de las filas ordenadas:
![{\displaystyle BWT[i]={\begin{cases}T[SA[i]-1],&{\text{si }}SA[i]>0\\\$,&{\text{en caso contrario}}\end{cases}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/887d46efbb40f6f35ac2b8a5a3a60e42cef84bb2)
desde curses.ascii importar STX , ETXdef bwt ( s : str , start = chr ( STX ), end = chr ( ETX )) -> str : r """ Aplicar la transformada de Burrows–Wheeler a la cadena de entrada. >>> bwt('BANANA') '\x03ANNB\x02AA' >>> bwt('BANANA', start='^', end='$') 'ANNB^AA$' >>> bwt('BANANA', start='%', end='$') 'A$NNB%AA' """ assert ( start not in s and end not in s ), "La cadena de entrada no puede contener caracteres STX y ETX" s = f " { start }{ s }{ end } " # Agregar marcador de inicio y fin de texto # Tabla de rotaciones de cadenas table = sorted ( f " { s [ i :] }{ s [: i ] } " for i , c in enumerate ( s )) last_column = [ row [ - 1 :] for row in table ] # Últimos caracteres de cada fila return "" . join ( last_column ) # Convertir lista de caracteres en cadenaLa transformación inversa inserta repetidamente rla columna izquierda de la tabla y ordena la tabla. Una vez que se crea toda la tabla, devuelve la fila que termina con ETX, menos STX y ETX.
def inverse_bwt ( r : str , start = chr ( STX ), end = chr ( ETX )) -> str : r """ Aplicar la transformada inversa de Burrows–Wheeler. >>> inverse_bwt('\x03ANNB\x02AA') 'BANANA' >>> inverse_bwt('ANNB^AA$', start='^', end='$') 'BANANA' >>> inverse_bwt('A$NNB%AA', start='%', end='$') 'BANANA' """ str_len = len ( r ) table = [ "" ] * str_len # Crea una tabla vacía para _ en el rango ( str_len ): table = sorted ( rc + tc for rc , tc in zip ( r , table )) # Agrega una columna de r # Iterar y verificar si el último carácter termina con ETX o no s = next (( fila por fila en la tabla si fila . endswith ( fin )), "" ) # Recupera datos de la matriz y elimina los marcadores de inicio y fin return s . rstrip ( end ) . strip ( start )Siguiendo las notas de implementación de Manzini, es equivalente a utilizar un sufijo de carácter nulo simple en su lugar. La clasificación debe realizarse en orden colexicográfico (cadena leída de derecha a izquierda), es decir, en Python. [4] (Los códigos de control anteriores en realidad no cumplen con que EOF sea el último carácter; los dos códigos son en realidad el primero . La rotación se mantiene de todos modos).sorted(..., key=lambda s: s[::-1])
Como algoritmo de compresión sin pérdidas , la transformada de Burrows-Wheeler ofrece la importante cualidad de que su codificación es reversible y, por lo tanto, los datos originales pueden recuperarse de la compresión resultante. La cualidad sin pérdidas del algoritmo de Burrows ha permitido que se utilicen diferentes algoritmos con diferentes propósitos. Por nombrar algunos, la transformada de Burrows-Wheeler se utiliza en algoritmos de alineación de secuencias , compresión de imágenes , compresión de datos , etc. A continuación, se incluye una recopilación de algunos usos dados a la transformada de Burrows-Wheeler.
La llegada de las técnicas de secuenciación de nueva generación (NGS) a finales de la década de 2000 ha dado lugar a otra aplicación de la transformación de Burrows-Wheeler. En la NGS, el ADN se fragmenta en pequeños trozos, de los que se secuencian las primeras bases , lo que produce varios millones de "lecturas", cada una de entre 30 y 500 pares de bases ("caracteres del ADN") de longitud. En muchos experimentos, por ejemplo, en ChIP-Seq , la tarea consiste ahora en alinear estas lecturas con un genoma de referencia , es decir, con la secuencia conocida, casi completa, del organismo en cuestión (que puede tener hasta varios miles de millones de pares de bases de longitud). Se publicaron varios programas de alineamiento, especializados para esta tarea, que inicialmente se basaban en el hash (por ejemplo, Eland, SOAP, [10] o Maq [11] ). En un esfuerzo por reducir el requisito de memoria para la alineación de secuencias, se desarrollaron varios programas de alineación ( Bowtie , [12] BWA, [13] y SOAP2 [14] ) que utilizan la transformada de Burrows-Wheeler.
La transformación de Burrows-Wheeler ha demostrado ser fundamental para las aplicaciones de compresión de imágenes . Por ejemplo, [15] mostró una secuencia de compresión basada en la aplicación de la transformación de Burrows-Wheeler seguida de codificadores de inversión, longitud de ejecución y aritméticos. La secuencia desarrollada en este caso se conoce como transformada de Burrows-Wheeler con un codificador de inversión (BWIC). Se ha demostrado que los resultados mostrados por BWIC superan el rendimiento de compresión de algoritmos conocidos y ampliamente utilizados como Lossless JPEG y JPEG 2000. Se ha demostrado que BWIC supera a aquellos en términos de tamaño de compresión final de imágenes médicas de radiografía en el orden del 5,1% y el 4,1% respectivamente. Las mejoras se logran combinando BWIC y un escaneo previo a BWIC de la imagen en forma de serpiente vertical. Más recientemente, trabajos adicionales como el de [16] han demostrado que la implementación de la Transformada de Burrows-Wheeler junto con la conocida transformada de movimiento al frente (MTF) logra una compresión de imágenes casi sin pérdidas.
Cox et al. [17] presentaron un esquema de compresión genómica que utiliza BWT como algoritmo aplicado durante la primera etapa de compresión de varios conjuntos de datos genómicos, incluida la información genómica humana. Su trabajo propuso que la compresión BWT podría mejorarse mediante la inclusión de un mecanismo de compresión de segunda etapa llamado codificación similar a la anterior ("SAP"), que aprovecha el hecho de que los sufijos de dos o más letras de prefijo pueden ser iguales. Con el mecanismo de compresión BWT-SAP, Cox et al. demostraron que en la base de datos genómica ERA015743, de 135,5 GB de tamaño, el esquema de compresión BWT-SAP comprime el conjunto de datos ERA015743 en alrededor del 94 %, a 8,2 GB.
También se ha demostrado que BWT es útil en la predicción de secuencias, que es un área de estudio común en el aprendizaje automático y el procesamiento del lenguaje natural . En particular, Ktistakis et al. [18] propusieron un esquema de predicción de secuencias llamado SuBSeq que explota la compresión sin pérdida de datos de la transformada de Burrows-Wheeler. SuBSeq explota BWT extrayendo el índice FM y luego realizando una serie de operaciones llamadas búsqueda hacia atrás, búsqueda hacia adelante, expansión de vecinos y obtención de consecuencias para buscar predicciones dado un sufijo . Luego, las predicciones se clasifican en función de un peso y se colocan en una matriz de la cual se proporciona el elemento con el peso más alto como la predicción del algoritmo SuBSeq. Se ha demostrado que SuBSeq supera a los algoritmos de última generación para la predicción de secuencias tanto en términos de tiempo de entrenamiento como de precisión.