Inverting Parameterized Burrows-Wheeler Transform
By: Shogen Kawanami, Kento Iseri, Tomohiro I
Potential Business Impact:
Lets computers find patterns with missing letters.
The Burrows-Wheeler Transform (BWT) of a string is an invertible permutation of the string, which can be used for data compression and compact indexes for string pattern matching. Ganguly et al. [SODA, 2017] introduced the parameterized BWT (pBWT) to design compact indexes for parameterized matching (p-matching), a variant of string pattern matching with parameter symbols introduced by Baker [STOC, 1993]. Although the pBWT was inspired by the BWT, it is not obvious whether the pBWT itself is invertible or not. In this paper we show that we can retrieve the original string (up to renaming of parameter symbols) from the pBWT of length $n$ in $O(n^2)$ time and $O(n)$ space.
Similar Papers
Fast and memory-efficient BWT construction of repetitive texts using Lyndon grammars
Data Structures and Algorithms
Finds patterns in huge data faster.
Encoding Co-Lex Orders of Finite-State Automata in Linear Space
Data Structures and Algorithms
Makes searching computer programs much faster.
Decomposing Words for Enhanced Compression: Exploring the Number of Runs in the Extended Burrows-Wheeler Transform
Data Structures and Algorithms
Finds better ways to shrink computer files.