CPM 2025 に論文がアクセプトされました

2025年6月17日〜19日にイタリア・ミラノで開催される 36th Annual Symposium on Combinatorial Pattern Matching (CPM 2025)(文字列処理のアルゴリズム・文字列の組合せ論の理論研究に関する主要国際会議)に、本分野のメンバーが著者となっている以下の論文がアクセプトされました。

Hideo Bannai, Tomohiro I, Yuto Nakashima, “On the compressiveness of the Burrows-Wheeler transform” [preprint]

今回の論文は SPIRE 2024 にて発表した内容 と関連する内容で、文字列に Burrows-Wheeler 変換 (BWT) を施す前と後とで、辞書式圧縮の下での圧縮可能性がどの程度変わるかについて解析しています。

主な発見は

1. 主要な辞書式圧縮に関する圧縮性指標は BWT および全単射 BWT を適用することで $O(\mathrm{poly}\log n)$ 倍にしかならないこと($n$ は文字列の長さ)
2. 逆に、全単射 BWT を適用することにより、辞書式圧縮では圧縮できない(圧縮性指標が $\Omega(n/\log n)$)文字列から、最も圧縮できる文字列(圧縮性指標が $O(1)$)に変換される文字列の無限集合が存在すること

です。このことは、BBWT で変換した後に辞書式圧縮を施すことで、理論的に辞書式圧縮の枠組みを超える圧縮性能が達成できる場合があることを示しており、これまで知られていたよりも BWT が文字列の圧縮性能に与える影響が大きい可能性があることを示唆しています。

技術的な面白さとしては 2. を示す際に BBWT の像がフィボナッチ文字列となる文字列を使用しており、逆変換および変換前の文字列が整数の Zeckendorf 表現を用いて特徴づけられることを発見し、美しい証明が得られたことが挙げられます。