Modeling and extracting elements in semi-structured documents

• US 10,114,906 B1
• Filed: 07/31/2015
• Issued: 10/30/2018
• Est. Priority Date: 07/31/2015
• Status: Active Grant

• Current Assignee: Intuit, Inc.
• Original Assignee: Intuit, Inc.
• Inventors: Becker, Richard J., Gomes, Carolina Simoes, Moise, Daniel L., Chan, Horace
• Primary Examiner(s): Chad, Aniss
• Assistant Examiner(s): Luu, Cuong V
• Application Number:
  US14/814,977
• Time in Patent Office: 1,187 Days
• Field of Search: None
• CPC Class Codes: G06F 16/80 of semi-structured data, e.g. markup language structured data such as SGML, XML or HTML content-based retrieval of web data G06F16/95
• CPC Class Codes: G06F 30/20 Design optimisation, verification or simulation optimisation, verification or simulation of circuit designs G06F30/30
• CPC Class Codes: G06F 40/137 Hierarchical processing, e.g. outlines
• CPC Class Codes: G06Q 30/04 Billing or invoicing
• CPC Class Codes: G06Q 40/123 Tax preparation or submission

Abstract

The disclosed embodiments provide a system that describes a semi-structured document for the purpose of acquiring a set of data elements from the semi-structured document. During operation, the system obtains a physics model of a semi-structured document, wherein the physics model includes a set of relationships represented by physical objects that describe relative positions of a set of data elements in the semi-structured document. Next, the system applies the physics model to a representation of the semi-structured document to automatically extract a set of data from the representation. The system then provides the extracted set of data for use with one or more applications without requiring manual input of the data into the one or more applications.

Claims

1. A computer-implemented method for extracting a set of data elements from a representation of a semi-structured document based on a physics model describing the semi-structured document, the method comprising:

obtaining, by a computer system, a physics model of the semi-structured document, wherein the physics model comprises a set of relationships represented by physical objects connecting different data elements in the semi-structured document that describe relative positions of each data element in the set of data elements in the semi-structured document, wherein the physical objects describe a relationship between a first data element and a second data element in the semi-structured document as a function of a distance range between the first and second data elements and at least one of;

an orientation relationship of the first and second data elements, or

an angular displacement range between the first and second data elements, and

wherein obtaining the physics model of the semi-structured document comprises;

requesting, from a user via a graphical user interface (GUI) having one or more area selection tools for selecting data elements in the semi-structured document and one or more connector tools for defining relationships between data elements in the semi-structured document, information identifying a relationship between the first and second data elements in the semi-structured document; and

obtaining, through the GUI, the set of relationships among the relative positions of the set of data elements in the semi-structured document from the user by receiving information defining the first and second data elements and information identifying a physical construct representing a relationship between the first and second data elements, wherein the physical construct comprises one or more of;

a flexible component defining the distance range between the first and second elements as a function of a weight describing an amount of compression or stretching between the first and second elements, or

a rigid component defining the distance range between the first and second elements as a substantially fixed distance between the first and second elements;

extracting, by the computer systems, a set of data from the representation of the semi-structured document based on the physical model, wherein the representation of the semi-structured document comprises an electronic file, and wherein extracting the set of data comprises;

identifying a probable range of positions in the representation of the semi-structured document at which the second data element is located, relative to a position of the first data element in the representation of the semi-structured document, based on the physical object connecting the first and second data elements in the physics model;

identifying, within the probable range of positions, a position of the second data element in the representation of the semi-structured document;

extracting data associated with the second data element from information located at the identified position in the representation of the semi-structured document;

identifying, based on the identified position of the second data element and physical objects in the model describing relationships between the second data element and a plurality of other data elements, position information associated with the plurality of other data elements in the representation of the semi-structured document; and

extracting data associated with each of the plurality of other data elements from information located, in the representation of the semi-structured document, at the position information associated with each of the plurality of other data elements; and

upon extracting the set of data from the representation, inputting, by the computer systems, the extracted set of data to one or more applications without requiring manual input of the data into the one or more applications.

2. The computer-implemented method of claim 1, further comprising:

updating one or more parameters of the physics model based on a set of locations of the data elements in the representation.

3. The computer-implemented method of claim 1, wherein obtaining the physics model of the semi-structured document comprises:

using a statistical model to identify the set of relationships among the relative positions of the set of data elements in the semi-structured document.

4. The computer-implemented method of claim 3, wherein using the statistical model to identify the set of relationships among the relative positions of the set of data elements comprises:

using the statistical model to iteratively adjust the set of relationships based on a set of locations of the data elements in a set of representations of the semi-structured document.

5. The computer-implemented method of claim 1, wherein the set of data elements comprises:

a target data element comprising data to be used with the one or more applications; and

a marker data element comprising an identifiable feature in the semi-structured document.

6. The computer-implemented method of claim 5, wherein the physics model comprises a relationship between a first position of the target data element and a second position of the marker data element.

7. The computer-implemented method of claim 6, wherein the relationship comprises:

a horizontal component;

a vertical component; and

a weight.

8. The computer-implemented method of claim 7, wherein the relationship further comprises:

a direction.

9. The computer-implemented method of claim 5, wherein the identifiable feature comprises an image or text.

10. The computer-implemented method of claim 1, wherein applying the physics model to the representation of the semi-structured document to automatically extract the set of data from the representation comprises:

using the physics model to identify a location of a data element in the representation;

using the location of the data element and the set of relationships to identify additional locations of one or more additional data elements in the representation; and

using the location and the additional locations to extract the set of data from the representation.

11. The computer-implemented method of claim 10, wherein using the location of the data element and the set of relationships to identify the additional locations of the one or more additional data elements in the representation comprises:

