Indexing the bijective BWT
Hideo Bannai, Juha Kärkkäinen, Dominik Köppl, Marcin Piątkowski · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2019
The Burrows-Wheeler transform (BWT) is a permutation whose applications are prevalent in data compression and text indexing. The bijective BWT is a bijective variant of it that has not yet been studied for text indexing applications. We fill this gap by proposing a self-index built on the bijective BWT . The self-index applies the backward search technique of the FM-index to find a pattern P with O(|P| lg|P|) backward search steps.