Automated transformation of unstructured data

• US 20050246353A1
• Filed: 05/03/2004
• Published: 11/03/2005
• Est. Priority Date: 05/03/2004
• Status: Abandoned Application

• Current Assignee: Cogniview Systems 2002 Limited
• Original Assignee: Cogniview Systems 2002 Limited
• Inventors: Ezer, Yoav, Hachlili, Guy, Dickman, Saar, Shir, Eran, Ruvio, Guy, Tayary, Ilan
• Application Number:
  US10/838,534
• Publication Number:
  US 20050246353A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 40/143 Markup, e.g. Standard Generalized Markup Language [SGML] or Document Type Definition [DTD]
• CPC Class Codes: G06F 40/18 of spreadsheets form-filling G06F40/174
• CPC Class Codes: G06F 40/186 Templates

Abstract

A data processing method for automatically identifying the underlying syntaxes of unstructured data items, where unstructured data items are strings that include incomplete syntactical information but implicitly are characterized by a nontrivial syntax. The method comprises receiving input of unstructured data items into a processing machine memory; and recognizing the underlying syntaxes of the data items by the processing machine by applying pattern recognition techniques, wherein this step comprises identifying potential syntax components; and combining the components until the underlying syntaxes emerge.

Claims

1. A data processing method for automatically identifying the underlying syntaxes of unstructured data items, where unstructured data items are strings that include incomplete syntactical information but implicitly are characterized by a nontrivial syntax, the method comprising:

receiving input of unstructured data items into a processing machine memory; and

recognizing the underlying syntaxes of the data items by the processing machine by applying pattern recognition techniques, wherein this step comprises;

identifying potential syntax components; and

combining the components until the underlying syntaxes emerge.

2. The method of claim 1 wherein combining the components is done stochastically.

3. The method of claim 1, wherein recognizing the underlying syntaxes of the data items comprises:

creating an initial pool of bots using deterministic heuristic methods, wherein a bot represents a potential element of a syntax;

creating an initial population of syntax models by choosing sets of bots from the pool of bots; and

applying combinatorial evolution algorithms to the initial population of syntax models to develop a syntax model for each data item.

4. The method of claim 3, wherein choosing of the sets of bots is done randomly.

5. The method of claim 3, wherein the step of creating an initial pool of bots using deterministic heuristic methods comprises:

applying a set of rules and templates to the data items to produce bots; and

combining the produced bots to create complex bots.

6. The method of claim 3 wherein the step of applying combinatorial evolution algorithms to the initial population of syntax models to develop a syntax model for each data item comprises:

evaluating a population of syntax models over a set of data items by applying a set of feedback rules, producing evaluation results, and possibly new bots;

if one or more bots are produced, adding the said one or more bots to the pool of bots;

applying a convergence test to the evaluation results, to produce convergence results and, if the convergence results are satisfactory, outputting a resultant syntax model;

applying, if the convergence results are unsatisfactory, a split test to the evaluation results;

splitting, if the split test requires it, the set of data items into two subsets and a syntax model population that is related to the set of data items into two subpopulations, and creating a new instance of the step of applying combinatorial evolution algorithms with one of the subsets and its corresponding subpopulation, while continuing to apply the combinatorial evolution algorithms to the second subset and corresponding subpopulation;

creating a population of candidate syntax models from the pool of bots, wherein each syntax model is composed of a set of bots; and

repeating the above steps until the convergence test results are satisfactory for all instances of the algorithm.

7. The method of claim 6, wherein satisfactory convergence results are determined by testing how close a current best solution is to a maxima and how close this maxima is to a global maxima.

8. The method of claim 6, wherein the step of creating a population of candidate syntax models from the pool of bots comprises:

copying top performing syntax models into a new population of syntax models;

creating new syntax models through recombination of two or more parent top performing syntax models;

creating new syntax models through structural manipulations of top performing syntax models which suffer a local fault in their structure by;

adding a bot if a consistent hole in coverage of a corresponding data item has been identified deleting a bot from a syntax model if its deletion improves the evaluation results of said syntax model changing order and properties of individual bots comprising the structure; and

creating syntax models from random sets of bots.

9. The method of claim 6, wherein the step of evaluating a population of candidate syntax models over a corresponding set of data items comprises

applying a set of feedback meta-rules, each of which outputs an evaluation result for each of the syntax models over each of the data items;

creating an overall evaluation result for each of the syntax models; and

identifying fault points in top performing models, where each fault point serves, in the step of creating a population of candidate syntax models from the pool of bots, to indicate a bad bot to be removed from a syntax model or a hole in the coverage of a syntax model.

