導入
最近、応用情報の勉強を始めたため、アウトプットとして自分なりの理解をまとめて投稿しています。誤りなどがあればご指摘いただけると助かります。この記事で5本目です。
BWT(ブロックソート)
BWTは文字列をソートすることで同じ文字の連続が多い文字列に変換するアルゴリズムである。BWT自体には圧縮の機能はないが、ランレングス符号化などと一緒に使うことで圧縮をすることができる。
BWTの特徴
- 可逆変換：並び替えた文字列から元の文字列に一意に復元可能
※復元にはソート後の文字列のどの行が元の文字列を示すかという情報が必要 - 圧縮機能はない：ランレングスなどとセットで用いる
BWTの流れ
- 左巡回(各文字を左に1文字ずらす)の文字列を文字数分のパターンを作る
- 1で得た文字列を辞書順にソートする
- 2で得られた文字列の最後の列を上から順に出力する
BWTの例
T = ababaababbについてBWTを行う。BWTを行うことで同じ文字の連続が以下のように増加した。
- 入力：T = ababaababb
- 出力：BWT(T) = bbbabaabaa
BWTの復元の流れ
- BWT(T)を辞書順に並び替え文字列の左から1列目を復元する
- 左端と右端の文字列の対応関係に上から出てきた順に番号を割り振る
- 2の番号順に復元する
※左巡回しかしていないため、同じ文字が複数あっても、上から順に番号を付けるだけで順序関係が保たれる。
BWTの復元例
BWT(T) = bbbabaabaaの復元を行う。今回は元の文字列と対応するソート後の文字列の行を上から3行目とする。
- 入力：BWT(T) = bbbabaabaa、対応するインデックスは上から3行目
- 出力：T = ababaababb
まとめ
- BWTはソートアルゴリズムであり、圧縮機能はない
- BWTはランレングスなどの圧縮とセットで用いる
- BWTは、可逆変換である
次回は、JPEGに関するデータ圧縮の簡単な流れについてまとめたいと思う。
参考
以下のサイトが分かりやすく、参考にさせていただきました。
https://everplay.jp/column/24186
https://ja.wikipedia.org/wiki/%E3%83%96%E3%83%AD%E3%83%83%E3%82%AF%E3%82%BD%E3%83%BC%E3%83%88