AUTOMATIC DATA EXTRACTION

Described are methods for automatically extracting data from structured documents e.g. spreadsheets, regardless of the manner in which data is organized, and using the extracted data to generate an output table that is in a standardized format. The method can include the operations for automatically extracting data from a spreadsheet that defines rows and columns and includes a plurality of cells that are delineated by the rows and the columns, by identifying characteristics of data included in each cell of the column, determining a template type of the column based on the characteristics of the data in each selected cell of the column, and determining, from among a plurality of cells of the column and based on characteristics of the data included in the plurality of cells of the column, a representative cell that is representative of the determined template type of the column.

TECHNICAL FIELD

This specification generally relates to automatically extracting data stored in digital files e.g., spreadsheets.

BACKGROUND

A spreadsheet (also referred to as a worksheet) is a type of an electronic document that has defined rows and columns making up a grid, in which data can be input and stored.

Data in a spreadsheet can be organized in numerous ways. As one example, data in a spreadsheet can be organized in a single table-format (also referred to as a one-dimensional table). In this example, the data in the table can be organized such that the first row of the table specifies headings for a set of columns and each subsequent row of the table includes data entries for the respective columns. As another example, data in a spreadsheet can be organized in a two-dimensional table-format. In this example, the data in the table can be organized such that the first row of the table specifies headings for a set of columns and the first column of the table specifies headings for a set of rows, and each row of the resulting table includes data entries for each of the respective rows and columns. As another example, data in the spreadsheet can be organized using multiple smaller tables or groupings of data, in which one or more of the tables are related (e.g., one or more tables may be part of one or more larger tables). As will be appreciated, there can be many additional ways in which data can be stored/organized in a spreadsheet.

As a result, conventional spreadsheet data analysis tools that generally function on a contiguous set of data (e.g., data organized in a contiguous set of rows and columns of the spreadsheet) cannot be readily used to analyze data in these columns—without restructuring and/or reformatting the data in the spreadsheet.

SUMMARY

This specification (and the accompanying appendices) generally relate to automatically extracting data from a spreadsheet, regardless of the manner in which data is organized in the spreadsheet, and using the extracted data to generate an output table that is in a standardized format (e.g., a one-dimensional table, a two-dimensional table, etc.).

In one aspect, a method can include the operations for automatically extracting data from a spreadsheet that defines rows and columns and includes a plurality of cells that are delineated by the rows and the columns, the operations can include: obtaining the spreadsheet, wherein the spreadsheet includes data that is stored in a set of rows and a set of columns of the spreadsheet; receiving a contiguous selection of cells of the spreadsheet, wherein the contiguous selection of cells spans a first set of rows and a first set of columns, and wherein the first set of rows is a subset of the set of rows and the first set of columns is a subset of the set of columns; for each column in the first set of columns: identifying characteristics of data included in each cell of the column; determining a template type of the column based on the characteristics of the data in each selected cell of the column, wherein the template type includes a categorical template or a detailed record template, and wherein (1) a categorical template specifies that data stored in the column includes categorical data that is associated with a plurality of rows of data in an extracted dataset or (2) a detailed record template specifies that data stored in the column includes detailed data that is associated with a single row of data in the extracted dataset; and determining, from among a plurality of cells of the column and based on characteristics of the data included in the plurality of cells of the column, a representative cell that is representative of the determined template type of the column; selecting, from among the first set of columns, a second set of columns that includes each column that is determined to be categorical template columns and a third set of columns that includes one or more columns that are determined to be detailed record template columns; identifying, based on the representative cells in each of the first set of columns, a single row in the contiguous selection, wherein each of a plurality of cells in the single row includes data in a format and a structure that is representative of a format and a structure of data stored in a corresponding column for the cell; generating, for each column in the third set of columns corresponding to the single row, a set of rules that define data extraction locations in the column; generated, based on the single row, the second set of columns, the third set of columns, and the set of rules for each of the third set of columns, an extracted dataset; and providing the extracted dataset for display on a computing device. Other embodiments of this aspect include corresponding methods, apparatus, and computer programs, configured to perform the actions of the methods, encoded on computer storage devices. These and other embodiments can each optionally include one or more of the following features.

