Data detection of a character sequence having multiple possible data types

• US 8,738,360 B2
• Filed: 09/29/2008
• Issued: 05/27/2014
• Est. Priority Date: 06/06/2008
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Bonnet, Olivier, de Jaeger, Frederic, Goyet, Romain
• Primary Examiner(s): Godbold, Douglas
• Application Number:
  US12/240,625
• Publication Number:
  US 20090306964A1
• Time in Patent Office: 2,066 Days
• Field of Search: 704 9- 10, 707/755, 717143-144
• US Class Current: 704/9
• CPC Class Codes: G06F 16/284 Relational databases
• CPC Class Codes: G06F 40/205 Parsing
• CPC Class Codes: G06F 40/211 Syntactic parsing, e.g. based on context-free grammar [CFG] or unification grammars
• CPC Class Codes: G06F 40/284 Lexical analysis, e.g. tokenisation or collocates
• CPC Class Codes: G06F 40/289 Phrasal analysis, e.g. finite state techniques or chunking
• CPC Class Codes: G06F 40/40 Processing or translation of natural language natural language analysis G06F40/20; semantic analysis G06F40/30
• CPC Class Codes: G06F 8/427 Parsing

Abstract

A method of processing a sequence of characters, the method comprising converting the sequence of characters into a sequence of tokens so that each token comprises a lexeme and one of a plurality of token types. Each of the plurality of token types relates to at least one of a plurality of predetermined functions, wherein at least one said token type relates to multiple functions of the plurality of predetermined functions.

Claims

1. A method to process a sequence of characters, the method comprising:

receiving the sequence of characters;

converting, by a lexer embodied in a processor, the sequence of characters into a sequence of tokens, each token comprising a lexeme and a token type,

wherein each lexeme comprises one or more of the sequence of characters,

wherein each token type describes at least one of a plurality of predetermined classes ascribed to lexemes by the lexer, and

wherein the conversion of characters into tokens includes ascribing multiple, different predetermined classes to a single token using one token type, wherein the lexeme for the single token may function as any one of the multiple, different predetermined classes ascribed to the single token; and

analyzing, by a parser embodied in the processor, the sequence of tokens to detect data types within the sequence of characters based upon the token types of the sequence of tokens, including the token type ascribing the multiple predetermined classes to the single token.

2. A method according to claim 1, wherein at least one said token type indicates that a lexeme is associated with a single one of said predetermined classes.

3. A method according to claim 1, wherein one of the predetermined classes describes one or more possible data types for the lexeme in a context of the sequence of characters.

4. A method according to claim 1, wherein a data type corresponds to a predetermined combination of said predetermined classes.

5. A method according to claim 1, wherein the data types include at least one of a physical address, an IP address, an e-mail address, a time, a day, a date, and a contact number.

6. A method according to claim 1, wherein the analyzing the sequence of tokens comprises providing a single parsing path in a decision tree for each token type, including the token type ascribing the multiple predetermined classes to the single token.

7. A method of processing data, comprising:

receiving, by a parser embodied in the processor, a sequence of tokens, each token converted by a lexer from a sequence of characters and comprising a lexeme and a token type,

wherein each lexeme comprises one or more of the sequence of characters,

wherein each token type describes at least one of a plurality of predetermined classes ascribed to lexemes by the lexer, and,

wherein the conversion of characters into tokens includes ascribing multiple, different predetermined classes to a single token using one token type, wherein the lexeme for the single token may function as any one of the multiple, different predetermined classes ascribed to the single token; and

analyzing, by the parser, the sequence of tokens to detect the data types within the sequence of characters based upon the token types of the sequence of tokens, including the token type ascribing the multiple predetermined classes to the single token.

8. A method according to claim 7, wherein the analyzing the sequence of tokens comprises providing a single path for each token type, including the token type ascribing the multiple predetermined classes to the single token.

