Efficient algorithms for document retrieval problems
Subramanian Muthukrishnan · 2002
Abstract We are given a collection D of text documents d1; : : : ; dk, withP i jdij = n, which may be preprocessed. In the documentlisting problem, we are given an online query comprising of a pattern string p of length m and our goal is to return the set ofall documents that contain one or more copies of p. In the closelyrelated occurrence listing problem, we output the set of all positions within the documents where pattern p occurs. In 1973, Weiner [24]presented an algorithm with O(n) time and space preprocessingfollowing which the occurrence listing problem can be solved in time O(m + output) where output is the number of positionswhere p occurs; this algorithm is clearly optimal. In contrast,no optimal algorithm is known for the closely related document listing problem, which is perhaps more natural and certainly well-motivated.