Data detection

• US 8,489,388 B2
• Filed: 11/10/2008
• Issued: 07/16/2013
• Est. Priority Date: 11/10/2008
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Bonnet, Olivier, de Jaeger, Frederick, Goyet, Romain, Ciudad, Jean-Pierre
• Primary Examiner(s): Borsetti, Greg
• Application Number:
  US12/268,410
• Publication Number:
  US 20100121631A1
• Time in Patent Office: 1,709 Days
• Field of Search: None
• 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, the statistical learning method converting the sequence of characters into a first sequence of tokens, each token comprising a lexeme and a token type relating to the function of the lexeme within the sequence of characters and having at least a predetermined probability that the corresponding data is of at least one of said types, the pattern detection method converting the sequence of characters into a second sequence of tokens, each token corresponding to data that matches a predetermined pattern indicative of the at least one of said types, the pattern detection method further parsing a combination of the first and second sequence of tokens;

comparing the first and second sequence of tokens, wherein when corresponding tokens from the first and second sequence of tokens for a portion of the sequence of characters are the same, parsing only one of the corresponding tokens, when the tokens are not name tokens and the corresponding tokens are different, parsing both corresponding tokens, and when the tokens are name tokens and the corresponding tokens are different, parsing the corresponding token only from the statistical learning method; and

outputting the data corresponding to the combination of tokens as the data that matches the predetermined pattern.

2. The method of claim 1, wherein the at least one of said types 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.

3. The method of claim 1, wherein each token in the first sequence of tokens further comprises a probability that the corresponding data is data of one of said types;

and parsing only tokens having at least a predetermined probability using the pattern detection method.

4. The method of claim 1, wherein each token in the first sequence of tokens corresponds to data having at least a predetermined probability that the data is data of one of said types.

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

6. The method of claim 3 or claim 4, wherein the predetermined probability is low and the pattern detection method extracts the data from a correspondingly large number of the tokens in the first sequence of tokens.

7. The method of claim 3 or claim 4, wherein the predetermined probability is 80%.

8. The method of claim 3 or claim 4, wherein the predetermined probability is high and the pattern detection method removes tokens in the first sequence of tokens matching a predetermined pattern to extract the data.

9. The method of claim 3 or claim 4, wherein the pattern detection method outputs tokens corresponding to data that matched a predetermined pattern, each token having a token type indicating the type of data.

10. The method of claim 1, 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.

11. 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, the statistical engine converting the text into a first sequence of tokens, each token comprising a lexeme and a token type relating to the function of the lexeme within the text and having at least a predetermined probability that the corresponding data is of at least one of the predetermined types, the pattern engine converting the text into a second sequence of tokens, each token corresponding to data that matches a predetermined pattern indicative of the at least one of the predetermined types, the pattern engine further parsing a combination of the first and second sequence of tokens; and

comparing the first and second sequence of tokens, wherein when corresponding tokens from the first and second sequence of tokens for a portion of the text are the same, parsing only one of the corresponding tokens, when the tokens are not name tokens and the corresponding tokens are different, parsing both corresponding tokens, and when the tokens are name tokens and the corresponding tokens are different, parsing the corresponding token only from the statistical engine; and

outputting the data corresponding to the combination of tokens as the data that matches the predetermined pattern.

12. The method of claim 11, wherein the at least one of the predetermined types 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.

13. The method of claim 11, wherein each token in the first sequence of tokens further comprises a probability of the corresponding data being data of a said predetermined type;

parsing only tokens that have at least a predetermined probability using the pattern engine.

14. The method of claim 11, 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.

15. An article of manufacture comprising:

a non-transitory computer readable storage 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, the statistical learning method converting the sequence of characters into a first sequence of tokens, each token comprising a lexeme and a token type relating to the function of the lexeme within the sequence of characters and having at least a predetermined probability that the corresponding data is of at least one of the types, the pattern detection method converting the sequence of characters into a second sequence of tokens, each token corresponding to data that matches a predetermined pattern indicative of the at least one of the types, the pattern detection method further parsing a combination of the first and second sequence of tokens; and

comparing the first and second sequence of tokens, wherein when corresponding tokens from the first and second sequence of tokens for a portion of the sequence of characters are the same, parsing only one of the corresponding tokens, when the tokens are not name tokens and the corresponding tokens are different, parsing both corresponding tokens, and when the tokens are name tokens and the corresponding tokens are different, parsing the corresponding token only from the statistical learning method; and

