Wavelet trees meet suffix trees

DOI10.1137/1.9781611973730.39MaRDI QIDQ5362987zbMATH OpenOpenAlexFDO

Authors Paweł Gawrychowski, Tomasz Kociumaka, Tatiana Starikovskaya, Maxim Babenko

Publication date 5 October 2017

Published in Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Data structures (68P05) Algorithms on strings (68W32)

Abstract: We present an improved wavelet tree construction algorithm and discuss its applications to a number of rank/select problems for integer keys and strings. Given a string of length n over an alphabet of size $sigmaleqn$, our method builds the wavelet tree in $O(nlogsigma/sqrtlogn)$ time, improving upon the state-of-the-art algorithm by a factor of $sqrtlogn$. As a consequence, given an array of n integers we can construct in $O(nsqrtlogn)$ time a data structure consisting of $O(n)$ machine words and capable of answering rank/select queries for the subranges of the array in $O(logn/loglogn)$ time. This is a $loglogn$-factor improvement in query time compared to Chan and Pu{a}trac{s}cu and a $sqrtlogn$-factor improvement in construction time compared to Brodal et al. Next, we switch to stringological context and propose a novel notion of wavelet suffix trees. For a string w of length n, this data structure occupies $O(n)$ words, takes $O(nsqrtlogn)$ time to construct, and simultaneously captures the combinatorial structure of substrings of w while enabling efficient top-down traversal and binary search. In particular, with a wavelet suffix tree we are able to answer in $O(log|x|)$ time the following two natural analogues of rank/select queries for suffixes of substrings: for substrings x and y of w count the number of suffixes of x that are lexicographically smaller than y, and for a substring x of w and an integer k, find the k-th lexicographically smallest suffix of x. We further show that wavelet suffix trees allow to compute a run-length-encoded Burrows-Wheeler transform of a substring x of w in $O(slog|x|)$ time, where s denotes the length of the resulting run-length encoding. This answers a question by Cormode and Muthukrishnan, who considered an analogous problem for Lempel-Ziv compression.

Recommendations

• On wavelet tree construction
• Online construction of wavelet trees
• Fast wavelet tree construction in practice
• Practical Wavelet Tree Construction
• Fast construction of wavelet trees

Cited in

(21)

• Internal dictionary matching
• Parallel lightweight wavelet tree, suffix array and FM-index construction
• Internal shortest absent word queries in constant time and linear space
• Weighted ancestors in suffix trees
• Fast construction of wavelet trees
• Computing minimal and maximal suffixes of a substring
• Order-preserving indexing
• The Myriad Virtues of Wavelet Trees
• New algorithms on wavelet trees and applications to information retrieval
• Online construction of wavelet trees
• Practical Wavelet Tree Construction
• Efficient indexes for jumbled pattern matching with constant-sized alphabet
• scientific article; zbMATH DE number 7651193 (Why is no real title available?)
• Absent Subsequences in Words
• Parallel external memory wavelet tree and wavelet matrix construction
• Internal pattern matching queries in a text and applications
• Internal pattern matching in small space and applications
• LZ78 substring compression in compressed space
• An almost optimal edit distance oracle
• Color distance oracles and snippets: separation between exact and approximate solutions
• Improved parallel construction of wavelet trees and rank/select structures

This page was built for publication: Wavelet trees meet suffix trees

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