Succinct dictionary matching with no slowdown
Djamal Belazzougui · 2010
The problem of dictionary matching is a classical problem in string matching: given a set S of d strings of total length n characters over an (not necessarily constant) alphabet of size σ, build a data structure so that we can match in a any text T all occurrences of strings belonging to S. The classical solution for this problem is the Aho-Corasick automaton which finds all occ occurrences in a text T in time O(|T | + occ) using a data structure that occupies O(m logm) bits of space where m ≤ n + 1 is the number of states in the automaton. In this paper we show that the Aho-Corasick automaton can be represented in just m(log σ+O(1))+ O(d log(n/d)) bits of space while still maintaining the ability to answer to queries in O(|T |+ occ) time. To the best of our knowledge, the currently fastest succinct data structure for the dictionary matching problem uses space O(n log σ) while answering queries in O(|T | log logn + occ) time. In this paper we also show how the space occupancy can be reduced to m(H0 + O(1)) + O(d log(n/d)) where H0 is the empirical entropy of the characters appearing in the trie representation of the set S, provided that σ < mε for any constant 0 < ε < 1. The query time remains unchanged. 1 introduction A recent trend in text pattern matching algorithms has been to succinctly encode data structures so that they occupy no more space than the data they are built on, without a too significant sacrifice in their query time. The most prominent example being the data structures used for indexing texts for substring matching queries [15, 8, 9]. In this paper we are interested in the succinct encoding of data structures for the dictionary matching problem, which consists in the construction of a data structure on a set S of d strings (a dictionary) of total length n over an alphabet of size σ (wlog we assume that σ ≤ n) so that we can answer to queries of 1 ar