outputting the data corresponding to the combination of tokens as the data that matches the predetermined pattern.

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

17. An article of manufacture comprising:

a non-transitory computer readable storage 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, the statistical engine converting the text into a first sequence of tokens, each token comprising a lexeme and a token type relating to the function of the lexeme within the text and having at least a predetermined probability that the corresponding data is of at least one of the predetermined types, the pattern engine converting the text into a second sequence of tokens, each token corresponding to data that matches a predetermined pattern indicative of the at least one of the predetermined types, the pattern engine further parsing a combination of the first and second sequence of tokens; and

comparing the first and second sequence of tokens, wherein when corresponding tokens from the first and second sequence of tokens for a portion of the text are the same, parsing only one of the corresponding tokens, when the tokens are not name tokens and the corresponding tokens are different, parsing both corresponding tokens, and when the tokens are name tokens and the corresponding tokens are different, parsing the corresponding token only from the statistical engine; and

outputting the data corresponding to the combination of tokens as the data that matches the predetermined pattern.

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

19. An article of manufacture according to claim 17, wherein each token in the first sequence of tokens further comprises a probability that the corresponding data is data of one of said predetermined types and wherein the non-transitory computer readable storage medium further includes data that, when accessed by a machine, causes the machine to perform operations comprising:

parsing only tokens corresponding to data which has at least a predetermined probability of being data of a said predetermined type using the pattern engine.

20. An article of manufacture according to claim 17, wherein the non-transitory computer readable storage 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.

21. A data processing system, the system comprising:

an input for receiving text, the input coupled to a processor through a bus;

a pattern engine executing on the processor;

a statistical engine executing on the processor, wherein the pattern engine and the statistical engine together detect data of a plurality of predetermined types in the text, the statistical engine converting the text into a first sequence of tokens, each token comprising a lexeme and a token type relating to the function of the lexeme within the text and having a predetermined probability that the corresponding data is of at least one of the predetermined types, the pattern engine converting the text into a second sequence of tokens, each token corresponding to data that matchers a predetermined pattern indicative of the at least one of the predetermined types, the pattern engine further parsing a combination of the first and second sequence of tokens; and

a comparison engine executing on the processor to compare the first and second sequence of tokens, wherein when corresponding tokens from the first and second sequence of tokens for a portion of the text are the same, parsing only one of the corresponding tokens, when the token are not name tokens and the corresponding tokens are different, parsing both corresponding tokens, and when the tokens are name tokens and the corresponding tokens are different, parsing the corresponding token only from the statistical engine; and

an output for outputting the data corresponding to the combination of tokens as the data that matches the predetermined pattern, the output coupled to a processor through the bus.

22. The system according to claim 21, wherein the at least one of said predetermined types 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.

23. The system according to claim 21, wherein each token in the first sequence of tokens further comprises a probability that the corresponding data is data of one of said predetermined types and

the pattern engine parses only tokens corresponding to data which has at least a predetermined probability of being data of a said predetermined type.

24. The system according to claim 21, 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.

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

a pattern detection means;

a statistical engine means, wherein the pattern detection means and the statistical learning means are operative together to detect the data, the statistical engine means converting the text into a first sequence of tokens, each token comprising a lexeme and a token type relating to the function of the lexeme within the text and having at least a predetermined probability that the corresponding data is of at least one of said types, the pattern detection means converting the text into a second sequence of tokens, each token corresponding to data that matches a predetermined pattern indicative of the at least one of said types, the pattern detection means further parsing a combination of the first and second sequence of tokens; and

a comparison means to compare the first and second sequence of tokens, wherein when corresponding tokens from the first and second sequence of tokens for a portion of the text are the same, parsing only one of the corresponding tokens, when the tokens are not name tokens and the corresponding tokens are different, parsing both corresponding tokens, and when the tokens are name tokens and the corresponding tokens are different, parsing the corresponding token only from the statistical engine means; and

means for outputting the data corresponding to the combination of tokens as the data that matches the predetermined pattern.

26. The system of claim 25, wherein the at least one of the predetermined types 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.

27. The system of claim 25, wherein

the statistical engine means outputs tokens in combination with a probability that the corresponding data is data of one of said types;

the pattern detection means parses only tokens having at least a predetermined probability.

28. The system of claim 25, wherein

the statistical learning means outputs tokens corresponding to data having at least a predetermined probability of being data of one of said types.

29. The system of claim 25, wherein the statistical engine 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.