Path-decomposed trie data structures

A method for retrieving a set of strings comprising:

• providing a plurality of arrays and a bit vector together representing a path-decomposed trie, wherein the path-decomposed trie is a compressed tree structure having a root connected to a plurality of nodes by branches where terminal nodes are leaves, the compressed tree structure representing a set of strings where prefixes common to two or more strings are represented by a same root-to-node path,
• wherein each node has a degree being a number of child nodes branching from the node, and wherein each node has a plurality of labels, the path-decomposed trie representing root-to-leaf paths of the compressed tree structure by a single node in the path-decomposed trie;
• and
• using the path-decomposed trie to return an identifier of a string in the path-decomposed trie or to obtain an indication that the string is not present in the path-decomposed trie, wherein using the path-decomposed trie comprises performing a sequential search of the plurality of labels represented in the plurality of arrays, each label is a set of characters of the string and a first one of the plurality of arrays stores the labels of the path-decomposed trie by interleaving the labels with the node degrees.

A device comprising:

• a processor coupled to a memory, the processor configured to execute computer-executable instructions to:
• store a plurality of arrays and a bit vector together representing a path-decomposed trie, wherein the path-decomposed trie is a compressed tree structure having a root connected to a plurality of nodes by branches where terminal nodes are leaves, the compressed tree structure representing a set of strings where prefixes common to two or more strings are represented by a same root-to-node path,
• wherein each node has a degree being a number of child nodes branching from the node, and wherein each node has a plurality of labels, the path-decomposed trie representing root-to-leaf paths of the compressed tree structure by a single node in the path-decomposed trie;
• and
• using the path-decomposed trie to return an identifier of a string in the path-decomposed trie or to obtain an indication that the string is not present in the path-decomposed trie, wherein using the path-decomposed trie comprises performing a sequential search of the plurality of labels represented in the plurality of arrays, each label is a set of characters of the string and a first one of the plurality of arrays stores the labels of the path-decomposed trie by interleaving the labels with the node degrees.