using the location of the data element and one or more parameters of a relationship between the data element and another data element to define a region in the representation in which the other data element is located.

12. An apparatus, comprising:

one or more processors; and

memory storing instructions that, when executed by the one or more processors, cause the apparatus to;

obtain a physics model of a semi-structured document, wherein the physics model comprises a set of relationships represented by physical objects connecting different data elements in the semi-structured document that describe relative positions of each data element in a set of data elements in the semi-structured document, wherein the physical objects describe a relationship between a first data element and a second data element in the semi-structured document as a function of a distance range between the first and second data elements and at least one of;

an orientation relationship of the first and second data elements, or

an angular displacement range between the first and second data elements, and

wherein obtaining the physics model of the semi-structured document comprises;

requesting, from a user via a graphical user interface (GUI) having one or more area selection tools for selecting data elements in the semi-structured document and one or more connector tools for defining relationships between data elements in the semi-structured document, information identifying a relationship between the first and second data elements in the semi-structured document; and

obtaining, through the GUI, a set of relationships among the relative positions of the data elements in the semi-structured document from the user by receiving information defining the first and second data elements and information identifying a physical construct representing a relationship between the first and second data elements, wherein the physical construct comprises one or more of;

a flexible component defining the distance range between the first and second elements as a function of a weight describing an amount of compression or stretching between the first and second elements, or

a rigid component defining the distance range between the first and second elements as a substantially fixed distance between the first and second elements;

extract a set of data from a representation of the semi-structured document based on the physical model, wherein the representation of the semi-structured document comprises an electronic file, and wherein extracting the set of data comprises;

identifying a probable range of positions in the representation of the semi-structured document at which the second data element is located, relative to a position of the first data element in the representation of the semi-structured document, based on the physical object connecting the first and second data elements in the physics model;

identifying, within the probable range of positions, a position of the second data element in the representation of the semi-structured document;

extracting data associated with the second data element from information located at the identified position in the representation of the semi-structured document;

identifying, based on the identified position of the second data element and physical objects in the model describing relationships between the second data element and a plurality of other data elements, position information associated with the plurality of other data elements in the representation of the semi-structured document; and

extracting data associated with each of the plurality of other data elements from information located, in the representation of the semi-structured document, at the position information associated with each of the plurality of other data elements; and

upon extracting the set of data from the representation, input the extracted set of data to one or more applications without requiring manual input of the data into the one or more applications.

13. The apparatus of claim 12, wherein the memory further stores instructions that, when executed by the one or more processors, cause the apparatus to:

update the physics model based on a set of locations of the data elements in the representation.

14. The apparatus of claim 12, wherein obtaining the physics model of the semi-structured document comprises:

using a statistical model to identify the set of relationships among the relative positions of the set of data elements in the semi-structured document.

15. The apparatus of claim 14, wherein using the statistical model to identify the set of relationships among the relative positions of the set of data elements comprises:

using the statistical model to iteratively adjust the set of relationships based on a set of locations of the data elements in a set of representations of the semi-structured document.

16. The apparatus of claim 12, wherein the set of relationships comprises:

a distance component;

an angular component; and

a weight.

17. A non-transitory computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for extracting a set of data elements from a representation of a semi-structured document based on a physics model describing the semi-structured document, the method comprising:

obtaining, by a computer system, a physics model of the semi-structured document, wherein the physics model comprises a set of relationships represented by physical objects connecting different data elements in the semi-structured document that describe relative positions of each data element in the set of data elements in the semi-structured document, wherein the physical objects describe a relationship between a first data element and a second data element in the semi-structured document as a function of a distance range between the first and second data elements and at least one of;

an orientation relationship of the first and second data elements, or

an angular displacement range between the first and second data elements, and

wherein obtaining the physics model of the semi-structured document comprises;

requesting, from a user via a graphical user interface (GUI) having one or more area selection tools for selecting data elements in the semi-structured document and one or more connector tools for defining relationships between data elements in the semi-structured document, information identifying a relationship between the first and second data elements in the semi-structured document; and

obtaining, through the GUI, a set of relationships among the relative positions of the data elements in the semi-structured document from the user by receiving information defining the first and second data elements and information identifying a physical construct representing a relationship between the first and second data elements, wherein the physical construct comprises one or more of;

a flexible component defining the distance range between the first and second elements as a function of a weight describing an amount of compression or stretching between the first and second elements, or

a rigid component defining the distance range between the first and second elements as a substantially fixed distance between the first and second elements;

extracting, by the computer systems, a set of data from the representation of the semi-structured document based on the physical model, wherein the representation of the semi-structured document comprises an electronic file, and wherein extracting the set of data comprises;

identifying a probable range of positions in the representation of the semi-structured document at which the second data element is located, relative to a position of the first data element in the representation of the semi-structured document, based on the physical object connecting the first and second data elements in the physics model;

identifying, within the probable range of positions, a position of the second data element in the representation of the semi-structured document;

extracting data associated with the second data element from information located at the identified position in the representation of the semi-structured document;

identifying, based on the identified position of the second data element and physical objects in the model describing relationships between the second data element and a plurality of other data elements, position information associated with the plurality of other data elements in the representation of the semi-structured document; and

extracting data associated with each of the plurality of other data elements from information located, in the representation of the semi-structured document, at the position information associated with each of the plurality of other data elements; and

upon extracting the set of data from the representation, inputting, by the computer systems, the extracted set of data to one or more applications without requiring manual input of the data into the one or more applications.

18. The non-transitory computer-readable storage medium of claim 17, wherein the physics model is a Newtonian physics model.