Method and system of extracting structured data from a document
This disclosure provides an exemplary method and system for extracting structured data from an unstructured textual document. According to an exemplary method, initially a layout analysis is performed resulting in one or more alternatives for grouping and ordering the page elements of interest. Next, the content of these page elements are tagged based on application-specific heuristics. Finally, a sequence-based method is applied to the tags for identifying repetitive contiguous patterns.
1. A computer implemented method of extracting structured data associated with a digital version of a document, the method comprising:
a) performing a layout analysis of the digital version of the document to generate two or more tabular layout structures including rows and columns of cells including structural elements associated with the document, each layout structure and associated cells including a plurality of structural elements vertically and horizontally regularly aligned in columns and rows where each structural element is defined as a typographical box including one or more lines of textual elements associated with the digital version of the document;
b) tagging one or more of the lines of textual elements with one of a plurality of content tags, a tagged line of textual elements including structured elements of information associated with one of a plurality of predefined sdata (structured data) heuristics associated with the plurality of content tags;
c) generating a content-layout model (clayout model), the clayout model associating the one or more content tags with respective repetitive layout positions associated with one of the two or more layout structures;
d) tagging one or more lines of textual elements which were not tagged in step b) with one of the plurality of content tags based on inferred repetitive locations of the plurality of content tags provided by the clayout model; and
e) extracting and merging the tagged lines of textual information from the two or more layout structures as representative of the structured data associated with the digital version of the document,
wherein step c) generates the clayout model using a sequence-based method to hierarchically segment a sequence of elements associated with the generated two or more layout structures associated with the document; and
wherein the sequence-based method includes:
c1) generating a set of n-grams from the sequence of elements, an n-gram including an ordered sequence of n features provided by a sequence of n named elements;
c2) electing sequential n-grams from the set of n-grams, the sequential n-grams defined as similar contiguous n-grams;
c3) selecting the most frequent sequential n-gram from the elected sequential n-grams;
c4) generating a new sequence of the elements by matching the selected most frequent sequential n-gram against the sequence of elements associated with the document, replacing matched elements of the sequence of elements with a respective node, and associating the matched elements of the sequence of elements as children of the respective node; and
c5) iteratively repeating steps c1)-c4) on the new sequence of elements generated in step c4) until all sequential n-grams associated with the sequence of elements are matched against the sequence of elements associated with the document, the respective matched elements of the sequence of elements are replaced with a respective node, and the respective matched elements of the sequence of elements are associated as children of the respective node; and
wherein step c4) includes:
matching the selected most frequent sequential n-gram against the sequence of elements to determine all sub-sequences of n contiguous element which are matched by the selected n-gram;
enriching the determined sub-sequences, wherein enriching is defined as generating n-grams for each determined sub-sequence; and
generating the new sequence of elements by replacing each sub-sequence of contiguous matched elements with the respective node and associating the matched elements of the sequence of elements as the children of the respective node.
2. The computer implemented method of extracting structured data according to claim 1 , wherein the structural elements are associated with one or more of a line of text, and a block of text, the text including one or more of letters, numbers and symbols.
3. The computer implemented method of extracting structured data according to claim 1 , wherein the two or more layout structures are associated with one or more of a 1D (Dimensional) structure and a 2D structure.
4. The computer implemented method of extracting structured data according to claim 1 , wherein the sdata includes one or more fields and step b) and step d) tags the fields based on one or more of a regular expression and a closed list to tag the most frequent elements of a field.
5. The computer implemented method of extracting structured data according to claim 4 , wherein the sdata includes one or more mandatory fields and one or more optional fields.
6. The computer implemented method of extracting structured data according to claim 4 , wherein basic entities covered by regular expressions include one or more of a phone number, address, URL (Uniform Resource Locator) and date.
7. The computer implemented method of extracting structured data according to claim 1 , wherein steps a)-e) are independently performed on a plurality of pages associated with the digital version of the document.
8. An image processing system comprising:
a controller configured to receive a digital version of a document, the controller configured to execute instructions to perform a method of extracting structured data associated with a digital version of a document, the method comprising:
a) performing a layout analysis of the digital version of the document to generate two or more tabular layout structures including rows and columns of cells including structural elements associated with the document, each layout structure and associated cells including a plurality of structural elements vertically and horizontally regularly aligned in columns and rows where each structural element is defined as a typographical box including one or more lines of textual elements associated with the digital version of the document;
b) tagging one or more of the lines of textual elements with one of a plurality of content tags, a tagged line of textual elements including structured elements of information associated with one of a plurality of predefined sdata (structured data) heuristics associated with the plurality of content tags;
c) generating a content-layout model (clayout model), the clayout model associating the one or more content tags with respective repetitive layout positions associated with one of the two or more layout structures;
d) tagging one or more lines of textual elements which were not tagged in step b) with one of the plurality of content tags based on inferred repetitive locations of the plurality of content tags provided by the clayout model; and
e) extracting and merging the tagged lines of textual information from the two or more layout structures as representative of the structured data associated with the digital version of the document,
wherein step c) generates the clayout model using a sequence-based method to hierarchically segment a sequence of elements associated with the generated two or more layout structures associated with the document; and
wherein the sequence-based method includes:
c1) generating a set of n-grams from the sequence of elements, an n-gram including an ordered sequence of n features provided by a sequence of n named elements;
c2) electing sequential n-grams from the set of n-grams, the sequential n-grams defined as similar contiguous n-grams;
c3) selecting the most frequent sequential n-gram from the elected sequential n-grams;
c4) generating a new sequence of the elements by matching the selected most frequent sequential n-gram against the sequence of elements associated with the document, replacing matched elements of the sequence of elements with a respective node, and associating the matched elements of the sequence of elements as children of the respective node; and
c5) iteratively repeating steps c1)-c4) on the new sequence of elements generated in step c4) until all sequential n-grams associated with the sequence of elements are matched against the sequence of elements associated with the document, the respective matched elements of the sequence of elements are replaced with a respective node, and the respective matched elements of the sequence of elements are associated as children of the respective node; and
wherein step c4) includes:
matching the selected most frequent sequential n-gram against the sequence of elements to determine all sub-sequences of n contiguous element which are matched by the selected n-gram;
enriching the determined sub-sequences, wherein enriching is defined as generating n-grams for each determined sub-sequence; and
generating the new sequence of elements by replacing each sub-sequence of contiguous matched elements with the respective node and associating the matched elements of the sequence of elements as the children of the respective node.
9. The image processing system according to claim 8 , wherein the structural elements are associated with one or more of a line of text, and a block of text, the text including one or more of letters, numbers and symbols.
10. The image processing system according to claim 8 , wherein the two or more layout structures are associated with one or more of a 1D (Dimensional) structure and a 2D structure.
11. The image processing system according to claim 8 , wherein the sdata includes one or more fields and step b) and step d) tags the fields based on one or more of a regular expression and a closed list to tag the most frequent elements of a field.
12. The image processing system according to claim 11 , wherein basic entities covered by regular expressions include one or more of a phone number, address, URL (Uniform Resource Locator) and date.
13. The image processing system according to claim 11 , wherein the sdata includes one or more mandatory fields and one or more optional fields.
14. The image processing system according to claim 8 , wherein steps a)-e) are independently performed on a plurality of pages associated with the digital version of the document.
15. A computer program product comprising a non-transitory recording medium storing instructions, which when executed on a computer cause the computer to perform a method of extracting structured data associated with a digital version of a document comprising:
a) performing a layout analysis of the digital version of the document to generate two or more tabular layout structures including rows and columns of cells including structural elements associated with the document, each layout structure and associated cells including a plurality of structural elements vertically and horizontally regularly aligned in columns and rows where each structural element is defined as a typographical box including one or more lines of textual elements associated with the digital version of the document;
b) tagging one or more of the lines of textual elements with one of a plurality of content tags, a tagged line of textual elements including structured elements of information associated with one of a plurality of predefined sdata (structured data) heuristics associated with the plurality of content tags;
c) generating a content-layout model (clayout model), the clayout model associating the one or more content tags with respective repetitive layout positions associated with two of the one or more layout structures;
d) tagging one or more lines of textual elements which were not tagged in step b) with one of the plurality of content tags based on inferred repetitive locations of the plurality of content tags provided by the clayout model; and
e) extracting and merging the tagged lines of textual information from the two or more layout structures as representative of the structured data associated with the digital version of the document,
wherein step c) generates the clayout model using a sequence-based method to hierarchically segment a sequence of elements associated with the generated two or more layout structures associated with the document; and
wherein the sequence-based method includes:
c1) generating a set of n-grams from the sequence of elements, an n-gram including an ordered sequence of n features provided by a sequence of n named elements;
c2) electing sequential n-grams from the set of n-grams, the sequential n-grams defined as similar contiguous n-grams;
c3) selecting the most frequent sequential n-gram from the elected sequential n-grams;
c4) generating a new sequence of the elements by matching the selected most frequent sequential n-gram against the sequence of elements associated with the document, replacing matched elements of the sequence of elements with a respective node, and associating the matched elements of the sequence of elements as children of the respective node; and
c5) iteratively repeating steps c1)-c4) on the new sequence of elements generated in step c4) until all sequential n-grams associated with the sequence of elements are matched against the sequence of elements associated with the document, the respective matched elements of the sequence of elements are replaced with a respective node, and the respective matched elements of the sequence of elements are associated as children of the respective node; and
wherein step c4) includes:
matching the selected most frequent sequential n-gram against the sequence of elements to determine all sub-sequences of n contiguous element which are matched by the selected n-gram;
enriching the determined sub-sequences, wherein enriching is defined as generating n-grams for each determined sub-sequence; and
generating the new sequence of elements by replacing each sub-sequence of contiguous matched elements with the respective node and associating the matched elements of the sequence of elements as the children of the respective node.
16. The computer program product according to claim 15 , wherein the structural elements are associated with one or more of a line of text, and a block of text, the text including one or more of letters, numbers and symbols.