Para un tamaño de bloque N prefijado de antemano, el algoritmo de la transformada
BWT realiza los siguientes pasos:
- Leer la secuencia N de símbolos.
- Construir una matriz cuadrada de lado igual al tamaño del bloque N, donde
la primera fila es la secuencia original, la segunda es la secuencia desplazada
un símbolo a la izquierda de forma cíclica, etc.
- Ordenar lexicográficamente la matriz por filas. Este es el paso pesado de
algoritmo y se ejecuta en un tiempo proporcional a N × log 2(N).
- Buscar en la columna N - 1 (la de más a la derecha) la fila en la que se
encuentra el primer símbolo de la secuencia original. Sea este valor i.
- La transformada BWT de la secuencia de entrada está formada por el
contenido de la columna N - 1 (la última) y el índice i.