2020/10/14 by Gonzalo Navarro, Navarro, Gonzalo · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #DNA and Biological Computing #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Network Packet Processing and Optimization
paper · pdf · doi:10.48550/arxiv.2010.07076
openalex publication_date 2020/10/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The research on indexing repetitive string collections has focused on the same search problems used for regular string collections, though they can make little sense in this scenario. For example, the basic pattern matching query "list all the positions where pattern P appears" can produce huge outputs when P appears in an area shared by many documents. All those occurrences are essentially the same. In this paper we propose a new query that can be more appropriate in these collections, which we call \em contextual pattern matching. The basic query of this type gives, in addition to P, a context length ℓ, and asks to report the occurrences of all \em distinct strings XPY, with |X|=|Y|=ℓ. While this query is easily solved in optimal time and linear space, we focus on using space related to the repetitiveness of the text collection and present the first solution of this kind. Letting \ovr be the maximum of the number of runs in the BWT of the text T[1..n] and of its reverse, our structure uses O(\ovrlog(n/\ovr)) space and finds the c contextual occurrences XPY of (P,ℓ) in time O(|P| + c log n). We give other space/time tradeoffs as well, for compressed and uncompressed indexes.