کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
436303 | 689986 | 2014 | 8 صفحه PDF | دانلود رایگان |
Text indexing is a fundamental problem in computer science, where the task is to index a given text (string) T[1..n]T[1..n], such that whenever a pattern P[1..p]P[1..p] comes as a query, we can efficiently report all those locations where P occurs as a substring of T. In this paper, we consider the case when P contains wildcard characters (which can match with any other character). The first non-trivial solution for the problem was given by Cole et al. [11], where the index space is O(nlogkn)O(nlogkn) words or O(nlogk+1n)O(nlogk+1n) bits and the query time is O(p+2hloglogn+occ)O(p+2hloglogn+occ), where k is the maximum number of wildcard characters allowed in P , h≤kh≤k is the number of wildcard characters in P and occ represents the number of occurrences of P in T . Even though many indexes offering different space-time trade-offs were later proposed, a clear improvement on this result is still not known. In this paper, we first propose an O(nlogk+ϵn)O(nlogk+ϵn) bits index achieving the same query time as the of Cole et al.'s index, where 0<ϵ<10<ϵ<1 is an arbitrary small constant. Then we propose another index of size O(nlogknlogσ)O(nlogknlogσ) bits, but with a slightly higher query time of O(p+2hlogn+occ)O(p+2hlogn+occ), where σ denotes the alphabet set size.We also study a related problem, where the task is to index a collection of documents (of n characters in total) so as to find the number of distinct documents containing a query pattern P. For the case where P contains at most a single wildcard character, we propose an O(nlogn)O(nlogn)-word index with optimal O(p)O(p) query time.
Journal: Theoretical Computer Science - Volume 557, 6 November 2014, Pages 120–127