An algebra for structured text search
Gordon V. Cormack, Charles L. A. Clarke · 1996
Querying a collection of text may be abstractly viewed as applying a search predicate to all substrings of the text and selecting those substrings that satisfy the predicate as solutions to the query. A single additional restriction is added to this simple model: The substrings accepted as solutions must not properly contain other substring that satisfy the query. The focus of the thesis is on the properties and applications of this shortest substring search model. The primary contribution of the thesis is an algebra for structured text search and its implementation framework. The algebra manipulates arbitrary intervals of text, which are recognized in the text from implicit or explicit markup. The algebra has seven basic operators, which combine intervals to yield new ones. The ultimate result of a query is the set of intervals that satisfy it. Implementation is based on four primitive access functions. Recursive definitions for the operators are given in terms of these access functions. A realization of the implementation in terms of inverted lists is examined. The model is also applied to the general problem of pattern matching in strings, and specifically to the problem of regular expression search. An implementation framework for scanning text with the search algebra is developed. Finally, properties of the model are exploited to develop a new technique for ranking query results according to relevance.