Compressed Dictionary Matching with One Error
Wing-Kai Hon, Tsung-Han Ku, Rahul Shah, Sharma V. Thankachan, Jeffrey Scott Vitter · 2011
Given a set D of d patterns of total length n, 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. This problem can be solved in optimal O(|T|+occ) time by the classical AC automaton (Aho and Corasick, 1975) where occ denotes the number of occurrences. The space requirement is O(n) words. In the {approximate} dictionary matching problem with one error, we consider a substring of T[i..j] an occurrence of P whenever the edit distance between T[i..j] and P is at most one. For this problem, the best known indexes are by Cole et al. (2004), which requires O(n+ d\log{d}) words of space and reports all occurrences in O(|T|\log{d}\log{\log{d}}+occ) time, and by Ferragina et al. (1999), which requires O(n^{1+\epsilon}) words of space and reports all occurrences in O(|T|\log\log n + occ) time. Recently, there have been successes in compressing the dictionary matching index while keeping the query time optimal (Belazzougui, 2010, Hon et al., 2010). However, a compressed index for approximate dictionary matching problem is still open. In this paper, we propose the first such index which requires an optimal nH_k+O(n)+o(n\log\sigma)-bit index space, where H_k denotes the kth-order empirical entropy of \D, and \sigma is the size of alphabet set from which all the characters in \D and T are drawn. The query time of our index is O(σ|T|log3n log \ log n + occ).