A Burrows-Wheeler transzformáció , amelyet a BWT ( angolul : Burrows-Wheeler Transform ) rövidítéssel szokás emlegetni, az adattömörítés során használt előfeldolgozás . Michael Burrows és David Wheeler találta fel , 1994-ben jelent meg, Wheeler korábbi, 1983-as munkáját követően . Ez nem egy tömörítési algoritmus, mivel méretcsökkentést nem hajtanak végre. Ez az adatok átszervezésének módszere: megnő annak a valószínűsége, hogy az eredetileg egymástól távol eső karakterek egymás mellett kerülnek az eredménybe.
A technika az alapja a bzip2 tömörítési algoritmusnak, amely jelenleg az egyik legjobb tömörítési arányt kínáló. Széles körben használják a genomikában is , például az új DNS (vagy RNS) szekvenálási technológiákból eredő rövid leolvasások összehangolási problémáira vagy szószámlálási problémákra (ismétlés detektálás).
Először is a kódolandó karakterláncot át kell másolni egy négyzet alakú tömbbe, a karakterláncot egy karakterrel jobbra tolva minden új sorhoz. Ezeket a sorokat ezután ábécé sorrendben soroljuk fel. Tudjuk, hogy a váltásnak köszönhetően minden sor minden utolsó betűje megelőzi ugyanazon sor első betűjét, kivéve az eredeti sort, amelynek helyzetét megjegyezzük. Ezenkívül, mivel a sorok betűrendbe vannak rendezve, az utolsó oszlopnak köszönhetően megtalálhatjuk a táblázat első oszlopát.
Vegyünk egy példát: tegyük fel, hogy a kódolni kívánt karakterlánc "TEXTUEL". Először elkészítjük az asztalt. Az első betűt itt piros színnel jelölik a táblázat olvasásának javítása érdekében.
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 TEzután betűrendbe osztályozzuk ezeket a húrokat:
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 7A kódolt szöveg ekkor az utolsó oszlopból áll, amelyet megelőz az eredeti szöveg helyzete, azaz: „4UTELXTE”. Az dekódoláshoz az eredeti szöveg helyzetét használják.
Burrows és Wheeler átalakulása nem eredményez tömörítést. Éppen ellenkezőleg, mivel a dekódoláshoz át kell adni az eredeti szöveg helyzetét.
Megfigyelhető azonban, hogy a viszonylag hosszú szövegek transzformációja sok egymásutános karakterismétlést tartalmaz, mivel sokszor tartalmazzák ugyanazokat a szavakat. Ennek oka, hogy a Burrows és a Wheeler transzformáció a karakterek betűrend szerinti rendezését jelenti, majd minden alkalommal, amikor az előző karaktert az eredeti szövegbe írja. Mivel forgatással konstruálják, az utolsó oszlop az előző karakterekből áll. Szembeötlő példa a "TEXTUELTEXTUEL" átalakulása, amely a következőt adja: "7UUTTEELLXXTTEE".
Ezért tömörítés céljából MTF típusú algoritmust használnak ezen a transzformáción. Az ismétlődő karakterek sok nullát eredményeznek. Ezt az eredményt kódoló Huffman nagy tömörítési sebességet biztosít.
A dekódolás abból áll, hogy rekonstruálja a teljes táblázatot az utolsó oszlopából (kódolt szöveg: "UTELXTE"), amelyből a "következő" oszlopot rekonstruálják, vagyis forgatással, az elsőt, amelyből tudjuk, hogy ábécé sorrendben van. ("EELTTUX"). Ezután beillesztjük az utolsó oszlopot közvetlenül az első oszlop elé, majd ábécé sorrendbe osztályozzuk az első két oszlop felépítéséhez kapott betűpárokat. Ezt a műveletet addig ismételjük, amíg a teljes tábla meg nem alakul, amelyben megtaláljuk az eredeti szöveget a sorszáma alapján:
| Megindítás, inicializálás | Válogató | Kollázs | Válogató | Kollázs | Válogató |
|---|---|---|---|---|---|
| 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 |
| Kollázs | Válogató | Kollázs | Válogató | Kollázs | Válogató |
| 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 |
| Kollázs | Válogató | Kiválasztás | |||
| UELTEXT TEXTUEL ELTEXTU LTEXTUE XTUELTE TUELTEX EXTUELT | ELTEXTU EXTUELT LTEXTUE TEXTUEL TUELTEX UELTEXT XTUELTE | 1 2 3 ← 4 5 6 7 |
Az eredeti szöveget azon a soron találjuk, amelynek számát a kódolt szöveggel továbbítottuk.
Mivel az átalakított karakterlánc az előző karakterekből áll ábécé sorrendben. A dekódolás megértésének másik módja abc-sorrendbe állítás és a transzformált karaktersorozatban a következő felvétele.
stb.