A scaleable technique for best-match retrieval of sequential information using metrics-guided search

Abstract

A new technique is described for retrieving infor mation by finding the best match or matches between a textual 'query' and a textual database. The technique uses principles of beam search with a measure of probability to guide the search and prune the search tree. Unlike many methods for comparing strings, the method gives a set of alternative matches, graded by the 'quality' of the matching achieved.