Burrows Wheeler Transform (BWT) es una técnica de transformación de cadena reversible, generalmente utilizada como un paso previo para varias técnicas de compresión, incluido el popular ‘bzip2’.
Lo que lo hace útil:
1) Después de aplicar BWT a una cadena, la cadena transformada tiende a tener caracteres repetitivos que aparecen muy juntos, haciendo que la cadena sea más fácil de comprimir.
2) No agrega datos adicionales, solo da una permutación de la cadena original
3) Por encima de dos cosas se puede lograr perfectamente incluso clasificando la cuerda (Ej .: ‘chaitanya’ se puede transformar en ‘aaachinty’), pero la verdadera fuerza de BWT radica en el hecho de que es reversible. Al ordenar, es posible que todos los caracteres repetitivos aparezcan juntos, pero no puede recuperar sus datos a menos que tenga información adicional sobre la cadena original.
¿Cómo se calcula?
Explicaré cómo se calcula BWT tomando un ejemplo.
Apliquemos BWT a la cadena ‘chaitanya’
- ¿Hay algún número que el binario no pueda producir?
- ¿Debo aprender a clasificar?
- ¿Cómo se almacenan las imágenes en Ram como una matriz bidimensional de bytes que representan un píxel?
- ¿Cuál es la diferencia básica entre loop y recursividad en C?
- ¿Por qué los algoritmos tienen tanta importancia en la programación?
Paso 1:
Agregue un carácter final único a su cadena,
digamos ‘$’.
Paso 2:
Encuentra todos los sufijos cíclicos de tu cadena.
chaitanya $
$ chaitanya
una $ chaitania
ya $ chaitan
nya $ chaita
anya $ chait
tanya $ chai
itanya $ cha
aitanya $ ch
haitanya $ c
Paso 3:
Ordenar las cadenas obtenidas
una $ chaitania
aitanya $ ch
anya $ chait
chaitanya $
haitanya $ c
itanya $ cha
nya $ chaita
tanya $ chai
ya $ chaitan
$ chaitanya
Esto se puede considerar como una tabla de caracteres, y generalmente se conoce como la ‘tabla BWT’
Tenga en cuenta que cada columna tiene todos los caracteres de la cadena original (eso es porque tomamos sufijos cíclicos)
Etapa 4:
Identificar el último carácter de cada cadena.
a $ chaitan y
aitanya $ c h
anya $ chai t
chaitanya $
haitanya $ c
itanya $ ch a
nya $ chait a
tanya $ cha i
ya $ chaita n
$ chaitany a
es decir, ‘yht $ caaina’
Así que esta será nuestra cadena BWT’d: ‘yht $ caaina’ (Observe cómo las a están juntas)
Okay. así que encontramos el BWT de una cadena, ahora veamos cómo podemos recuperar nuestros datos de la cadena transformada, haciendo un BWT inverso.
Cálculo de BWT inverso:
Idea: si pudiéramos reconstruir la tabla BWT, dado que sabemos que nuestra cadena original tiene ‘$’ como el carácter final, podemos tomar la cadena que termina con un ‘$’ para recuperar el texto original.
¿Cómo podemos reconstruir la tabla BWT?
Para la columna 1:
Como las filas están ordenadas, la primera columna solo será la cadena ordenada de la transformación
una
una
una
do
h
yo
norte
t
y
PS
Para la columna 2:
1) Agregue la cadena transformada como una nueva columna en el lado izquierdo
ya
decir ah
ejército de reserva
$ c
ch
ai
un
eso
Nueva York
a $
2) Ordenar las filas resultantes
a $
ai
un
ch
decir ah
eso
Nueva York
ejército de reserva
ya
$ c
La razón por la que hicimos estos dos pasos es que
El paso 1 nos da todas las combinaciones consecutivas en nuestra cadena original, que son todas subcadenas cíclicas de 2 longitudes
El paso 2 es básicamente ordenar estas cadenas, ese es el método real en el que obtuvimos nuestra tabla BWT
Para todas las demás columnas, mediante una lógica similar podemos reconstruir la tabla
1) Agregue la cadena transformada como una nueva columna en el lado izquierdo
2) Ordenar las filas resultantes
Y finalmente llegamos
una $ chaitania
aitanya $ ch
anya $ chait
chaitanya $
haitanya $ c
itanya $ cha
nya $ chaita
tanya $ chai
ya $ chaitan
$ chaitanya
de donde tomamos la fila que termina con un ‘$’ y eliminamos el ‘$’
Por lo tanto, recuperamos nuestra cadena original: ‘chaitanya’ 🙂
Si estaba buscando implementar esto realmente:
Puede mirar el código en la página de Wikipedia: Burrows – Wheeler transform
También lo implementé durante mi segundo año de BTech para mi curso de algoritmos: https://github.com/chaitan94/kni…
Ambos códigos están en python.
Pero estos dos ejemplos utilizan el método ingenuo de calcular el BWT. Si realmente lo estuviera implementando, le sugiero que mire las implementaciones optimizadas de memoria del algoritmo. Hay varios artículos publicados sobre este tema. La razón por la que desea una versión optimizada de memoria es simple: como ha visto, la tabla BWT es del tamaño O (n ^ 2) donde n es la longitud de su cadena, por lo que si desea BWT un archivo de texto de 32 KB, su memoria ¡el uso podría subir hasta (32K * 32KB) = 1 GB!
