Searching Strings by Prefix
Paolo Ferragina · Cambridge University Press eBooks · 2023
The present and following chapter extend the treatment of the dictionary problem to the case of more sophisticated forms of key matching, namely prefix match and substring match between a variable-length pattern string and all strings of an input dictionary. In particular, this chapter addresses the former problem, which occurs in many real-life applications concerned, first and foremost, with key-value stores and search engines. Discussion starts with very simple array-based solutions for internal and external memory (i.e. disks), and then moves to evaluate their time , space, and I/O complexities, which motivates the introduction of more advanced solutions for string compression (i.e. front coding and locality-preserving front coding), and data-structure design for prefix string search (i.e. compacted tries and Patricia tries). The chapter is concluded with a discussion on the management of dynamic and very large string dictionaries, which leads to the description of String B-trees. As for all previous chapters, the algorithmic discussion is enriched with pseudocodes, illustrative figures, and many running examples.