Patent ID: 8341096
Filing Date: 2012-12-25
Classification: G06F

Abstract:
1. A system for learning a data format, the system comprising: a processor in data communication with a computer readable medium; a computer program comprising instructions embedded in the computer readable medium, that when executed by a computer perform functions that are useful in learning the data format, the computer program further comprising instructions to input an initial description of a data format and a batch of data comprising data in a new data format not covered by the initial description, instructions to use the initial description to parse the records in a data source, instructions to discard records in the input data that parse successfully, instructions to collect records that fail to parse, instructions to accumulate a quantity, M of records that fail to parse, instructions to return a modified description that extends the initial description to cover the new data, instructions to transform the first description, D into a second description D′ to accommodate differences between the input data format and the first description D by introducing options where a piece of data was missing in the input data and introducing unions where a new type of data was found in the input data; and instructions to use a non-incremental format inference system to infer descriptions for an aggregated portions of input data that did not parse using the first description D, wherein a term with type R is a parse tree obtained from parsing the input data using a description D and wherein parsing a base type results in a value with the corresponding type, wherein a parse of a pair is a pair of representations, and a parse of a union is a parse selected from the group consisting of a parse of a first branch of the union or a parse of the second branch of the union, the system further comprising: an aggregate data structure embedded in the computer readable medium for containing data indicating an accumulation of parse trees and data that cannot be parsed using the first description, D and therefore must be re-learned, a learn node data structure embedded in the computer readable medium containing data indicating an accumulation of the data that did not parse using the first description that needs to be learned, the computer program further comprising instructions to finish parsing all the data, instructions to obtain a final list of aggregates and instructions to select the best aggregate according to at least one criterion, instruction to update the first description, D to produce the new description D′ using the best aggregate and instructions to introduces Opt nodes whenever a corresponding Base or Sync token in the initial description D, failed to parse, wherein when faced with an entirely new form of data, the computer program further comprises instructions to apply a set of rewriting rules that server to improve the description by reducing a metric designed to measure description quality, the computer program further comprising instructions to rank the parses by a metric that measures their quality and return only the top quantity k of the parses metric comprises a triple: m=(e, s, c), where e is a quantity of errors, s is a quantity of characters skipped during Sync token recovery, and c is a quantity of characters correctly parsed.