Inverting Parameterized Burrows-Wheeler Transform
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915278942633984 |
|---|---|
| author | Kawanami, Shogen Iseri, Kento I, Tomohiro |
| author_facet | Kawanami, Shogen Iseri, Kento I, Tomohiro |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_06970 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Inverting Parameterized Burrows-Wheeler Transform Kawanami, Shogen Iseri, Kento I, Tomohiro Data Structures and Algorithms 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. |
| title | Inverting Parameterized Burrows-Wheeler Transform |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2503.06970 |