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—they 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 ℓ) bits in the worst case, where ℓ is the average string length, as opposed to O(|S|ℓ) bits for a dictionary. We show a lower bound implying that this space usage is optimal.