Path-decomposed trie data structures are described, for example, for representing sets of strings in a succinct manner while still enabling fast operations on the string sets such as string retrieval or looking up a string with a specified identifier. A path-decomposed trie is a trie (tree data structure for storing a set of strings) where each node in the path decomposed trie represents a path in the trie. In various embodiments a path-decomposed trie data structure is represented succinctly by interleaving node labels and node degrees in an array and optionally by compressing the node labels using a static dictionary. Node labels may be string characters and a node degree may be a number of children of a node. In some embodiments a path-decomposed hollow trie data structure is used to provide a hash function for string sets.