Fast prefix search in little space, with applications. (English) Zbl 1287.68188

Belazzougui, Djamal; Boldi, Paolo; Pagh, Rasmus; Vigna, Sebastiano

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