AUTOMATED DATA PARSING

• US 20140280256A1
• Filed: 03/17/2014
• Published: 09/18/2014
• Est. Priority Date: 03/15/2013
• Status: Active Grant

• Current Assignee: Wolfram Alpha LLC (Wolfram Research Incorporated)
• Original Assignee: Wolfram Alpha LLC (Wolfram Research Incorporated)
• Inventors: Wolfram, Stephen, Beynon, Taliesin Sebastian
• Granted Patent: US 9,875,319 B2
• Time in Patent Office: Days
• US Class Current: 707/755
• CPC Class Codes: G06F 16/90 Details of database functions independent of the retrieved data types
• CPC Class Codes: G06F 40/205 Parsing
• CPC Class Codes: G06F 8/37 Compiler construction; Parser generation

Abstract

A framing technique included in a set of framing techniques is applied to at least a portion of a target data set. When a result of the application of the framing technique meets a first condition, a typing technique included in a set of typing techniques is applied to the target data set. When a result of the application of the typing technique meets a second condition, a tokenization technique included in a set of tokenization techniques is applied to the target data set. When a result of the application of the tokenization technique meets a third condition, a parsing technique for the target data set is determined to include the framing technique, the typing technique and the tokenization technique. An indication of the parsing technique is generated.

Claims

1. A method for determining a parsing technique for a target data set, the method comprising:

receiving, via a communication link at one or more computing devices, a target data set;

applying a framing technique included in a set of framing techniques to at least a portion of the target data set;

when a result of the application of the framing technique meets a first condition across the at least the portion of the target data set, applying a typing technique included in a set of typing techniques to the at least the portion of the target data set, the typing technique corresponding to the framing technique;

when a result of the application of the typing technique meets a second condition across the at least the portion of the target data set, applying a tokenization technique included in a set of tokenization techniques to the at least the portion of the target data set, the tokenization technique corresponding to the typing technique; and

when a result of the application of the tokenization technique meets a third condition across the at least the portion of the target data set,

determining the parsing technique for the target data set to include the framing technique, the typing technique and the tokenization technique; and

causing an indication of the parsing technique to be generated by the one or more computing devices,

wherein the set of framing techniques, the set of typing techniques and the set of tokenization techniques are included in a set of defined parsing techniques.

2. The method of claim 1, further comprising at least one of:

selecting the framing technique based on a value of a confidence indicator corresponding to the framing technique, the value of the confidence indicator corresponding to the framing technique being indicative of a measure of confidence that the framing technique is applicable to the target data set;

selecting the typing technique based on a value of a confidence indicator corresponding to the typing technique, the value of the confidence indicator corresponding to the typing technique being indicative of a measure of confidence that the typing technique is applicable to the target data set;

or

selecting the tokenization technique based on a value of a confidence indicator corresponding to the tokenization technique, the value of the confidence indicator corresponding to the tokenization technique being indicative of a measure of confidence that the tokenization technique is applicable to the target data set.

3. The method of claim 1,

further comprising updating a value of at least one confidence indicator corresponding to the set of defined parsing techniques based on at least one of:

(i) the result of the application of the framing technique, (ii) the result of the application of the typing technique, or (iii) the result of the application of the tokenization technique,

wherein the value of the confidence indicator is indicative of a measure of confidence that a particular parsing technique corresponding to the confidence indicator is applicable to the target data set.

4. The method of claim 3, further comprising determining, based on the updated value, that one or more parsing techniques of the set of defined parsing techniques is inapplicable to the target data set.

5. The method of claim 3, wherein:

the framing technique is a first framing technique, the typing technique is a first typing technique, and the tokenization technique is a first tokenization technique; and

the method further comprises;

selecting, based on the updated value of the at least one confidence indicator, at least one of;

a second framing technique, a second typing technique, or a second tokenization technique;

applying the selection to the target data set; and

evaluating a result of the application of the selection to the target data set against a respective condition.

6. The method of claim 1, further comprising at least one of:

when the result of the application of the framing technique fails to meet the first condition, generating a first determination that the framing technique and defined parsing techniques that are dependent on the framing technique is inapplicable to the target data set;

when the result of the application of the typing technique fails to meet the second condition, generating a second determination that the typing technique and defined parsing techniques that are dependent on the typing technique are inapplicable to the target data set;

or

when the result of the application of the tokenization technique fails to meet the third condition, generating a third determination that the tokenization technique is inapplicable to the target data set.

7. The method of claim 6,

the framing technique is a first framing technique, the typing technique is a first typing technique, and the tokenization technique is a first tokenization technique;

and

wherein the method further comprises;

selecting, based on at least one of the first determination, the second determination, or the third determination, at least one of;

a second framing technique, a second typing technique, or a second tokenization technique;

applying the selection to the target data set; and

evaluating a result of the application of the selection to the target data set against a respective condition.

8. The method of claim 1, further comprising parsing the target data set using the determined parsing technique to generate a parsed data set, and wherein causing the indication of the parsing technique to be generated comprises causing the parsed data set to be provided to an application.

9. The method of claim 1, wherein each of the first condition, the second condition and the third condition respectively corresponds to at least one of:

a threshold of consistency or inconsistency,

a threshold of compatibility or incompatibility, or

a threshold of coherence or incoherence.

10. The method of claim 1, further comprising determining a candidate class of parsing techniques from the set of parsing techniques, the candidate class of parsing techniques being a subset of the set of parsing techniques and including the framing technique, the typing technique, and the tokenization technique.

