Abstract 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 ( ( n lg ⁡ σ + s lg 2 ⁡ N ) lg ⁡ 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 ( m lg 1 + ϵ ⁡ N ⋅ ndoc ) , for any constant ϵ > 0 (and tells in time O ( m lg ⁡ 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 ( r lg ⁡ N ) bits and counts the number of occurrences of a pattern P [ 1 , m ] in time O ( m 2 + m lg 2 + ϵ ⁡ r ) , for any constant ϵ > 0 . We also give the first index using O ( z lg ⁡ ( N z ) lg ⁡ N ) bits, where T is parsed by Lempel–Ziv into z phrases, counting occurrences in time O ( m lg 2 + ϵ ⁡ N ) .
@cite_37: We introduce the first grammar-compressed representation of a sequence that supports searches in time that depends only logarithmically on the size of the grammar. Given a text @math that is represented by a (context-free) grammar of @math (terminal and nonterminal) symbols and size @math (measured as the sum of the lengths of the right hands of the rules), a basic grammar-based representation of @math takes @math bits of space. Our representation requires @math bits of space, for any @math . It can find the positions of the @math occurrences of a pattern of length @math in @math in @math time, and extract any substring of length @math of @math in time @math , where @math is the height of the grammar tree.
@cite_50: Representing versioned documents, such as Wikipedia history, web archives, genome databases, backups, is challenging when we want to support searching for an exact substring and retrieve the documents that contain the substring. This problem is called document listing. We present an index for the document listing problem on versioned documents. Our index is the first one based on grammar-compression. This allows for good results on repetitive collections, whereas standard techniques cannot achieve competitive space for solving the same problem. Our index can also be addapted to work in a more standard way, allowing users to search for word-based phrase queries and conjunctive queries at the same time. Finally, we discuss extensions that may be possible in the future, for example, supporting ranking capabilities within the index itself.
One precedent is Claude and Munro's index based on grammar compression @cite_50 . It builds on a grammar-based pattern-matching index @cite_37 and adds an inverted index that explicitly indicates the documents where each nonterminal appears; this inverted index is also grammar-compressed. To obtain the answer, an unbounded number of those lists of documents must be merged. No relevant worst-case time or space guarantees are offered.