Alphabet-dependent string searching with wexponential search trees

DOI10.1007/978-3-319-19929-0_14MaRDI QIDQ2942254zbMATH OpenOpenAlexFDO

Authors Johannes Fischer, Paweł Gawrychowski

Publication date 20 August 2015

Published in Combinatorial Pattern Matching (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Data structures (68P05) Searching and sorting (68P10) Algorithms on strings (68W32)

Abstract: It is widely assumed that $O(m+lgsigma)$ is the best one can do for finding a pattern of length $m$ in a compacted trie storing strings over an alphabet of size $sigma$, if one insists on linear-size data structures and deterministic worst-case running times [Cole et al., ICALP'06]. In this article, we first show that a rather straightforward combination of well-known ideas yields $O(m+lglgsigma)$ deterministic worst-case searching time for static tries. Then we move on to dynamic tries, where we achieve a worst-case bound of $O(m+fracl{g}^{2}lgsigmalglglgsigma)$ per query or update, which should again be compared to the previously known $O(m+lgsigma)$ deterministic worst-case bounds [Cole et al., ICALP'06], and to the alphabet emph{in}dependent $O(m+sqrtlgn/lglgn)$ deterministic worst-case bounds [Andersson and Thorup, SODA'01], where $n$ is the number of nodes in the trie. The basis of our update procedure is a weighted variant of exponential search trees which, while simple, might be of independent interest. As one particular application, the above bounds (static and dynamic) apply to suffix trees. There, an update corresponds to pre- or appending a letter to the text, and an additional goal is to do the updates quicker than rematching entire suffixes. We show how to do this in $O(lglgn+fracl{g}^{2}lgsigmalglglgsigma)$ time, which improves the previously known $O(lgn)$ bound [Amir et al., SPIRE'05].

Recommendations

• Packed Compact Tries: A Fast and Efficient Data Structure for Online String Processing
• Top Tree Compression of Tries.
• Linear-size suffix tries
• Top tree compression of tries
• Space efficient suffix trees

Cites work

• A Space-Economical Suffix Tree Construction Algorithm
• Alphabet-dependent string searching with wexponential search trees
• Constructing Efficient Dictionaries in Close to Sorting Time
• Dynamic Binary Search
• Dynamic ordered sets with exponential search trees
• scientific article; zbMATH DE number 2086622 (Why is no real title available?)
• Managing unbounded-length keys in comparison-driven data structures with applications to online indexing
• Near real-time suffix tree construction via the fringe marked ancestor problem
• Optimal bounds for the predecessor problem and related problems
• Storing a Sparse Table with 0 (1) Worst Case Access Time
• Suffix Arrays: A New Method for On-Line String Searches

Cited in

(23)

• Fast compressed self-indexes with deterministic linear-time construction
• Fully-online suffix tree and directed acyclic word graph construction for multiple texts
• Packed Compact Tries: A Fast and Efficient Data Structure for Online String Processing
• Alphabet-dependent string searching with wexponential search trees
• Lempel Ziv computation in small space (LZ-CISS)
• Time-optimal top-k document retrieval
• Fast entropy-bounded string dictionary look-up with mismatches
• Conversion from RLBWT to LZ77
• Online algorithms for constructing linear-size suffix trie
• Engineering practical Lempel-Ziv tries
• Fast Compressed Self-Indexes with Deterministic Linear-Time Construction
• Practical evaluation of Lempel-Ziv-78 and Lempel-Ziv-Welch tries
• scientific article; zbMATH DE number 3894487 (Why is no real title available?)
• Linear-time computation of DAWGs, symmetric indexing structures, and MAWs for integer alphabets
• Subsequences in bounded ranges: matching and analysis problems
• Linear time online algorithms for constructing linear-size suffix trie
• Faster sliding window string indexing in streams
• Internal pattern matching in small space and applications
• Maintaining the size of LZ77 on semi-dynamic strings
• Gapped string indexing in subquadratic space and sublinear query time
• The variable-processor cup game
• Lempel-Ziv-78 compressed string dictionaries
• Lempel-Ziv factorization powered by space efficient suffix trees

This page was built for publication: Alphabet-dependent string searching with wexponential search trees

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