Computing the parameterized Burrows-Wheeler transform online

DOI10.1007/978-3-031-20643-6_6zbMATH Open1525.68206arXiv2206.15100MaRDI QIDQ6166973FDOQ6166973

Authors: Daiki Hashimoto, Diptarama Hendrian, Dominik Köppl, Ryo Yoshinaka, Ayumi Shinohara 

Publication date: 4 August 2023

Published in: String Processing and Information Retrieval (Search for Journal in Brave)

Abstract: Parameterized strings are a generalization of strings in that their characters are drawn from two different alphabets, where one is considered to be the alphabet of static characters and the other to be the alphabet of parameter characters. Two parameterized strings are a parameterized match if there is a bijection over all characters such that the bijection transforms one string to the other while keeping the static characters (i.e., it behaves as the identity on the static alphabet). Ganguly et al. [SODA 2017] proposed the parameterized Burrows--Wheeler transform (pBWT) as a variant of the Burrows--Wheeler transform for space-efficient parameterized pattern matching. In this paper, we propose an algorithm for computing the pBWT online by reading the characters of a given input string one-by-one from right to left. Our algorithm works in $O(|Pi|logn/loglogn)$ amortized time for each input character, where $n$ and $Pi$ denote the size of the input string and the alphabet of the parameter characters, respectively.

Full work available at URL: https://arxiv.org/abs/2206.15100

zbMATH Keywords

online algorithmparameterized stringBurrows-Wheeler transform

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Data structures (68P05) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Algorithms on strings (68W32)

Cites Work

• Optimal Dynamic Sequence Representations
• Parameterized pattern matching: Algorithms and applications
• Efficient parameterized string matching
• Generalization of a suffix tree for RNA structural pattern matching
• Lightweight parameterized suffix array construction
• A theory of parameterized pattern matching
• pBWT: achieving succinct data structures for parameterized pattern matching and related problems
• Simpler FM-index for parameterized string matching
• A brief history of parameterized matching problems
• Position heaps for parameterized strings
• DAWGs for Parameterized Matching: Online Construction and Related Indexing Structures

Cited In (2)

• Computing the Burrows-Wheeler transform of a string and its reverse in parallel
• A faster implementation of online run-length Burrows-Wheeler transform

This page was built for publication: Computing the parameterized Burrows-Wheeler transform online

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6166973)