Compressed Index for Dictionary Matching
Wing-Kai Hon, Tak‐Wah Lam, Rahul Shah, Siu-Lung Tam, Jeffrey Scott Vitter · 2008
The past few years have witnessed several exciting results on compressed representation of a string T that supports efficient pattern matching, and the space complexity has been reduced to |T| Hk(T) + o (|T| log sigma) bits, where Hk(T) denotes the kth-order empirical entropy of T, and sigma is the size of the alphabet. In this paper we study compressed representation for another classical problem of string indexing, which is called dictionary matching in the literature. Precisely, a collection D of strings (called patterns) of total length n is to be indexed so that given a text T, the occurrences of the patterns in T can be found efficiently. In this paper we show how to exploit a sampling technique to compress the existingO(n)-word index to an (n Hk(D) + o(n log sigma))-bit index with only a small sacrifice in search time.