DATA DETECTION

• US 20100121631A1
• Filed: 11/10/2008
• Published: 05/13/2010
• Est. Priority Date: 11/10/2008
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Goyet, Romain, de Jaeger, Frederick, Bonnet, Olivier, Ciudad, Jean-Pierre
• Granted Patent: US 8,489,388 B2
• Time in Patent Office: Days
• US Class Current: 704/9
• CPC Class Codes: G06F 40/205 Parsing
• CPC Class Codes: G06F 40/216 using statistical methods
• CPC Class Codes: G06V 30/10 Character recognition
• CPC Class Codes: G06V 30/268 Lexical context
• CPC Class Codes: G06V 30/274 Syntactic or semantic context, e.g. balancing

Abstract

A method for detecting data in a sequence of characters or text using both a statistical engine and a pattern engine. The statistical engine is trained to recognize certain types of data and the pattern engine is programmed to recognize the grammatical pattern of certain types of data. The statistical engine may scan the sequence of characters to output first data, and the pattern engine may break down the first data into subsets of data. Alternatively, the statistical engine may output items that have a predetermined probability or greater of being a certain type of data and the pattern engine may then detect the data from the output items and/or remove incorrect information from the output items.

Claims

1. A machine-implemented method of detecting data of a plurality of types in a sequence of characters, the method comprising:

combining the use of a pattern detection method and a statistical learning method to detect the data.

2. The method of claim 1, comprising:

scanning the sequence of characters using the statistical learning method, the statistical learning method detecting and outputting data of at least one of said plurality of types;

using the pattern detection method to decompose the output data into data of a subset of types.

3. The method of claim 2, wherein the at least one type is an address and the subset of types comprises at least one of a street, a town, a county, a state, a country and a postal code.

4. The method of claim 1, comprising:

scanning the sequence of characters using the statistical learning method, the statistical learning method outputting items, each in combination with a probability that the output item is data of one of said types;

scanning only output items having at least a predetermined probability using the pattern detection method to detect and output the data of said types.

5. The method of claim 1, comprising:

scanning the sequence of characters using the statistical learning method, the statistical learning method outputting items, each having at least a predetermined probability that the output item is data of one of said types;

scanning the output items using the pattern detection method to detect and output the data of said types.

6. The method of claim 4 or claim 5, wherein the predetermined probability is 5%.

7. The method of claim 4 or claim 5, wherein the predetermined probability is low and the pattern detection method extracts the data from a correspondingly large number of the output items.

8. The method of claim 4 or claim 5, wherein the predetermined probability is 80%

9. The method of claim 4 or claim 5, wherein the predetermined probability is high and the pattern detection method removes output items matching a predetermined pattern to extract the data.

10. The method of claim 4 or claim 5, wherein the pattern detection method decomposes output items to output each output item as a plurality of items of the predetermined data, each having a label indicating the type of predetermined data.

11. The method of claim 1, comprising:

scanning the sequence of characters using the statistical learning method, the statistical learning method outputting items of data having at least a predetermined probability that the output item is of at least one of said types;

scanning the sequence of characters using the pattern detection method, the pattern detection method outputting items of data that match a predetermined pattern indicative of a said type;

combining the items output by the statistical learning method and the pattern detection method; and

outputting the combination as the predetermined data.

12. The method of claim 1,

the statistical learning method converting the sequence of characters into a sequence of tokens, each token comprising a lexeme and a token type relating to the function of the lexeme within the sequence of characters;

the pattern detection method parsing the tokens to detect data of the plurality of types.

13. The method of claim 12,

the pattern detection method also converting the sequence of characters into a sequence of tokens, the pattern detection method parsing the tokens from both the statistical learning method and the pattern detection method.

14. The method of claim 13, further comprising comparing the tokens from the statistical learning method with the tokens from the pattern detection method,

where corresponding tokens from the statistical learning method and the pattern detection method for a portion of the sequence of characters are the same, parsing only one of said tokens, and

where corresponding tokens are different, parsing both tokens.

15. The method of claim 13, further comprising comparing the tokens from the statistical learning method with the tokens from the pattern detection method,

where corresponding tokens from the statistical learning method and the pattern detection method for a portion of the sequence of characters are the same, parsing only one of said tokens, and

