Conference paper
Deterministic indexing for packed strings
Given a string S of length n, the classic string indexing problem is to preprocess S into a compact data structure that supports efficient subsequent pattern queries. In the deterministic variant the goal is to solve the string indexing problem without any randomization (at preprocessing time or query time).
In the packed variant the strings are stored with several character in a single word, giving us the opportunity to read multiple characters simultaneously. Our main result is a new string index in the deterministic and packed setting. Given a packed string S of length n over an alphabet σ, we show how to preprocess S in O(n) (deterministic) time and space O(n) such that given a packed pattern string of length m we can support queries in (deterministic) time O (m/α + log m + log log σ), where α = w/log σ is the number of characters packed in a word of size w = θ(log n).
Our query time is always at least as good as the previous best known bounds and whenever several characters are packed in a word, i.e., log σ
Language: | English |
---|---|
Publisher: | Schloss Dagstuhl - Leibniz-Zentrum für Informatik |
Year: | 2017 |
Proceedings: | 28th Annual Symposium on Combinatorial Pattern Matching |
Series: | Leibniz International Proceedings in Informatics |
ISBN: | 3959770391 and 9783959770392 |
ISSN: | 18688969 |
Types: | Conference paper |
DOI: | 10.4230/LIPIcs.CPM.2017.6 |
ORCIDs: | Bille, Philip and Gørtz, Inge Li |
Combinatorial Mathematics, Includes Graph Theory, Set Theory Compact data structure Deterministic algorithm Deterministic algorithms Information Sources and Analysis Pattern matching Pattern query Pattern strings Preprocessing time Single words Suffix array Suffix arrays Suffix tree Suffix-trees Trees (mathematics) Word packing