Intelligent extraction and organization of data from unstructured documents

• US 10,296,578 B1
• Filed: 02/20/2018
• Issued: 05/21/2019
• Est. Priority Date: 02/20/2018
• Status: Active Grant

• Current Assignee: Paycor, Inc.
• Original Assignee: Paycor, Inc.
• Inventors: Maslin, Matt
• Primary Examiner(s): Hong, Stephen S
• Assistant Examiner(s): Roy, Sanchita
• Application Number:
  US15/900,311
• Time in Patent Office: 455 Days
• Field of Search: None
• CPC Class Codes: G06F 16/353 into predefined classes
• CPC Class Codes: G06F 40/18 of spreadsheets form-filling G06F40/174
• CPC Class Codes: G06V 30/414 Extracting the geometrical structure, e.g. layout tree; Block segmentation, e.g. bounding boxes for graphics or text

Abstract

Data elements from an input document can be automatically organized into rows and columns in a structured output document using a grouping process that automatically applies matching criteria based on horizontal position, data content and horizontal extent and tests for horizontal overlaps between data elements and neighbors of data elements in existing groups, assigns columns to those groups based on horizontal positions of data elements from groups that have already been assigned to columns. Rows may be assigned to data elements based on those data elements'"'"' vertical positions.

Claims

1. A system comprising a computer configured with instructions encoded on a non-transitory computer readable medium, the instructions operable to, when executed, cause the computer to perform acts comprising:

a) organizing a plurality of data elements from an input document into a set of groups by repeatedly, until satisfaction of a completion condition, performing a grouping process comprising;

i) performing a matching determination of whether a subject data element satisfies a matching criterion for an existing group;

ii) performing an overlap determination of whether the subject data element is associated with a horizontal extent that overlaps a horizontal neighbor of one of the existing group'"'"'s data elements; and

iii) selectively adding the subject data element to the existing group based on the matching determination and the overlap determination, wherein when the subject data element is associated with a horizontal extent that overlaps a horizontal neighbor of one of the existing group'"'"'s data elements the subject data element is excluded from the existing group;

b) assigning each group from the set of groups to a column based on horizontal positions of data elements from groups that have already been assigned to columns;

c) for each data element, assigning that data element to a row based on that data element'"'"'s vertical position; and

d) for each data element, adding that data element to a structured document in the row assigned to that data element and in the column assigned to the group which comprises that data element;

wherein each data element has data comprising one or more non-whitespace characters.

2. The system of claim 1, wherein:

no matching criteria used on a particular repetition of the grouping process is more exclusive than any matching criteria used on a repetition of the grouping process that precedes the particular repetition, such that for each existing group on the particular repetition of the grouping process, all data elements which satisfy the matching criteria for that existing group on the particular repetition also satisfy any matching criteria used on any repetition subsequent to the particular repetition for that existing group.

3. The system of claim 2, wherein the matching criteria used in repeating the grouping process comprise:

a) a first matching criterion satisfied based on the subject data element having data and horizontal position matching the existing group;

b) a second matching criterion satisfied based on the subject data element having data type, horizontal position and horizontal extent matching the existing group;

c) a third matching criterion satisfied based on the subject data element having data type and horizontal position matching the existing group and horizontal extent matching the existing group within an extent offset;

d) a fourth matching criterion satisfied based on the subject data element having horizontal position matching the existing group; and

e) a fifth matching criterion satisfied based on the subject data element having a horizontal position matching the existing group within a position offset.

4. The system of claim 3, wherein repeatedly performing the grouping process comprises:

a) performing the matching determination a first time with the third matching criterion with a first extent offset; and

b) performing the matching determination a second time with the third matching criterion with a second extent offset.

5. The system of claim 1, wherein adding the subject data element to the existing group is performed by a group combination process comprising adding all data elements in a group that comprises the subject data element to the existing group.

6. The system of claim 5, wherein:

a) the existing group and the group that comprises the subject data element are each associated with

i) a preceding whitespace extent that includes only whitespace between data elements comprised by that group and that group'"'"'s data elements'"'"' left neighbors;

ii) a data element extent that horizontally encompasses all data elements comprised within that group;

iii) a subsequent whitespace extent that includes only whitespace between data elements comprised by that group and that group'"'"'s data elements'"'"' right neighbors;

 

and

b) the overlap determination is performed based on

i) comparing the data element extent of the existing group with the preceding whitespace extent and subsequent whitespace extent of the group that comprises the subject data element; and

ii) comparing the data element extent of the group that comprises the subject data element with the preceding whitespace extent and subsequent whitespace extent of the existing group.

