zbMATH — the first resource for mathematics

Fast prefix search in little space, with applications. (English) Zbl 1287.68188
de Berg, Mark (ed.) et al., Algorithms – ESA 2010. 18th annual European symposium, Liverpool, UK, September 6–8, 2010. Proceedings, Part I. Berlin: Springer (ISBN 978-3-642-15774-5/pbk). Lecture Notes in Computer Science 6346, 427-438 (2010).
Summary: 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 \ell )$$ bits in the worst case, where $$\ell$$ is the average string length, as opposed to $$O(|S| \ell )$$ bits for a dictionary. We show a lower bound implying that this space usage is optimal.
For the entire collection see [Zbl 1194.68069].

MSC:
 68W32 Algorithms on strings 68P05 Data structures
Full Text: