REGULAR EXPRESSION OPTIMIZER

• US 20120005184A1
• Filed: 08/17/2010
• Published: 01/05/2012
• Est. Priority Date: 06/30/2010
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Thilagar, Parthiban, Anderson, Richard J. Jr., Wright, William A., Errede, Joseph E., Fry, Patrick H., Pfau, Raymond L., Skarpelos, Michael J.
• Granted Patent: US 9,507,880 B2
• Time in Patent Office: Days
• US Class Current: 707/706
• CPC Class Codes: G06F 16/90335 Query processing

Abstract

Systems, methods, and other embodiments associated with processing regular expressions are described. One example method includes analyzing a rule for a regular expression and deleting the regular expression.

Claims

1. A non-transitory computer-readable medium storing computer-executable instructions that when executed by a computer cause the computer to perform a method, the method comprising:

analyzing a rule to identify a regular expression; and

modifying the rule by deleting the regular expression from the rule.

2. The non-transitory computer-readable medium of claim 1, where the analyzing comprises parsing the rule to identify one or more regular expression quantifiers and one or more substrings search quantifiers;

and

where the modifying deletes the regular expression quantifiers to transform the rule to a substring search based on the one or more substring search quantifiers that does not contain a regular expression.

3. The non-transitory computer-readable medium of claim 1, where the analyzing comprises determining that the regular expression is a greedy quantifier;

and

where the deleting comprises deleting the greedy quantifier and replacing the greedy quantifier with a lazy quantifier or a possessive quantifier.

4. The non-transitory computer-readable medium of claim 1, where the analyzing comprises determining that the regular expression is a quantifier being a match all quantifier, an anchor quantifier, a wild card quantifier, or a zero-or-more quantifier;

and

where the deleting comprises deleting the quantifier where only a substring remains in the rule.

5. The non-transitory computer-readable medium of claim 1, where the analyzing comprises detecting an escaped regular expression delimiter in leading text of a filename;

and

removing the escaped regular expression delimiter from the filename where only the filename is searched as a substring search.

6. The non-transitory computer-readable medium of claim 1, further comprising:

determining whether the modified rule includes a remaining regular expression; and

if no regular expression remains in the modified rule, then diverting the modified rule from being executed by a regular expression search engine and executing the modified rule with a substring search engine.

7. A non-transitory computer-readable medium storing computer-executable instructions that when executed by a computer cause the computer to perform a method, the method comprising:

pre-processing a rule to identify regular expressions in the rule, where the rule is to be executed by a regular expression search engine; and

transforming the rule by modifying the regular expression from the rule and causing the transformed rule to be executed by a substring search engine.

8. The non-transitory computer-readable medium of claim 7, where if a match is found by the substring search engine, then remaining strings in the rule are executed by the regular expression search engine to determine additional pattern matches.

9. The non-transitory computer-readable medium of claim 7, where modifying the regular expression includes:

identifying an anchor quantifier and deleting the anchor quantifier from the rule.

10. The non-transitory computer-readable medium of claim 7, where modifying the regular expression includes:

identifying a zero-or more greedy quantifier and deleting the zero-or more greedy quantifier from the rule.

11. The non-transitory computer-readable medium of claim 7, where modifying the regular expression includes:

identifying a one-or-more greedy quantifier and deleting the one-or-more greedy quantifier from the rule.

12. The non-transitory computer-readable medium of claim 7, where modifying the regular expression includes:

identifying a match-all quantifier and deleting the match-all quantifier from the rule.

13. The non-transitory computer-readable medium of claim 7, where modifying the regular expression includes:

identifying leading text and trailing text in the regular expression; and

converting the regular expression into two substrings from the leading text and trailing text and performing substring searches without executing a regular expression search.

14. The non-transitory computer-readable medium of claim 7, where modifying the regular expression includes:

identifying a wild card quantifier and deleting the wild card quantifier from the rule.

15. The non-transitory computer-readable medium of claim 7, further comprising:

determining whether the modified rule causes a match with a string from an object; and

if a match is found, caching the object in a cache memory.

16. A method comprising:

analyzing a rule to identify a regular expression; and

modifying the rule by deleting the regular expression from the rule.

17. The method of claim 16, where the modifying deletes the regular expression quantifiers to transform the rule to a substring search based on the one or more substring search quantifiers that do not contain a regular expression.

18. The method of claim 16, where the analyzing comprises determining that the regular expression is a greedy quantifier;

and

where the deleting comprises deleting the greedy quantifier and replacing the greedy quantifier with a lazy quantifier or a possessive quantifier.

19. The method of claim 16, where the analyzing comprises identify two or more regular expression quantifiers;

and

where the deleting comprises replacing the two or more regular expression quantifiers with different quantifiers that produce the same search results.