Computing the parameterized Burrows-Wheeler transform online

DOI10.1007/978-3-031-20643-6_6zbMath1525.68206arXiv2206.15100MaRDI QIDQ6166973

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

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 algorithmBurrows-Wheeler transformparameterized string

Mathematics Subject Classification ID

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

Cites Work

• Efficient parameterized string matching
• Generalization of a suffix tree for RNA structural pattern matching
• Parameterized pattern matching: Algorithms and applications
• Simpler FM-index for parameterized string matching
• A brief history of parameterized matching problems
• Lightweight Parameterized Suffix Array Construction
• pBWT: Achieving Succinct Data Structures for Parameterized Pattern Matching and Related Problems
• Position Heaps for Parameterized Strings
• Optimal Dynamic Sequence Representations
• A theory of parameterized pattern matching
• DAWGs for Parameterized Matching: Online Construction and Related Indexing Structures