10. The method of claim 6, wherein the step of adding a new bot to the pool of bots comprises identifying bots which correlate well to one another, or have a new meaning when put together, and creating a new bot in the pool of bots.

identifying variant repetitions of a bot, or a set of bots, and using the variant repetition to create a new, repeating, bot, where such a repeating bot can appear one or more times in one or more data items.

11. The method of claim 6, wherein the step of adding a new bot to the pool of bots comprises identifying variant repetitions of a bot, or a set of bots, and using the variant repetition to create a new, repeating, bot, where such a repeating bot can appear one or more times in one or more data items.

12. The method of claim 6, wherein the convergence test comprises at least one of the following:

testing the level of uniformity of the evaluation results of top performing candidate syntax models;

testing the derivative of the evaluation results across evolution generations;

testing the difference between the syntax model with the highest evaluation results and the syntax model with the lowest evaluation results; and

testing the rate of addition of new syntax models to the top crop of the population across several generations.

13. The method of claim 6, wherein the step of applying, if the results of the convergence test are unsatisfactory, a split test to the results of the evaluation;

comprises at least one of the following;

testing whether there is a dominant syntax model in the population of candidate syntax models that does not perform well on a subset of data items;

testing whether there are large variances in the average evaluation results of candidate syntax models over different, coexisting data items.

14. The method of claim 6, wherein the step of splitting comprises:

identifying a set of candidate syntax models, whose evaluation results are similar over a subset of data items and the corresponding subset of data items;

creating a new instance of the combinatorial evolution algorithms applied on the subpopulation and subset of data items; and

continuing the original instance of the combinatorial evolution algorithms with the remaining set of data items and subpopulation of candidate syntax models.

15. The method of claim 3 further comprising:

creating a data processing adapter from a syntax model; and

converting, using the adapter, unstructured data items into structured output.

16. The method of claim 15 wherein the structured output is in a database format.

17. The method of claim 15 wherein the structured output is in XML format.

18. The method of claim 15 wherein the structured output is in a spreadsheet format.

19. The method of claim 15 wherein the structured output is in a comma separated value (CSV) format.

20. The method of claim 15 wherein the structured output is in a hierarchical format.

21. The method of claim 3 further comprising identifying duplicate syntax models in data items that have the same underlying syntax as a set that the model is based on.

22. The method of claim 3 further comprising identifying deviations in data items that have the same underlying syntax as a set that the model is based on.

23. The method of claim 3 further comprising identifying levels of similarity in a set of syntax models.

24. The method of claim 3 further comprising transforming data items from one visual representation to another.

25. The method of claim 3 further comprising:

receiving a new data item;

matching a most suitable syntax model from a set of syntax models to the new data item.

26. The method of claim 3 further comprising dividing a set of data items into a set of clusters based on a set of corresponding syntax models.

27. A data processing system for automatically identifying underlying syntaxes of unstructured data items, where unstructured data items are strings that include incomplete syntactical information but implicitly are characterized by a nontrivial syntax, the system comprising a processor, a computer-readable medium operatively coupled to the processor and storing data, and a computer program executed by the processor from the medium and comprising:

module that receives input of unstructured data items into a processing machine memory; and

module that recognizes the underlying syntaxes of the data items by the processing machine by applying pattern recognition techniques, wherein this step comprises;

module that identifies potential syntax components; and

module that combines the components until the underlying syntaxes emerge.

28. The system of claim 27 wherein the module that combines the components does so stochastically.

29. The system of claim 27, wherein the module that recognizes the underlying syntaxes of the data items comprises:

module that creates an initial pool of bots using deterministic heuristic methods, wherein a bot represents a potential element of a syntax;

module that creates an initial population of syntax models by choosing sets of bots from the pool of bots; and

module that applies combinatorial evolution algorithms to the initial population of syntax models to develop a syntax model for each data item.

30. The system of claim 29, wherein the module that chooses of the sets of bots does so randomly.

31. The system of claim 29, wherein the module that creates an initial pool of bots does so using deterministic heuristic methods and comprises:

module that applies a set of rules and templates to the data items to produce bots; and

module that combines the produced bots to create complex bots.

32. The system of claim 29 wherein the module that applies combinatorial evolution algorithms to the initial population of syntax models to develop a syntax model for each data item comprises:

module that evaluates a population of syntax models over a set of data items by applying a set of feedback rules, producing evaluation results, and possibly new bots;

module that, if one or more bots are produced, adds the said one or more bots to the pool of bots;

module that applies a convergence test to the evaluation results, to produce convergence results and, if the convergence results are satisfactory, outputs a resultant syntax model;

module that applies, if the convergence results are unsatisfactory, a split test to the evaluation results;

