Abstract
Given a set D of d patterns, the dictionary matching problem is to index D such that for any query text T, we can locate the occurrences of any pattern within T efficiently. When D contains a total of n characters drawn from an alphabet of size σ, Hon et al. (2008) gave an nH <sub>k</sub> (D) + o(n log σ)-bit index which supports a query in O(|T| (log <sup>ε</sup> n+ log d) + occ) time, where ε > 0 and H <sub>k</sub> (D) denotes the kth order entropy of D. Very recently, Belazzougui (2010) proposed an elegant scheme, which takes n log σ +O(n) bits of index space and supports a query in optimal O(|T|+occ) time. In this paper, we provide connections between Belazzougui's index and the XBW compression of Ferragina et al. (2005), and show that Belazzougui's index can be slightly modified to be stored in nH <sub>k</sub> (D) + O(n) bits, while query time remains optimal; this improves the compressed index by Hon et al. (2008) in both space and time. © 2010 Springer-Verlag.