Compressió de Burrows-Wheeler

La transformació de Burrows–Wheeler (BWT de l'anglés Burrows–Wheeler transform, també coneguda com a compressió per ordenació de blocs), és un algoritme usat en tècniques de compressió de senyes com en bzip2. Va ser inventat per Michael Burrows i David Wheeler en 1994 mentres treballaven en el DEC Systems Research Center en Pal Alt, Califòrnia. Es basa en una transformació prèviament descoberta per Wheeler que no es troba publicada.

Quan es transforma una cadena de caràcters per mig de la BWT, cap dels seus caràcters canvia de valor. La transformació permuta l'orde dels caràcters. Si la cadena original conté moltes subcadena que apareixen a sovint, llavors la cadena transformada contindrà múltiples posicions en les que un mateix caràcter estiga repetit vàries voltes en una fila. Açò és útil per a la compressió, ya que tendix a ser fàcil comprimir una cadena que conté seqüències de caràcters repetits en tècniques com move-to-front transform i run-length encoding.

Per eixemple:

Entrada	SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES
Eixida	TEXYDST.E.IXIXIXXSSMPPS.B..E.S.EUSFXDIIOIIIT

L'eixida és més fàcil de comprimir ya que té molts caràcters repetits. De fet, en la cadena transformada, apareix un total de sis seqüències de caràcters idèntics:

XX, SS, PP, .., II, i III, que junts representen 13 dels 44 caràcters.

Eixemple

La transformació es realisa ordenant totes les rotacions del text en orde lexicogràfic, i seleccionant l'última columna. Per eixemple, el text "^BANANA" es transforma en "BNN^AAA" a través d'estos passos (el símbol roig indica el 'EOF (final de ficher)'):

Transformació
Entrada	Totes les Rotacions	Ordenar Files	Eixida
^BANANA	^BANANA ^BANANA A^BANAN NA^BANA ANA^BAN NANA^BA ANANA^B BANANA^	ANANA^B ANA^BAN A^BANAN BANANA^ NANA^BA NA^BANA ^BANANA' ^BANANA	BNN^AAA |}. El següent pseudocódigo oferix una forma simple pero ineficiente de calcular el BWT i la seua inversa. S'assumix que la cadena d'entrada s conté un caràcter especial 'EOF' que serà l'últim caràcter, que solament apareix una volta en el text, i serà ignorat durant l'ordenació. function BWT (string s) crear una taula a on les files són totes les rotacions possibles de s ordenar les files alfabéticamente return (última columna de la taula) function invertirBWT (string s) crear una taula buida repeat length(s) claves Insertar s com una columna de la taula abans de la primera columna de la taula // la primera inserció crea la primera columna ordenar les files de la taula alfabéticamente return (la fila que acabe en el caràcter 'EOF') Per a entendre per qué es creen senyes més fàcils de comprimir, es pot considerar la transformació d'un text llarc en anglés que continga freqüentment la paraula "the". Ordenant les rotacions d'este text a sovint agruparà rotacions que escomencen per "he ", i l'últim caràcter d'eixa rotació (que també serà el caràcter anterior a "he ") normalment serà "t", per lo que el resultat de la transformació contindrà un número de caràcters "t" junt en algunes excepcions menys comunes (per eixemple, si continguera la cadena "Brahe "). Per lo tant, es pot vore que l'èxit d'esta transformació depén d'un únic valor en una provabilitat molt alta d'ocurrència abans d'una seqüència, per lo que en general necessita mostres molt llargues (d'a lo manco uns pocs kilobytes) de senyes apropiades (com a text). Lo més interessant sobre la BWT no és que genere una eixida més fàcil de codificar—una ordenació ordinària podria fer-ho igualment—sino que és un procés reversible, permetent re-generar el document original a partir de l'última columna de senyes. L'inversa pot entendre's de la següent manera. Es pren la taula final de l'algoritme BWT i s'eliminen totes les columnes llevat l'última. En esta informació, es pot reconstruir fàcilment la primera columna. L'última columna indica tots els caràcters del text, aixina que s'ordena, per a obtindre la primera columna. Llavors, la primera i l'última columna juntes indiquen tots els parells de caràcters successius en el document, a on els parells estan presos cíclicamente de manera que l'últim i el primer caràcter formen un parell. Ordenant la llista de parells s'obtindran la primera i la segona columna. Continuant d'esta manera, es pot reconstruir la llista sancera. Per últim, la fila en el caràcter "EOF" al final serà el text original. L'inversa de l'eixemple anterior es realisa com seguix: Transformació Inversa Entrada BNN^AAA |- Afegir 1 Ordenar 1 Afegir 2 Ordenar 2 B N N ^ A A A A A A B N N ^ BA NA NA ^B AN AN ^ A AN AN A BA NA NA ^B ^ Afegir 3 Ordenar 3 Afegir 4 Ordenar 4 BAN NAN NA ^BA ANA ANA ^B A^ ANA ANA A^ BAN NAN NA ^BA ^B BANA NANA NA^ ^BAN ANAN ANA ^BA A^B ANAN ANA A^B BANA NANA NA^ ^BAN ^BA Afegir 5 Ordenar 5 Afegir 6 Ordenar 6 BANAN NANA NA^B ^BANA ANANA ANA^ ^BAN A^BA ANANA ANA^ A^BA BANAN NANA NA^B ^BANA ^BAN BANANA NANA^ NA^BA ^BANAN ANANA ANA^B ^BANA A^BAN ANANA ANA^B A^BAN BANANA NANA^ NA^BA ^BANAN ^BANA Afegir 7 Ordenar 7 Afegir 8 Ordenar 8 BANANA NANA^B NA^BAN ^BANANA ANANA^ ANA^BA ^BANAN A^BANA ANANA^ ANA^BA A^BANA BANANA NANA^B NA^BAN ^BANANA ^BANAN BANANA^ NANA^BA NA^BANA ^BANANA ANANA^B ANA^BAN ^BANANA A^BANAN ANANA^B ANA^BAN A^BANAN BANANA^ NANA^BA NA^BANA ^BANANA ^BANANA Eixida ^BANANA Optimisació Es pot realisar una série d'optimisacions per a que estos algoritmes s'eixecuten de manera més eficient sense canviar l'eixida. En BWT, no hi ha necessitat de representar la taula ni en el codificador ni en el decodificador. En el codificador, cada fila de la taula pot ser representada per una única busca entre les cadenes, realisar l'ordenació per mig dels índexs. Es deu dur conte per a assegurar que l'ordenació no present un mal comportament en el pijor cas: les llibreries estàndar d'ordenació provablement no resulten adequades. En el decodificador, tampoc hi ha necessitat d'almagasenar la taula o realisar l'ordenació. En temps proporcional al tamany de l'alfabet i a la llongitut de la cadena, la cadena decodificada pot generar-se caràcter a caràcter de dreta a esquerra. Un "caràcter" en l'algoritme pot ser un byte, un bit o qualsevol atre tamany pertinent. No és necessari dispondre d'un caràcter 'EOF' real. A canvi, es pot usar una busca que recorde on deuria aparéixer el 'EOF' si existira. En esta aproximació, l'eixida del BWT deu incloure tant la cadena transformada com el valor de la busca final. Açò significa que el BWT expandix llaugerament la seua entrada. Per lo que la transformació inversa es reduïx al tamany original: es proporciona una cadena i una busca, i es torna solament una cadena. Es pot trobar una descripció completa dels algoritmes en el paper de Burrows i Wheeler o vàries fonts en llínea. Referències Referències