Remove ads
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 DEC Systems Research Center en Palo Alto, California.[1] 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 move-to-front transform y run-length encoding.
Por ejemplo:
| Entrada | SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES |
|---|---|
| Salida | TEXYDST.E.IXIXIXXSSMPPS.B..E.S.EUSFXDIIOIIIT |
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, y III, que juntos representan 13 de los 44 caracteres.
Remove ads
La transformación se realiza ordenando todas las rotaciones del texto en orden lexicográfico, y seleccionando la última columna. Por ejemplo, el texto "^BANANA@" se transforma en "BNN^AA@A" a través de estos pasos (el símbolo rojo @ indica el 'EOF (final de fichero)'):
| Transformación | |||
|---|---|---|---|
| Entrada | Todas las Rotaciones |
Ordenar Filas |
Salida |
^BANANA@ |
^BANANA@ @^BANANA A@^BANAN NA@^BANA ANA@^BAN NANA@^BA ANANA@^B BANANA@^ |
ANANA@^B ANA@^BAN A@^BANAN BANANA@^ NANA@^BA NA@^BANA ^BANANA@ @^BANANA |
BNN^AA@A |
El siguiente pseudocódigo ofrece una forma simple pero ineficiente de calcular el BWT y su inversa. Se asume que la cadena de entrada s contiene un carácter especial 'EOF' que será el último carácter, que solo aparece una vez en el texto, y será ignorado durante la ordenación.
function BWT (string s) crear una tabla donde las filas son todas las rotaciones posibles de s ordenar las filas alfabéticamente return (última columna de la tabla)
function invertirBWT (string s)
crear una tabla vacía
repeat length(s) times
Insertar s como una columna de la tabla antes de la primera columna de la tabla // la primera inserción crea la primera columna
ordenar las filas de la tabla alfabéticamente
return (la fila que acabe en el carácter 'EOF')
Para entender por qué se crean datos más fáciles de comprimir, se puede considerar la transformación de un texto largo en inglés que contenga frecuentemente la palabra "the". Ordenando las rotaciones de este texto a menudo agrupará rotaciones que empiecen por "he ", y el último carácter de esa rotación (que también será el carácter anterior a "he ") normalmente será "t", por lo que el resultado de la transformación contendrá un número de caracteres "t" junto con algunas excepciones menos comunes (por ejemplo, si contuviese la cadena "Brahe "). Por lo tanto, se puede ver que el éxito de esta transformación depende de un único valor con una probabilidad muy alta de ocurrencia antes de una secuencia, por lo que en general necesita muestras muy largas (de al menos unos pocos kilobytes) de datos apropiados (como texto).
Lo más interesante sobre la BWT no es que genere una salida más fácil de codificar—una ordenación ordinaria podría hacerlo igualmente—sino que es un proceso reversible, permitiendo re-generar el documento original a partir de la última columna de datos.
La inversa puede entenderse de la siguiente manera. Se toma la tabla final del algoritmo BWT y se eliminan todas las columnas salvo la última. Con esta información, se puede reconstruir fácilmente la primera columna. La última columna indica todos los caracteres del texto, así que se ordena, para obtener la primera columna. Entonces, la primera y la última columna juntas indican todos los pares de caracteres sucesivos en el documento, donde los pares están tomados cíclicamente de manera que el último y el primer carácter forman un par. Ordenando la lista de pares se obtendrán la primera y la segunda columna. Continuando de esta manera, se puede reconstruir la lista entera. Por último, la fila con el carácter "EOF" al final será el texto original. La inversa del ejemplo anterior se realiza como sigue:
| Transformación Inversa | |||
|---|---|---|---|
| Entrada | |||
BNN^AA@A | |||
| Añadir 1 | Ordenar 1 | Añadir 2 | Ordenar 2 |
B
N
N
^
A
A
@
A |
A
A
A
B
N
N
^
@ |
BA NA NA ^B AN AN @^ A@ |
AN AN A@ BA NA NA ^B @^ |
| Añadir 3 | Ordenar 3 | Añadir 4 | Ordenar 4 |
BAN NAN NA@ ^BA ANA ANA @^B A@^ |
ANA ANA A@^ BAN NAN NA@ ^BA @^B |
BANA NANA NA@^ ^BAN ANAN ANA@ @^BA A@^B |
ANAN ANA@ A@^B BANA NANA NA@^ ^BAN @^BA |
| Añadir 5 | Ordenar 5 | Añadir 6 | Ordenar 6 |
BANAN NANA@ NA@^B ^BANA ANANA ANA@^ @^BAN A@^BA |
ANANA ANA@^ A@^BA BANAN NANA@ NA@^B ^BANA @^BAN |
BANANA NANA@^ NA@^BA ^BANAN ANANA@ ANA@^B @^BANA A@^BAN |
ANANA@ ANA@^B A@^BAN BANANA NANA@^ NA@^BA ^BANAN @^BANA |
| Añadir 7 | Ordenar 7 | Añadir 8 | Ordenar 8 |
BANANA@ NANA@^B NA@^BAN ^BANANA ANANA@^ ANA@^BA @^BANAN A@^BANA |
ANANA@^ ANA@^BA A@^BANA BANANA@ NANA@^B NA@^BAN ^BANANA @^BANAN |
BANANA@^ NANA@^BA NA@^BANA ^BANANA@ ANANA@^B ANA@^BAN @^BANANA A@^BANAN |
ANANA@^B ANA@^BAN A@^BANAN BANANA@^ NANA@^BA NA@^BANA ^BANANA@ @^BANANA |
| Salida | |||
^BANANA@ | |||
Remove ads
Se puede realizar una serie de optimizaciones para que estos algoritmos se ejecuten de manera más eficiente sin cambiar la salida. En BWT, no hay necesidad de representar la tabla ni en el codificador ni en el decodificador. En el codificador, cada fila de la tabla puede ser representada por un único puntero entre las cadenas, realizar la ordenación mediante los índices. Se debe llevar cuidado para asegurar que la ordenación no presente un mal comportamiento en el peor caso: las librerías estándar de ordenación probablemente no resulten adecuadas. En el decodificador, tampoco hay necesidad de almacenar la tabla o realizar la ordenación. En tiempo proporcional al tamaño del alfabeto y a la longitud de la cadena, la cadena decodificada puede generarse carácter a carácter de derecha a izquierda. Un "carácter" en el algoritmo puede ser un byte, un bit o cualquier otro tamaño pertinente.
No es necesario disponer de un carácter 'EOF' real. A cambio, se puede usar un puntero que recuerde dónde debería aparecer el 'EOF' si existiese. En esta aproximación, la salida del BWT debe incluir tanto la cadena transformada como el valor del puntero final. Esto significa que el BWT expande ligeramente su entrada. Por lo que la transformación inversa se reduce al tamaño original: se proporciona una cadena y un puntero, y se devuelve solo una cadena.
Se puede encontrar una descripción completa de los algoritmos en el paper de Burrows y Wheeler o varias fuentes en línea.
Remove ads
Puesto que cualquier rotación de la cadena de entrada derivará en la misma cadena transformada, la BWT no puede invertirse sin añadir una marca de 'EOF' a la entrada, o aumentando la salida con información, como un índice, que haga posible identificar la cadena de entrada del conjunto de todas sus rotaciones.
Existe una versión biyectiva de la transformación, por la cual la cadena transformada identifica inequívocamente a la original. En esta versión, cada cadena tiene una inversa única de la misma longitud.
La transformación biyectiva se procesa, primero factorizando la entrada como palabras de Lyndon, y luego ordenando todas las rotaciones de esas palabras. La cadena transformada se obtiene recogiendo el último carácter de las cadenas de la lista ordenada.
Por ejemplo, una aplicación de la transformación biyectiva:
| Input | SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES |
|---|---|
| Output | STEYDST.E.IXXIIXXSMPPXS.B..EE..SUSFXDIOIIIIT |
La transformación biyectiva proporciona ocho secuencias de caracteres idénticos. Estas secuencias son, en orden: XX, II, XX, PP, .., EE, .., y IIII. En total, 18 caracteres forman parte de estas secuencias.
Se puede encontrar una descripción completa del algoritmo en el artículo de Gil y Scott.
Remove ads
En lugar de reconstruir la transformación de Burrows–Wheeler de un texto editado, Salson et al.[2] proponen un algoritmo que deduce la nueva transformación de Burrows–Wheeler desde la original, realizando un número limitado reordenaciones locales sobre la transformación de Burrows–Wheeler original.
Esta implementación en Python sacrifica velocidad frente a simplicidad: el programa es corto, pero tiene un coste temporal mayor que lineal, que el deseado para una implementación práctica.
Usando un carácter nulo como marca de final de fichero y usando s[i:] + s[:i] para construir la i-ésima rotación de s, la transformación final recoge el último carácter de cada una de las filas ordenadas.
def bwt(s):
"""Applica la transformación de Burrows–Wheeler a la cadena de entrada."""
assert "\0" not in s, "La cadena de entrada no puede contener el carácter nulo ('\0')"
s += "\0" # Se añade la marca de final de fichero
table = sorted(s[i:] + s[:i] for i in range(len(s))) # Tabla de rotaciones de la cadena
last_column = [row[−1] for row in table] # Últimos caracteres de cada fila
return "".join(last_column) # Convierte la lista de caracteres en una cadena
La transformada inversa inserta r repetidas veces como columna izquierda de la tabla y ordena la tabla. Tras completar la tabla entera, la función devuelve la fila que acaba en carácter nulo, salvo el carácter nulo.
def ibwt(r):
"""Aplica la transformación inversa de Burrows–Wheeler."""
table = [""] * len(r) # Crea una tabla vacía
for i in range(len(r)):
table = sorted(r[i] + table[i] for i in range(len(r))) # Añade una columna de r
s = [row for row in table if row.endswith("\0")][0] # Encuentra la fila correcta (acabada en "\0")
return s.rstrip("\0") # Deshacerse del carácter nulo
Remove ads
La llegada de técnicas de secuenciación de alto rendimiento (HTS, del inglés High-Throughput Sequencing) en la década del 2000 lleva a otra aplicación de la transformación de Burrows–Wheeler. En la HTS, se fragmenta el ADN en pequeñas piezas, de las cuales las primeras bases son secuenciadas, arrojando millones de "lecturas", de una longitud de 30 a 500 pares de bases ("caracteres del ADN"). En numerosos experimentos, e.g., en la ChIP-Seq, la tarea es alinear estas lecturas a un genoma de referencia, i.e., a la secuencia conocida y casi completa del organismo en cuestión (el cual puede tener una longitud de varios miles de millones de pares). Se publicaron numerosos programas de alineamiento especializados en esta tarea, que inicialmente confiaban en el hashing (e.g., SOAP,[3] o Maq[4]). En un esfuerzo por reducir las necesidades de memoria para el alineamiento de secuencias, se desarrollaron muchos programas de alineamiento (Bowtie,[5] BWA,[6] and SOAP2[7]), que usan la transformación de Burrows–Wheeler para reducir la memoria necesaria para indizar el genoma humano.
Remove ads
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
Remove ads