Üdvözlöm, Ön a
Burrows-Wheeler transform szó jelentését keresi. A DICTIOUS-ban nem csak a
Burrows-Wheeler transform szó összes szótári jelentését megtalálod, hanem megismerheted az etimológiáját, a jellemzőit és azt is, hogyan kell a
Burrows-Wheeler transform szót egyes és többes számban mondani. Minden, amit a
Burrows-Wheeler transform szóról tudni kell, itt található. A
Burrows-Wheeler transform szó meghatározása segít abban, hogy pontosabban és helyesebben fogalmazz, amikor beszélsz vagy írsz. A
Burrows-Wheeler transform és más szavak definíciójának ismerete gazdagítja a szókincsedet, és több és jobb nyelvi forráshoz juttat.
Főnév
Burrows-Wheeler transform (tsz. Burrows-Wheeler transforms)
- (informatika) A Burrows–Wheeler transzformáció (röviden BWT) egy reverzibilis szövegtranszformáció, amelyet elsősorban adatkompresszió előfeldolgozásaként használnak.
🧠 Lényege
A BWT nem tömörít önmagában, de átalakítja a szöveget úgy, hogy az utána következő tömörítő algoritmusok (pl. Run-Length Encoding, Move-To-Front, Huffman-kódolás) hatékonyabbak legyenek.
🔁 Fő tulajdonságai
- Reverzibilis: az eredeti szöveg visszaállítható a BWT alapján.
- Az átalakítás után a hasonló karakterek egymás mellé kerülnek, ami növeli a tömöríthetőséget.
- Különösen jól működik ismétlődő minták esetén (pl. forráskód, természetes nyelv, genom).
🧩 Hogyan működik?
- Szó kiegészítése egy speciális lezáró karakterrel (pl.
$, ami lexikografikusan kisebb minden betűnél).
- Ciklikus eltolások létrehozása az eredeti szóból.
- Az összes eltolás lexikografikus rendezése.
- Az összes rendezett sor utolsó karakterét vesszük → ez a BWT eredmény.
📐 Példa
Szó: banana
- Kiegészítjük:
banana$
- Ciklikus eltolások:
banana$
anana$b
nana$ba
ana$ban
na$bana
a$banan
$banana
- Rendezés:
$banana
a$banan
ana$ban
anana$b
banana$
na$bana
nana$ba
- Utolsó oszlop (BWT):
annb$aa
🔁 Visszafejtés vázlata
- A BWT visszafejthető, ha ismerjük a BWT karakterláncot és a lezáró karakter helyét.
- A dekódolás LF-mapping elvén alapul, ahol a „Last” és „First” oszlop közti kapcsolat segít helyreállítani a karakterek sorrendjét.
📦 Alkalmazások
- 📚 bzip2: híres tömörítő, amely a BWT-t használja az első lépésben.
- 🧬 Bioinformatika: pl. genom indexelés (pl. FM-index, Bowtie algoritmus).
- 📄 Szövegindexelés és tömörített keresés.
💡 Előnyök
- Növeli a lokális redundanciát, ezáltal hatékonyabb tömörítés érhető el.
- Nem veszteséges.