Hashing and Indexing: Succinct DataStructures and Smoothed Analysis

Abstract

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 \sigma + o(n\log \sigma )$ bits of space with a randomized algorithm having smoothed complexity $\mathcal {O}((2\sigma )^k(\log n)^k(\log m+\xi ) + (occ+1)\cdot m)$, where $\sigma$ is the alphabet size, $occ$ is the number of occurrences, and $\xi$ is a term depending on $m$, $n$, and on the amplitude $\epsilon$ of the noise perturbing text and pattern. Significantly, we obtain that for any $\epsilon >0$, for $m$ large enough, $\xi \in \mathcal {O}(\log m)$: our results improve upon previous linear-space solutions of the $k$-mismatch problem.