DATA DETECTION

• US 20090306965A1
• Filed: 09/29/2008
• Published: 12/10/2009
• Est. Priority Date: 06/06/2008
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Jaeger, Frederic de, Bonnet, Olivier, Goyet, Romain
• Granted Patent: US 8,311,806 B2
• Time in Patent Office: Days
• US Class Current: 704/9
• CPC Class Codes: G06F 16/9027 Trees
• 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/237 Lexical tools

Abstract

An apparatus for processing a sequence of tokens to detect predetermined data, wherein each said token has a token type, and the predetermined data has a structure that comprises a predetermined sequence of token types, including at least one optional token type. The apparatus comprises a processor arranged to: provide a tree for detecting the predetermined data, the tree comprising a plurality of states, each said state being linked with at least one other state by a respective condition, the arrangement of linked states forming a plurality of paths; and compare the token types of the sequence of tokens to respective conditions in the tree to match the sequence of tokens to one or more paths in the tree, wherein the predetermined data can be detected without using an epsilon reduction to take account of said at least one optional token type.

Claims

1. A method of processing a sequence of tokens to detect predetermined data, comprising:

receiving the sequence of tokens,

wherein each token has at least one token type and the predetermined data has a structure that comprises at least one required token of first predetermined token type and further includes at least one other optional token of a second predetermined token type; and

comparing, in a starting state of a decision tree, a token type of a first token in the sequence with one or more conditions provided for the starting state,

wherein, if one of the starting state conditions is not met, the predetermined data cannot be detected.

2. A method according to claim 1, further comprising:

if one of said starting state conditions is met, updating the sequence by consuming the first token and proceeding to a next state of the decision tree corresponding to the met condition;

if there is a token remaining in the updated sequence, comparing the token type of the token in the updated sequence with one or more conditions provided for the now current state;

if one of said next state conditions is met, updating the sequence by consuming the token and proceeding to the next state corresponding to the met condition;

iterating said comparing and said updating until there is no token remaining in the sequence matching a condition of the current state;

determining whether a reduction is associated with the current state and, if so, using the reduction.

3. A method according to claim 2, further comprising:

if no reduction is associated with the current state, determining that the predetermined data cannot be detected.

4. A method according to claim 2, wherein at least one of one or more reductions associated with one or more states of the decision tree determines that the predetermined data has been detected.

5. A method according to claim 2, further comprising prohibiting association with a state of a reduction in which the sequence is revised by adding another token to a beginning of the sequence and then comparing the revised sequence with conditions of the state.

6. A method according to claim 1, wherein the predetermined data is 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 of processing a sequence of tokens to detect predetermined data, the method comprising:

providing a tree for detecting the predetermined data, wherein

each said token has a token type, and the predetermined data has a structure that comprises a predetermined sequence of token types, at least one token type being optional, wherein the tree comprises a plurality of states, each of said plurality of states being linked with at least one other state by a respective condition, and an arrangement of linked states forms a plurality of paths; and

comparing token types of the sequence of tokens to respective conditions in the tree to match the sequence of tokens to one or more paths in the tree,

wherein a path is provided in the tree for the predetermined sequence including a token of an optional token type and a separate path is provided for the predetermined sequence without the token of the optional token type.

8. A method according to claim 7, wherein the predetermined data includes a plurality of tokens of a plurality of optional token types and a separate path is provided for each of the plurality of optional token types.

9. A method according to claim 7, further comprising:

using a single path in the tree to detect the predetermined data in the sequence of tokens including the token of the optional token type.

10. A method according to claim 7, wherein the predetermined data is at least one of a physical address, an IP address, an e-mail address, a time, a day, a date, and a contact number.

11. A method of processing a sequence of tokens to detect predetermined data, the method comprising:

providing a tree for detecting the predetermined data, wherein

each said token has a token type, and the predetermined data has a structure that comprises a predetermined sequence of token types, including at least one optional token type, the tree comprising a plurality of states, each said state being linked with at least one other state by a respective condition, the arrangement of linked states forming a plurality of paths;

comparing token types of the sequence of tokens to respective conditions in the tree to match the sequence of tokens to one or more paths in the tree; and

detecting the predetermined data without using an epsilon reduction to take account of at least one said optional token type.

12. A method according to claim 11, further comprising:

detecting the predetermined data in the sequence of tokens without adding a token to the sequence of tokens to take account of the optional token type.

13. A method according to claim 11, wherein the predetermined data includes a plurality of optional token types and the predetermined data can be detected without using an epsilon reduction to take account of any of said optional token types.

14. A method according to claim 11, wherein the predetermined data is at least one of a physical address, an IP address, an e-mail address, a time, a day, a date, and a contact number.

15. A method to detect predetermined data from a sequence of tokens, the method comprising:

providing a tree having a plurality of states, at least one of said plurality of state being associated with an epsilon reduction, each said token having a token type, and the predetermined data having a structure that comprises a predetermined sequence of token types, including at least one optional token type,

removing the epsilon reduction from the tree; and

comparing the tokens with the tree to detect whether the sequence of tokens matches the predetermined structure.

16. A method according to claim 15, further comprising:

adding a path in the tree for the predetermined data without the optional token type.

17. A method according to claim 15, wherein the predetermined data is at least one of a physical address, an IP address, an e-mail address, a time, a day, a date, and a contact number.

18. An apparatus for processing a sequence of tokens to detect predetermined data, the apparatus comprising:

a network interface to receive the sequence of tokens wherein;

each said token has a token type, and

the predetermined data has a structure that comprises a predetermined sequence of token types, at least one said token type being optional; and

a processor configured to;

provide a tree for detecting the predetermined data, the tree comprising a plurality of states, each said state being linked with at least one other state by a respective condition, the arrangement of linked states forming a plurality of paths; and

compare the token types of the sequence of tokens to respective conditions in the tree to match the sequence of tokens to one or more paths in the tree,

wherein the predetermined data can be detected without using an epsilon reduction to take account of at least one said optional token type.

19. An apparatus according to claim 18, wherein the predetermined data is at least one of a physical address, an IP address, an e-mail address, a time, a day, a date, and a contact number.

20. A machine-readable storage medium storing executable program instructions, which, when executed cause a data processing apparatus to perform a method to process a sequence of tokens, wherein each of said sequence of tokens has a token type, and the predetermined data has a structure that comprises a predetermined sequence of token types, including at least one optional token type, the method comprising:

providing a tree for detecting the predetermined data, the tree comprising a plurality of states, each of said plurality of states being linked with at least one other state by a respective condition, an arrangement of linked states forming a plurality of paths in the tree;

comparing the token types of the sequence of tokens to respective conditions in the tree to match the sequence of tokens to one or more paths in the tree; and

detecting the predetermined data without using an epsilon reduction to take account of said at least one optional token type.

21. A machine-readable storage medium according to claim 20, the method further comprising:

providing a path in the tree for the predetermined data including a token of the at least one optional token type; and

providing a separate path for the predetermined data without the token of the at least one optional token type.

22. A machine-readable storage medium according to claim 20, wherein the predetermined data is at least one of a physical address, an IP address, an e-mail address, a time, a day, a date, and a contact number.