String lookup using three-transition tree structure

A computer-implemented method comprising:

• storing, by a computing device, a data structure with a tree form having at least two levels for storing two or more strings and at least one associated output string, wherein the data structure comprises at least one node at a first level of the tree form data structure having a field for storing a first substring of the two or more stored strings, at least three nodes at a second level of the tree form data structure respectively storing three substrings of the two or more stored strings, and at least three transitions, a match transition, a first fail transition, and a second fail transition, respectively governing transition from the one node at the first level to a first, a second and a third of the at least three nodes at the second level;
• receiving, by the computing device, a string;
• comparing, by the computing device, a first portion of the string to the substring of the one node of the first level;
• in response to the first portion of the string matching the substring of the one node of the first level, transitioning, by the computing device, from the one node of the first level, using the match transition, to the first node of the second level;
• in response to the first portion of the string not matching the substring of the one node of the first level, transitioning, by the computing device, from the one node of the first level, using a selected one of the first and second fail transitions, to a corresponding selected one of the second and third node of the second level.

One or more computer-readable media including instructions stored thereon which, in response to execution by a computing device, cause the computing device to:

• store a data structure with a tree form having at least two levels for storing two or more strings and at least one associated output string, wherein the data structure comprises at least one node at a first level of the tree form data structure having a field for storing a first substring of the two or more stored strings, at least three nodes at a second level of the tree form data structure respectively storing three substrings of the two or more stored stings, and at least three transitions, a match transition, a first fail transition, and a second fail transition, respectively governing transition from the one node at the first level to a first, a second, and a third of the at least three nodes at the second level of the tree form data structure;
• receive a string;
• compare a first portion of the string to the substring of the one node of the first level;
• in response to a match of the first portion of the string to the substring of the one node of the first level, use the match transition to transition from the one node of the first level to the first node of the second level;
• in response to a mismatch of the first portion of the string to the substring of the one node of the first level, use a selected one of the first and second fail transitions to transition from the one node of the first level to a corresponding selected one of the second and third node of the second level.

The one or more computer-readable media of claim 36, wherein:

• the at least three nodes at the second level comprise at least a tree node and two trie nodes;
• the first of the at least three nodes at the second level comprises a tree node;
• the second and third nodes at the second level comprise two trie nodes;
• the instructions are configured to cause the computing device, in response to execution of the instructions, to transition to the first of the at least three nodes at the second level through transition to the tree node;
• and
• the instructions are configured to cause the computing device, in response to execution of the instructions, to transition to a selected one of the second and third nodes at the second level through transition to a selected one of the trie nodes.

An apparatus, comprising:

• a memory configured to store strings;
• a searchable data structure with tree form, stored in the memory, and having at least two levels for storing two or more strings and at least one associated output string, wherein the data structure comprises at least one node at a first level of the tree form data structure having a field for storing a first substring of the two or more stored strings, a tree node and two trie nodes at a second level of the tree form data structure respectively storing three substrings of the two or more stored strings, and at least three transitions, a match transition, a first fail transition, and a second fail transition, to the tree node and two trie nodes at the second level;
• and
• one or more processors coupled to the memory and configured to execute logic to:
• store the tree form data structure;
• receive a string;
• compare an initial portion of the string to the substring of the one node of the first level;
• in response to a match of the initial portion of the string to the substring of the one node of the first level, use the match transition to transition from the one node of the first level to the tree node of the second level;
• in response to a mismatch of the initial portion of the received string to the sub string:
• compare an initial character of the initial portion of the received string with characters associated with the first and second fail transitions;
• in response to a match of the initial character to the character associated with the first fail transition, use the first fail transition to transition to a first trie node of the trie nodes of the second level of the tree form data structure;
• and
• in response to a match of the initial character to the character associated with the second fail transition, use the second fail transition to transition to a second trie node of the trie nodes of the second level of the tree form data structure.