I have a large list of strings with associated values. I need to do a fast lookup into the list by the string prefix, but also by the string's ordinal within the list. For example,

alice, 10, 0
bob,   99, 1
carol, 32, 2

search_by_prefix("bo") -> [("bob", 99),]
search_by_ordinal(2) -> ("carol", 32)

I'm looking for a good compressed data structure.

A simple sorted string table (SST) does the job, but it's not well-compressed. You can do key prefix compression, but it doesn't buy you much.

I'd prefer to do a finite state transducer (FST) because it's very compact and lookups are fast. The problem is that I can't find a simple explanation of how to construct one, and it also isn't clear how to do a by-ordinal lookup.


This data structure can be read-only. No need for inserts or deletes.


1 Answer 1


A reasonable approach is to build two data structures, one optimized for prefix-based search and one optimized for ordinal-based lookup.

For prefix-based search, a trie is the natural data structure. It might not be very compressed, either, due to number of pointers it requires. A Patricia tree may be somewhat better but it still requires many pointers. It's possible you might be able to come up with a way to lay out nodes in memory so that most pointers can be replaced by small indices.

For ordinal-based search, a simple array of pointers should suffice.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.