In some implementations, identifying the third set of columns that includes one or more columns that are determined to be detailed record template columns, can include: determining a candidacy fitness score for each column in the first set of columns, wherein the candidacy fitness score for a particular column specifies a likelihood of the particular column being suitable for data extraction; and identifying, from among the first set of columns, the one or more columns based on the candidacy fitness score for each of the one or more columns being higher relative to the candidacy fitness score for each of a remaining number of columns in the first set of columns.

In some implementations, the candidacy fitness score for each column in the first set of columns can be determined based on: whether the column includes numeric data, text data, or data identifying dates; and whether the column is sparsely populated, wherein a column is sparsely populated if a threshold number of cells of the column are blank.

In some implementations, the characteristics of data in each selected cell of the column can include one or more of: a type of the data that specifies whether the data is a text, a number, a currency, or a date; border characteristics of the cell including the data; color or shading characteristics of the cell including the data; font characteristics of the data; and alignment characteristics of the data within the cell.

In some implementations, determining a representative cell that is representative of the determined template type of the column, can include: for each of the plurality of cells in the column: computing a score for a set of metrics, including a largest like metric, a smallest like metric, a smallest like background metric, a largest like data type, and a content length metric; determining a weighted score for each metric in the set of metrics by combining a weight assigned to the metric with the computed score for the metric; and combining the weighted score each metric to obtain a combined weighted score for the cell; and determining that the combined weighted score for the representative cell exceeds the combined weighted score for each of a remaining cells in the plurality of cells.

