Trie specialization allowing storage of value keyed by patterns and retrieval by tokens

• US 8,380,758 B1
• Filed: 11/30/2011
• Issued: 02/19/2013
• Est. Priority Date: 11/14/2011
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Stephens, Omari
• Primary Examiner(s): Chbouki, Tarek
• Application Number:
  US13/307,487
• Time in Patent Office: 447 Days
• Field of Search: None
• US Class Current: 707/803
• CPC Class Codes: G06F 9/45512 Command shells

Abstract

Methods, systems, and computer-readable media for efficiently and flexibly invoking programs or subroutines specified by command terminal input strings using a trie data structure include: receiving a command string; dividing the command string into one or more tokens, wherein the one or more tokens are delimited by whitespace within the command string; identifying a node-path within a trie data structure corresponding to the one or more tokens; extracting a program stored in a final node in the node-path; and executing the program.

Claims

1. A method of invoking a program associated with a command string, the method comprising:

receiving the command string;

dividing the command string into a plurality of tokens, wherein one or more of the plurality of tokens include a plurality of adjacent characters in the command string;

using a processor, identifying a node-path within a trie data structure corresponding to the plurality of tokens, wherein;

the trie data structure comprises a plurality of nodes arranged in a tree-like manner;

each node in the plurality of nodes includes a lookup key in the form of a regular expression;

one or more nodes in the plurality of nodes includes a value in the form of a program; and

identifying the node-path comprises identifying a series of sequential, connected, descending nodes in the trie data structure such that the regular expression lookup key included in each node in the series matches a respective sequential token in the command string;

determining that the lookup key included in a final node is a wildcard;

extracting a program included in the final node in the node-path; and

in response to determining the lookup key included in the final node is a wildcard, executing the program associated with the final node by providing one or more tokens subsequent to the token that matches the final node as arguments to the program.

2. A method of invoking a program associated with a command string, the method comprising:

receiving the command string;

dividing the command string into a plurality of tokens, wherein one or more of the plurality of tokens include a plurality of adjacent characters in the command string

using a processor, identifying a node-path within a trie data structure corresponding to the plurality of tokens, wherein

the trie data structure comprises a plurality of nodes arranged in a tree-like manner;

each node in the plurality of nodes includes a lookup key in the form of a text string;

the lookup keys included in one or more nodes in the data structure are regular expressions;

one or more nodes in the plurality of nodes is associated with a value in the form of a program; and

identifying the node-path comprises identifying a series of sequential, connected, descending nodes in the data structure such that the lookup key included in each node in the series matches a respective sequential token in the command string;

determining that the lookup key included in a final node is a wildcard;

extracting a program associated with the final node in the node-path; and

in response to determining that the lookup key included in the final node is a wildcard, executing the program associated with the final node by providing one or more tokens subsequent to the token that matches the final node as arguments to the program.

3. The method of claim 2, wherein the programs associated with one or more nodes in the data structure are stored as objects instantiated from classes containing one or more functions.

4. The method of claim 3, wherein executing the program comprises:

invoking the one or more functions stored in the object included in the final node in the node-path.

5. The method of claim 3, wherein the objects are instantiated from classes that are of type Java Runnable.

6. The method of claim 2, further comprising:

determining one or more capture results from capture groups defined by the regular expressions of one or more nodes in the series matching one or more tokens in the command string; and

using the one or more capture results to determine the program or to execute the program in a manner consistent with the one or more capture results.

7. The method of claim 2, further comprising:

determining that the lookup keys of two or more sibling nodes in the trie data structure match a token in the command string; and

selecting a node-path that includes a node from among the two or more sibling nodes that has a highest priority.

8. The method of claim 2, further comprising:

determining that the lookup keys of two or more sibling nodes in the trie data structure match a token in the command string;

prompting a user to select a lookup key from among the two or more sibling nodes; and

selecting a node-path that includes the node associated with the selected lookup key.

9. A system configured to invoke a program associated with a command string, the system comprising:

a processing system comprising one or more processors; and

a memory system comprising one or more computer-readable media, wherein the computer-readable media contain instructions stored thereon that, if executed by the processing system, cause the system to perform operations comprising;

receiving the command string;

dividing the command string into a plurality of tokens, wherein one or more of the plurality of tokens include a plurality of adjacent characters in the command string;

identifying a node-path within a trie data structure corresponding to the plurality of tokens, wherein

the trie data structure comprises a plurality of nodes arranged in a tree-like manner;

each node in the plurality of nodes includes a lookup key in the form of a text string;

the lookup keys included in one or more nodes in the trie data structure are regular expressions;

one or more nodes in the plurality of nodes is associated with a value in the form of a program; and

identifying the node-path comprises identifying a series of sequential, connected, descending nodes in the trie data structure such that the lookup key included in each node in the series matches a respective sequential token in the command string;

determining that the look key included in a final node is a wildcard;

extracting a program associated with the final node in the node-path; and

in response to determining that the lookup key in the final node is a wildcard, executing the program associated with the final node by providing one or more tokens subsequent to the token that matches the final node as arguments to the program.

10. The system of claim 9, wherein the programs associated with one or more nodes in the data structure are stored as objects instantiated from classes containing one or more functions.

11. The system of claim 10, wherein executing the program comprises:

invoking the one or more functions stored in the object included in the final node in the node-path.

12. The system of claim 10, wherein the objects are instantiated from classes that are of type Java Runnable.

13. The system of claim 9, the operations further comprising:

determining one or more capture results from capture groups defined by the regular expressions of one or more nodes in the series matching one or more tokens in the command string; and

using the one or more capture results to determine the program or to execute the program in a manner consistent with the one or more capture results.

14. The system of claim 9, the operations further comprising:

determining that the lookup keys of two or more sibling nodes in the trie data structure match a token in the command string; and

selecting a node-path that includes a node from among the two or more sibling nodes that has a highest priority.

15. The system of claim 9, the operations further comprising:

determining that the lookup keys of two or more sibling nodes in the trie data structure match a token in the command string;

prompting a user to select a lookup key from among the two or more sibling nodes; and

selecting a node-path that includes the node associated with the selected lookup key.

16. A memory device containing instructions stored therein, wherein the instructions, if executed by a processing system within a computing system, cause the computing system to perform operations comprising:

receiving a command string;

dividing the command string into a plurality of tokens, wherein one or more of the plurality of tokens include a plurality of adjacent characters in the command string;

identifying a node-path within a trie data structure corresponding to the plurality of tokens, wherein

the trie data structure comprises a plurality of nodes arranged in a tree-like manner;

each node in the plurality of nodes includes a lookup key in the form of a text string;

the lookup keys included in one or more nodes in the trie data structure are regular expressions;

one or more nodes in the plurality of nodes includes a value in the four of a program; and

identifying the node-path comprises identifying a series of sequential, connected, descending nodes in the trie data structure such that the lookup key included in each node in the series matches a respective sequential token in the command string;

determining that the lookup key included in a final node is a wildcard;

extracting a program associated with the final node in the node-path; and

in response to determining that the lookup key included in the final node is a wildcard, executing the program associated with the final node by providing one or more tokens subsequent to the token that matches the final node as arguments to the program.

17. The memory device of claim 16, wherein the programs included in one or more nodes in the trie data structure are stored as objects instantiated from classes containing one or more functions.