Patent Document ID: 9471715
Application ID: 13854105

Base Claim:
1. A method of evaluating a regular expression in computing, said method comprising: utilizing a processor to execute computer code configured to perform the steps of: receiving text strings; generating, using the received text strings and a list of regular expression meta-characters, a data structure containing a plurality of grams with positional information identifying a location of each of the plurality of grams within the received text strings, wherein the grams are of a certain character length based upon an input gram length; receiving a query comprising a regular expression, wherein the regular expression comprises a pattern for recognizing at least one text string from among the received text strings; converting the regular expression into a gram-constrained parse tree comprising nodes comprising character classes and nodes comprising a gram having a character length equal to the input gram length; generating a positional index query based on the gram-constrained parse tree; and identifying, within the data structure, a subset of the text strings comprising at least one match for the query, wherein the identifying comprises filtering the data structure by executing the positional index query on the data structure to generate a list of candidate text strings and filtering the list of candidate text strings against the regular expression to generate the subset of text strings.

---

Claim 3:
3. The method according to claim 1 , wherein said generating comprises building an inverted index containing the grams along with positional information related to the grams.