2017/07/20 by Gonzalo Navarro, Navarro, Gonzalo · 1 citation
Computer Science · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.DS
paper · pdf · doi:10.48550/arxiv.1707.06374
Extended version of CPM'17 paper
arxiv created 2018/11/14 · arxiv updated 2018/11/15
We consider document listing on string collections, that is, finding in which strings a given pattern appears. In particular, we focus on repetitive collections: a collection of size N over alphabet [1,σ] is composed of D copies of a string of size n, and s edits are applied on ranges of copies. We introduce the first document listing index with size O(n+s), precisely O((nlogσ+slog2 N)log D) bits, and with useful worst-case time guarantees: Given a pattern of length m, the index reports the \ndoc>0 strings where it appears in time O(mlog1+ε N ⋅ \ndoc), for any constant ε>0 (and tells in time O(mlog N) if \ndoc=0). Our technique is to augment a range data structure that is commonly used on grammar-based indexes, so that instead of retrieving all the pattern occurrences, it computes useful summaries on them. We show that the idea has independent interest: we introduce the first grammar-based index that, on a text T[1,N] with a grammar of size r, uses O(rlog N) bits and counts the number of occurrences of a pattern P[1,m] in time O(m2 + mlog2+ε r), for any constant ε>0. We also give the first index using O(zlog(N/z)log N) bits, where T is parsed by Lempel-Ziv into z phrases, counting occurrences in time O(mlog2+ε N).