Compresión de Burrows-Wheeler
algoritmo usado en técnicas de compresión de datos / De Wikipedia, la enciclopedia encyclopedia
Estimado Wikiwand AI, Seamos breves simplemente respondiendo estas preguntas clave:
¿Puede enumerar los principales datos y estadísticas sobre Compresión de Burrows-Wheeler?
Resumir este artículo para un niño de 10 años
La transformación de Burrows–Wheeler (BWT del inglés Burrows–Wheeler transform, también conocida como compresión por ordenación de bloques), es un algoritmo usado en técnicas de compresión de datos como en bzip2. Fue inventado por Michael Burrows y David Wheeler en 1994 mientras trabajaban en el DEC Systems Research Center en Palo Alto, California.[1] Se basa en una transformación previamente descubierta por Wheeler que no se encuentra publicada.
Cuando se transforma una cadena de caracteres mediante la BWT, ninguno de sus caracteres cambia de valor. La transformación permuta el orden de los caracteres. Si la cadena original contiene muchas subcadenas que aparecen a menudo, entonces la cadena transformada contendrá múltiples posiciones en las que un mismo carácter esté repetido varias veces en una fila. Esto es útil para la compresión, ya que tiende a ser fácil comprimir una cadena que contiene secuencias de caracteres repetidos con técnicas como move-to-front transform y run-length encoding.
Por ejemplo:
Entrada | SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES |
---|---|
Salida | TEXYDST.E.IXIXIXXSSMPPS.B..E.S.EUSFXDIIOIIIT |
La salida es más fácil de comprimir ya que tiene muchos caracteres repetidos. De hecho, en la cadena transformada, aparece un total de seis secuencias de caracteres idénticos:
XX, SS, PP, .., II, y III, que juntos representan 13 de los 44 caracteres.