Compressed property suffix trees

Property matching is a biologically motivated problem where the task is to find those occurrences of an online pattern P in a string text T (of size n), such that the matched text part satisfies some conceptual property. The property of a string is a set π of (possibly overlapping) intervals { ( s 1, f 1 ), ( s 2, f 2 ), … } corresponding to the part of text and an occurrence of a pattern P = T [ i, …, ( i + | P | − 1 ) ] is a valid output only if T [ i, …, ( i + | P | − 1 ) ] is completely contained in at least one interval ( s j, f j ) ∈ π. The indexing version of this problem was introduced by A. Amir (2008), where the text is preprocessed in O ( n log σ + n log log n ) time and an O ( n log n ) bits index, named Property Suffix Tree (PST) is maintained. PST can perform property matching in O ( | P | log σ + occ π ) time, where occ π is the number of occurrences of P in T satisfying the property. T. Kopelowitz (2010) considered the dynamic version of this problem where intervals can be added or deleted. However, all these indexes take space linear to the size of text ( O ( n log n ) bits), which can be much more than the size of the text ( n log σ bits). In this paper, we propose the first index for property matching occupying space close to the entropy compressed space requirement of the text. Our compressed index takes | CSA | + n ( 2 + ϵ + o ( 1 ) ) bits space and performs query answering in O ( t ( | P | ) + 1 ϵ ( 1 + occ π ) t SA ) time, where | CSA | is the size of compressed suffix array of T, t ( | P | ) be the time for searching a pattern of length | P | in CSA, t SA is the time for computing the suffix array value and ϵ > 0 is a constant. We also introduce a dynamic index, which takes | CSA | + O ( n + | π | log n ) bits space and performs query answering in O ( t ( | P | ) + ( 1 + occ π ) log n ( t SA + log n / log log n ) ) time and can update (insert/delete) an interval ( s, f ) in O ( ( f − s ) ( log n + t SA ) ) time.

Authors

• Wing-Kai Hon
• Manish Patil
• Rahul Shah
• Sharma V. Thankachan

Keywords

• Property matching
• Suffix trees
• Property suffix trees