where corresponding name tokens are different, parsing the name token from the statistical learning method.

16. The method of claim 13, wherein the statistical learning method outputs tokens of a first token type and the pattern detection method outputs tokens of a second token type, and at least one of said plurality of types of data comprises at least a token of the first token type and a token of the second token type.

17. A machine-implemented method of processing data comprising:

receiving text;

processing the text using both a pattern engine and a statistical engine to detect data of a plurality of predetermined types.

18. The method of claim 17, comprising:

processing the text using the statistical engine, the statistical engine detecting and outputting data of at least one of the predetermined types;

breaking the output data into data of a subset of types using the pattern engine.

19. The method of claim 18, wherein the at least one predetermined type is an address and the subset of types comprises at least one of a street, a town, a county, a state, a country and a postal code.

20. The method of claim 17, comprising:

processing the text using the statistical engine, the statistical engine outputting items in combination with a probability of being data of a said predetermined type;

processing only output items that have at least a predetermined probability using the pattern engine, to detect and output the data of said predetermined types.

21. The method of claim 17, comprising:

processing the text using both the statistical engine and the pattern engine, the statistical engine outputting items having at least a probability of being a data of a said predetermined type, and the pattern engine outputting items that match a predetermined pattern indicative of a said predetermined type;

combining the items output by the statistical engine and the pattern engine; and

outputting the combination as the predetermined data.

22. The method of claim 17, comprising:

converting the text into a sequence of tokens using the statistical engine, each token comprising a block of text and a descriptor of the block of text;

processing the tokens using the pattern engine to detect data of the plurality of types.

23. The method of claim 22, comprising:

further converting the text into a sequence of tokens using the pattern engine, and processing the tokens from both the statistical engine and the pattern engine.

24. The method of claim 23, wherein the statistical engine outputs tokens of a first token type and the pattern engine outputs tokens of a second token type, and at least one said predetermined types of data includes at least a token of the first token type and a token of the second token type.

25. An article of manufacture comprising:

a machine-accessible medium including instructions that, when accessed by a machine, causes the machine to detect data of a plurality of types in an input sequence of characters by performing operations comprising;

combining the use of a pattern detection method and a statistical learning method to detect the data.

26. An article of manufacture according to claim 25, wherein the article of manufacture is a client application program that is being executed on a processor.

27. An article of manufacture comprising:

a machine-accessible medium including data that, when accessed by a machine, causes the machine to perform operations comprising;

receiving text;

processing the text using both a pattern engine and a statistical engine to detect data of a plurality of predetermined types.

28. An article of manufacture according to claim 27, wherein the article of manufacture is a client application program that is being executed on a processor.

29. An article of manufacture according to claim 27, wherein the machine-accessible medium further includes data that, when accessed by a machine, causes the machine to perform operations comprising:

processing the text using the statistical engine, the statistical engine detecting and outputting the data of the predetermined types;

breaking the output data into data of a subset of types using the pattern engine.

30. An article of manufacture according to claim 27, wherein the machine-accessible medium further includes data that, when accessed by a machine, causes the machine to perform operations comprising:

processing the text using the statistical engine, the statistical engine outputting items;

processing output items, each of which has at least a predetermined probability of being data of a said predetermined type, using the pattern engine to detect and output the data of said predetermined types.

31. An article of manufacture according to claim 27, wherein the machine-accessible medium further includes data that, when accessed by a machine, causes the machine to perform operations comprising:

processing the text using both the statistical engine and the pattern engine, the statistical engine outputting items having at least a probability of being a data of a said predetermined type, and the pattern engine outputting items that match a predetermined pattern indicative of a said predetermined type;

combining the items output by the statistical engine and the pattern engine; and

outputting the combination as the predetermined data.

32. An article of manufacture according to claim 27, wherein the machine-accessible medium further includes data that, when accessed by a machine, causes the machine to perform operations comprising:

converting the text into a sequence of tokens using the statistical engine, each token comprising a block of text and a descriptor of the block of text;

processing the tokens using the pattern engine to detect data of the plurality of types.

33. An article of manufacture according to claim 32, wherein the machine-accessible medium further includes data that, when accessed by a machine, causes the machine to perform operations comprising:

