We consider the problem of indexing a text T (of length n) with a light data structure that supports efficient search of patterns P (of length m) allowing errors under the Hamming distance. We propose a hash-based strategy that employs two classes of hash functions—dubbed Hamming-aware and de Bruijn—to drastically reduce search space and memory footprint of the index, respectively. We use our succinct hash data structure to solve the k-mismatch search problem in 2n log σ + o(n log σ) bits of space with a random- ized algorithm having smoothed complexity O((2σ)k(log n)k(log m+ξ)+ (occ + 1) · m), where σ is the alphabet size, occ is the number of occur- rences, and ξ is a term depending on m, n, and on the amplitude ε of the noise perturbing text and pattern. Significantly, we obtain that for any ε > 0, for m large enough, ξ ∈ O(log m): our results improve upon previous linear-space solutions of the k-mismatch problem.
|Data di pubblicazione:||2014|
|Titolo:||Hashing and Indexing: Succinct DataStructures and Smoothed Analysis|
|Titolo del libro:||Algorithms and Computation: 25th International Symposium, ISAAC 2014, Jeonju, Korea, December 15-17, 2014, Proceedings|
|Digital Object Identifier (DOI):||http://dx.doi.org/10.1007/978-3-319-13075-0_13|
|Appare nelle tipologie:||4.1 Articolo in Atti di convegno|
File in questo prodotto: