Document information extraction system using sequenced comparators

Abstract

A document information extraction system determines a structure of an electronic document based on characteristics of the document's constituent elements. The system segments the document to generate elements with each element having similar characteristics. Elements may be clustered to assist in determining the document structure. The system determines directional relationships between elements (e.g., above, below, etc.). The system then employs a master comparator to determine familial relationships between adjacent elements. The master comparator includes a set of unit comparators and each unit comparator compares a specific characteristic between two elements. The master comparator sequentially applies the unit comparators to determine the familial relationship based on the comparisons. The system outputs a document hierarchy tree reflecting the determined familial relationships. The hierarchy tree represents the structure of the document.

What is claimed is: 
     
         1 . A computer-implemented method for determining a hierarchical structure of an electronic document, the method comprising:
 segmenting the document into a plurality of elements that, in aggregate, include the hierarchical structure, and each element having one or more visual characteristics and one or more location characteristics;   applying a master comparator including a set of unit comparators to the plurality of elements to determine the hierarchical structure of the document, the master comparator determining the hierarchical structure by:
 for each pair of elements in the document, applying, in an ordered sequence, the set of unit comparators to determine a familial relationship between the pair of elements using at least the visual characteristics or the location characteristics of the pair of elements, and 
   wherein the familial relationships between the plurality of elements identify the hierarchical structure of the document; and   generating a document hierarchy tree representing the hierarchical structure of the document, the document hierarchy tree a visualization of the familial relationships between the plurality of elements.   
     
     
         2 . The method of  claim 1 , further comprising:
 for each element, determining a plurality of directional relationships for the element, the directional relationship defining an adjacency type between the element and any adjacent element in the document, and   wherein the master comparator compares pairs of elements based on the directional relationships.   
     
     
         3 . The method of  claim 2 , wherein the familial relationships are further based on the directional relationships between elements. 
     
     
         4 . The method of  claim 1 , wherein each unit comparator in the set of set of unit comparators compares a different visual characteristic. 
     
     
         5 . The method of  claim 1 , wherein each unit comparator of the set of unit comparators compares a different location characteristic. 
     
     
         6 . The method of  claim 1 , wherein determining the hierarchal structure further comprises:
 determining a formatting structure for the plurality of elements in the document, and   wherein hierarchical structure is based on the formatting structure.   
     
     
         7 . The method of  claim 1 , wherein determining the hierarchal structure further comprises:
 determining an indexing structure for the plurality of elements in the document, and   wherein hierarchical structure is based on the indexing structure.   
     
     
         8 . The method of  claim 1 , wherein the hierarchical structure of the document comprises a plurality of familial relationships, and the plurality of familial relationships comprises a plurality of parent relationships, a plurality of child relationships, and a plurality of sibling relationships. 
     
     
         9 . The method of  claim 8 , wherein:
 the document includes a first element and a second element,   a parent relationship between the first element and the second element defines the first element having a higher-level hierarchy in the hierarchical structure of the document than the second element,   a child relationship between the first element and the second element defines a the first element segment having a lower-level hierarchy in the hierarchical structure of the document than the second element, and   a sibling relationship between the first element and the second element defines the first element and the second element having a same-level hierarchy in the hierarchical structure of the document.   
     
     
         10 . The method of  claim 1 , further comprising:
 validating the familial relationships between the plurality of elements by applying the master comparator to pairs of elements having a grandparent and a grandchild relationship in the hierarchical structure of the document.   
     
     
         11 . The method of  claim 1 , further comprising:
 receiving, from a remote client system, a request to generate the visualization; and   transmitting the visualization to the remote client system.   
     
     
         12 . The method of  claim 1 , wherein the request includes a configuration of the set of unit comparators of the master comparator. 
     
     
         13 . A non-transitory computer readable storage medium including computer instructions for determining a hierarchical structure of an electronic document, the computer instructions, when executed by a processor, causing the processor to:
 segment the document into a plurality of elements that, in aggregate, include the hierarchical structure, and each element having one or more visual characteristics and one or more location characteristics;   apply a master comparator including a set of unit comparators to the plurality of elements to determine the hierarchical structure of the document, the master comparator determining the hierarchical structure by:
 for each pair of elements in the document, apply, in an ordered sequence, the set of unit comparators to determine a familial relationship between the pair of elements using at least the visual characteristics or the location characteristics of the pair of elements, and 
   wherein the familial relationships between the plurality of elements identify the hierarchical structure of the document; and   generate a document hierarchy tree representing the hierarchical structure of the document, the document hierarchy tree a visualization of the familial relationships between the plurality of elements.   
     
     
         14 . The non-transitory computer readable storage medium of  13 , wherein the computer instructions, when executed by the processor, further cause the processor to:
 for each element, determine a plurality of directional relationships for the element, the directional relationship defining an adjacency type between the element and any adjacent element in the document, and   wherein the master comparator compares pairs of elements based on the directional relationships.   
     
     
         15 . The non-transitory computer readable storage medium of  13 , wherein the familial relationships are further based on the directional relationships between elements. 
     
     
         16 . The non-transitory computer readable storage medium of  13 , wherein each unit comparator in the set of set of unit comparators compares a different visual characteristic. 
     
     
         17 . The non-transitory computer readable storage medium of  13 , wherein each unit comparator of the set of unit comparators compares a different location characteristic. 
     
     
         18 . The non-transitory computer readable storage medium of  13 , wherein the hierarchical structure of the document comprises a plurality of familial relationships, and the plurality of familial relationships comprises a plurality of parent relationships, a plurality of child relationships, and a plurality of sibling relationships. 
     
     
         19 . The non-transitory computer readable storage medium of  13 , wherein:
 the document includes a first element and a second element,   a parent relationship between the first element and the second element defines the first element having a higher-level hierarchy in the hierarchical structure of the document than the second element,   a child relationship between the first element and the second element defines a the first element segment having a lower-level hierarchy in the hierarchical structure of the document than the second element, and   a sibling relationship between the first element and the second element defines the first element and the second element having a same-level hierarchy in the hierarchical structure of the document.   
     
     
         20 . A system for determining a hierarchical structure of an electronic document, the system comprising:
 a computer processor for executing computer program instructions; and   a non-transitory computer-readable medium storing computer program instructions executable by the computer processor to perform operations comprising:
 segmenting the document into a plurality of elements that, in aggregate, include the hierarchical structure, and each element having one or more visual characteristics and one or more location characteristics; 
 applying a master comparator including a set of unit comparators to the plurality of elements to determine the hierarchical structure of the document, the master comparator determining the hierarchical structure by:
 for each pair of elements in the document, applying, in an ordered sequence, the set of unit comparators to determine a familial relationship between the pair of elements using at least the visual characteristics or the location characteristics of the pair of elements, and 
 
 wherein the familial relationships between the plurality of elements identify the hierarchical structure of the document; and 
 generating a document hierarchy tree representing the hierarchical structure of the document, the document hierarchy tree a visualization of the familial relationships between the plurality of elements.