Deterministic indexing for packed strings

DOI10.4230/LIPICS.CPM.2017.6MaRDI QIDQ5110869zbMATH OpenOpenAlexFDO

Authors Philip Bille, Inge Li Gørtz, Frederik Rye Skjoldjensen

Publication date 25 May 2020

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

zbMATH Keywords

deterministic algorithmsuffix arraysuffix treeword packing

Mathematics Subject Classification ID

Data structures (68P05)

Abstract: 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 emph{deterministic} variant the goal is to solve the string indexing problem without any randomization (at preprocessing time or query time). In the emph{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 emph{and} packed setting. Given a packed string $S$ of length $n$ over an alphabet $sigma$, 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 $Oleft(m/alpha+logm+loglogsigmaight),$ where $alpha=w/logsigma$ is the number of characters packed in a word of size $w=Theta(logn)$. 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., $logsigmallw$, the query times are faster.

Recommendations

• Fast Searching in Packed Strings
• Fast searching in packed strings
• Average optimal string matching in packed strings
• Compressed indexing with signature grammars

Cited in

(11)

• Fast compressed self-indexes with deterministic linear-time construction
• Top tree compression of tries
• c-trie++: a dynamic trie tailored for fast prefix searches
• Packed Compact Tries: A Fast and Efficient Data Structure for Online String Processing
• Indexing permutations for binary strings
• Fast entropy-bounded string dictionary look-up with mismatches
• Construction of Fundamental Data Structures for Strings
• Fast Compressed Self-Indexes with Deterministic Linear-Time Construction
• scientific article; zbMATH DE number 7651193 (Why is no real title available?)
• Compressed string dictionaries via data-aware subtrie compaction
• Predecessor on the Ultra-Wide Word RAM

This page was built for publication: Deterministic indexing for packed strings

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