Dictionary matching with uneven gaps

Abstract

A gap-pattern is a sequence of sub-patterns separated by bounded sequences of don’t care characters (called gaps). A one-gap-pattern is a pattern of the form P[α,β]Q , where P and Q are strings drawn from alphabet Σ and [α,β] are lower and upper bounds on the gap size g . The gap size g is the number of don’t care characters between P and Q . The dictionary matching problem with one-gap is to index a collection of one-gap-patterns, so as to identify all sub-strings of a query text T that match with any one-gap-pattern in the collection. Let D be such a collection of d patterns, where D={P i [α i ,β i ]Q i ∣1≤i≤d} . Let n=∑ d i=1 |P i |+|Q i | . Let γ and λ be two parameters defined on D as follows: γ=|{j∣j∈[α i ,β i ],1≤i≤d}| and λ=|{α i ,β i ∣1≤i≤d}| . Specifically γ is the total number gap lengths possible over all patterns in D and λ is the number of distinct gap boundaries across all the patterns. We present a linear space solution (i.e., O(n) words) for answering a dictionary matching query on D in time O(|T|γlogλlogd+occ) , where occ is the output size. The query time can be improved to O(|T|γ+occ) using O(n+d 1+ϵ ) space, where ϵ>0 is an arbitrarily small constant. Additionally, we show a compact/succinct space index offering a space-time trade-off. In the special case where parameters α i and β i ’s for all the patterns are same, our results improve upon the work by Amir et al. [CPM, 2014]. We also explore several related cases where gaps can occur at arbitrary locations and where gap can be induced in the text rather than pattern.