11. The method of claim 10, wherein determining the candidate class of parsing techniques comprises determining the candidate class of parsing techniques to include all defined parsing techniques included in the set of defined parsing techniques.

12. The method of claim 10, wherein:

determining the candidate class of parsing techniques comprises selecting the candidate class from the set of defined parsing techniques based on a value of a confidence indicator corresponding to the candidate class, and

the value of the confidence indicator is indicative of a measure of confidence that the target data set is included in the candidate class.

13. The method of claim 12, further comprising determining an initial value of the confidence indicator corresponding to the candidate class based on historical data.

14. The method of claim 10, wherein:

the candidate class of parsing techniques is a first candidate class; and

updating the value of at least one confidence indicator corresponding to the set of parsing techniques comprises at least one of;

updating a value of at least one confidence indicator corresponding to the first candidate class, or

updating a value of at least one confidence indicator corresponding to a second candidate class.

15. An automated data parsing system for automatically parsing a target data set, the system comprising:

an interface to a communication link, the interface configured to receive the target data set;

an evaluator engine configured to determine a parsing technique for the target data set, the determination based on an evaluation of at least one candidate parsing technique against the target data set, the at least one candidate parsing technique included in a set of candidate parsing techniques;

a register configured to store a set of confidence indicators corresponding to the set of candidate parsing techniques, wherein a set of values of the set of confidence indicators are updated based on a result of an application of the at least one candidate parsing technique to the target data set; and

an output engine configured to provide an output corresponding to the parsing technique.

16. The system of claim 15, further comprising a parsing execution engine configured to parse the target data set using the parsing technique to generate a parsed data set, and wherein the output provided by the output engine includes the parsed data set.

17. The system of claim 15, wherein the output engine is configured to provide the output corresponding to the parsing technique when the set of values of the set of confidence indicators meet a condition, the condition including at least one of:

at least a subset of the set of values of the set of confidence indicators corresponds to at least one of an absolute threshold or a relative threshold;

each member of the set of candidate parsing techniques has been evaluated against the target data set;

or

a time limit has been reached.

18. The system of claim 15, wherein the parsing technique for the target data set comprises:

a framing technique to determine a structure of at least a portion of the target data set,

a typing technique to determine a format of one or more entries included in the target data set, and

a tokenization technique to determine and interpret segments of information included in the one or more entries of the target data set.

19. The system of claim 15, wherein the at least one candidate parsing technique comprises at least one of:

one or more candidate framing techniques operable on data sets to determine respective structures of one or more portions of the data sets,

one or more candidate typing techniques operable on the data sets to determine formats of entries included in the data sets, or

one or more candidate tokenization techniques operable on the data sets to determine and interpret segments of information included in the entries of the data sets.

20. The system of claim 15, wherein the application of the at least one candidate parsing technique comprises an application of the at least one candidate parsing technique to at least a portion of the target data set.

21. The system of claim 15, wherein the evaluator engine is further configured to:

initiate an evaluation of the at least one candidate parsing technique against the target data set, including generating the application of the at least one candidate parsing technique to at least a portion of the target data set;

update a value of at least one confidence indicator based on a result of the initiated evaluation of the at least one candidate parsing technique.

22. The system of claim 21, wherein the at least one confidence indicator having the updated value corresponds to another candidate parsing technique that is excluded from the at least one candidate parsing technique.

23. The system of claim 21, wherein:

the at least a portion of the target data set is a first portion of the target data set, and the at least one candidate parsing technique is a first at least one candidate parsing technique; and

the evaluator engine is further configured to, based on the updated value of the at least one confidence indicator, at least one of;

initiate an evaluation of a second at least one candidate parsing technique against the target data set;

apply the first at least one candidate parsing technique to a second portion of the target data set;

or

cause an evaluation of candidate parsing technique that is excluded from the at least one candidate parsing technique to be terminated.

24. The system of claim 15, wherein a value of a particular confidence indicator corresponding to a particular candidate parsing technique is indicative of a measure of confidence that the particular parsing technique is applicable to the target data set.

25. The system of claim 15, wherein at least a subset of the set of confidence indicators corresponds to the at least one candidate parsing technique, and wherein the at least the subset includes at least one of:

a first confidence indicator corresponding to a candidate framing technique,

a second confidence indicator corresponding to a candidate typing technique, or

a third confidence indicator corresponding to a candidate tokenization technique.

26. The system of claim 15, wherein the evaluator engine is further configured to determine the set of candidate parsing techniques.

27. The system of claim 15, wherein the evaluator engine is further configured to determine a set of initial values of the set of confidence indicators.

28. The system of claim 15, wherein the evaluator engine is further configured to determine the set of initial values of the set of confidence indicators based on at least one of:

historical data or a characteristic of the target data set.

29. The system of claim 15, wherein the evaluator engine is further configured to generate a new candidate parsing technique applicable to other target data sets, the generation of the new candidate parsing technique based on the evaluation of the at least one candidate parsing technique against the target data set.

30. The system of claim 15, wherein the parsing technique for the target data set determined by the evaluator engine is applicable to the target data set.

31. The system of claim 15, wherein:

the set of candidate parsing techniques is included in a set of defined parsing techniques;

the set of defined parsing techniques includes one or more classes of parsing techniques, and each of the one or more classes includes a respective set of framing techniques, a respective set of typing techniques, and a respective set of tokenization techniques; and

the evaluator engine is further configured to select the set of candidate parsing techniques based a value of a confidence indicator corresponding to a particular class of parsing techniques, the particular class including at least a subset of the set of candidate parsing techniques.