Creation of structured data from plain text

• US 20030167266A1
• Filed: 01/08/2001
• Published: 09/04/2003
• Est. Priority Date: 01/08/2001
• Status: Active Grant

• Current Assignee: Ariba Incorporated (SAP SE)
• Original Assignee: Softface, Inc. (SAP SE)
• Inventors: McGeer, Patrick C., Carloni, Luca, Saldanha, Alexander
• Granted Patent: US 6,714,939 B2
• Time in Patent Office: Days
• US Class Current: 707/6
• CPC Class Codes: G06F 16/258 Data format conversion from or to a database
• CPC Class Codes: G06F 40/131 Fragmentation of text files, e.g. creating reusable text-blocks; Linking to fragments, e.g. using XInclude; Namespaces
• CPC Class Codes: G06F 40/143 Markup, e.g. Standard Generalized Markup Language [SGML] or Document Type Definition [DTD]
• CPC Class Codes: G06F 40/211 Syntactic parsing, e.g. based on context-free grammar [CFG] or unification grammars
• CPC Class Codes: G06F 40/30 Semantic analysis
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A method and system for converting plain text into structured data. Parse trees for the plain text are generated based on the grammar of a natural language, the parse trees are mapped on to instance trees generated based on an application-specific model. The best map is chosen, and the instance tree is passing to an application for execution. The method and system can be used both for populating a database and/or for retrieving data from a database based on a query.

Claims

9. A method for creating structured data representation from a plain text description for an application domain, the method comprising:

constructing a model which defines objects of the application domain and relationships between the objects, and identifies the objects with a vocabulary;

parsing the plain text using a grammar and the vocabulary to generate a parse tree;

mapping the parse tree onto an instance tree of objects of the application domain using the model; and

generating structured data based on the mapping.

10. A method for creating structured data representation from a plain text description for an application domain, the method comprising:

constructing a model which defines objects of the application domain and relationships between the objects, and identifies the objects with a vocabulary;

parsing the plain text using a grammar and the vocabulary to generate a plurality of parse trees;

generating, based on the model, a plurality of instance trees comprising an instance tree generated corresponding to each parse tree;

choosing one instance tree from the plurality of instance trees; and

generating structured data based on the chosen instance tree.

11. A method for creating structured data representation from a plain text description for an application, the method comprising:

constructing a model which defines objects of the application domain and relationships between the objects, and identifies the objects with a vocabulary;

parsing the plain text using a grammar and the vocabulary to generate a plurality of parse trees;

generating, based on the model, a plurality of instance trees comprising an instance tree generated corresponding to each parse tree;

pruning the plurality of instance trees to create a second plurality of instance trees;

choosing one instance tree from the second plurality of instance trees; and

generating structured data based on the chosen instance tree.

12. A system for creating structured data representation from a plain text description for an application domain, the system comprising:

a parser for parsing the plain text using a grammar and a vocabulary to generate a plurality of parse trees;

a mapper communicatively coupled to the parser for mapping the plurality of parse trees onto a plurality of instance trees based on a model which defines objects of the application domain and relationships between the objects, and identifies the objects with the vocabulary; and

an output simplifier communicatively coupled to the mapper, wherein instructions to the output simplifier are included in the model.

1. A method for creating structured data representation from a plain text description for an application domain, the method comprising:

constructing a model which defines objects of the application domain and relationships between the objects, and identifies the objects with a vocabulary;

parsing the plain text description using a grammar and the vocabulary to generate a plurality of parse trees;

mapping the plurality of parse trees onto a plurality of instance trees created using the model; and

generating structured data based on the mapping.

2. The method of claim 1, wherein all possible parse trees for the plain text are generated.

3. The method of claim 1, further comprising:

representing the plurality of parse trees generated in a single directed acyclic graph.

4. The method of claim 1, wherein the grammar used to generate the plurality of parse trees is context-free.

5. The method of claim 1, wherein the vocabulary used is a general vocabulary.

6. The method of claim 1, wherein the vocabulary used is specific to the application domain.

