Burrows: algoritmo de transformación de datos de Wheeler

¿Qué es la Transformada de Burrows-Wheeler?

El BWT es un algoritmo de transformación de datos que reestructura los datos de tal manera que el mensaje transformado es más comprimible. Técnicamente, es una permutación reversible lexicográfica de los caracteres de una string. Es el primero de los tres pasos que se realizarán en sucesión mientras se implementa el algoritmo de compresión de datos de Burrows-Wheeler que forma la base de la utilidad de compresión bzip2 de Unix.

 ¿Por qué BWT? La idea principal detrás de esto. 

La aplicación más importante de BWT se encuentra en las ciencias biológicas, donde los genomas (strings largas escritas en alfabetos A, C, T, G) no tienen muchas corridas pero sí muchas repeticiones. La idea de BWT es construir una array cuyas filas sean todos cambios cíclicos de la string de entrada en el orden del diccionario y devolver la última columna de la array que tiende a tener largas series de caracteres idénticos. El beneficio de esto es que una vez que los caracteres se han agrupado, efectivamente tienen un orden, lo que puede hacer que nuestra string sea más comprimible para otros algoritmos como la codificación de longitud de ejecución y la codificación Huffman. Lo notable de BWT es que esta transformación en particular es reversible con una sobrecarga de datos mínima. 

Pasos involucrados en el algoritmo BWT 

Tomemos la palabra “banana$” como ejemplo.

• Paso 1: Forma todas las rotaciones cíclicas del texto dado.

                                     banana$ 
       $    b                        $banana 
    a           a                    a$banan
   Cyclic rotations    ---------->   na$bana
    n         n                      ana$ban 
          a                          nana$ba
                                     anana$b

• Paso 2: El siguiente paso es ordenar lexicográficamente las rotaciones. El signo ‘$’ se ve lexicográficamente como la primera letra, incluso antes de ‘a’ .

banana$                    $banana
$banana                    a$banan
a$banan       Sorting      ana$ban
na$bana      ---------->   anana$b 
ana$ban    alphabetically  banana$
nana$ba                    na$bana
anana$b                    nana$ba

• Paso 3: La última columna es lo que generamos como BWT.

BWT(banana$) = annb$aa

Ejemplos:

Entrada: texto = “banana$” Salida: Transformación Burrows-Wheeler = “annb$aa” Entrada: texto = “abracadabra$” Salida: Transformación Burrows-Wheeler = “ard$rcaaaabb”

¿Por qué la última columna se considera BWT?

1. La última columna tiene una mejor agrupación de símbolos que cualquier otra columna.
2. Si solo tenemos BWT de nuestra string, podemos recuperar el resto de las rotaciones cíclicas por completo. El resto de las columnas no poseen esta característica que es muy importante al calcular el inverso de BWT.

¿Por qué el signo ‘$’ está incrustado en el texto? Podemos calcular BWT incluso si nuestro texto no está concatenado con ningún carácter EOF ( ‘$’ aquí). La implicación del signo ‘$’ viene al calcular el inverso de BWT. Forma de implementación

1. Vamos a crear una instancia de «banana$» como nuestro texto de entrada y una array de caracteres bwt_arr para nuestra salida.
2. Obtengamos todos los sufijos de “banana$” y calculemos su sufijo_arr para almacenar el índice de cada sufijo.

0 banana$                6 $   
1 anana$                 5 a$
2 nana$      Sorting     3 ana$
3 ana$     ---------->   1 anana$
4 na$     alphabetically 0 banana$
5 a$                     4 na$
6 $                      2 nana$

1. Iterando sobre suffix_arr , agreguemos ahora a nuestra array de salida bwt_arr , el último carácter de cada rotación.
2. El último carácter de cada rotación de input_text que comienza en la posición indicada por el valor actual en la array de sufijos se puede calcular con input_text[(suffix_arr[i] – 1 + n ) % n] , donde n es el número de elementos en el sufijo_arr .

bwt_arr[0] 
  = input_text[(suffix_arr[0] - 1 + 7) % 7] 
  = input_text[5] 
  = a
bwt_arr[1] 
  = input_text[(suffix_arr[1] - 1 + 7) % 7] 
  = input_text[4] 
  = n

A continuación se muestra el código de la forma de implementación explicada anteriormente. 

// C program to find Burrows Wheeler transform
// of a given text
 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
// Structure to store data of a rotation
struct rotation {
    int index;
    char* suffix;
};
 
// Compares the rotations and
// sorts the rotations alphabetically
int cmpfunc(const void* x, const void* y)
{
    struct rotation* rx = (struct rotation*)x;
    struct rotation* ry = (struct rotation*)y;
    return strcmp(rx->suffix, ry->suffix);
}
 
// Takes text to be transformed and its length as
// arguments and returns the corresponding suffix array
int* computeSuffixArray(char* input_text, int len_text)
{
    // Array of structures to store rotations and
    // their indexes
    struct rotation suff[len_text];
 
    // Structure is needed to maintain old indexes of
    // rotations after sorting them
    for (int i = 0; i < len_text; i++) {
        suff[i].index = i;
        suff[i].suffix = (input_text + i);
    }
 
    // Sorts rotations using comparison
    // function defined above
    qsort(suff, len_text, sizeof(struct rotation),
        cmpfunc);
 
    // Stores the indexes of sorted rotations
    int* suffix_arr
        = (int*)malloc(len_text * sizeof(int));
    for (int i = 0; i < len_text; i++)
        suffix_arr[i] = suff[i].index;
 
    // Returns the computed suffix array
    return suffix_arr;
}
 
// Takes suffix array and its size
// as arguments and returns the
// Burrows - Wheeler Transform of given text
char* findLastChar(char* input_text,
                int* suffix_arr, int n)
{
    // Iterates over the suffix array to find
    // the last char of each cyclic rotation
    char* bwt_arr = (char*)malloc(n * sizeof(char));
    int i;
    for (i = 0; i < n; i++) {
        // Computes the last char which is given by
        // input_text[(suffix_arr[i] + n - 1) % n]
        int j = suffix_arr[i] - 1;
        if (j < 0)
            j = j + n;
 
        bwt_arr[i] = input_text[j];
    }
 
    bwt_arr[i] = '\0';
 
    // Returns the computed Burrows - Wheeler Transform
    return bwt_arr;
}
 
// Driver program to test functions above
int main()
{
    char input_text[] = "banana$";
    int len_text = strlen(input_text);
 
    // Computes the suffix array of our text
    int* suffix_arr
        = computeSuffixArray(input_text, len_text);
 
    // Adds to the output array the last char
    // of each rotation
    char* bwt_arr
        = findLastChar(input_text, suffix_arr, len_text);
 
    printf("Input text : %s\n", input_text);
    printf("Burrows - Wheeler Transform : %s\n",
        bwt_arr);
    return 0;
}

Input text : banana$
Burrows - Wheeler Transform : annb$aa

Complejidad de tiempo: O (Inicio de sesión). Esto se debe al método utilizado anteriormente para crear una array de sufijos que tieneuna complejidad de tiempo O(Logn), debido al tiempo O(n) para las comparaciones de strings en el algoritmo de clasificación O(nLogn). Ejercicio: 

1. Calcule la array de sufijos en tiempo O (nLogn) y luego implemente BWT.
2. Implementar la transformación inversa de Burrows-Wheeler.

Este artículo es una contribución de Anureet Kaur . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.