\input zb-basic
\input zb-ioport
\iteman{io-port 05609198}
\itemau{Tam, Alan; Wu, Edward; Lam, Tak-Wah; Yiu, Siu-Ming}
\itemti{Succinct text indexing with wildcards.}
\itemso{Karlgren, Jussi (ed.) et al., String processing and information retrieval. 16th international symposium, SPIRE 2009, Saariselk\"a, Finland, August 25--27, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-03783-2/pbk). Lecture Notes in Computer Science 5721, 39-50 (2009).}
\itemab
Summary: A succinct text index uses space proportional to the text itself, say, two times $n \log \sigma $ for a text of $n$ characters over an alphabet of size $\sigma $. In the past few years, there were several exciting results leading to succinct indexes that support efficient pattern matching. In this paper we present the first succinct index for a text that contains wildcards. The space complexity of our index is $(3 + o(1))n \log \sigma + O(\ell \log n)$ bits, where $\ell $ is the number of wildcard groups in the text. Such an index finds applications in indexing genomic sequences that contain single-nucleotide polymorphisms (SNP), which could be modeled as wildcards. In the course of deriving the above result, we also obtain an alternate succinct index of a set of $d$ patterns for the purpose of dictionary matching. When compared with the succinct index in the literature, the new index doubles the size (precisely, from $n \log \sigma $ to $2 n \log \sigma $, where $n$ is the total length of all patterns), yet it reduces the matching time to $O(m \log \sigma + m \log d + \text{occ})$, where $m$ is the length of the query text. It is worth-mentioning that the time complexity no longer depends on the total dictionary size.
\itemrv{~}
\itemcc{}
\itemut{}
\itemli{doi:10.1007/978-3-642-03784-9\_5}
\end