9. An apparatus to detect predetermined data in a sequence of characters, the apparatus comprising:

an interface to receive the sequence of characters; and

a processing device coupled to the interface, the processing device implementing a lexer and a parser,

the lexer to convert the sequence of characters into a sequence of tokens, each token comprising a lexeme and a token type,

wherein each lexeme comprises one or more of the sequence of characters,

wherein each token type describes at least one of a plurality of predetermined classes that correspond to data types,

wherein the conversion of characters into tokens includes ascribing multiple, different predetermined classes to a single token using one token, wherein the lexeme for the single token may function as any one of the multiple, different predetermined classes ascribed to the single token; and

the parser to analyze the sequence of tokens to detect data types within the sequence of characters based upon the token types of the sequence of tokens, including the token type ascribing the multiple predetermined classes to the single token.

10. An apparatus according to claim 9, wherein each token type indicates that a corresponding lexeme is associated with either a single predetermined class or a combination of more than one predetermined class.

11. An apparatus according to claim 9, wherein one of the predetermined classes describes one or more possible data types for the lexeme in a context of the sequence of characters.

12. An apparatus according to claim 9, wherein the data types include at least one of a physical address, an IP address, an e-mail address, a time, a day, a date, and a contact number.

13. An apparatus according to claim 9, wherein the analyzing the sequence of tokens comprises a decision tree having a single parsing path for each token type, including the token type ascribing the multiple predetermined classes to the single token.

14. A non-transitory machine-readable storage medium storing executable program instructions, which, when executed, cause a data processing system to process a sequence of characters by:

receiving the sequence of characters;

converting, by a lexer, the sequence of characters into a sequence of tokens, each token comprising a lexeme and a token type,

wherein each lexeme comprises one or more of the sequence of characters,

wherein each token type describes at least one of a plurality of predetermined classes ascribed to lexemes by the lexer, and

wherein the conversion of characters into tokens includes ascribing multiple, different predetermined classes to a single token using one token type, wherein the lexeme for the single token may function as any one of the multiple, different predetermined classes ascribed to the single token; and

analyzing, by a parser embodied in the processor, the sequence of tokens to detect data types within the sequence of characters based upon the token types of the sequence of tokens, including the token type ascribing the multiple predetermined classes to the single token.

15. An apparatus to detect predetermined data in a sequence of characters, the apparatus comprising:

an interface to receive the sequence of characters; and

a processing device coupled to the interface, the processing device implementing a lexer and a parser, the parser to

receive a sequence of tokens, each token converted by the lexer from the sequence of characters and comprising a lexeme and a token type,

wherein each lexeme comprises one or more of the sequence of characters,

wherein each token type describes at least one of a plurality of predetermined classes ascribed to lexemes by the lexer, and,

wherein the conversion of characters into tokens includes ascribing multiple, different predetermined classes to a single token using one token type, wherein the lexeme for the single token may function as any one of the multiple, different predetermined classes ascribed to the single token; and

analyze the sequence of tokens to detect data types within the sequence of characters based upon the token types of the sequence of tokens, including the token type ascribing the multiple predetermined classes to the single token.

16. A non-transitory machine-readable storage medium storing executable program instructions, which, when executed cause a data processing system to detect data in a sequence of characters by:

receiving, by a parser, a sequence of tokens, each token converted by a lexer from the sequence of characters and comprising a lexeme and a token type,

wherein each lexeme comprises one or more of the sequence of characters,

wherein each token type describes at least one of a plurality of predetermined classes ascribed to lexemes by the lexer, and,

wherein the conversion of characters into tokens includes ascribing multiple, different predetermined classes to a single token using one token type, wherein the lexeme for the single token may function as any one of the multiple, different predetermined classes ascribed to the single token; and

analyzing, by the parser, the sequence of tokens to detect data types within the sequence of characters based upon the token types of the sequence of tokens, including the token type ascribing the multiple predetermined classes to the single token.