Patent Document ID: 6131092
Application ID: 08274123

Base Claim:
1. A text pattern matching system for identifying ones of a plurality of documents in a document text base which satisfy a query, each of said documents comprising a series of ordered text symbols, with each text symbol being represented by a text token, each query comprising a series of query symbols, with each query symbol being represented by a query token, said text pattern matching system comprising: A. a match token generator for generating a match token for each text token whose text symbol corresponds to a query token's query symbol, the match token generator associating each match token with (i) document identifier information identifying one of said documents containing the text symbol corresponding to the query symbol, (ii) text symbol sequence information identifying the position of the text symbol in the series of text symbols which comprise the document, and (iii) query symbol sequence information identifying the position of the query symbol in the series of query symbols which comprise the query; B. a match token sorter for sorting match tokens generated by said match token generator according to the document identifier information and the text symbol sequence information associated therewith; and C. a query processor for identifying, using the query symbol sequence information associated with the match tokens as sorted by the match token sorter, sequences of match tokens relating to a query which satisfy the query, the document identifier information of match tokens in the identified sequences of match tokens identifying the documents that satisfy the query.

---

Claim 4:
4. A text pattern matching system as defined in claim 1 in which said query processor includes: A. a match token query begin sequence identifier for identifying one of said match tokens whose query symbol sequence information identifies the match token as having a query symbol corresponding to an initial query symbol in the query; B. a match token query end sequence identifier for identifying one of said match tokens whose query symbol sequence information identifies the match token as having a query symbol corresponding to a final query symbol in the query; C. a match token sequence processor for determining whether the document identifier information and the text symbol sequence information of proximate match tokens in the sorted order established by the match token sorter satisfies a selected query criterion; and D. a query processor controller for enabling said match token query begin sequence identifier, said match token query end sequence identifier and said match token sequence processor to operate in connection with successive match tokens in the sorted order established by said match token sorter, the query processor controller: i. enabling said match token query begin sequence identifier to operate to identify a match token whose query symbol sequence information identifies the match token as having a query symbol corresponding to an initial query symbol in the query; ii. enabling said match token sequence processor, beginning with the match token identified by said match token query begin sequence identifier, in a series of iterations, to determine whether the document identifier information and the text symbol sequence information of each successive match tokens, in the order established by the match token sorter, satisfies the selected query criterion with the document identifier information and the text symbol sequence information of a previous match token, the query processor controller enabling the match token sequence detector to iteratively operate in response to a positive determination in each iteration, and otherwise enabling said match token query begin identifier to operate; iii. enabling said match token query end identifier to, in response to each positive determination by said match token sequence detector, determine whether the match token for which the match token sequence detector generated the positive determination includes query symbol sequence information that identifies the match token as having a query symbol corresponding to an end query symbol in the query, the query processor controller, in response to a positive determination by said match token query end identifier, identifying the series of match tokens from the match token for which the match token query end identifier generated the positive determination and the match token identified by the match token query begin identifier as satisfying the query.