Detection of data in a sequence of characters

• US 9,489,371 B2
• Filed: 07/12/2013
• Issued: 11/08/2016
• 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): MCFADDEN, SUSAN IRIS
• Application Number:
  US13/941,195
• Publication Number:
  US 20140025370A1
• Time in Patent Office: 1,215 Days
• Field of Search: 704/9
• US Class Current: 1/1
• 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 a plurality of types of data in a sequence of characters representing text in a human language, the method comprising:

converting, by a statistical learning method executing on a processor, the sequence of characters into blocks of input text by detecting text in the sequence of characters that correspond to the plurality of types of data, each block of input text comprising text corresponding to a single one of the plurality of types of data and assigned a tag by the statistical learning method to indicate the type of data detected and assigned a numerical value by the statistical learning method representing a probability that the block of text comprises the type of data indicated by the tag;

parsing, by a pattern detection method executing on a processor, the blocks of input text having a numerical value representing at least a pre-determined probability into blocks of output text, the blocks of output text comprising a block of output text directly corresponding to a block of input text and having the tag assigned by the statistical learning method to the corresponding block of input text; and

decomposing, by the pattern detection method, one or more blocks of output text from a block of input text using grammatical patterns of the human language to detect text corresponding to subsets of the type of data indicated by the tag assigned by the statistical learning method, each of the one or more blocks of output text having a tag assigned by the pattern detection method to indicate the subset detected, and each of the decomposed one or more blocks of output text comprising at least one lexeme for subsequent processing by an application designed to process a lexeme having the type identified by the tag assigned by the pattern detection method.

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

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

4. The method of claim 1, wherein the predetermined probability is low and the pattern detection method parses a correspondingly large number of the blocks of text.

5. The method of claim 1, wherein the predetermined probability is 80%.

6. The method of claim 1, wherein the predetermined probability is high and the pattern detection method parses the blocks of text matching a predetermined pattern.

7. A non-transitory machine-readable storage medium comprising executable instructions to cause a processor to perform operations comprising:

converting, by a statistical learning method, the sequence of characters into blocks of input text by detecting text in the sequence of characters that correspond to the plurality of types of data, each block of input text comprising text corresponding to a single one of the plurality of types of data and assigned a tag by the statistical learning method to indicate the type of data detected and assigned a numerical value by the statistical learning method representing a probability that the block of text comprises the type of data indicated by the tag;

parsing, by a pattern detection method, the blocks of input text having a numerical value representing at least a pre-determined probability into blocks of output text, the blocks of output text comprising a block of output text directly corresponding to a block of input text and having the tag assigned by the statistical learning method to the corresponding block of input text; and

decomposing, by the pattern detection method, one or more blocks of output text from a block of input text using grammatical patterns of the human language to detect text corresponding to subsets of the type of data indicated by the tag assigned by the statistical learning method, each of the one or more blocks of output text having a tag assigned by the pattern detection method to indicate the subset detected, and each of the decomposed one or more blocks of output text comprising at least one lexeme for subsequent processing by an application designed to process a lexeme having the type identified by the tag assigned by the pattern detection method.

8. The non-transitory machine-readable storage medium of claim 7, 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.

9. The non-transitory machine-readable storage medium of claim 7, wherein the predetermined probability is 5%.

10. The non-transitory machine-readable storage medium of claim 7, wherein the predetermined probability is low and the pattern detection method parses a correspondingly large number of the blocks of text.

11. The non-transitory machine-readable storage medium of claim 7, wherein the predetermined probability is 80%.

12. The non-transitory machine-readable storage medium of claim 7, wherein the predetermined probability is high and the pattern detection method parses the blocks of text matching a predetermined pattern.

13. A system comprising:

a processor; and

a memory coupled to the processor through a bus, the memory storing instructions to cause the processor

to execute a pattern detection method to convert the sequence of characters into blocks of input text by detecting text in the sequence of characters that correspond to the plurality of types of data, each block of input text comprising text corresponding to a single one of the plurality of types of data and assigned a tag by the statistical learning method to indicate the type of data detected and assigned a numerical value by the statistical learning method representing a probability that the block of text comprises the type of data indicated by the tag,

to execute a pattern detection method to parse the blocks of input text having a numerical value representing at least a pre-determined probability into blocks of output text, the blocks of output text comprising a block of output text directly corresponding to a block of input text and having the tag assigned by the statistical learning method to the corresponding block of input text, and

to further execute the pattern detection method to decompose one or more blocks of output text from a block of input text using grammatical patterns of the human language to detect text corresponding to subsets of the type of data indicated by the tag assigned by the statistical learning method, each of the one or more blocks of output text having a tag assigned by the pattern detection method to indicate the subset detected, and each of the decomposed one or more blocks of output text comprising at least one lexeme for subsequent processing by an application designed to process a lexeme having the type identified by the tag assigned by the pattern detection method.

14. The system of claim 13, 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.

15. The system of claim 13, wherein the predetermined probability is 5%.

16. The system of claim 13, wherein the predetermined probability is low and the pattern detection method parses a correspondingly large number of the blocks of text.

17. The system of claim 13, wherein the predetermined probability is 80%.

18. The system of claim 13, wherein the predetermined probability is high and the pattern detection method parses the blocks of text matching a predetermined pattern.