Constructing Antidictionaries in Output-Sensitive Space

Abstract

A word $x$ that is absent from a word $y$ is called minimal if all its proper factors occur in $y$. Given a collection of $k$ words $y_1,y_2,\dots ,y_k$ over an alphabet $\Sigma$, we are asked to compute the set ${\mathrm{M}}_{y_1\#\dots \#y_k}^{\ell }$ of minimal absent words of length at most $\ell$ of word $y=y_1\#y_2\#\dots \#y_k$, $\#\notin \Sigma$. In data compression, this corresponds to computing the antidictionary of $k$ documents. In bioinformatics, it corresponds to computing words that are absent from a genome of $k$ chromosomes. This computation generally requires $\Omega (n)$ space for $n=|y|$ using any of the plenty available $\mathcal{O}(n)$-time algorithms. This is because an $\Omega (n)$-sized text index is constructed over $y$ which can be impractical for large $n$. We do the identical computation incrementally using output-sensitive space. This goal is reasonable when $||{\mathrm{M}}_{y_1\#\dots \#y_N}^{\ell }||=o(n)$, for all $N\in [1,k]$. For instance, in the human genome, $n\approx 3\times 10^9$ but $||{\mathrm{M}}_{y_1\#\dots \#y_k}^{12}||\approx 10^6$. We consider a constant-sized alphabet for stating our results. We show that all ${\mathrm{M}}_{y_1}^{\ell },\dots ,{\mathrm{M}}_{y_1\#\dots \#y_k}^{\ell }$ can be computed in $\mathcal{O}(kn+{\sum }_{N=1}^k||{\mathrm{M}}_{y_1\#\dots \#y_N}^{\ell }||)$ total time using $\mathcal{O}(\mathrm{MaxIn}+\mathrm{MaxOut})$ space, where $\mathrm{MaxIn}$ is the length of the longest word in $\{y_1,\dots ,y_k\}$ and $\mathrm{MaxOut}=\max \{||{\mathrm{M}}_{y_1\#\dots \#y_N}^{\ell }||:N\in [1,k]\}$. Proof-of-concept experimental results are also provided confirming our theoretical findings and justifying our contribution.

Version accepted to DCC 2019