7. The system of claim 1, wherein assigning each group from the set of groups to a column based on horizontal positions of data elements from groups that have already been assigned to columns comprises, for each group:

a) determining if any data element in that group shares a row with any data element in any other group that has already been assigned a column; and

b) in the event that any data element in that group shares a row with any data element in any other group that has already been assigned a column, assign that group to the first column following a rightmost column assigned to a group comprising a data element with a shared row.

16. The system of claim 1, wherein:

a) a plurality of different matching criteria are used in repeating the grouping process; and

b) the completion condition is satisfied when each matching criterion of the plurality of different matching criteria, has been applied to each data element.

17. The system of claim 16 wherein, for each data element and each matching criterion, that matching criterion is applied to that data element by applying that matching criterion to a group comprising that data element.

8. A method for automatically organizing data from one or more input documents into rows and columns in a structured output document, the method comprising:

a) obtaining a set of matching criteria that define matches based on horizontal position, data content and horizontal extent associated with data elements;

b) obtaining a plurality of data elements from an input document corresponding to information for rows and columns in the structured output document;

c) generating a set of data element groups by repeatedly, until satisfaction of a completion condition, applying the set of matching criteria to the data elements and testing for horizontal overlaps between data elements and neighbors of data elements in existing groups; and

d) applying the data elements and set of data element groups, respectively, to rows and columns of the output document to generate a structured output document with columns extending vertically across any internal headings in the one or more input documents that extend across multiple columns;

wherein each data element has data comprising one or more non-whitespace characters.

9. The method of claim 8, wherein repeatedly applying the set of matching criteria to the data elements comprises applying a first matching criterion to the set of data elements and subsequently applying a second matching criterion to the set of data elements, wherein all data elements that satisfy the first matching criterion also satisfy the second matching criterion.

10. The method of claim 9, wherein:

a) the first matching criteria is satisfied based on matching data and horizontal position;

b) the second matching criteria is satisfied based on matching data type, horizontal position and horizontal extent; and

c) the set of matching criteria comprises;

i) a third matching criteria satisfied based on matching data type, horizontal position, and horizontal extent within an extent offset;

ii) a fourth matching criteria satisfied based on matching horizontal position; and

iii) a fifth matching criteria satisfied based on matching horizontal position within a position offset.

11. The method of claim 10, wherein repeatedly applying the set of matching criteria comprises applying the third matching criterion at least two times using different extent offsets.

12. The method of claim 8, wherein:

a) the existing groups that are tested for horizontal overlaps are each associated with;

i) a preceding whitespace extent that includes only whitespace between data elements comprised by that group and that group'"'"'s data elements'"'"' left neighbors;

ii) a data element extent that horizontally encompasses all data elements comprised within that group; and

iii) a subsequent whitespace extent that includes only whitespace between data elements comprised by that group and that group'"'"'s data elements'"'"' right neighbors;

 

and

b) testing for horizontal overlaps between data elements and neighbors of data elements in existing groups is performed based on;

i) comparing the data element extent of a first existing group with the preceding whitespace extent and subsequent whitespace extent of a second existing group; and

ii) comparing the data element extent of the second existing group with the preceding whitespace and subsequent whitespace extent of the first existing group.

13. The method of claim 12, wherein, in the event that a data element from the second existing group is added to the first existing group, all data elements from the second existing group are simultaneously added to the first existing group.

14. The method of claim 8, wherein the data element groups are applied to columns of the output document by, for each group from the set of data element groups:

a) determining if any data element in that group shares a row with any data element in any other group that has already been applied to a column; and

b) in the event that any data element in that group shares a row with any data element in any other group that has already been applied to a column, apply that group to the first column following a rightmost column assigned to a group comprising a data element in a shared row.

18. The method of claim 8, wherein:

a) a plurality of different matching criteria are used in the grouping process; and

b) the completion condition is satisfied when each matching criteria criterion of the plurality of different matching criteria, has been applied to each data element.

15. A system for automatically organizing data from one or more input documents into rows and columns in a structured output document, the system comprising:

a) means for grouping data elements from an input document into a set of groups based on satisfaction of matching criteria and testing for horizontal overlaps between data elements and neighbors of other data elements; and

b) means for assigning columns to data elements from the input document based on the set of groups;

wherein

A) the means for grouping data elements from the input document into the set of groups based on satisfaction of matching criteria and testing for horizontal overlaps between data elements and neighbors of other data elements and the means for assigning columns to data elements from the input document based on the set of groups are implemented with a single computer;

B) the computer is operable to generate a structured output document having columns extending across internal subheadings regardless of whether the internal subheadings prevent data elements in the columns from being separated from data elements in other columns by continuous vertical whitespace.