Prerrequisito: Burrows – Algoritmo de transformación de datos de Wheeler
¿Por qué inversa de BWT? La idea principal detrás de esto:
1. Lo notable del algoritmo BWT es que esta transformación en particular es invertible con una sobrecarga de datos mínima.
2. Calcular el inverso de BWT es deshacer el BWT y recuperar la string original. El método ingenuo de implementar este algoritmo se puede estudiar desde aquí . El enfoque ingenuo requiere mucha velocidad y memoria y requiere que almacenemos |texto| rotaciones cíclicas de la string |texto|.
3. Analicemos un algoritmo más rápido en el que solo tenemos dos cosas:
- bwt_arr[] que es la última columna de la lista de rotaciones ordenadas dada como “annb$aa” .
- ‘x’, que es el índice de fila en el que aparece nuestra string original «banana$» en la lista de rotaciones ordenadas. Podemos ver que ‘x’ es 4 en el siguiente ejemplo.
Row Index Original Rotations Sorted Rotations
~~~~~~~~~ ~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~
0 banana$ $banana
1 anana$b a$banan
2 nana$ba ana$ban
3 ana$ban anana$b
*4 na$bana banana$
5 a$banan na$bana
6 $banana nana$ba
4. Una observación importante: si la j-ésima rotación original (que es la rotación original desplazada j caracteres a la izquierda) es la i-ésima fila en el orden ordenado, entonces l_shift[i] registra en el orden ordenado donde (j+1)st original aparece la rotación. Por ejemplo, la rotación original 0 «banana$» es la fila 4 del orden ordenado, y dado que l_shift[4] es 3, la siguiente rotación original «anana$b» es la fila 3 del orden ordenado.
Row Index Original Rotations Sorted Rotations l_shift ~~~~~~~~~ ~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~~ ~~~~~~~ 0 banana$ $banana 4 1 anana$b a$banan 0 2 nana$ba ana$ban 5 3 ana$ban anana$b 6 *4 na$bana banana$ 3 5 a$banan na$bana 1 6 $banana nana$ba 2
5. Nuestro trabajo es deducir l_shift[] de la información disponible que es bwt_arr[] y ‘x’ y con su ayuda calcular el inverso de BWT. ¿Cómo calcular l_shift[] ? 1. Sabemos BWT que es «annb$aa» . Esto implica que conocemos todos los caracteres de nuestra string original, aunque estén permutados en el orden incorrecto. 2. Al ordenar bwt_arr[] , podemos reconstruir la primera columna de la lista de rotaciones ordenadas y la llamamos sorted_bwt[] .
Row Index Sorted Rotations bwt_arr l_shift
~~~~~~~~~ ~~~~~~~~~~~~~~~~~~~~~~~~~~ ~~~~~~~
0 $ ? ? ? ? ? a 4
1 a ? ? ? ? ? n
2 a ? ? ? ? ? n
3 a ? ? ? ? ? b
*4 b ? ? ? ? ? $ 3
5 n ? ? ? ? ? a
6 n ? ? ? ? ? a
3. Dado que ‘$’ aparece solo una vez en la string ‘sorted_bwt[]’ y las rotaciones se forman mediante el ajuste cíclico, podemos deducir que l_shift[0] = 4. De manera similar, ‘b’ aparece una vez, por lo que podemos deducir que l_desplazamiento[4] = 3.
4. Pero, debido a que ‘n’ aparece dos veces, parece ambiguo si l_shift[5] = 1 y l_shift[6] = 2 o si l_shift[5] = 2 y l_shift[6] = 1.
5. La regla para resolver esta ambigüedad es que si las filas i y j comienzan con la misma letra e i<j, entonces l_shift[i] < l_shift[j] . Esto implica l_shift[5] = 1 y l_shift[6] =2. Continuando de manera similar, l_shift[] se calcula de la siguiente manera.
Row Index Sorted Rotations bwt_arr l_shift
~~~~~~~~~ ~~~~~~~~~~~~~~~~~~~~~~~~~~ ~~~~~~~
0 $ ? ? ? ? ? a 4
1 a ? ? ? ? ? n 0
2 a ? ? ? ? ? n 5
3 a ? ? ? ? ? b 6
*4 b ? ? ? ? ? $ 3
5 n ? ? ? ? ? a 1
6 n ? ? ? ? ? a 2
¿Por qué es válida la regla de resolución de ambigüedades?
- Las rotaciones se ordenan de tal manera que la fila 5 es lexicográficamente menor que la fila 6.
- Por lo tanto, los cinco caracteres desconocidos en la fila 5 deben ser menores que los cinco caracteres desconocidos en la fila 6 (ya que ambos comienzan con ‘n’ ).
- También sabemos que entre las dos filas que terminan en ‘n’ , la fila 1 es más baja que la fila 2.
- Pero, los cinco caracteres desconocidos en las filas 5 y 6 son precisamente los primeros cinco caracteres en las filas 1 y 2 o esto contradiría el hecho de que las rotaciones fueron ordenadas.
- Por lo tanto, l_shift[5] = 1 y l_shift[6] = 2.
Forma de implementación:
1. Ordenar BWT: Usando qsort() , organizamos los caracteres de bwt_arr[] en orden ordenado y los almacenamos en sorted_arr[] .
2. Calcule l_shift[]:
i. Tomamos una array de punteros struct node *arr[] , cada uno de los cuales apunta a una lista enlazada.
ii. Convirtiendo cada carácter distinto de bwt_arr[] en un Node principal de una lista vinculada, agregamos Nodes a la lista vinculada cuya parte de datos contiene el índice en el que aparece ese carácter en bwt_arr[] .
i *arr[128] Linked Lists ~~~~~~~~~ ~~~~~~~~~ ~~~~~~~~~~~~~~~~~~~~~~ 37 $ -----> 4 -> NULL 97 a -----> 0 -> 5 -> 6 -> NULL 110 n -----> 1 -> 2 -> NULL 98 b -----> 3 -> NULL
iii. Haciendo caracteres distintos de sorted_bwt[] encabezados de listas enlazadas, recorremos listas enlazadas y obtenemos los valores correspondientes de l_shift[] .
int[] l_shift = { 4, 0, 5, 6, 3, 1, 2 };
3. Iterando la longitud de la string, decodificamos BWT con x = l_shift[x] y generamos bwt_arr[x].
x = l_shift[4]
x = 3
bwt_arr[3] = 'b'
x = l_shift[3]
x = 6
bwt_arr[6] = 'a'
Ejemplos:
Input : annb$aa // Burrows - Wheeler Transform
4 // Row index at which original message
// appears in sorted rotations list
Output : banana$
Input : ard$rcaaaabb
3
Output : abracadabra$
El siguiente es el código C para la forma de implementación explicada anteriormente:
C
// C program to find inverse of Burrows
// Wheeler transform
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// Structure to store info of a node of
// linked list
struct node {
int data;
struct node* next;
};
// Compares the characters of bwt_arr[]
// and sorts them alphabetically
int cmpfunc(const void* a, const void* b)
{
const char* ia = (const char*)a;
const char* ib = (const char*)b;
return strcmp(ia, ib);
}
// Creates the new node
struct node* getNode(int i)
{
struct node* nn =
(struct node*)malloc(sizeof(struct node));
nn->data = i;
nn->next = NULL;
return nn;
}
// Does insertion at end in the linked list
void addAtLast(struct node** head, struct node* nn)
{
if (*head == NULL) {
*head = nn;
return;
}
struct node* temp = *head;
while (temp->next != NULL)
temp = temp->next;
temp->next = nn;
}
// Computes l_shift[]
void* computeLShift(struct node** head, int index,
int* l_shift)
{
l_shift[index] = (*head)->data;
(*head) = (*head)->next;
}
void invert(char bwt_arr[])
{
int i,len_bwt = strlen(bwt_arr);
char* sorted_bwt = (char*)malloc(len_bwt * sizeof(char));
strcpy(sorted_bwt, bwt_arr);
int* l_shift = (int*)malloc(len_bwt * sizeof(int));
// Index at which original string appears
// in the sorted rotations list
int x = 4;
// Sorts the characters of bwt_arr[] alphabetically
qsort(sorted_bwt, len_bwt, sizeof(char), cmpfunc);
// Array of pointers that act as head nodes
// to linked lists created to compute l_shift[]
struct node* arr[128] = { NULL };
// Takes each distinct character of bwt_arr[] as head
// of a linked list and appends to it the new node
// whose data part contains index at which
// character occurs in bwt_arr[]
for (i = 0; i < len_bwt; i++) {
struct node* nn = getNode(i);
addAtLast(&arr[bwt_arr[i]], nn);
}
// Takes each distinct character of sorted_arr[] as head
// of a linked list and finds l_shift[]
for (i = 0; i < len_bwt; i++)
computeLShift(&arr[sorted_bwt[i]], i, l_shift);
printf("Burrows - Wheeler Transform: %s\n", bwt_arr);
printf("Inverse of Burrows - Wheeler Transform: ");
// Decodes the bwt
for (i = 0; i < len_bwt; i++) {
x = l_shift[x];
printf("%c", bwt_arr[x]);
}
}
// Driver program to test functions above
int main()
{
char bwt_arr[] = "annb$aa";
invert(bwt_arr);
return 0;
}
Burrows - Wheeler Transform: annb$aa Inverse of Burrows - Wheeler Transform: banana$
Complejidad de tiempo: O(nLogn) ya que qsort() toma tiempo O(nLogn).
Ejercicio: Implementar el inverso de Inverse of Burrows – Wheeler Transform en tiempo O(n).
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.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA