Methods and Apparatus for User-Guided Inference of Regular Expressions for Information Extraction

• US 20080133443A1
• Filed: 11/30/2006
• Published: 06/05/2008
• Est. Priority Date: 11/30/2006
• Status: Abandoned Application

• Current Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Flaster, Michael E., Bohannon, Philip L.
• Application Number:
  US11/565,213
• Publication Number:
  US 20080133443A1
• Time in Patent Office: Days
• US Class Current: 706/48
• CPC Class Codes: G06F 40/205 Parsing

Abstract

Methods and apparatus are provided for inferring regular expressions that parse and extract information from line-oriented data. A regular expression is generated that matches a line of text by: evaluating a plurality of characters of the line of text to identify one or more domains associated with each of the plurality of characters; assigning a run-length to each of the identified domains; populating a data structure having a data position corresponding to each of the characters with the identified domains and corresponding run-lengths; and generating the regular expression based on the data structure.

Claims

1. A method for generating a regular expression that matches a line of text, comprising:

evaluating a plurality of characters of said line of text to identify one or more domains associated with each of said plurality of characters;

assigning a run-length to each of said identified domains;

populating a data structure having a data position corresponding to each of said characters with said identified domains and corresponding run-lengths; and

generating said regular expression based on said data structure.

2. The method of claim 1, further comprising the step of stopping said evaluating step based on a plurality of characters.

3. The method of claim 1, wherein said evaluating step identifies the domains applicable to said plurality of characters based on a prioritization of said domains.

4. The method of claim 1, further comprising the step of generating one or more lines of code that allow information to be extracted from said line of text.

5. The method of claim 1, further comprising the step of generating one or more lines of code that allow information to be extracted from said line of text in a name/value pair format.

6. The method of claim 1, wherein said domains can be specified by a user.

7. A method for generating a regular expression that matches a line of text, comprising:

evaluating a plurality of characters of said line of text to identify one or more domains associated with each of said plurality of characters;

comparing said assigned domains to a plurality of regular expression patterns that have been established, each of said patterns associated with a different disjunct;

generating said regular expression based on said comparing step; and

adding a regular expression pattern for an additional disjunct by removing said lines of text that match said existing plurality of regular expression patterns and determining a regular expression pattern for said remaining lines of text.

8. The method of claim 7, wherein a maximum number of said disjuncts may be specified by a user.

9. A method for generating a regular expression that matches a line of text, comprising:

evaluating a plurality of characters of said line of text to identify sub-groups of characters that belong to one or more domains;

presenting said identified sub-groups of characters to a user for review;

allowing said user to adjust said sub-groups of characters using a visual interface; and

generating said regular expression based on said adjusted sub-groups of characters.

10. The method of claim 9, further comprising the step of stopping said evaluating step based on a plurality of characters.

11. The method of claim 9, wherein said evaluating step identifies the domains applicable to said plurality of characters based on a prioritization of said domains.

12. The method of claim 9, wherein said regular expression allows information to be extracted from said line of text.

13. The method of claim 9, wherein said domains can be specified by a user.

14. A system for generating a regular expression that matches a line of text, comprising:

a memory; and

at least one processor, coupled to the memory, operative to;

evaluate a plurality of characters of said line of text to identify one or more domains associated with each of said plurality of characters;

assign a run-length to each of said identified domains;

populate a data structure having a data position corresponding to each of said characters with said identified domains and corresponding run-lengths; and

generate said regular expression based on said data structure.

15. The system of claim 14, wherein said processor is further configured to stop said evaluating step based on a plurality of characters.

16. The system of claim 14, wherein said processor is further configured to identify the domains applicable to said plurality of characters based on a prioritization of said domains.

17. The system of claim 14, wherein said processor is further configured to generate one or more lines of code that allow information to be extracted from said line of text.

18. The system of claim 14, wherein said processor is further configured to generate one or more lines of code that allow information to be extracted from said line of text in a name/value pair format.

19. A system for generating a regular expression that matches a line of text, comprising:

a memory; and

at least one processor, coupled to the memory, operative to;

evaluate a plurality of characters of said line of text to identify sub-groups of characters that belong to one or more domains;

present said identified sub-groups of characters to a user for review;

allow said user to adjust said sub-groups of characters using a visual interface; and

generate said regular expression based on said adjusted sub-groups of characters.

20. The system of claim 19, wherein said domains can be specified by a user.