IP Library Granted Patent US 7,324,936
Granted Patent B2
US 7,324,936 · App. 10/794,335 · Granted Jan 29, 2008

Creation of structured data from plain text

Assignee: Ariba, Inc.
View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 7,324,936
App. No.
10/794,335
Granted
Jan 29, 2008
Kind
B2
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 (42)

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.

Assignments (1)
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Aug 1, 2005
From: SOFTFACE, INC.
To: SOFTFACE, INC.
Reel/Frame 016826/0143 →
Continuity (2)
Continuation 0975707500 · Jan 8, 2001
Related Publication 20040172237A1 · Sep 2, 2004