7. The method of claim 1, wherein mapping the plurality of parse trees onto instance trees comprises:

generating a plurality of instance trees based on the model;

pruning the plurality of generated instance trees by discarding incomplete instance trees, to create a second plurality of instance trees; and

choosing one instance tree from the second plurality of instance trees.

8. The method of claim 7, wherein choosing one instance tree from the second plurality of instance trees comprises:

choosing the instance tree which covers the maximum number of words of plain text.

13. The system of claim 12, further comprising:

a model storage communicatively coupled to the mapper for providing it with the model.

14. The system of claim 12, further comprising:

a grammar storage communicatively coupled to the parser for providing the parser with the grammar.

15. The method of claim 12, further comprising:

a vocabulary storage for storing general vocabulary.

16. The method of claim 12, wherein updating the vocabulary updates the model.

14-1. The method of claim 12, further comprising:

a vocabulary storage for storing vocabulary specific to the application.

17. A system for creating structured data representation from a plain text description for an application domain, the system comprising:

a content engine comprising;

a parser for parsing the plain text using a grammar and a vocabulary to generate a plurality of parse trees;

a mapper communicatively coupled to the parser, for mapping the plurality of parse trees onto a plurality of instance trees based on a model; and

an output simplifier communicatively coupled to the mapper, wherein instructions to the output simplifier are included in the model;

a grammar storage communicatively coupled to the content engine for providing the content engine with the grammar;

a model storage communicatively coupled to the content engine for providing the content engine with the model which defines objects of the application domain and relationships between the objects, and identifies the objects with a vocabulary; and

a vocabulary storage for providing the content engine with the vocabulary.

18. A system for creating structured data representation from a plain text description for an application domain, the system comprising:

a parser for parsing the plain text using a grammar and a vocabulary to generate a parse tree;

a mapper communicatively coupled to the parser for mapping the parse tree onto an instance tree based on a model which defines objects of the application domain and relationships between the objects, and identifies the objects with the vocabulary; and

an output simplifier communicatively coupled to the mapper, wherein instructions to the output simplifier are included in the model.

19. A computer program product for storing a program for permitting a computer to perform a method for creating structured data representation from a plain text description for an application domain, the method comprising:

constructing a model which defines objects of the application domain and relationships between the objects, and identifies the objects with a vocabulary;

parsing the plain text using a grammar and the vocabulary to generate a plurality of parse trees;

mapping the plurality of parse trees onto a plurality of instance trees created using the model; and

generating structured data based on the mapping.

20. A computer program product for storing a program for permitting a computer to perform a method for creating structured data representation from a plain text description for an application domain, the method comprising:

constructing a model which defines objects of the application domain and relationships between the objects, and identifies the objects with a vocabulary;

parsing the plain text using a grammar and the vocabulary to generate a parse tree;

mapping the parse tree onto an instance tree of objects of the application domain using the model; and

generating structured data based on the mapping.

21. A computer program product for storing a program for permitting a computer to perform a method for creating structured data representation from a plain text description for an application domain, the method comprising:

constructing a model which defines objects of the application domain and relationships between the objects, and identifies the objects with a vocabulary;

parsing the plain text using a grammar and the vocabulary to generate a plurality of parse trees;

generating, based on the model, a plurality of instance trees comprising an instance tree generated corresponding to each parse tree;

choosing one instance tree from the plurality of instance trees; and

generating structured data based on the chosen instance tree.

22. A computer program product for storing a program for permitting a computer to perform a method for creating structured data representation from a plain text description for an application, the method comprising:

constructing a model which defines objects of the application domain and relationships between the objects, and identifies the objects with a vocabulary;

parsing the plain text using a grammar and the vocabulary to generate a plurality of parse trees;

generating, based on the model, a plurality of instance trees comprising an instance tree generated corresponding to each parse tree;

pruning the plurality of instance trees to create a second plurality of instance trees;

choosing one instance tree from the second plurality of instance trees; and

generating structured data based on the chosen instance tree.