The techniques described in this specification (and the accompanying appendices) can be implemented in particular embodiments to realize the following advantages. Specifically, the techniques described in this specification can automatically (e.g., without any user input or with very limited user input, such as a user's selection of a portion of the spreadsheet) infer the structure and organization of a spreadsheet and extract data from the spreadsheet.

DETAILED DESCRIPTION

Described herein are systems and methods for automatic data extraction from documents, e.g., spreadsheets. Some conventional solutions attempt to extract data from documents. However, such solutions are generally able to extract data only when data is organized/structure in certain known ways. In other words, such solutions are generally unable to handle new ways in which data may be structured or organized. This in turn results in poor data extraction and/or requires additional functionality/development to try to extract data using the new data organization/structure. As a result, such conventional solutions can be resource intensive, may require constant updating, and yet may not accurately or consistently extract data from a spreadsheet. In contrast, the techniques described in this specification are agnostic to the structure and organization of the data in a document and can efficiently and consistently extract data from spreadsheets regardless of the structure/organization of data in these documents. While in the examples used herein the documents are generally spreadsheets, it will be recognized that the same techniques can be applied to other types of documents, e.g., PDF documents etc.

An example system100for data extraction is shown inFIG.1. The system100includes a data extraction platform150maintained on a server computer system102that includes one or more server computers.

The server computer system102is illustrated as a respective single component. However, in practice, it can be implemented on one or more computing devices (e.g., each computing device including at least one processor such as a microprocessor or microcontroller). A server computer system102can be, for instance, a single computing device that is connected to the network106, and the data extraction platform150can be maintained and operated on the single computing device. In some implementations, the server computer system102can include multiple computing devices that are connected to the network106, and the data extraction platform150can be maintained and operated on some or all of the computing devices. For instance, the server computer system102can include several computing devices, and the data extraction platform150can be distributive on one or more of these computing devices. In some implementations, the server computer system102need not be located locally to the rest of the system100, and portions of a server computer system102can be located in one or more remote physical locations.

The server computer system102is communicatively connected to client computer systems104a-cusing the network106. Each client computer system104a-cincludes a respective user interface108a-c. Users interact with the user interfaces108a-cto view data (e.g., data on the server computer system102and the platform150, and/or data on other the client computer systems104a-c). Users also interact with the user interfaces108a-cto transmit data to other devices (e.g., to the server computer system102and the platform150, and/or to the other client computer systems104a-c). Users interact with the user interfaces108a-cto issue commands (e.g., to the server computer system102and the platform150, and/or to the other client computer systems104a-c). Commands can be, for example, any user instruction to the server computer system102and/or to the other client computer systems104a-c. In some implementations, a user can install a software application onto a client computer system104a-cin order to facilitate performance of these tasks. For example, data extraction platform150can be installed on a client computer system104a-cas a stand-alone platform that does not require a connection to the server computer system102.

A client computer system104a-ccan be any electronic device that is used by a user to view, process, transmit and receive data. Examples of the client computer systems104a-cinclude computers (such as desktop computers, notebook computers, server systems, etc.), mobile computing devices (such as cellular phones, smartphones, tablets, personal data assistants, notebook computers with networking capability), and other computing devices capable of transmitting and receiving data from the network106. The client computer systems104a-ccan include devices that operate using one or more operating system (e.g., Microsoft Windows, Apple OS X, Linux, Unix, Android, Apple iOS, etc.) and/or architectures (e.g., x86, PowerPC, ARM, etc.) In some implementations, one or more of the client computer systems104a-cneed not be located locally with respect to the rest of the system100, and one or more of the client computer systems104a-ccan be located in one or more remote physical locations.

The server computer system102is also communicatively connected to data extraction computer systems110aand110busing the network106. The data extraction computer systems110aand110bstore electronic content items (e.g., one or more data files, images, audio files, video files, computerized models, text files, spreadsheets, and/or other electronic content). Each data extraction computer system110aand110bis illustrated as a respective single component. However, in practice, a data extraction computer system110aor110bcan be implemented on one or more computing devices (e.g., each computing device including at least one processor such as a microprocessor or microcontroller). A data extraction computer system110aor110bcan be, for instance, a single computing device that is connected to the network106. In some implementations, a data extraction computer system110aor110bcan include multiple computing devices that are connected to the network106. In some implementations, the data extraction computer system110aand110bneed not be located locally to the rest of the system100, and portions of the data extraction computer system110aand110bcan be located in one or more remote physical locations.

The network106can be any communications network through which data can be transferred and shared. For example, the network106can be a local area network (LAN) or a wide-area network (WAN), such as the Internet. The network106can be implemented using various networking interfaces, for instance wireless networking interfaces (such as Wi-Fi, Bluetooth, or infrared) or wired networking interfaces (such as Ethernet or serial connection). The network106also can include combinations of more than one network, and can be implemented using one or more networking interfaces.

In some embodiments, as described above with reference to client devices1-4a-c, the data extraction platform may be executed on a stand-alone workstation. The workstation may, or may not be connected to a network.

FIG.2shows various aspects of the data extraction platform150. The data extraction platform150includes several modules that perform particular functions related to the operation of the system100. For example, the data extraction platform150can include a storage module202, a transmission module204, and a processing module206. The output of the data extraction platform150can be extracted data208, which is a subset of the input data212.

The storage module202can store input data212as one or more data files, text files, and/or other electronic content. In some cases, at least some of the electronic content items stored by the storage module202are obtained from the data extraction computer systems110aand/or110b. Further, the storage module202can store information describing the electronic content items. Input data212can be one or more files from which data is to be extracted, for example a spreadsheet in which data is input/organized in multiple tables. For example, the spreadsheet can be a shipping report that includes multiple tables, with each table storing data regarding a particular purchase order for a particular customer. While the spacing and separation of the different tables within the spreadsheet can visually aid a viewer discern the data about each purchase order in the spreadsheet, this separation and spacing between the different tables can make data analysis of the entire dataset challenging.

The storage module can further store data extraction rules210, e.g., rules indicating a location of data to be extracted.

The storage module can store one or more templates214for data extraction. The template214can be selected based on the characteristics of the data in the input data212. For example, for a column of a spreadsheet from which data is to be extracted, in each selected cell of the column, template types can include a categorical template or a detailed record template. A categorical template specifies that data stored in the column includes categorical data that is associated with a plurality of rows of data in an extracted dataset. A detailed record template specifies that data stored in the column includes detailed data that is associated with a single row of data in the extracted database.

The transmission module204allows for the transmission of data to and from the data extraction platform150. For example, the transmission module204can be communicatively connected to the network106, such that it can transmit data to the client computer systems104a-c, and receive data from the client computer systems104a-cvia the network106. As an example, information inputted by users on the client computer systems104a-ccan be transmitted to the data extraction platform150through the transmission module204. This information can then be processed (e.g., using the processing module206) and/or stored (e.g., using the storage module202). As another example, information from the data extraction platform150(e.g., information stored on the storage module202) can be transmitted to the client computer systems104a-cthrough transmission module204.

The processing module206processes data stored or otherwise accessible to the data extraction platform150. For instance, the processing module206can execute automated or user-initiated processes that extract data pertaining to one or more input items212. As an example, the processing module206can deploy templates214and data extraction rules210to extract data from input data212. Further, the processing module206can process data that is received from the transmission module204or stored at the storage module202. Likewise, processed data from the processing module206can be stored on the storage module202and/or sent to the transmission module204for transmission to other devices. Example processes that can be performed by the processing module206are described in greater detail below.

As described above, one or more implementations of the data extraction platform150enables a user to extract data208from input data212. The extracted data208can be provided as a separate spreadsheet (e.g., within a separate spreadsheet document or within a separate sheet of the received spreadsheet document). In some implementations, the extracted data can be provided as an input to another system (e.g., an enterprise resource planning (ERP) system, an analytics system, etc.), which in turn can perform further processing on this output data. Examples of this functionality is illustrated inFIGS.3-8.

FIG.3is a flow diagram of an example method of data extraction. In an example a platform for data extraction e.g., platform150can obtain302a spreadsheet that defines rows and columns and includes plurality of cells that are delineated by the rows and the columns.

The platform receives304a contiguous selection of cells of the spreadsheet, wherein the contiguous selection of cells spans a first set of rows and a first set of columns, and wherein the first set of rows is a subset of the set of rows and the first set of columns is a subset of the set of columns. The can be received via user input, for example by selecting, highlighting or otherwise inputting via a user interface a selection of cells.

For each column in the first set of column, the platform identifies306characteristics of data included in each cell of the column. For example, the data extraction platform may analyze one or more aspects of the data in each cell to determine if, for instance, the data is text data, numeric data, time/data etc. If the data is text data, the data extraction platform may determine a type of the data that specifies whether the data is a text, a number, a currency, or a date, border characteristics of the cell including the data, color or shading characteristics of the cell including the data, font characteristics of the data, alignment characteristics of the data within the cell, etc.

The platform further determines308a template type of the column based on the characteristics of the data in each selected cell of the column. One example template type includes a categorical template. Categorical templates specify that data stored in the column includes categorical data that is associated with a plurality of rows of data in an extracted dataset. For example, an append template defines a shape or pattern whose matches correspond to categorical data that applies to one or more records. Another example of a template is a detailed record template. Detailed record templates specify that data stored in the column includes detailed data that is associated with a single row of data in the extracted dataset. For example, the detail template can define a shape or pattern whose matches correspond one-to-one with a single row of tabular data in the extracted table. A further type of template is an append template.

The template type of the column is determined308by constructing a column template evaluation node network (described with reference toFIG.4below). An evaluation node is a single logical unit that accepts an input container (a data structure containing all references and data required for formula evaluation within each node of a node network.) and a statistics aggregator. The node evaluates a formula based on its input and submits its evaluation score with a corresponding categorization type and type weight to the statistics aggregator. Evaluation then proceeds to one or more referenced evaluation nodes or terminates the evaluation process based upon how the evaluation score relates to a pass threshold, e.g., a decimal value between 0.0 and 1.0 that represents the minimum evaluation score to categorize a formula result e.g., meets, exceeds the pass threshold of the evaluation score. The evaluation node network is a collection of evaluation node logical units that has a defined starting node. Given its defined input, a statistics aggregator is compiled with each evaluation node's result and is returned as the output of the network. The network itself contains the predefined node structure that all input passes through.

For example, the column template evaluation node network may use a statistical aggregator, where a statistical aggregator is container for all categorization types that are being evaluated. Each entry contains a categorization type paired with a weighted average that can be updated by providing an evaluation score and a type weight. The statistical aggregator outputs the categorization type with the highest weighted average. The categorization type is a singular entry in a given set of uniquely identifiable members. If two or more categorization types are tied for the highest weighted average, the categorization type with the highest type weight is chosen. Where the type weight is an integer value between 1 and 10 that represents how heavily an evaluation score should affect a weighted average for a given categorization type. One is considered the lowest or lightest weight, whereas 10 is considered the highest or heaviest weight.

The platform determines310from among a plurality of cells of the column and based on characteristics of the data included in the plurality of cells of the column, a representative cell that is representative of the determined template type of the column. The output of the node network can be stored in an evaluation node network output container data structure that stores information related to and calculated by Node Network output. The node network output container contains a Template Type, the selection column index, the selection column's candidacy fitness evaluation score, and a row index of the cell that has been identified as the most representative of the Template Type's data within that column.

The platform determines310the cell that is representative of the determined template type of the column by initiating a detail column node network (described in more detail with reference toFIG.5, andFIG.6) or append column node network (described in more detail with reference toFIG.7) depending on whether the template type is a detail template or a categorical template, respectively. Using the statistics aggregator returned from the detail column node network or append column node network, the platform150acquires the row index location of the cell associated to the highest average evaluation score and add it to the current Node Network Output Container.

Determining310the cell that is representative can include, for each of the plurality of cells in the column, computing a score for a set of metrics, including a largest like metric, a smallest like metric, a smallest like background metric, a largest like data type, and a content length metric. A weighted score for each metric in the set of metrics can be determined by combining a weight assigned to the metric with the computed score for the metric. A combined weighted score for the cell can be determined by combining the weighted score for each metric to obtain a combined weighted score for the cell. When the combined weighted score for a representative cell exceeds the combined weighted score for each of the remaining cells in the plurality of cells, that cell is determined to be the representative cell.

If there are any columns remaining in the selection of cells then then items306-310are repeated312for each further column.

The platform selects314, from among the first set of columns, a second set of columns that includes each column that is determined to be categorical template columns and a third set of columns that includes one or more columns that are determined to be detailed record template columns. Further, the platform identifies316based on the representative cells in each of the first set of columns, a single row in the contiguous selection. Each of a plurality of cells in the single row includes data in a format and a structure that is representative of a format and a structure of data stored in a corresponding column for the cell.

In an implementation, the selecting314by the platform includes determining a candidacy fitness score for each column in the first set of columns. The candidacy fitness score for a particular column specifies a likelihood of the particular column being suitable for data extraction. The selecting314can further include identifying, from among the first set of columns, the one or more columns based on the candidacy fitness score for each of the one or more columns being higher relative to the candidacy fitness score for each of a remaining number of columns in the first set of columns. The candidacy fitness score for each column in the first set of columns can be determined based on whether the column includes numeric data, text data, or data identifying dates; and whether the column is sparsely populated. A column is sparsely populated if a threshold number of cells of the column are blank.

The platform further identifies316, based on the representative cells in each of the first set of columns, a single row in the contiguous selection, wherein each of a plurality of cells in the single row includes data in a format and a structure that is representative of a format and a structure of data stored in a corresponding column for the cell.

For each column in the third set of columns corresponding to the single row, a set of rules can be generated318that define data extraction locations in the column. The rules can related to the value of a cell, the border, background, font, alignment, etc. The platform can then generate320, based on the single row, the second set of columns, the third set of columns, and the set of rules for each of the third set of columns, an extracted dataset and provide the extracted dataset for display on a computing device.

The data extraction process described with reference toFIG.3can be deployed on any computing system (e.g., one or more servers or another data processing apparatuses) that can be configured to receive, as input, spreadsheets from one or more devices or storage locations (e.g., databases, third party servers, etc.). The computing system, and in particular the automatic model definition algorithm, can be configured to receive a user selection of a contiguous set of data in the received spreadsheet (e.g., selection of data stored in a contiguous set of rows and columns), and to process this selection of data, without any further user input. Based on this processing, the data extraction process can infer the structure, formatting, and organization of the data in a structured document, e.g., spreadsheet. Based on this analysis/processing, the data extraction process can extract data from the spreadsheet and generate an output table using the extracted data that is in a standardized format (e.g., a one-dimensional table, a two-dimensional table, etc.).

FIG.4is a schematic diagram of an example column template evaluation node network400. The node network output container is data structure that stores information related to and calculated by Node Network output. The node network output container contains a Template Type, the selection column index, the selection column's candidacy fitness evaluation score, and a row index of the cell that has been identified as the most representative of the Template Type's data within that column. The column template evaluation node network400includes 3 types of nodes; two types of evaluation nodes (a single logical unit that accepts an input container) and network end nodes. The node evaluates a formula based on its input and submits its evaluation score with a corresponding categorization type and type weight to a statistics aggregator. Evaluation then proceeds to one or more referenced evaluation nodes or terminates the evaluation process based upon how the evaluation score relates to the pass threshold (e.g., meets, exceeds, etc.), and network end nodes402, which terminate the network output container. The two types of evaluation nodes are testing nodes404which evaluate a binary pass/fail condition, and function nodes406which compute an evaluation score that is representative of fitness for a particular condition or application. Each node has a pass threshold, e.g., a decimal value between 0.0 and 1.0 that represents the minimum evaluation score to categorize a formula result. Depending on whether the score computed at a node is a pass (e.g., passing state) or fail (e.g., failing state) the evaluation proceeds to a further node, until a network end node402is reached. Some example evaluation node types used in the column template evaluation node network400are described in Table 1.

TABLE 1Node NameFunction DescriptionAll Normal Font WeightCalculates a ratio of cells between those whose text content is non-bold, non-italic, and non-underlined, versus the total number of cells in a given columnexpressed as an evaluation score. Pass threshold is much closer to 1 in order toindicate a majority of normal values.All Bold Font WeightCalculates a ratio of cells between those whose text font weight is bold versusthe total number of non-blank cells in a given column expressed as anevaluation score. Pass threshold is much closer to 1 in order to indicate amajority of bold values.All Underlined TextCalculates a ratio of cells between those whose text font is underlined versusthe total number of non-blank cells in a given column selection expressed asan evaluation score. Pass threshold is much closer to 1 in order to indicate amajority of underlined values.All Italicized TextCalculates a ratio of cells between those whose text font is italicized versusthe total number of non-blank cells in a given column selection expressed asan evaluation score. Pass threshold is much closer to 1 in order to indicate amajority of italicized values.Partial Bold Font WeightCalculates a ratio of cells between those whose text font weight is bold versusthe total number of non-blank cells in a given column selection expressed asan evaluation score. Pass threshold is much closer to .5 to indicate a splitbetween bold and non-bold values.Partial Underlined TextCalculates a ratio of cells between those whose text font is underlined versusthe total number of non-blank cells in a given column selection expressed asan evaluation score. Pass threshold is much closer to .5 to indicate a splitbetween underlined and non-underlined values.Partial Italicized TextCalculates a ratio of cells between those whose text font is italicized versusthe total number of non-blank cells in a given column selection expressed asan evaluation score. Pass threshold is much closer to .5 to indicate a splitbetween italicized and non-italicized values.Font IntervalStarting at the top of the given column selection, counts the occurrences ofnormal text cell intervals between non-normal (includes bold, italic, andunderline) text cells. Standard deviation and average are calculated on thecollection of interval lengths and related to express an evaluation score.Font Metrics WithGiven a set of font metrics that occur within the column, calculates a ratio ofMatching Data Typecells between those whose cells have matching font metrics related to the mostfrequently occurring data type among those cells. of selection expressed as anevaluation score. Pass threshold is much closer to 1 to indicate a correlationbetween font metrics and template classification.Population IntervalStarting at the top of the given column selection, counts the occurrences ofcontiguous blank cell intervals between non-blank cells. Standard deviationand average are calculated on the collection of interval lengths and related toexpress an evaluation score.Partial BlankCalculates a ratio of cells between those whose cell content contains nocharacters, only white-space characters, or no value at all versus the totalnumber of cells in a given column expressed as an evaluation score. Passthreshold is much closer to .5 in order to indicate a majority of blank values.All Non-BlankCalculates a ratio of cells between those whose cell content contains nocharacters, only white-space characters, or no value at all versus the totalnumber of cells in a given column expressed as an evaluation score. Passthreshold is much closer to 1 in order to indicate a majority of non-blank values.Matching Data TypeCalculates a ratio of cells between those whose cell content matches the mostfrequently occurring data type versus the total number of cells in a givencolumn selection expressed as an evaluation score. Pass threshold is muchcloser to 1 in order to indicate a majority of similar data type content.

FIG.5is a schematic diagram of an example detail column candidacy node network. The detail column candidacy node network400, when given a single column within a contiguous rectangular selection on a document containing structured data e.g., a spreadsheet returns a Statistics Aggregator containing a single generic categorization type whose evaluation score weighted average represents the single column's fitness to contain a trap in the detail column template.

A trap is a worksheet (X, Y) location relative to a grouping of one or more traps, or that represents an origin point for data extraction. A trap contains a collection of rules that define data extraction locations in a single column. Traps can be combined across multiple columns or rows to produce specific record extraction locations. That is, the platform150acquires the row index location of the cell associated to the highest average evaluation score and associates it with a trap.

Rules can be, for example, a predicate expression evaluated on a single cell at a time in the spreadsheet. Rules have a type which determine the predicate function evaluated therein. For example, rules can related to values, borders, font, alignment, background, etc. as described above.

As described above with reference toFIG.4and the column template evaluation node network, the detail column candidacy node network500includes 3 types of nodes; two types of evaluation nodes (a single logical unit that accepts an input container) and network end nodes. The node evaluates a formula based on its input and submits its evaluation score with a corresponding categorization type and type weight to a statistics aggregator. Evaluation then proceeds to one or more referenced evaluation nodes or terminates the evaluation process based upon how the evaluation score relates to the pass threshold (e.g., meets, exceeds, etc.), and network end nodes502, which terminate the network output container. The two types of evaluation nodes are testing nodes504which evaluate a binary pass/fail condition, and function nodes506which compute an evaluation score that is representative of fitness for a particular condition or application. Each node has a pass threshold, e.g., a decimal value between 0.0 and 1.0 that represents the minimum evaluation score to categorize a formula result. Depending on whether the score computed at a node is a pass (e.g., passing state) or fail (e.g., failing state) the evaluation proceeds to a further node, until a network end node502is reached. Some example evaluation node types used in the detail column evaluation node network400are described in Table 2.

TABLE 2Node NameFunction DescriptionIs SparseCalculates an evaluation score based on the number of cells in a selection that areblank versus the total number of cells in that selection. A lower evaluation scorecorrelates to a less densely populated column and less desirable location for theconstruction of a Trap definition.Is Not SparseCalculates an evaluation score based on the number of cells in a selection that arenot blank versus the total number of cells in that selection. A higher evaluationscore correlates to a densely populated column and more desirable location for theconstruction of a Trap definition.Is NumericCalculates an evaluation score based on the number of cells in a selection whosetext value is classified as numeric versus the total number of cells in that selection.Pass threshold is much closer to .75 in order to indicate a majority of numeric values.Is Date/TimeCalculates an evaluation score based on the number of cells in a selection whosetext value is classified as a date/time versus the total number of cells in thatselection. Pass threshold is much closer to .75 in order to indicate a majority ofdate/time values.Is TextCalculates an evaluation score based on the number of cells in a selection whosetext value is classified as non-numeric and non-date/time versus the total numberof cells in that selection. Pass threshold is much closer to .75 in order to indicate amajority of non-numeric and non-date/time values.

FIG.6is a schematic diagram of an example detail column node network. Given a single column within a contiguous rectangular selection in a document the detail column node network, returns a Statistics Aggregator with an integer as its categorization type whose highest evaluation score represents the row index of the cell that has been identified as the most representative of the detail data within the column. The detail column node network includes function nodes602which (as previously described) compute an evaluation score that is representative of fitness for a particular condition or application. Each node has a pass threshold, e.g., a decimal value between 0.0 and 1.0 that represents the minimum evaluation score to categorize a formula result. The result transitions via one or more state transitions until a network end node604is reached. Some example evaluation node types used in the detail column node network600are described in Table 3.

TABLE 3Node NameFunction DescriptionLargest Like MetricCalculates an evaluation score based on the number of cells in a selection thatdiffer from the most frequently occurring set of font metrics in that selection.Dynamically weights row index integers as its categorization types with thelowest (closest to zero) receiving the highest weights.Smallest Like MetricCalculates an evaluation score based on the number of cells in a selection thatdiffer from the least frequently occurring set of font metrics in that selection.Dynamically weights row index integers as its categorization types with thelowest (closest to zero) receiving the highest weights.Smallest LikeCalculates an evaluation score based on the number of cells in a selection thatBackground Metricdiffer from the least frequently occurring cell background color in thatselection. Dynamically weights row index integers as its categorization typeswith the lowest (closest to zero) receiving the highest weights.Largest Like DataCalculates an evaluation score based on the number of cells in a selection thatTypediffer from the most frequently occurring data type in that selection.Dynamically weights row index integers as its categorization types with thelowest (closest to zero) receiving the highest weights.Content Length MetricCalculates an evaluation score based on an individual cell's text content lengthvariance from the standard deviation of all text content lengths (in characters)in a column selection. Dynamically weights row index integers as itscategorization types with the lowest (closest to zero) receiving the highest weights.

FIG.7is a schematic diagram of an example append column node network. Given a single column within a contiguous rectangular selection on an Excel worksheet, an append column node network returns a Statistics Aggregator with an integer categorization type whose highest evaluation score represents the row index of the cell that has been identified as the most representative of the append data within the column. The append column node network operates in a similar manner to the detail column node network described with reference toFIG.6. The append column node network includes function nodes702which (as previously described) compute an evaluation score that is representative of fitness for a particular condition or application. Each node has a pass threshold, e.g., a decimal value between 0.0 and 1.0 that represents the minimum evaluation score to categorize a formula result. The result transitions via one or more state transition until a network end node704is reached. Some example evaluation node types used in the append column evaluation node network700are described in Table 4.

TABLE 4Node NameFunction DescriptionSmallest Like MetricCalculates an evaluation score based on the number of cells in a selection thatdiffer from the least frequently occurring set of font metrics in that selection.Dynamically weights row index integers as its categorization types withthe lowest (closest to zero) receiving the highest weights.Largest Like MetricCalculates an evaluation score based on the number of cells in a selection that(Inverted Score)differ from the most frequently occurring set of font metrics in that selection.Dynamically weights row index integers as its categorization types with thelowest (closest to zero) receiving the highest weights. The evaluation score issubtracted from 1 to create an inverse score.Smallest Like DataCalculates an evaluation score based on the number of cells in a selection thatTypediffer from the least frequently occurring data type in that selection. Dynamicallyweights row index integers as its categorization types with the lowest (closest tozero) receiving the highest weights.Content LengthCalculates an evaluation score based on an individual cell's text content lengthMetricvariance from the standard deviation of all text content lengths (in characters) ina column selection. Dynamically weights row index integers as its categorizationtypes with the lowest (closest to zero) receiving the highest weights.

FIG.8is a schematic diagram of an example user interface800of a computing system within which the data extraction algorithm is executing. The bottom right portion of each screenshot shows the standardized output table (in this case, a one-dimensional table) that consolidates the data from the different tables included a structured data file, for example a spreadsheet.

In some implementations, the user interface of the model algorithm can be configured to provide controls that enable user modification of the inferences drawn by the algorithm about the data in the spreadsheet, which in turn enables quick modifications to the data to be extracted (without requiring the user/operator to have any programming knowledge).

FIG.9shows an example computer system900. Computer system900may be used to implement, at least in part, data extraction platform150. Process700can be performed at least in part, using the computer system900. Computer system900includes a processor910, a memory920, a storage device930and an input/output device940. Each of the components910,920,930and940can be interconnected, for example, by a system bus950. The processor910is capable of processing instructions for execution within the system900. In some implementations, the processor910is a single-threaded processor, a multi-threaded processor, or another type of processor. The processor910is capable of processing instructions stored in the memory920or on the storage device930. The memory920and the storage device930can store information within the system900.

The input/output device940provides input/output operations for the system900. In some implementations, the input/output device840can include one or more of a network interface device, e.g., an Ethernet card, a serial communication device, e.g., an RS-232 port, and/or a wireless interface device, e.g., an 802.11 card, a 3G wireless modem, a 4G wireless modem, a 5G wireless modem, etc. In some implementations, the input/output device can include driver devices configured to receive input data and send output data to other input/output devices, e.g., keyboard, printer and display devices960. In some implementations, mobile computing devices, mobile communication devices, and other devices can be used.

In this specification (including the accompany appendices), the different functions can be implemented using “engines,” which broadly refer to software-based systems, subsystems, or processes that are programmed to perform one or more specific functions. Generally, an engine is implemented as one or more software modules or components, installed on one or more computers, in one or more locations. In some cases, one or more computers can be dedicated to a particular engine; in other cases, multiple engines can be installed and running on the same computer or computers.

Data processing apparatus for implementing models described in this specification (including the accompany appendices) can also include, for example, special-purpose hardware accelerator units for processing common and compute-intensive parts of machine learning training or production, i.e., inference, workloads. Machine learning models can be implemented and deployed using a machine learning framework, e.g., a TensorFlow framework, a Microsoft Cognitive Toolkit framework, an Apache Singa framework, or an Apache MXNet framework.

Particular embodiments of the subject matter have been described in this specification (including the accompany appendices). Other embodiments are within the scope of the following claims. For example, the actions recited in the claims can be performed in a different order and still achieve desirable results. As one example, the processes depicted in the accompanying figures do not necessarily require the particular order shown, or sequential order, to achieve desirable results. In some cases, multitasking and parallel processing may be advantageous.