Computing the parameterized Burrows-Wheeler transform online

DOI10.1007/978-3-031-20643-6_6MaRDI QIDQ6166973zbMATH OpenFDO

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)

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)

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.

Recommendations

• pBWT: achieving succinct data structures for parameterized pattern matching and related problems
• DAWGs for Parameterized Matching: Online Construction and Related Indexing Structures
• Parameterized DAWGs: efficient constructions and bidirectional pattern searches
• Fast parameterized matching with \(q\)-grams
• Sublinear Algorithms for Parameterized Matching

Cites work

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

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)