METHOD AND SYSTEM FOR AUTOMATICALLY GENERATING REGULAR EXPRESSIONS FOR RELAXED MATCHING OF TEXT PATTERNS

• US 20090070328A1
• Filed: 05/22/2008
• Published: 03/12/2009
• Est. Priority Date: 09/06/2007
• Status: Active Grant

• Current Assignee: Alexander Stephan Loeser, Shivakumar Vaithyanathan, Sriram Raghavan
• Original Assignee: Alexander Stephan Loeser, Shivakumar Vaithyanathan, Sriram Raghavan
• Inventors: Loeser, Alexander Stephan, Vaithyanathan, Shivakumar, Raghavan, Sriram
• Granted Patent: US 8,484,238 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/3329 Natural language query formulation or dialogue systems
• CPC Class Codes: G06F 16/3338 Query expansion

Abstract

A method and system for automatically generating regular expressions for relaxed matching of text patterns. A received input phrase expressed in a natural language is determined to be a plain text pattern. The plain text pattern is automatically tokenized, thereby generating a first token list. Rules loaded from a predefined rule set are automatically applied to the first token list to automatically generate a modified token list. The order of the rules being applied to the first token list is specified by the rule set. The modified token list is automatically converted into a regular expression that matches the plain text pattern and one or more variations of the plain text pattern. A utilization of the regular expression for an information extraction facilitates a recall and a precision of the information extraction.

Claims

1. A computer-implemented method of automatically generating regular expressions for relaxed matching of text patterns, comprising:

receiving, by a computing system, an input phrase expressed in a natural language;

determining, by said computing system, that said input phrase is a plain text pattern;

automatically tokenizing, by said computing system, said plain text pattern, wherein said automatically tokenizing includes automatically generating a first token list;

automatically applying, by said computing system, one or more rules to said first token list, wherein said automatically applying includes automatically modifying said first token list and automatically generating a modified token list in response to said automatically modifying said first token list; and

automatically converting, by said computing system, said modified token list into a regular expression, wherein said regular expression matches said plain text pattern and one or more variations of said plain text pattern.

2. The method of claim 1, further comprising loading, by said computing system, a predefined set of rules from a rule file in a repository coupled to said computing system, wherein said predefined set of rules includes said one or more rules, and wherein said automatically applying further includes applying said one or more rules in an order specified by said predefined set of rules.

3. The method of claim 2, wherein each rule of said set of rules is expressed in an Extensible Markup Language (XML) format.

4. The method of claim 1, wherein a rule of said one or more rules includes a predefined modification operator of a set of modification operators, and wherein said automatically modifying said first token list includes applying said predefined modification operator to said first token list.

5. The method of claim 4, wherein said predefined modification operator is a replace word operator, and wherein said automatically modifying said first token list further includes replacing a sequence of one or more tokens in said first token list with a replacement regular expression specified by said rule.

6. The method of claim 4, wherein said predefined modification operator is a split-at-character operator, and wherein said automatically modifying said first token list further includes detecting a character specified by said rule and splitting a token of said first token list into two tokens in response to said detecting said character.

7. The method of claim 4, wherein said predefined modification operator is a whitespace operator, and wherein said automatically modifying said first token list further includes replacing whitespace in said first token list with a replacement regular expression specified by said rule.

8. The method of claim 1, further comprising utilizing said regular expression for an information extraction, wherein said automatically converting said modified token list into said regular expression facilitates a recall and a precision of said information extraction, wherein said recall is associated with a detection of said plain text pattern and said one or more variations, and wherein said precision is associated with avoiding a detection of spurious instances of said plain text pattern and said one or more variations.

9. The method of claim 1, wherein said determining that said input phrase is said plain text pattern includes determining that said input phrase is not a regular expression.

10. The method of claim 1, further comprising automatically learning, by a software-based rule learning component of said computing system, said one or more rules based on information processed by an information extraction system implemented by said computing system.

11. A computing system comprising a processor coupled to a computer-readable memory unit, said memory unit comprising a software application, said software application comprising instructions that when executed by said processor implement the method of claim 1.

12. A computer program product, comprising a computer usable medium having a computer readable program code embodied therein, said computer readable program code containing instructions that when executed by a processor of a computing system implement a method for automatically generating regular expressions for relaxed matching of text patterns, said method comprising:

receiving an input phrase expressed in a natural language;

determining that said input phrase is a plain text pattern;

automatically tokenizing said plain text pattern, wherein said automatically tokenizing includes automatically generating a first token list;

automatically applying one or more rules to said first token list, wherein said automatically applying includes automatically modifying said first token list and automatically generating a modified token list in response to said automatically modifying said first token list; and

automatically converting said modified token list into a regular expression, wherein said regular expression matches said plain text pattern and one or more variations of said plain text pattern.

13. The program product of claim 12, wherein said method further comprises loading a predefined set of rules from a rule file in a repository, wherein said predefined set of rules includes said one or more rules, and wherein said automatically applying further includes applying said one or more rules in an order specified by said predefined set of rules.

14. The program product of claim 13, wherein each rule of said set of rules is expressed in an Extensible Markup Language (XML) format.

15. The program product of claim 12, wherein a rule of said one or more rules includes a predefined modification operator of a set of modification operators, and wherein said automatically modifying said first token list includes applying said predefined modification operator to said first token list.

16. The program product of claim 15, wherein said predefined modification operator is a replace word operator, and wherein said automatically modifying said first token list further includes replacing a sequence of one or more tokens in said first token list with a replacement regular expression specified by said rule.

17. The program product of claim 15, wherein said predefined modification operator is a split-at-character operator, and wherein said automatically modifying said first token list further includes detecting a character specified by said rule and splitting a token of said first token list into two tokens in response to said detecting said character.

18. The program product of claim 15, wherein said predefined modification operator is a whitespace operator, and wherein said automatically modifying said first token list further includes replacing an occurrence of whitespace in said first token list with a replacement regular expression specified by said rule.

19. The program product of claim 12, wherein said method further comprises utilizing said regular expression for an information extraction, wherein said automatically converting said modified token list into said regular expression facilitates a recall and a precision of said information extraction, wherein said recall is associated with a detection of said plain text pattern and said one or more variations, and wherein said precision is associated with avoiding a detection of spurious instances of said plain text pattern and said one or more variations.

20. The program product of claim 12, wherein said determining that said input phrase is said plain text pattern includes determining that said input phrase is not a regular expression.