Abstract:
Much valuable information in documents is presented within tables. However, the information within tables is hard to extract automatically with high accuracy due to the wide variety and low quality of typical tables found in electronic documents. Information extraction technology can provide a method of extracting information from heterogeneous tables by recognizing tables, the header cells, and cells that are merged or should be merged, creating a richer representation of table structure and providing a convenient way of linking cells to their row and column headers. Use of this richer representation allows a few extraction patterns to successfully pull out information from a wide variety of differently formatted tables.

Description:
CROSS-REFERENCE TO RELATED APPLICATION(S) 
       [0001]    This application claims priority to U.S. Patent Application No. U.S. 62/337,216, entitled “EXTRACTING INFORMATION FROM TABLES EMBEDDED WITHIN DOCUMENTS,” filed May 16, 2016 which is incorporated by reference in its entirety. 
     
    
     BACKGROUND 
       [0002]    Key information can be contained within tables that are themselves embedded in documents, whether full-text journal articles, patents, slides or health records. For example, important experimental results may be contained within a table in a PowerPoint presentation, or key lab values relevant to a patient may be contained within a table in an electronic health record. Information contained within tables is hard to extract automatically with high accuracy due to the wide variety and low quality of typical tables found in electronic documents. 
         [0003]    One particular difficulty in extracting information contained within tables arises from the way in which table structures are typically represented in semi-structured formats like SGML, HTML, document or presentation formats such as Word or PowerPoint or various XML formats (e.g., XHTML, XML OASIS or CALS table models). Cells can span multiple rows or columns, and even for simple cells there is no association between the cell and its respective column and row headers. 
         [0004]    Another difficulty arises from the fact that many tables found in electronic formats contain representation errors. These can arise from a variety of factors, including imperfect optical character recognition (OCR) and the breaking apart of cells to improve the readability of items within a table. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0005]      FIG. 1A  is a flow diagram illustrating a process used in some implementations for extracting table information from semi-structured text. 
           [0006]      FIG. 1B  is a flow diagram illustrating a process used in some implementations for extracting table information from unstructured text. 
           [0007]      FIG. 1C  is a flow diagram illustrating a process used in some implementations for extracting table information from unstructured text. 
           [0008]      FIG. 1D  is a flow diagram illustrating a process used in some implementations for extracting table information using OCR to create semi-structured text. 
           [0009]      FIGS. 2A and 2B  show an example illustrating merging the cells of a table. 
           [0010]      FIG. 3  shows an example illustrating an annotated table in which a cell spans multiple rows. 
           [0011]      FIG. 4  is a flow diagram illustrating a process used in some implementations for associating cells in the same column via a shared index term column identifier. 
           [0012]      FIG. 5A-5D  show an example of processing a table within a patent document. 
           [0013]      FIG. 6  shows an example of information extracted from a processed table in  FIG. 5C . 
           [0014]      FIG. 7  shows highlighting within an example table rendered in HTML showing the evidence for the extraction provided in  FIG. 6 . 
           [0015]      FIG. 8A  presents an example of table represented in plain text. 
           [0016]      FIG. 8B  shows an example of the table of  FIG. 8A  converted to HTML format. 
       
    
    
     DETAILED DESCRIPTION 
       [0017]    The following description and drawings are illustrative and are not to be construed as limiting. Numerous specific details are described to provide a thorough understanding of the disclosure. However, in certain instances, well-known or conventional details are not described in order to avoid obscuring the description. References to one or an embodiment in the present disclosure can be, but not necessarily are, references to the same embodiment; and, such references mean at least one of the embodiments. 
         [0018]    Reference in this specification to “one embodiment” or “an embodiment” means that a particular feature, structure or characteristic described in connection with the embodiment is included in at least one embodiment of the disclosure. The various appearances of the phrase “in one embodiment” in the specification do not necessarily refer to the same embodiment, nor are separate or alternative embodiments mutually exclusive of other embodiments. Moreover, various features are described that may be exhibited by some embodiments and not by others. Similarly, various requirements are described that may be requirements for some embodiments but not others. 
         [0019]    The terms used in this specification generally have their ordinary meanings in the art, within the context of the disclosure, and in the specific context in which each term is used. Certain terms that are used to describe the disclosure are discussed below, or elsewhere in the specification, to provide additional guidance to the practitioner regarding the description of the disclosure. Certain terms may be highlighted, for example, by using italics and/or quotation marks. The use of highlighting has no influence on the scope and meaning of a term; the scope and meaning of a term is the same, in the same context, whether or not it is highlighted. It will be appreciated that the same thing can be said in more than one way. 
         [0020]    Consequently, alternative language and synonyms may be used for any one or more of the terms discussed herein; no special significance is to be placed on whether or not a term is elaborated or discussed herein. Synonyms for certain terms are provided. A recital of one or more synonyms does not exclude the use of other synonyms. The use of examples anywhere in this specification, including examples of any terms discussed herein, is illustrative only, and is not intended to further limit the scope and meaning of the disclosure or of any exemplified term. Likewise, the disclosure is not limited to various embodiments given in this specification. 
         [0021]    Without intent to further limit the scope of the disclosure, examples of instruments, apparatus, methods and their related results according to the embodiments of the present disclosure are given below. Note that titles or subtitles may be used in the examples for the convenience of a reader, which in no way should limit the scope of the disclosure. Unless otherwise defined, all technical and scientific terms used herein have the same meaning as commonly understood by one of ordinary skill in the art to which this disclosure pertains. In the case of conflict, the present document, including definitions, will control. 
         [0022]    Various examples of the invention will now be described. The following description provides certain specific details for a thorough understanding and enabling description of these examples. One skilled in the relevant technology will understand, however, that the invention may be practiced without many of these details. Likewise, one skilled in the relevant technology will also understand that the invention may include many other obvious features not described in detail herein. Additionally, some well-known structures or functions may not be shown or described in detail below, to avoid unnecessarily obscuring the relevant descriptions of the various examples. 
         [0023]    The terminology used below is to be interpreted in the broadest reasonable manner, even though it is being used in conjunction with a detailed description of certain specific examples of the invention. Indeed, certain terms may even be emphasized below; however, any terminology intended to be interpreted in any restricted manner will be overtly and specifically defined as such in this Detailed Description. 
         [0024]    The information extraction technology disclosed herein can provide a method of extracting information from heterogeneous tables in either semi-structured or unstructured text by recognizing headers and merged cells. The information extraction technology can also create a richer representation of table structure to provide a linking of cells to their respective row and column headers. 
         [0025]    Information extraction is concerned with extracting relationships from unstructured and semi-structured text. Unstructured text might contain a statement such as “profit in 2015 for Company A was 2 million dollars.” A table might include a legend of “profits (million dollars),” a column header of “2015,” a row header of “Company A” and a cell value of “2.” Even when the table is annotated with XML or HTML elements, there can be several challenges to extracting the information, such as the following:
       1) Many formats represent table cells as elements contained in table rows, and the table rows as elements contained in tables. The relationship between a cell and the table column it belongs to is not directly represented.   2) Cells, including header cells, may span multiple columns and rows.   3) Logical cells in tables are often split to aid visibility or during OCR.   4) Distinctions between value cells and header cells are often missing in text-based content sources.       
 
         [0030]    As described in greater detail below, the information extraction technology can overcome these challenges by recognizing tables, header cells, and cells that are merged or should be merged, creating a richer representation of table structures and providing a convenient way of linking cells to their respective row and column headers. Use of this richer representation allows extraction patterns to successfully pull out information from a wide variety of differently formatted tables. 
         [0031]      FIG. 1A  is a flow diagram illustrating a process  100  used in some implementations for extracting table information from semi-structured text. Examples of semi-structured text include documents in formats such as HTML or XML. These formats may provide a structure for tables based on tables containing one or more rows, which themselves contain one or more cells, but they may not provide relationships between cells and their respective row and column headers or other defining cells. Moreover, although these formats may allow for differentiation between row- and column-defining or header cells and data cells, in practice, many tables found in semi-structured documents fail to correctly apply these identifiers. 
         [0032]    At stage  106 , process  100  can find one or more tables in a semi-structured portion of input document  101 . Stage  106  can involve looking for a structured element such as “table,” although other element names are also possible. 
         [0033]    At stage  108 , process  100  can identify cell contexts. Each cell can be classified as either a header cell or a data cell. Header cells can be recognized based on one or more of the following: explicit coding of header cells in the input; formatting differences between header cells and other cells; the presence of at least one header cell for every column; the presence of horizontal lines; the nature of the cell content (blank vs. numeric vs. textual; lowercase vs. uppercase text); the presence of measurement units within brackets; words referring to operations on the values in the table (e.g., “sum,” “total,” “average,” “avg.”). Header cells can be further classified as being a column header cell, a row header cell or both, based on their position in the table. Any cell not recognized as a header cell may be considered to be a data cell. 
         [0034]    Each data cell can be linked to its respective column and row headers. A data cell can be linked to multiple column or row headers, for example, when the table has individual column headers for each column, and then other column headers spanning several columns. Header cells can also be linked to other header cells when there are multiple levels of headers. In some implementations, column and row headers can be encoded directly by annotating each data cell with the text of the column header cell(s) in its column and the text of the row header cell(s) in its row. In some implementations, the relation between a data cell and its respective row header(s) and column header(s) can be encoded indirectly. Each cell can be annotated with one or more identifiers for the rows that it spans and one or more identifiers for the columns that it spans. 
         [0035]    These annotations, represented in  FIGS. 1A-1D  as Annotated representation of tables  112 , are generated by process  108  in  FIGS. 1A, 1B and 1D  and process  109  in  FIG. 1C . The annotations can use any identifier, for instance, numeric identifiers (indexes) that reflect the position of that row or column within the table. For example,  FIG. 3  provides an example of an annotated representation of table. These embodiments allow identification of any two cells in the same row or column, even if neither is a header cell. In some implementations, at least some of the column and row headers can be encoded directly and at least some can be encoded indirectly.  FIG. 5D  shows another possible implementation where these annotations are made available for inspection in tooltips (or other layers or portions of display) of tables and table cells. These tooltips pop up when a user hovers their mouse cursor over a table cell.  FIG. 5D  shows a tooltip  532  for one of the table cells, displaying the annotated identifiers for the row and column that the cell occupies, and also another tooltip  534  for the entire table, showing a unique identifier for the table. 
         [0036]    Cells that span multiple rows or columns can be recognized according to the input format (e.g., XML CALS format, HTML, XHTML). In some implementations, cells that span multiple rows or columns may be expanded out. In some implementations, cells that span multiple rows or columns may have multiple headers, and headers that span multiple rows or columns are shared by multiple cells. In some implementations, cells including header cells that span multiple rows or columns may have multiple indexes corresponding to the individual rows and columns that they span. 
         [0037]    At stage  110 , process  100  can optionally merge two or more cells of a table. In some implementations, table structures may be corrected by merging cells and/or rows. Despite the structured format, often the initial structuring provided in a semi-structured document is appropriate for the reading of the text, but does not reflect the logical structure of the table.  FIG. 2A  shows an example table  200  in which the second row of column header text has been split into separate rows,  201  and  202 . One of the chemical descriptions has also been split across multiple cells,  203  and  204 . The first column of row headers contains empty cells,  205  and  206 , which reflects that the cell above should span the row with the empty cell as well.  FIG. 2B  shows a table  250 , which is the result of merging cells from table  200 . There is now a single header cell,  251 , with the text “Measured Component,” rather than two cells,  207  and  208 , where this text was separated. The column header with the text “Experiment,”  252 , is now correctly aligned with the last three columns of the table. The row header with the text “II,”  253 , is now correctly aligned with the last two rows. The chemical description,  254 , is now in a single cell. 
         [0038]    Process  100  can merge cells based on one or more of the following: empty cells; rows with similar structure (e.g., where the same number of cells span the same columns); the distinguishing of header cells and data cells; the amount of text within a cell suggesting wrapping into the next cell; mismatched brackets in the text that would match if cells are merged; cell contents starting or ending with a conjunction or a preposition; or any combination thereof. For table  200  in  FIG. 2A , stage  110  in  FIG. 1A  can merge every cell in row  210  with the cell above it (row  209 ) due to these rows being rows of column headers and there being no empty cell in the bottom row ( 210 ), but many empty cells in the top row ( 209 ). Row  210  is merged into row  209  because column headers are typically vertically aligned to the bottom. In the case of rows  211  and  212 , stage  110  can merge every cell in row  212  with the cell above it due to these rows not being rows of column headers and there being multiple empty cells in row  212 . Row  212  can be merged into row  211  because the text in data cells tends to be vertically aligned to the top and the text in row  212  (“hexahydrate”) being lowercase suggests that it is not the start of a cell. In the case of the last cells of the first row (labeled  213 ,  214  and  215 ), stage  110  can prefer to merge them horizontally rather than vertically because this is the first row of column headers. Tables often contain main column headers spanning multiple columns, with sub-headers below. 
         [0039]    At stage  114 , process  100  can optionally index the document into a format optimized for large-scale querying search and text mining. For example, an index can be created that allows fast searching of tabular information contained within millions of individual documents. Process  100  can manipulate the representation, which includes the annotations for the table cells, and these can be converted to different formats and optimized for different needs, where the annotations for the table cells are nevertheless preserved. One example of this is converting the representation into a format optimized for efficient search. In some embodiments, the annotation process is automatic and results in annotations represented in a digital format that is amenable to further automatic manipulation, namely of the kind needed to facilitate computer-based search. The identifiers for the rows and columns of a table enable a search engine to find cells that occupy the same row or column by comparing these identifiers. 
         [0040]    At stage  116 , process  100  can extract information from the table. In an HTML table, you can extract rows, but they will not always be correct. For example,  FIG. 3  shows an example annotated table,  300 , in which a cell,  301 , spans multiple rows. In HTML (not shown in  FIG. 3 ), a table corresponding to table  300  can typically be represented by including the cell inside the first row (e.g., corresponding to row  302 ) that it spans, and annotating the cell as spanning two rows. This means that the first row (e.g., corresponding to row  302 ) of the corresponding HTML table has three elements (e.g., corresponding to cells  301 ,  304  and  305 ), and the second row (e.g., corresponding to row  303 ) has only two elements (e.g., corresponding to cells  306  and  307 ). In the HTML representation, although a cell (e.g., corresponding to cell  301 ), could be the header for the second row(e.g., corresponding to row  303 ), it does not even appear within that row. Moreover, finding the appropriate column headers for elements in the second row in the HTML representation can be particularly challenging, because counting alone will not be enough: you may need to adjust for any spanning issues. 
         [0041]    In comparison, table  300  of  FIG. 3  includes the column and row identifier annotations using the index term approach discussed above in relation to stage  108 . In the index term approach, each cell can contain an annotation with respect to both the row and column to which the cell belongs. The content of a cell can be linked to its headers by finding matching index values. For example, assuming that cell  301  is a header cell, cell  307  would adopt cell  301  as a row header because they both have a row index of 2. Cells in the same row share the same row identifiers, so cell  307  becomes a member of rows 1 and 2. Similarly, cells in the same column can have the same column identifiers, so any cell can be associated with other cells in that column (including the header cells for the column). For example, cell  307  shares the same column as cell  305  via having a column index of 3. 
         [0042]      FIG. 4  shows a process  400  used in some implementations in which associating cells in the same column via a shared index term column identifier can be achieved using a join operator, where the column indexes of pairs of cells are joined. This leaves only pairs of cells with the same column index (i.e., cells in the same column). Process  100  can restrict one of the cells in each pair to be a column header cell and the other to be a data cell, for example, by looking at the annotations. This process can find all pairs of cells such that one is a data cell, the other is a column header cell and they belong to the same column. Searching for cells in the same row is a similar process, with row indexes used instead of column indexes, and restricting one of the cells to be a row header instead of a column header. 
         [0043]    In some implementations in which the row and column headers are directly copied into each cell, the extraction stage  116  can output the column header for the cell (readily available in the annotations) along with the cell contents (also readily available in the representation for the cell). 
         [0044]    To extract particular relationships, constraints can be imposed on the content of the headers and the cell. This can be based on the type of the content, such as number, date, company, chemical description or disease. It can be based on a particular kind of disease such as “neoplasm” using an ontology, or a particular range (e.g., 1 to 100). It can also be based on pattern matching of the content using regular expressions or linguistic patterns. 
         [0045]      FIG. 1B  is a flow diagram illustrating a process  120  used in some implementations for extracting table information from unstructured text, for example, where the tables are initially in plain text. An example of such a document includes some types of electronic health records. In this case, an additional initial stage  102  can be performed to convert the unstructured text to a semi-structured representation similar to the one used as input for process  100 . Process  120  can then continue from stage  102  to stages  106 - 116 , discussed above in relation to process  100 . Illustratively,  FIG. 8A  presents a table  800  represented in plain text, where the vertical alignment of the text is the only indication of the table&#39;s structure.  FIG. 8B  shows the same table converted to HTML format  810 . This is a possible output of process  102  ( FIG. 1B ). 
         [0046]    Stage  102  can include identifying one or more tables in unstructured text (e.g., which lines of text contain tables) and establishing the table structure (e.g., determining row and column boundaries). 
         [0047]    Process  120  can identify the tables by performing one or more of: identifying lines within the text; identifying multiple rows where text or white space is aligned; identifying table captions or headers; or any combination thereof. 
         [0048]    Once identified, process  120  can establish table structures by one or more of the following: establishing the column boundaries based on the alignment of white space across rows; recognizing the columns that a header spans based on the alignment of the header with respect to the columns below; establishing cell contents according to alignment of contents and white space; or any combination thereof. 
         [0049]      FIG. 1C  is a flow diagram illustrating a process  130  used in some implementations for extracting table information from unstructured text, as in process  120 . Process  130  uses a single stage for identifying the tables and for establishing the table structure, and can then continue from stage  109  to stages  110 - 116 , discussed above in relation to process  100 . 
         [0050]    Stage  107  can include identifying one or more tables in unstructured text (e.g. which lines of text contain tables) and establishing some of the table structure (e.g. determining row and column boundaries). 
         [0051]    Process  130  can identify the tables by performing one or more of: identifying lines within the text; identifying multiple rows in which text or white space is aligned; identifying table captions or headers; or any combination thereof. 
         [0052]    Stage  109  can establish table structures by one or more of the following: establishing the number of columns based on the differences in the amount of white space between one column of text and the next; recognizing the columns that a header spans based on the alignment of the header vs. columns below; establishing cell contents according to alignment of contents and white space; or any combination thereof. Each cell can be classified as either a header cell or a data cell. Header cells are recognized based on one or more of the following: explicit coding of header cells in the input; formatting differences between header cells and other cells; the presence of at least one header cell for every column. Header cells can be further classified as being a column header cell, a row header cell or possibly both, based on their position in the table. 
         [0053]    Each cell can be linked to its respective column and row headers. A cell can be linked to multiple column or row headers, for example, when the table has individual headers for each column, and then other headers spanning multiple columns. In some implementations, column and row headers can be encoded directly by annotating each cell with the text of the column header cells in its column and the text of the row header cells in its row. In some implementations, the relation between a cell and its respective row headers and column headers can be encoded indirectly. Each cell can be annotated with one or more identifiers for the rows that it spans and one or more identifiers for the columns that it spans. 
         [0054]    These annotations, represented in  FIGS. 1A-1D  as Annotated representation of tables  112 , can use any unique identifier, for instance, numeric identifiers (indexes) that reflect the position of that row or column within the table. These embodiments allow identification of any two cells in the same row or column, even if neither is a header cell. In some implementations, at least some of the column and row headers can be encoded directly and at least some can be encoded indirectly. 
         [0055]    In some implementations, cells that span multiple rows or columns may be expanded out. In some implementations, cells that span multiple rows or columns may have multiple headers, and headers that span multiple rows or columns are shared by multiple cells. In some implementations, cells including header cells that span multiple rows or columns may have multiple indexes corresponding to the individual rows and columns they span. 
         [0056]      FIG. 1D  is a flow diagram illustrating a process  140  used in some implementations for extracting table information using OCR to create semi-structured text. This could involve documents in PDF format (image or text). In this case, an additional initial stage  104  can be performed to run an OCR process on input document  101 , thereby creating a semi-structured representation similar to the one used as input for stage  106  in  FIG. 1A . In some implementations, the OCR process may create an unstructured document that can be provided to stage  102  in  FIG. 1B  or stage  107  in  FIG. 1C . 
         [0057]      FIG. 5A  shows an example of a table  500  in a patent PDF document. Table  510  in  FIG. 5B  shows a stylesheet rendering of an XML version of the same table. This XML might be derived from conversion of the PDF document, or, in some embodiments, the patent authority may provide an XML version of the patent document.  FIG. 5C  shows a stylesheet rendering of XML (e.g., table  520 ) after the XML version of table  500  is processed in accordance with some embodiments of the presently disclosed technology. As illustrated in  FIG. 5C , the cells containing the text “ARC1172 (SEQ ID NO 222)” have been merged, and this entire piece of text is the row header for the values 17 and 3 in the data cells in the same row. 
         [0058]      FIG. 5D  shows embodiments of the presently disclosed technology where annotations to tables or table cells are made available for inspection in tooltips (or other layers or portion of display). These tooltips pop up when a user hovers their mouse cursor over a table cell.  FIG. 5D  shows a tooltip  532  for one of the table cells, displaying the annotated identifiers for the row and column that the cell occupies, and also another tooltip  534  for the entire table, showing a unique identifier for the table. 
         [0059]      FIG. 6  shows an example  600  of data extracted from table  520  in  FIG. 5C . Illustratively, the example extraction can be performed in response to searches, queries, or other informational requests for the half-life values (T½) of the aptamers. The data extracted can be shown in HTML but can also be extracted into other formats such as Excel, XML, JSON, TSV and CSV. 
         [0060]      FIG. 7  provides evidence for the extracted information in example  600 . In accordance with some embodiments, a user can be referred directly to the correct position of a table (e.g., table  700 ) with highlighting to show the different pieces of data that have been extracted. 
         [0061]    Those skilled in the art will appreciate that the components illustrated in each of the flow diagrams discussed above may be altered in a variety of ways. For example, the order of the logic may be rearranged, sub-steps may be performed in parallel, illustrated logic may be omitted, other logic may be included, etc. 
         [0062]    Several implementations of the disclosed technology are described above in reference to the figures. The computing devices on which the described technology may be implemented can include one or more central processing units, memory, input devices (e.g., keyboard and pointing devices), output devices (e.g., display devices), storage devices (e.g., disk drives) and network devices (e.g., network interfaces). The memory and storage devices are computer-readable storage media that can store instructions that implement at least portions of the described technology. In addition, the data structures and message structures can be stored or transmitted via a data transmission medium, such as a signal on a communications link. Various communications links can be used, such as the Internet, a local area network, a wide area network, or a point-to-point dial-up connection. Thus, computer-readable media can comprise computer-readable storage media (e.g., “non-transitory” media) and computer-readable transmission media. 
         [0063]    As used herein, the word “or” refers to any possible permutation of a set of items. For example, the phrase “A, B, or C” refers to at least one of A, B, C, or any combination thereof, such as any of the following: A; B; C; A and B; A and C; B and C; A, B, and C; or multiples of any item such as A and A; B, B, and C; A, A, B, C, and C; etc. 
         [0064]    Although the subject matter has been described in language specific to structural features and/or methodological acts, it is to be understood that the subject matter defined in the appended claims is not necessarily limited to the specific features or acts described above. Specific embodiments and implementations have been described herein for purposes of illustration, but various modifications can be made without deviating from the scope of the embodiments and implementations. The specific features and acts described above are disclosed as example forms of implementing the claims that follow. Accordingly, the embodiments and implementations are not limited except as by the appended claims. 
         [0065]    Any patents, patent applications, and other references noted above are incorporated herein by reference. Aspects can be modified, if necessary, to employ the systems, functions, and concepts of the various references described above to provide yet further implementations. If statements or subject matter in a document incorporated by reference conflicts with statements or subject matter of this application, then this application shall control.