Fast prefix search in little space, with applications

A prefix search returns the strings out of a given collection S that start with a given prefix. Traditionally, prefix search is solved by data structures that are also dictionaries, that is, they actually contain the strings in S. For very large collections stored in slow-access memory, we propose extremely compact data structures that solve weak prefix searches\u2014they return the correct result only if some string in S starts with the given prefix. Our data structures for weak prefix search use O(|S |log \u2113) bits in the worst case, where \u2113 is the average string length, as opposed to O(|S|\u2113) bits for a dictionary. We show a lower bound implying that this space usage is optimal