module that splits, if the split test requires it, the set of data items into two subsets and a syntax model population that is related to the set of data items into two subpopulations, and creates a new instance of the step of applying combinatorial evolution algorithms with one of the subsets and its corresponding subpopulation, while continuing to apply the combinatorial evolution algorithms to the second subset and corresponding subpopulation;

module that creates a population of candidate syntax models from the pool of bots, wherein each syntax model is composed of a set of bots; and

module that repeats the above steps until the convergence test results are satisfactory for all instances of the algorithm.

33. The system of claim 32, wherein satisfactory convergence results are determined by a module that tests how close a current best solution is to a maxima and how close this maxima is to a global maxima.

34. The system of claim 32, wherein the module that creates a population of candidate syntax models from the pool of bots comprises:

module that copies top performing syntax models into a new population of syntax models;

module that creates new syntax models through recombination of two or more parent top performing syntax models;

module that creates new syntax models through structural manipulations of top performing syntax models which suffer a local fault in their structure by;

module that adds a bot if a consistent hole in coverage of a corresponding data item has been identified module that deletes a bot from a syntax model if its deletion improves the evaluation results of said syntax model module that changes order and properties of individual bots comprising the structure; and

module that creates syntax models from random sets of bots.

35. The system of claim 32, wherein the module that evaluates a population of candidate syntax models over a corresponding set of data items comprises

module that applies a set of feedback meta-rules, each of which outputs an evaluation result for each of the syntax models over each of the data items;

module that creates an overall evaluation result for each of the syntax models; and

module that identifies fault points in top performing models, where each fault point serves, in the module that creates a population of candidate syntax models from the pool of bots, to indicate a bad bot to be removed from a syntax model or a hole in the coverage of a syntax model.

36. The system of claim 32, wherein the module that adds a new bot to the pool of bots comprises a module that identifies bots which correlate well to one another, or have a new meaning when put together, and module that creates a new bot in the pool of bots.

identifying variant repetitions of a bot, or a set of bots, and using the variant repetition to create a new, repeating, bot, where such a repeating bot can appear one or more times in one or more data items.

37. The system of claim 32, wherein the module that adds a new bot to the pool of bots comprises a module that identifies variant repetitions of a bot, or a set of bots, and a module that uses the variant repetition to create a new, repeating, bot, where such a repeating bot can appear one or more times in one or more data items.

38. The system of claim 32, wherein the module that performs the convergence test comprises at least one of the following:

module that tests the level of uniformity of the evaluation results of top performing candidate syntax models;

module that tests the derivative of the evaluation results across evolution generations;

module that tests the difference between the syntax model with the highest evaluation results and the syntax model with the lowest evaluation results; and

module that tests the rate of addition of new syntax models to the top crop of the population across several generations.

39. The system of claim 32, wherein the module that applies, if the results of the convergence test are unsatisfactory, a split test to the results of the evaluation;

comprises at least one of the following;

module that tests whether there is a dominant syntax model in the population of candidate syntax models that does not perform well on a subset of data items;

module that tests whether there are large variances in the average evaluation results of candidate syntax models over different, coexisting data items.

40. The system of claim 32, wherein the module that splits comprises:

module that identifies a set of candidate syntax models, whose evaluation results are similar over a subset of data items and the corresponding subset of data items;

module that creates a new instance of the combinatorial evolution algorithms applied on the subpopulation and subset of data items; and

module that continues the original instance of the combinatorial evolution algorithms with the remaining set of data items and subpopulation of candidate syntax models.

41. The system of claim 32 further comprising:

module that creates a data processing adapter from a syntax model; and

module that converts, using the adapter, unstructured data items into structured output.

42. The system of claim 41 wherein the structured output is in a database format.

43. The system of claim 41 wherein the structured output is in XML format.

44. The system of claim 41 wherein the structured output is in a spreadsheet format.

45. The system of claim 41 wherein the structured output is in a comma separated value (CSV) format.

46. The system of claim 41 wherein the structured output is in a hierarchical format.

47. The system of claim 29 further comprising a module that identifies duplicate syntax models in data items that have the same underlying syntax as a set that the model is based on.

48. The system of claim 29 further comprising a module that identifies deviations in data items that have the same underlying syntax as a set that the model is based on.

49. The system of claim 29 further comprising a module that identifies levels of similarity in a set of syntax models.

50. The system of claim 29 further comprising a module that transforms data items from one visual representation to another.

51. The system of claim 29 further comprising:

module that receives a new data item;

module that matches a most suitable syntax model from a set of syntax models to the new data item.

52. The system of claim 29 further comprising module that divides a set of data items into a set of clusters based on a set of corresponding syntax models.