Patent Document ID: 9754050
Application ID: 13406549

Base Claim:
1. A system comprising: a processor coupled to a memory, the processor configured to execute computer-executable instructions to: provide 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 use 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, and 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.

---

Claim 6:
6. A system as claimed in claim 1 , wherein the processor is configured to execute further computer-executable instructions to compute a monotone, minimal, perfect hash value of the string by making a blind search for the string in the path-decomposed trie, a blind search being one in which the path-decomposed trie is traversed matching only the branching characters of the string, the monotone minimal perfect hash value being one which preserves a lexicographic order of the strings.