System and method for creating pattern-recognizing computer structures from example text

• US 5,864,789 A
• Filed: 06/24/1996
• Issued: 01/26/1999
• Est. Priority Date: 06/24/1996
• Status: Expired due to Term

• Current Assignee: Apple Computer Incorporated (Apple Inc.)
• Original Assignee: Apple Computer Incorporated (Apple Inc.)
• Inventors: Wright, David J., Lieberman, Henry A., Nardi, Bonnie A.
• Primary Examiner(s): Dorvil, Richemond
• Assistant Examiner(s): Edouard, Patrick N.
• Application Number:
  US08/669,642
• Time in Patent Office: 946 Days
• Field of Search: 704/1, 704/8-9, 704/243, 704/244, 707/1-2, 707/6, 707/100-103, 707/513
• US Class Current: 704/9
• CPC Class Codes: G06F 40/166 Editing, e.g. inserting or deleting
• CPC Class Codes: G06F 40/289 Phrasal analysis, e.g. finite state techniques or chunking
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

A system comprises a structure editor, a structure library, an extractor and a user interface, which are stored in computer memory and create structures for recognizing patterns in computer text. The structure editor via the user interface enables a user to input a text string called a model pattern, and uses previously-created structures such as lexical category structures for parsing the model pattern into default definition items. Each default definition item includes attributes specifying the patterns recognizable by the definition item and relationships with other definition items. The structure editor enables and facilitates user modification of the default definition items by generating attribute choices for user selection and allowing a user to generate a new structure if none of the choices is adequate. The resulting definition items form a new definition of a new structure, which is stored in the structure library. The extractor locates a pattern in computer text by satisfying the conditions of a definition of a new structure.

Claims

1. A computer-based method for using a model pattern to create a structure to identify patterns in computer text, the method comprising the steps of:

inputting a model pattern;

parsing the model pattern into components based on previously-created structures;

generating user-modifiable default definition items based on the components, wherein the default definition items specify a definition of a new structure; and

identifying patterns in computer text based on the new structure.

2. The method of claim 1, wherein the previously-created structures comprise lexical category structures.

3. The method of claim 1, wherein the model pattern is obtained by inputting a string of computer text.

4. The method of claim 1, wherein each definition item includes a structure reference attribute denoting a set of patterns that are recognized by the definition item.

5. The method of claim 4, further comprising, after the step of generating and before the step of identifying, the step of modifying the structure reference attributes.

6. The method of claim 4, further comprising, after the step of generating and before the step of identifying, the steps of:

providing choices for redefining the structure reference attribute;

enabling user selection of one of the choices; and

modifying the structure reference attribute to refer to the selected choice.

7. The method of claim 6, further comprising the steps of:

generating another new structure; and

modifying the structure reference attribute to refer to the other new structure.

8. The method of claim 1, wherein each definition item includes a structure reference attribute denoting a set of patterns that are recognized by the definition item, and wherein the definition item comprises further attributes selected from the group consisting of "optional", "repeating", "order independent", and "constraints".

9. A computer-based system for creating a structure to identify patterns in computer text based on a model pattern, the system comprising:

a central processor unit for processing computer text;

input means coupled to the central processor unit for receiving information from a user;

display means coupled to the central processor unit for displaying information to a user; and

a memory coupled to the central processor unit, wherein the memory contains stored computer text, and further contains information comprising;

a structure library containing previously-created structures;

a structure editor containing program instructions for enabling input of a model pattern through said input means, parsing the model pattern into components based on the previously-created structures, and generating user-modifiable default definition items based on the components, wherein the default definition items specify a first definition of a new structure; and

an extractor containing program instructions for identifying patterns in the stored computer text based on the new structure.

10. The system of claim 9, wherein the previously-created structures include lexical category structures.

11. The system of claim 10, wherein the lexical category structures include structures for recognizing numbers, letters, punctuation, spaces, tabs, and carriage returns.

12. The system of claim 9, wherein each definition item includes a structure reference attribute denoting a set of patterns that are recognized by the definition item.

13. The system of claim 12, wherein the component of the model pattern corresponding to the definition item is a member of the set of patterns.

14. The system of claim 12, further comprising a user interface containing program instructions for enabling user modification of the structure reference attribute by the input means and display means.

15. The system of claim 14, wherein the user interface enables user creation of another structure and modification of the structure reference attribute to refer to the other structure.

16. The system of claim 9, wherein the previously-created structures include lexical category structures, and each definition item includes a structure reference attribute denoting a set of patterns that are recognized by the definition item.

17. The system of claim 16, wherein the default value of each structure reference attribute refers to the lexical category structures.

18. The system of claim 9, wherein each definition item includes a structure reference attribute denoting a set of patterns that are recognized by the definition item, and wherein the definition item comprises further attributes selected from the group consisting of "optional", "repeating", "order independent", and "constraints".

19. The system of claim 18, wherein the default values of the further attributes are "NO".

20. The system of claim 9, wherein each definition item includes a structure reference attribute denoting a set of patterns that are recognized by the definition item, and further comprising a user interface for generating choices to redefine each structure reference attribute and for displaying the choices by the display means for selection by the input means.

21. The system of claim 20, wherein the choices include the component corresponding to the selected definition item.

22. The system of claim 20, wherein the choices include all previously created structures recognizing the component of the model pattern corresponding to the definition item.

23. The system of claim 9, wherein each structure includes a label, and wherein the structure editor generates alternative definitions for a structure by assigning the same label to different definitions.

24. A program storage medium having a program stored therein for causing a computer to perform the steps of:

inputting a model pattern;

parsing the model pattern into components based on previously-created structures;

generating default definition items based on the components, wherein the default definition items specify a definition of a new structure;

enabling user modification of the default definition items; and

identifying patterns in computer text based on the new structure.