Burrows Wheeler変換(BWT)
tl:dr
Burrows Wheeler変換(BWT)について調べためも
Burrows Wheeler変換(BWT)とは
変換すると，似たような記号がたくさん並ぶようになる，文字列の可逆変換手法。 これ自体はデータのサイズは変更しないですが、圧縮しやすくなるのでデータ圧縮の前処理で使われます。
# 定義
TB - 1] , T[n-1]
文字列TのBWTの結果の文字列TbをTのBWTと呼びます。
例
定義だけではわかりにくいので、「abracatabra$」の場合で考えてみます。 文字列「abracatabra$」の接尾辞配列は以下でした。
| 開始位置 i | suffix(Si) |
|---|---|
| 11 | $ |
| 10 | a$ |
| 7 | abra$ |
| 0 | abracadabra$ |
| 3 | acadabra$ |
| 5 | adabra$ |
| 8 | bra$ |
| 1 | bracadabra$ |
| 4 | cadabra$ |
| 6 | dabra$ |
| 2 | racadabra$ |
| 9 | ra$ |
このの場合、tb1は
SA[1] = 10 T(SA[1) - 1] = r
です。 「abracatabra$」の接尾辞配列の2番目は11文字目〜末尾の「a$」です。 T(SA[1) - 1] はその一つ前の文字 = 10文字目なので「r」になります。
つまり、T(SA[i) - 1]は接尾辞(SA[i])の一つ前の文字を指します。
これを0~12文字目まで行ったabracatabra$のBWTは、ard$rcaaabbになります。
じつはこれは、abracatabra$の先頭の文字を後ろにまわして辞書順にソートした最後の文字を取り出したものになります。
abracadabra$ bracadabra$a racadabra$ab acadabra$abr cadabra$abra adabra$abrac dabra$abraca abra$abracad bra$abracada ra$abracadab a$abracadabr $abracadabra
これを辞書順にソートすると
$abracadabra a$abracadabr abra$abracad abracadabra$ acadabra$abr adabra$abrac bra$abracada bracadabra$a cadabra$abra dabra$abraca ra$abracadab racadabra$ab
最後の文字をつなげるとard$rcaaabb
