Transformación de Burrows-Wheeler

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 suele 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 "gratuito" método para mejorar la eficiencia de los algoritmos de compresión de texto, que cuesta solo algunos cálculos adicionales. La transformada de Burrows-Wheeler es un algoritmo que se 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.

Descripción

Cuando el BWT transforma una cadena de caracteres, la transformación cambia 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.

Por ejemplo:

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, .., II, y III, que juntos forman 13 de los 44 caracteres.

Ejemplo

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 S = ^BANANA| (paso 1 en la tabla a continuación), gírela N< /i> veces (paso 2), donde N = 8 es la longitud de la cadena S considerando también el símbolo ^ que representa el inicio de la cadena y el carácter rojo | que representa el 'EOF' puntero; estas rotaciones, o desplazamientos circulares, se clasifican lexicográficamente (paso 3). El resultado de la fase de codificación es la última columna L = BNN^AA|A después del paso 3, y el índice (basado en 0) I de la fila que contiene la cadena original S, en este caso I = 6.

^BANANASilencio

^BANANASilencioSilencio^BANANA
ASilencio^BANAN
NASilencio^BANA
ANASilencio^BAN
NANASilencio^BA
ANANASilencio^ B
BANANASilencio^

ANANASilencio^ B
ANASilencio^BAN
ASilencio^BANAN
BANANASilencio^
NANASilencio^BA
NASilencio^BANA
^BANANASilencioSilencio^BANANA

ANANASilencio^BANASilencio^BANASilencio^BANANBANANASilencio^NANASilencio^ BANASilencio^BANA^BANANASilencioSilencio^BANANA

BNN^AASilencioA

El siguiente pseudocódigo brinda una forma simple (aunque ineficiente) de calcular el BWT y su inversa. Asume que la cadena de entrada s contiene un carácter especial 'EOF' que es el último carácter y no aparece en ningún otro lugar del texto.

función BWT (BWT)cuerda s)
crear una tabla, donde las filas son todas posibles rotaciones de s
filas ordenadas alfabéticamente
 retorno (última columna de la tabla)

función inverseBWT ()cuerda s)
crear mesa vacía
 repetición longitud(s) veces// primera inserción crea primera columna
insertar s como columna de tabla antes de la primera columna de la tabla
filas de la tabla alfabéticamente
 retorno (ya que termina con el personaje de 'EOF')

Explicación

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 comenzando con "he " juntos, 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ía una cantidad de "t" caracteres junto con las excepciones quizás menos comunes (como si contiene "ache ") mezclados. Por lo tanto, se puede ver que el éxito de esta transformación depende de que un valor tenga una alta probabilidad de ocurrir antes 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 codificada más fácilmente (una ordenación normal lo haría), sino que lo hace de forma reversible, lo que permite que se vuelva a generar el documento original. de los datos de la última columna.

Lo contrario se puede entender de esta manera. Tome la tabla final en el algoritmo BWT y borre todo menos la última columna. Con solo esta información, puede reconstruir fácilmente la primera columna. La última columna le indica todos los caracteres del texto, así que ordene estos caracteres alfabéticamente para obtener la primera columna. Luego, la última y la primera columna (de cada fila) juntas le dan todos los pares de caracteres sucesivos en el documento, donde los pares se toman cíclicamente para que el último y el primer carácter formen un par. Al ordenar la lista de pares, se obtiene la primera y la segunda columnas. Continuando de esta manera, puede reconstruir la lista completa. Luego, la fila con el "fin de archivo" carácter al final es el texto original. La inversión del ejemplo anterior se hace así:

BNN^AASilencioA

B
N
N
^
A
A
SilencioA

A
A
A
B
N
N
^
Silencio

BA
NA
NA
^ B
ANTES
ANTES
Silencio^
ASilencio

ANTES
ANTES
ASilencioBA
NA
NA
^ B
Silencio^

BAN
NAN
NASilencio^BA
ANA
ANA
Silencio^ B
ASilencio^

