Creation of structured data from plain text

• US 7,324,936 B2
• Filed: 03/05/2004
• Issued: 01/29/2008
• Est. Priority Date: 01/08/2001
• Status: Expired due to Term

• Current Assignee: Softface, Inc. (SAP SE)
• Original Assignee: Ariba Incorporated (SAP SE)
• Inventors: Carloni, Luca, McGreer, Patrick, Saldanha, Alexander
• Primary Examiner(s): Dorvil; Richemond
• Assistant Examiner(s): Han; Qi
• Application Number:
  US10/794,335
• Publication Number:
  US 20040172237A1
• Time in Patent Office: 1,425 Days
• Field of Search: 704 1- 10
• US Class Current: 704/9
• 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

1. A computerized method comprising:

tokenizing a plain text description;

creating parse trees from the tokenized plain text description based on grammar from a grammar storage area;

generating an instance tree from each parse tree based upon an application domain specific natural markup language provided by a natural markup language model module;

discarding each invalid or incomplete instance tree;

choosing an instance tree from remaining instance trees representing a best map based upon a cost function;

processing the best map with a domain markup language generator to generate a structured data representation.

2. The computerized method of claim 1, further comprising:

using the structured data representation to populate a database.

3. The computerized method of claim 1, further comprising:

using the structured data representation to query a database.

4. The computerized method of claim 1, further comprising:

using the structured data representation to invoke an application.

5. The computerized method of claim 1, wherein the cost function comprises choosing maps with less structure over maps with more created structure.

6. The computerized method of claim 1, wherein the cost function comprises:

(a) choosing maps that use the most tokens contained in compact groups over maps using fewer tokens spread further over text segments;

(b) choosing maps with the tightest possible bindings; and

(c) choosing maps that have fewer objects.

7. The computerized method of claim 1, wherein the cost function comprises:

(a) choosing a map with the most tokens;

(b) if maps are equal under (a), then choosing a map having a topmost expression farthest from a root of the map;

(c) if maps are equal under (a) and (b), then choosing a map with a least distance between tokens;

(d) if maps are equal under (a) through (c), then choosing a map with fewer objects created by enumerations;

(e) if maps are equal under (a) through (d), then choosing a map with fewer unused primitives;

(f) if maps are equal under (a) through (e), then choosing a map with fewer objects created by database lookup;

(g) if maps are equal under (a) through (f), then choosing a map with fewer natural markup language objects;

(h) if maps are equal under (a) through (g), then choosing a map with fewer inferred objects.

8. The computerized method of claim 7, wherein the cost function further comprises:

(i) if maps are equal under (a) through (h), then regarding all maps as equally valid.

9. The method of claim 1, wherein all possible parse trees from the tokenized plain text are created.

10. The computerized method of claim 1, further comprising:

representing all the parse trees in a single directed acyclic graph.

11. The computerized method of claim 1, wherein the grammar from the grammar storage area is context free.

12. A computer-implemented system, comprising:

a parser to create all parse trees from a tokenized plain text description based on grammar from a grammar storage area;

a mapper to (A) generate an instance tree from each parse tree based upon an application domain specific natural markup language provided by a natural markup language model module, (B) prune the instance trees, and (C) choose an instance tree from remaining instance trees representing a best map based on a cost function;

a domain markup language generator to process the best map to generate a domain markup language document.

13. The computer-implemented system of claim 12, further comprising:

a domain markup language processing system to receive the domain markup language document and generate a structured data representation.

14. The computer-implemented system of claim 12, further comprising:

an online dictionary that includes words in a natural language; and

a domain dictionary that includes terms specific to a domain.