SPIRE 2024 にて研究発表を行いました

2024年9月23日〜25日にメキシコのプエルト・バヤルタにて開催された 31st International Symposium on String Processing and Information Retrieval (SPIRE 2024) において、論文:

Bijective BWT based compression schemes, Golnaz Badkobeh, Hideo Bannai, Dominik Köppl [link] [preprint]

の研究発表を行いました。

内容は、全単射 Burrows-Wheeler 変換 (BBWT) に基づく圧縮方法を扱ったものです。BBWT は従来の BW 変換(BWT) が全単射となるように拡張した変換で、BWT と同様に文字列の索引構造として使えることや、線型時間で変換が計算できることが知られていましたが、その圧縮性能についてはこれまでほとんど研究がなされていませんでした。

今回の論文は全単射 BWT の連長圧縮サイズ $r_B$ について、

• 通常の BWT の連長圧縮サイズ $r$ と同様にサイズ $O(r_B)$ の双方向マクロスキームを誘導できること
• LZ77 サイズ $z$ に対して $r_B = O(z\log^2 n)$ と上から抑えられること
• BBWT と文字列の回転操作を組合わせることで、より高い圧縮率を実現できる新たな圧縮方式の可能性

などを示しています。