BWT
BWT es la abreviatura de la transformada de Burrows-Wheeler, que reescribe el texto en una forma donde los caracteres similares se agrupan, y es la primera etapa de bzip2.
Propósito
Es un paso de preprocesamiento reversible que mejora la compresión posterior, agrupando caracteres idénticos para que RLE y la codificación entrópica funcionen mejor.
Mecanismo
Se construye la matriz ordenada de todas las rotaciones cíclicas, se toma la última columna y se registra el número de la fila original. La transformada inversa recupera el texto original desde la última columna y el número de fila mediante el mapeo LF.
Casos de uso
- Compresión bzip2
- Alineamiento genómico
- Indexación de texto completo