Tartalomjegyzék:
- Meghatározás - Mit jelent a Burrows-Wheeler Transform (BWT)?
- A Techopedia magyarázza a Burrows-Wheeler Transform (BWT)
Meghatározás - Mit jelent a Burrows-Wheeler Transform (BWT)?
A Burrows-Wheeler transzformáció (BWT) egy olyan algoritmus, amely adatblokkokból, például karakterláncokból áll, és hasonló karakterkészletekké sorolja át őket. A transzformáció után a kimeneti blokk ugyanolyan pontos adatelemeket tartalmaz, mielőtt elindult volna, de a sorrendben különbözik. Az algoritmus jellege hajlamos hasonló karakterek egymás mellé helyezésére, megkönnyítve a kapott adatsorok tömörítését. Ezért sok tömörítési algoritmusban használják.
A Techopedia magyarázza a Burrows-Wheeler Transform (BWT)
A Burrows-Wheeler transzformációs algoritmus egy viszonylag új algoritmus, amelyet 1994-ben fedeztek fel Michael Burrows és David Wheeler, és egy nem közzétett transzformáción alapul, amelyet Wheeler fedezett fel 1983-ban.
A legalapvetőbb esetben a BWT adatblokkot vesz, például egy karakterláncot, hozzáad egy EOF karaktert, majd a karakterlánc összes forgását lexikográfiai sorrendbe rendezi. A következő álnév vagy lépések illusztrálják az algoritmust:
- Készítsen egy táblázatot, amely sorokat tartalmaz, amelyek a karakterlánc összes lehetséges egylépéses forgását reprezentálják.
- Az összes sort betűrendben rendezze.
- Adja ki a táblázat utolsó oszlopát.
Például: a „banán” szó; ha hozzáadunk egy EOF karaktert, akkor "banana $" lesz, majd alkalmazzuk az algoritmust:
1. Készítsen egy táblázatot az összes lehetséges forgatást reprezentáló sorokkal:
banán $
Añana $ b
nana $ ba
ana $ ban
na $ Bana
Egy $ banan
$ banán
2. Osztja a sorokat ábécé / lexikográf szerint az első oszlop alapján:
$ banán
Egy $ banan
ana $ ban
Añana $ b
banán $
nana $ ba
na $ Bana
3.Tatkoztassa az utolsó oszlopot BWT kimenetként: annb $ aa
A kapott karakterláncot könnyebben lehet tömöríteni, mivel az ismételt karaktereket egymás mellé csomózzák. De a transzformált adatokkal együtt további adatokat kell tárolni, hogy fordított átalakítást lehessen végrehajtani. Annak ellenére, hogy a kapott transzformált adatok nagyobbak, mint az eredeti formájuk, tömöríthetõségi tulajdonságuk sokszorosára növekszik, lényegében „ingyenes” módszerrel javítva a tömörítési módszereket.
