De Burrows-Wheeler transform , ofte referert til ved forkortelsen BWT (for engelsk : Burrows-Wheeler Transform ) er et forbehandlingstrinn som brukes i datakomprimering . Oppfunnet av Michael Burrows og David Wheeler , ble den utgitt i 1994, etter Wheelers tidligere arbeid i 1983 . Dette er ikke en komprimeringsalgoritme, da det ikke utføres noen størrelsesreduksjon. Dette er en metode for omorganisering av data: sannsynligheten for at identiske tegn som i utgangspunktet er fjernt fra hverandre, havner side om side i resultatet, økes.
Teknikken er grunnlaget for bzip2 komprimering algoritmen som er i dag en av de som tilbyr en av de beste komprimering priser. Det er også mye brukt i genomikk , for eksempel for justeringsproblemer ved korte avlesninger som følge av nye DNA (eller RNA) sekvenseringsteknologier eller for ordtellingsproblemer (repetisjon påvisning).
Først må tegnstrengen som skal kodes kopieres til en firkantet matrise ved å flytte strengen ett tegn til høyre for hver nye linje. Disse linjene blir deretter oppført i alfabetisk rekkefølge. Vi vet at takket være skiftet, går hver siste bokstav på hver linje foran den første bokstaven i samme linje, bortsett fra den originale linjen hvis posisjon vi vil merke. I tillegg, da radene er ordnet i alfabetisk rekkefølge, kan vi finne den første kolonnen i tabellen takket være den siste kolonnen.
La oss ta et eksempel: anta at strengen som skal kodes er "TEXTUEL". Vi lager først bordet. Den første bokstaven er merket med rødt for å gjøre tabellen lettere å lese.
Chaîne T E X T U E L L T E X T U E E L T E X T U U E L T E X T T U E L T E X X T U E L T E E X T U E L TDeretter klassifiserer vi disse strengene i alfabetisk rekkefølge:
Chaîne Position E L T E X T U 1 E X T U E L T 2 L T E X T U E 3 T E X T U E L 4 ← position du texte original T U E L T E X 5 U E L T E X T 6 X T U E L T E 7Den kodede teksten består da av den siste kolonnen som ble innledet av plasseringen av originalteksten, dvs.: “4UTELXTE”. Plasseringen til originalteksten brukes til dekoding.
Transformasjonen av Burrows and Wheeler gir ingen gevinst i komprimering. Tvert imot, siden det er nødvendig å overføre posisjonen til originalteksten for avkoding.
Imidlertid observeres det at transformasjonen av relativt lange tekster har mange sammenhengende gjentakelser av tegn fordi de inneholder et høyt antall ganger de samme ordene. Dette er fordi Burrows and Wheeler-transformasjonen tilsvarer å sortere tegnene alfabetisk, og hver gang du skriver forrige tegn i originalteksten. Siden den er konstruert ved rotasjon, består den siste kolonnen av de foregående tegnene. Et skarpt eksempel er transformasjonen av "TEXTUELTEXTUEL" som gir: "7UUTTEELLXXTTEE".
Derfor, for kompresjonsformål, brukes en MTF- type algoritme på denne transformasjonen. Gjentatte tegn vil gi mange nuller. En Huffman som koder for dette resultatet gir høy kompresjonshastighet.
Avkodingen består i å rekonstruere hele tabellen fra den siste kolonnen (kodet tekst "UTELXTE") hvorfra den "neste" kolonnen rekonstrueres, det vil si ved rotasjon, den første, som vi vet at den er i alfabetisk rekkefølge ("EELTTUX"). Deretter limer vi inn den siste kolonnen like før denne første kolonnen, og deretter klassifiserer vi i alfabetisk rekkefølge bokstavparene som er oppnådd for å bygge de to første kolonnene. Denne operasjonen gjentas deretter til hele tabellen er dannet der vi finner originalteksten gitt av radnummeret:
| Innvielse | Sortering | Collage | Sortering | Collage | Sortering |
|---|---|---|---|---|---|
| U T E L X T E | E E L T T U X | UE TE EL LT XT TU EX | EL EX LT TE TU UE XT | UEL TEX ELT LTE XTU TUE EXT | ELT EXT LTE TEX TUE UEL XTU |
| Collage | Sortering | Collage | Sortering | Collage | Sortering |
| UELT TEXT ELTE LTEX XTUE TUEL EXTU | ELTE EXTU LTEX TEXT TUEL UELT XTUE | UELTE TEXTU ELTEX LTEXT XTUEL TUELT EXTUE | ELTEX EXTUE LTEXT TEXTU TUELT UELTE XTUEL | UELTEX TEXTUE ELTEXT LTEXTU XTUELT TUELTE EXTUEL | ELTEXT EXTUEL LTEXTU TEXTUE TUELTE UELTEX XTUELT |
| Collage | Sortering | Utvalg | |||
| UELTEXT TEXTUEL ELTEXTU LTEXTUE XTUELTE TUELTEX EXTUELT | ELTEXTU EXTUELT LTEXTUE TEXTUEL TUELTEX UELTEXT XTUELTE | 1 2 3 ← 4 5 6 7 |
Vi finner originalteksten på linjen hvis nummer ble overført med kodet tekst.
Siden den transformerte strengen består av de foregående tegnene i alfabetisk rekkefølge. En annen måte å forstå denne dekodingen består i å sortere i alfabetisk rekkefølge og hver gang ta den neste i den transformerte strengen.
etc.