ANA
ANA
ASilencio^
BAN
NAN
NASilencio^BA
Silencio^ B

BANA
NANA
NASilencio^
^BAN
ANAN
ANASilencioSilencio^BA
ASilencio^ B

ANAN
ANASilencioASilencio^ B
BANA
NANA
NASilencio^
^BAN
Silencio^BA

BANAN
NANASilencioNASilencio^ B
^BANA
ANANA
ANASilencio^
Silencio^BAN
ASilencio^BA

ANANA
ANASilencio^
ASilencio^BA
BANAN
NANASilencioNASilencio^ B
^BANA
Silencio^BAN

BANANA
NANASilencio^
NASilencio^BA
^BANAN
ANANASilencioANASilencio^ B
Silencio^BANA
ASilencio^BAN

ANANASilencioANASilencio^ B
ASilencio^BAN
BANANA
NANASilencio^
NASilencio^BA
^BANAN
Silencio^BANA

BANANASilencioNANASilencio^ B
NASilencio^BAN
^BANANA
ANANASilencio^
ANASilencio^BA
Silencio^BANAN
ASilencio^BANA

ANANASilencio^
ANASilencio^BA
ASilencio^BANA
BANANASilencioNANASilencio^ B
NASilencio^BAN
^BANANA
Silencio^BANAN

BANANASilencio^
NANASilencio^BA
NASilencio^BANA
^BANANASilencioANANASilencio^ B
ANASilencio^BAN
Silencio^BANANA
ASilencio^BANAN

ANANASilencio^ B
ANASilencio^BAN
ASilencio^BANAN
BANANASilencio^
NANASilencio^BA
NASilencio^BANA
^BANANASilencioSilencio^BANANA

^BANANASilencio

Optimización

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 solo puntero en las cadenas y la ordenación se realiza mediante los índices. En el decodificador, tampoco hay necesidad de almacenar la tabla y, de hecho, no se necesita ordenar en absoluto. En un tiempo proporcional al tamaño del alfabeto y la longitud de la cadena, la cadena decodificada puede generarse un carácter a la vez de derecha a izquierda. Un "personaje" en el algoritmo puede ser un byte, un bit o cualquier otro tamaño conveniente.

También se puede hacer la observación de 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 memoria y tiempo lineal. El BWT se puede definir con respecto a la matriz de sufijos SA del texto T como (indexación basada en 1):

${displaystyle BWT[i]={begin{cases}T[SA[i]-1], limitada{text{if }SA[i] confianza0\\$, ventaja{otherwise}end{cases}}}}$

No es necesario tener un 'EOF' personaje. En su lugar, se puede usar un puntero que recuerda en qué parte de una cadena se encuentra el 'EOF' sería si existiera. En este enfoque, la salida del BWT debe incluir tanto la cadena transformada como el valor final del puntero. La transformación inversa luego lo reduce al tamaño original: se le da una cadena y un puntero, y devuelve solo una cadena.

Puede encontrar una descripción completa de los algoritmos en el artículo de Burrows y Wheeler, o en varias fuentes en línea. Los algoritmos varían un poco según si se usa EOF y en qué dirección se realizó la clasificación. De hecho, la formulación original no usaba un marcador EOF.

Variante biyectiva

Dado que cualquier rotación de la cadena de entrada conducirá a la misma cadena transformada, el 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 incómodos.

Existe una versión biyectiva de la transformación, en la que la cadena transformada identifica de forma única al original, y las dos tienen la misma longitud y contienen exactamente los mismos caracteres, solo que en un orden diferente.

La transformada biyectiva se calcula factorizando la entrada en una secuencia no creciente de palabras de Lyndon; tal factorización existe y es única por el teorema de Chen-Fox-Lyndon, y se puede encontrar en tiempo lineal. 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. Luego, la cadena transformada se obtiene eligiendo el carácter final de cada cadena en esta lista ordenada. La única advertencia importante aquí es que las cadenas de diferentes longitudes no se ordenan de la manera habitual; las dos cadenas se repiten para siempre y las repeticiones infinitas se ordenan. Por ejemplo, "ORO" precede a "O" porque "OROORO..." precede a "OROROR...".

