Patent ID: 8548979

Claim:
A method for building an electronic index to support efficient evaluation of complex regular expressions, comprising: extracting index terms from a collection of documents to create an electronic index based upon metadata associated with the index terms, wherein each index term is a sequence of characters and character classes, each character class being a variable representing all characters from a pre-determined set of characters; receiving a query regular expression, wherein the query regular expression is composed of characters, character classes, quantifiers, and disjunctions, each quantifier identifying a minimum and maximum number of occurrences for an associated character class; and converting the query regular expression into a set of disjunct-free regular expressions comprising: identifying in the query regular expression groups containing disjunctions and quantifiers; unrolling a group containing a quantifier until a selective constraint is obtained for each subgroup within the group; and expanding each group containing a disjunction to obtain a set of disjunct-free regular expressions.