Compressed Index for Property Matching

In this paper, we revisit the Property Matching problem and present a better indexing scheme for the problem. Let T be a text of length n with property p, and P be a pattern of length m, both strings are over a fixed finite alphabet. In particular, the existing data structures all require O(n log n)-bit space, where n is the length of the text. By using compressed suffix array and other supporting data structures, we propose a new index structure for the problem. We discuss the index structure and searching process for the case |π| = O(n/ log n) and |π| = Ω(n/ log n). Our index only needs nH_k(T)+O(n log |Σ|)-bits and nH_k(T)+nH₀(A)+O(n(log |Σ|+log log n)) bits space for the above cases respectively (A is an array with length n here), while needing a little more searching time as return.