Practical Wavelet Tree Construction

DOI10.1145/3457197zbMath1499.68078OpenAlexW3182475993MaRDI QIDQ5102058

Patrick Dinklage, Florian Kurpicz, Johannes Fischer, Jonas Ellert, Marvin Löbel

Publication date: 6 September 2022

Published in: ACM Journal of Experimental Algorithmics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3457197

zbMATH Keywords

data structuresshared memoryexternal memorytext indexingdistributed memory

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Parallel algorithms in computer science (68W10) Data structures (68P05)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fast construction of wavelet trees
• Improved parallel construction of wavelet trees and rank/select structures
• Large alphabets and incompressibility
• Position-restricted substring searching over small alphabets
• Fixed block compression boosting in FM-indexes: theory and practice
• Faster average case low memory semi-external construction of the Burrows-Wheeler transform
• The myriad virtues of wavelet trees
• Parallel lightweight wavelet tree, suffix array and FM-index construction
• Wavelet trees for all
• Rank and select revisited and extended
• On Wavelet Tree Construction
• Suffix Arrays: A New Method for On-Line String Searches
• Indexing compressed text
• Permuted Longest-Common-Prefix Array
• Compression of Low Entropy Strings with Lempel--Ziv Algorithms
• Constructing the Wavelet Tree and Wavelet Matrix in Distributed Memory
• String synchronizing sets: sublinear-time BWT construction and optimal LCE data structure
• Simple, Fast and Lightweight Parallel Wavelet Tree Construction
• Wavelet Trees Meet Suffix Trees
• A Method for the Construction of Minimum-Redundancy Codes
• Fast wavelet tree construction in practice

This page was built for publication: Practical Wavelet Tree Construction