Detection of data in a sequence of characters

• US 9,454,522 B2
• Filed: 05/23/2014
• Issued: 09/27/2016
• 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:
  US14/286,838
• Publication Number:
  US 20140372103A1
• Time in Patent Office: 858 Days
• Field of Search: 704/1, 704/9
• US Class Current: 1/1
• 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 representing natural or computer language, the method comprising:

receiving, by a lexer executing on a processor, the sequence of characters in a communication between users or in output from one of a compiler and an interpreter;

converting, by a lexer, the sequence of characters into a sequence of tokens, at least one token comprising a proto-lexeme and a proto-token type, the proto-token type representing multiple token types, each of the multiple token types describing one of a plurality of predetermined classes ascribed to the proto-lexeme within the sequence of characters during the conversion,

wherein a parser, executing on the processor, resolves the proto-lexeme into a single lexeme having a single class that is one of the multiple classes represented by the proto-token type, and further resolves the proto-token type into a single token type describing the single class; and

when the single class is associated with a user application, presenting, by the processor, an option to update the user application with the single lexeme, wherein the user application includes one of a calendar and an address book.

2. A method according to claim 1, wherein the proto-token type indicates that the proto-lexeme relates to the single class.

3. A method according to claim 1, wherein the predetermined classes describe classes of the lexeme in the context of the sequence of characters.

4. A method according to claim 1, wherein the parser further parses the tokens to detect predetermined types of data in the sequence of characters.

5. A method according to claim 4, wherein each said type of data corresponds to at least one of said multiple classes and a predetermined combination of said multiple classes.

6. A method according to claim 4, wherein the predetermined types of data 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.

7. A method according to claim 4, wherein the parser further provides a single parsing path in a decision tree for each token type and each proto-token type in the sequence of token.

8. A method of processing data in a sequence of characters representing natural or computer language, comprising:

receiving, by a parser executing on a processor, a sequence of tokens, at least one token comprising a proto-lexeme and a proto-token type, the proto-token type representing multiple token types, each of the multiple token types describing one of a plurality of predetermined classes previously ascribed to the proto-lexeme within the sequence of characters received by a lexer in a communication between users or in output from one of a compiler and an interpreter;

parsing, by the parser, the sequence of tokens to detect predetermined types of data;

resolving, by the parser, the proto-lexeme into a single lexeme having a single class that is one of the multiple classes represented by the proto-token type, and further resolving the proto-token type into a single token type describing the single class; and

when the single class is associated with a user application, presenting, by the processor, an option to update the user application with the single lexeme, wherein the user application includes one of a calendar and an address book.

9. A method according to claim 8, the method comprising:

providing, by the parser, a single path for each token type and each proto-token type in the sequence of tokens.

10. A method of processing a sequence of characters representing natural or computer language, the method comprising:

receiving, by a lexer executing on a processor, the sequence of characters in a communication between users or in output from one of a compiler and an interpreter;

converting, by the lexer, the sequence of characters into a sequence of tokens comprising one or more proto-lexemes and one or more corresponding proto-token types, wherein each proto-lexeme is defined as belonging to one of;

a first set comprising one class, wherein the proto-token type represents the one class, and

a second set comprising a combination of classes, wherein the proto-token type represents the classes in the combination;

resolving, by a parser executing on the processor, each proto-lexeme into a single lexeme and the corresponding proto-token type into a single token type;

when the single class is associated with a user application, presenting, by the processor, an option to update the user application with the single lexeme, wherein the user application includes one of a calendar and an address book.

11. A method according to claim 10, wherein the resolving comprises providing a single analysis path for each said proto-lexeme in a decision tree.

12. A method according to claim 10, wherein the classes in the combination may include the single class.

13. A method according to claim 10, further comprising converting the sequence of characters into lexemes and proto-lexemes.

14. An apparatus to detect predetermined data in a sequence of characters representing natural or computer language, the apparatus comprising:

a processor;

a network interface coupled to the processor to receive the sequence of characters in a communication between users or in output from one of a compiler and an interpreter;

a lexer executing on the processor to convert the sequence of characters into a sequence of tokens, at least one token comprising a proto-lexeme and a proto-token type that represents multiple token types, each of the multiple token types describing one of a plurality of predetermined classes ascribed to the proto-lexeme within the sequence of characters during the conversion,

wherein a parser, executing the processor, resolves the proto-lexeme into a single lexeme having a single class that is one of the multiple classes represented by the proto-token type, and further resolves the proto-token type into a single token type describing the single class; and

when the single class is associated with a user application, presenting, by the processor, an option to update the user application with the single lexeme, wherein the user application includes one of a calendar and an address book.

15. An apparatus according to claim 14, wherein the predetermined classes describe classes of the lexeme in the context of the sequence of characters.

16. An apparatus according to claim 14, wherein the parser further parses the tokens to detect predetermined types of data in the sequence of characters.

17. An apparatus according to claim 16, wherein each type of data corresponds to at least one said multiple classes and a predetermined combination said multiple classes.

18. An apparatus according to claim 16, wherein the predetermined types of data 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.

19. An apparatus according to claim 16, wherein the parser comprises a decision tree having a single parsing path for each token type and each proto-token type in the sequence of tokens.

20. A data processing system for processing a sequence of characters representing natural or computer language comprising:

means for receiving the sequence of characters in a communication between users or in output from one of a compiler and an interpreter,

means for converting the sequence of characters into a sequence of one or more proto-lexemes and one or more proto-token types, wherein each proto-lexeme is defined as belonging to one of;

a first set comprising one class, wherein the corresponding proto-token type represents the one class, and

a second set comprising a combination of classes, wherein the corresponding proto-token type represents the classes in the combination;

means for parsing the sequence of one or more proto-lexemes by providing a single analysis path in a decision tree for each said proto-lexeme to resolve each proto-lexeme into a single lexeme and the corresponding proto-token type into a single token type; and

means for presenting an option to update the user application with the single lexeme when the single class is associated with a user application, wherein the user application includes one of a calendar and an address book.

21. 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 representing natural or computer language by:

receiving, by a lexer executing on a processor, the sequence of character in a communication between users or in output from one of a compiler and an interpreter; and

converting by the lexer, the sequence of characters into a sequence of tokens, at least one token comprising a proto-lexeme and a proto-token type, the proto-token type representing multiple token types, each of the multiple token types describing one of a plurality of predetermined classes ascribed to the proto-lexeme within the sequence of characters during the conversion,

wherein a parser, executing on the processor, resolves the proto-lexeme into a single lexeme having a single class that is one of the multiple classes represented by the proto-token type, and further resolves the proto-token type into a single token type describing the single class; and

when the single class is associated with a user application, presenting, by the processor, an option to update the user application with the single lexeme, wherein the user application includes one of a calendar and an address book.

22. A non-transitorymachine-readable storage medium storing executable program instructions, which, when executed cause a data processing system to detect data in a sequence of characters representing natural or computer language by:

converting, by a lexer executing on a processor, the sequence of characters into a sequence of one or more proto-lexemes and one or more proto-token types, the sequence of characters previously received by the lexer in a communication between users or in output from one of a compiler and an interpreter, wherein each proto-lexeme is defined as being associated with one of;

a first set comprising a single class, wherein the corresponding proto-token type represents the single class, and

a second set comprising a combination of classes, wherein the corresponding proto-token type represents the classes in the combination;

resolving, by a parser executing on the processor, the sequence of one or more proto-lexemes into a sequence of single lexemes and the corresponding one or more proto-token types into single token types, said resolving comprising providing a single analysis path for each said proto-lexeme; and

when the single class is associated with a user application, presenting, by the processor, an option to update the user application with the single lexeme, wherein the user application includes one of a calendar and an address book.