Por ejemplo, el texto "^BANANA|" se transforma en "ANNBAA^|" a través de 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 elimina durante la transformación y se vuelve a agregar a su lugar adecuado en el archivo.

La cadena se divide en palabras Lyndon, por lo que las palabras de la secuencia disminuyen utilizando el método de comparación anterior. (Tenga en cuenta que estamos clasificando '^' como sucesores de otros caracteres). "^BANANA" se convierte en (^) (B) (AN) (AN) (A).

^BANANASilencio

^^^^^^^^^^
BBBBBBBBBB... (B)
ANANANAN...
NANANANA...
ANANANAN...
NANANANA...
AAAAAAAA... (A)

AAAAAAAA... (A)
ANANANANAN...
ANANANANAN...
BBBBBBBBBB... (B)
NANANANA...
NANANANA...
^^^^^^^^^^

AAAAAAAA... ()A)
ANANANANAN... (AN)
ANANANANAN... (AN)
BBBBBBBB... ()B)
NANANANA... (NA)
NANANANA... (NA)
^^^^^^^^^ ()^)

ANNBAA^Silencio

ANNBAA^

A
N
N
B
A
A
^

A
A
A
B
N
N
^

AA
NA
NA
BB
ANTES
ANTES
^

AA
ANTES
ANTES
BB
NA
NA
^

AAA
NAN
NAN
BBB
ANA
ANA
^^^

AAA
ANA
ANA
BBB
NAN
NAN
^^^

AAAA
NANA
NANA
BBB
ANAN
ANAN
^^^^

AAAA
ANAN
ANAN
BBB
NANA
NANA
^^^^

^BANANA

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 distintas de Lyndon: (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 clasifican en orden inverso: (^), (B), (AN), (AN), (A). Luego se concatenan para obtener

^BANANA

La transformada de Burrows-Wheeler puede verse como un caso especial de esta transformada biyectiva; en lugar de la introducción tradicional de una nueva letra de fuera de nuestro alfabeto para indicar el final de la cadena, podemos introducir una nueva letra que compare como anterior a todas las letras existentes que se coloca al principio de la cadena. Toda la cadena es ahora una palabra de Lyndon y, al ejecutarla a través del proceso biyectivo, se obtendrá un resultado transformado que, cuando se invierte, devuelve la palabra de Lyndon, sin necesidad de volver a ensamblarla al final.

Relativamente, el texto transformado solo diferirá del resultado de BWT en un carácter por palabra de Lyndon; por ejemplo, si la entrada se descompone en seis palabras Lyndon, la salida solo diferirá en seis caracteres. Por ejemplo, aplicando la transformada biyectiva se obtiene:

La transformada biyectiva incluye ocho ejecuciones de idénticos caracteres. Estas ejecuciones son, en orden: XX, II, XX, PP, .., EE, .., y IIII.

En total, se utilizan 18 caracteres en estas ejecuciones.

Transformación dinámica de Burrows–Wheeler

Cuando se edita un texto, su transformación Burrows–Wheeler cambiará. Salson et al. 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 original de Burrows-Wheeler, que puede ser más rápido que construir la transformación de Burrows-Wheeler del texto editado directamente.

Implementación de muestra

Esta implementación de Python sacrifica la velocidad por la simplicidad: el programa es corto, pero toma más tiempo que el lineal que se desearía en una implementación práctica. Esencialmente hace lo que hace la sección de pseudocódigo.

Usando los códigos de control STX/ETX para marcar el inicio y el final del texto, y usando s[i:] + s[:i] para construir la iésima rotación de s, la transformación directa toma el último carácter de cada una de las filas ordenadas:

def Bwt()s: str) - str: ""Apply Burrows –Wheeler se transforma en cadena de entrada."" afirmación "

Contenido relacionado