کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
430902 | 688228 | 2013 | 7 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Compressed text indexing with wildcards Compressed text indexing with wildcards](/preview/png/430902.png)
Let T=T1ϕk1T2ϕk2⋯ϕkdTd+1T=T1ϕk1T2ϕk2⋯ϕkdTd+1 be a text of total length n , where characters of each TiTi are chosen from an alphabet Σ of size σ, and ϕ denotes a wildcard symbol. The text indexing with wildcards problem is to index T such that when we are given a query pattern P, we can locate the occurrences of P in T efficiently. This problem has been applied in indexing genomic sequences that contain single-nucleotide polymorphisms (SNP) because SNP can be modeled as wildcards. Recently Tam et al. (2009) and Thachuk (2011) have proposed succinct indexes for this problem. In this paper, we present the first compressed index for this problem, which takes only nHh+o(nlogσ)+O(dlogn) bits of space, where HhHh is the h th-order empirical entropy (h=o(logσn)) of T.
Journal: Journal of Discrete Algorithms - Volume 19, March 2013, Pages 23–29