Intelligent extraction and organization of data from unstructured documents

• US 10,678,998 B1
• Filed: 04/01/2019
• Issued: 06/09/2020
• Est. Priority Date: 02/20/2018
• Status: Active Grant

• Current Assignee: Paycor, Inc.
• Original Assignee: Paycor, Inc.
• Inventors: Maslin, Matt
• Primary Examiner(s): Roy, Sanchita
• Application Number:
  US16/371,626
• Time in Patent Office: 435 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 a set of acts comprising:

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

b) generating a set of data element groups based on applying a set of matching criteria to the data elements after the data elements have been assigned to a set of existing groups, each of which comprises one or more data elements, and testing for horizontal overlaps between neighbors of data elements in a first existing group and data elements in a second existing group and combining the first and second existing groups based on determining the existence of a match and absence of neighbor overlap between the first and second existing groups; and

c) assigning the data elements to columns based on the set of data element groups to generate the structured output document with columns having data elements separated from data elements in neighboring columns by whitespace and extending vertically across any internal headings in the one or more input documents regardless of whether the internal headings cause vertical whitespace between neighboring columns to be discontinuous.

2. The system of claim 1, wherein generating the set of data element groups based on applying the set of matching criteria comprises applying a first matching criterion to the plurality of data elements and subsequently applying a second matching criterion to the plurality of data elements, wherein all data elements that satisfy the first matching criteria also satisfy the second matching criteria.

3. The system of claim 2, wherein:

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

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

c) the set of matching criteria comprises;

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

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

iii) a fifth matching criterion satisfied based on matching horizontal position within a position offset;

wherein the first, second and third matching criteria are applied by matching existing groups against each other.

4. The system of claim 3, wherein generating the set of data element groups based on applying the set of matching criteria comprises applying the third matching criterion at least two times using different extent offsets.

5. The system of claim 1, wherein:

a) existing groups that would be tested for horizontal overlaps during performance of the set of acts by the computer would each be associated with;

i) a preceding whitespace extent that includes only whitespace between data elements within 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 within 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 by the computer would be 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.

6. The system of claim 1, wherein assigning the data elements to columns based on the set of data element groups comprises applying the data element groups 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 a first column to the right of a rightmost column assigned to a group comprising a data element in a shared row.

7. 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 between 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 based on applying the set of matching criteria to the data elements after the data elements have been assigned to a set of existing groups, each of which comprises one or more data elements, and testing for horizontal overlaps between neighbors of data elements in a first existing group and data elements in a second existing group and combining the first and second existing groups based on determining the existence of a match and absence of neighbor overlap between the first and second existing groups; and

d) assigning the data elements to columns of the output document based on the set of data element groups to generate a structured output document with columns having data elements separated from data elements in neighboring columns by whitespace and extending vertically across any internal headings in the one or more input documents regardless of whether the internal subheadings cause vertical whitespace between neighboring columns to be discontinuous.

8. The method of claim 7, wherein generating the set of data element groups based on applying the set of matching criteria comprises applying a first matching criterion to the plurality of data elements and subsequently applying a second matching criterion to the plurality of data elements, wherein all data elements that satisfy the first matching criteria also satisfy the second matching criteria.

9. The method of claim 8, wherein:

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

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

c) the set of matching criteria comprises;

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

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

iii) a fifth matching criterion satisfied based on matching horizontal position within a position offset;

wherein the first, second and third matching criteria are applied by matching existing groups against each other.

10. The method of claim 9, wherein generating the set of data element groups based on applying the set of matching criteria comprises applying the third matching criterion at least two times using different extent offsets.

11. The method of claim 7, wherein:

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

i) a preceding whitespace extent that includes only whitespace between data elements by within 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 within 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.

12. The method of claim 7, 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 a first column to the right of a rightmost column assigned to a group comprising a data element in a shared row.

13. A non-transitory computer readable medium encoded with instructions operable to, when executed, cause a computer to perform a set of acts comprising:

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

b) generating a set of data element groups based on applying a set of matching criteria to the data elements after the data elements have been assigned to a set of existing groups, each of which comprises one or more data elements, and testing for horizontal overlaps between neighbors of data elements in a first existing group and data elements in a second existing group and combining the first and second existing groups based on determining the existence of a match and absence of neighbor overlap between the first and second existing groups; and

c) assigning the data elements to columns based on the set of data element groups to generate the structured output document with columns having data elements separated from data elements in neighboring columns by whitespace and extending vertically across any internal headings in the one or more input documents regardless of whether the internal headings cause vertical whitespace between neighboring columns to be discontinuous.

14. The non-transitory computer readable medium of claim 13, wherein generating the set of data element groups based on applying the set of matching criteria comprises applying a first matching criterion to the plurality of data elements and subsequently applying a second matching criterion to the plurality of data elements, wherein all data elements that satisfy the first matching criteria also satisfy the second matching criteria.

15. The non-transitory computer readable medium of claim 14, wherein:

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

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

c) the set of matching criteria comprises;

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

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

iii) a fifth matching criterion satisfied based on matching horizontal position within a position offset;

wherein the first, second and third matching criteria are applied by matching existing groups against each other.

16. The non-transitory computer readable medium of claim 15, wherein generating the set of data element groups based on applying the set of matching criteria comprises applying the third matching criterion at least two times using different extent offsets.

17. The non-transitory computer readable medium of claim 13, wherein:

a) existing groups that would be tested for horizontal overlaps during performance of the set of acts would each be associated with;

i) a preceding whitespace extent that includes only whitespace between data elements within 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 within 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 would be 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.

18. The non-transitory computer readable medium of claim 13, wherein assigning the data elements to columns based on the set of data element groups comprises applying the data element groups 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 a first column to the right of a rightmost column assigned to a group comprising a data element in a shared row.