further converting the text into a sequence of tokens using the pattern engine, and processing the tokens from both the statistical engine and the pattern engine.

34. An article of manufacture according to claim 27, wherein the machine-accessible medium further includes data that, when accessed by a machine, causes the machine to perform operations comprising:

using the statistical engine to output tokens having a first token type and the pattern engine to output tokens having a second token type, wherein at least one of said plurality of types of data comprises at least a token of the first token type and a token of the second token type.

35. A data processing system, the system comprising:

an input for receiving text;

a pattern engine; and

a statistical engine, wherein the pattern engine and the statistical engine together detect data of a plurality of predetermined types in the text.

36. The system according to claim 35, wherein

the statistical engine detects and outputs data of a said predetermined type;

and

the pattern engine splits the output data into data of a subset of types.

37. The system according to claim 36, wherein the said predetermined type is an address and the subset of types comprises at least one of a street, a town, a county, a state, a country and a postal code.

38. The system according to claim 35, wherein

the statistical engine processes the text and outputs items;

the pattern engine processes output items, each of which has at least a predetermined probability of being data of a said predetermined type, to detect and output the data of said predetermined types.

39. The system according to claim 35, further comprising a combination module, wherein:

both the statistical engine and the pattern engine process the text, the statistical engine outputting items having at least a probability of being a data of a said predetermined type, and the pattern engine outputting items that match a predetermined pattern indicative of a said predetermined type;

the combination module combines the items output by the statistical engine and the pattern engine and outputs the combination as the predetermined data.

40. The system according to claim 35, wherein:

the statistical engine converts the text into a sequence of tokens, each token comprising a block of text and a descriptor;

the pattern engine processes the tokens to detect data of the plurality of predetermined types.

41. The system according to claim 40, wherein:

the pattern engine comprises a lexer, the lexer also converting the text into a sequence of tokens and the pattern engine processing the tokens from both the statistical engine and the lexer.

42. The system according to claim 35, further comprising a combination module, wherein:

the statistical engine outputs tokens of a first token type and the pattern engine comprises a lexer, which outputs tokens of a second token type;

wherein at least one of said predetermined types of data comprises at least a token of the first token type and a token of the second token type.

43. A data detecting system for detecting data of a plurality of types in text, the system comprising:

a pattern detection means; and

a statistical learning means, wherein the pattern detection means and the statistical learning means are operative together to detect the data.

44. The system of claim 43, wherein

the statistical learning means scans the text, the statistical learning means detecting and outputting the data of at least one of said plurality of predetermined types;

pattern detection means decomposes the output data into data of a subset of types.

45. The system of claim 44, wherein the at least one predetermined type is an address and the subset of types comprises at least one of a street, a town, a county, a state, a country and a postal code.

46. The system of claim 43, wherein

the statistical learning means scans the text, the statistical learning means outputting items, each in combination with a probability that the output item is data of one of said types;

the pattern detection means scans only output items having at least a predetermined probability to detect and output the data of said predetermined types.

47. The system of claim 43, wherein

the statistical learning means scans the text, the statistical learning means outputting items having at least a predetermined probability of being data of one of said types;

the pattern detection means scans the output items to detect and output the data of said types.

48. The system of claim 43, wherein:

the statistical learning means scans the text, the statistical learning means outputting items of data having at least a probability that the output item is of at least one of said types;

the pattern detection means scans the text, the pattern detection means outputting items of data that match a predetermined pattern indicative of a said type;

the system combines the items output by the statistical learning means and the pattern detection means; and

the system outputs the combination as the predetermined data.

49. The system of claim 43,

the statistical learning means converting the text into a sequence of tokens, each token comprising a lexeme and a token type relating to the function of the lexeme within the text;

the pattern detection means parsing the tokens to detect data of the plurality of types.

50. The system of claim 49, the pattern detection means also converting the text into a sequence of tokens, the pattern detection means parsing the tokens from both the statistical learning means and the pattern detection means.

51. The system of claim 43, wherein the statistical learning means outputs tokens of a first token type, the pattern detection means outputs tokens of a second type and at least one of said predetermined types of data comprises at least a token of the first token type and a token of the second token type.