File PrefixSearch.h

↰ Parent directory (ADS/string)

The search by prefix in a sorted dictionary of n strings, beyond the book: the strings prefixed by P are consecutive, between the lexicographic position of P (the number of strings smaller than P) and that of P#, # being a character larger than all the others, so that two lexicographic searches give their range.

Definition (ADS/string/PrefixSearch.h)

Detailed Description

  • lexicographicPosition(), prefixEnd() and prefixRange() search the array of the strings by a binary search, :math:` O( p log n ) ` time for a pattern of p characters, each step a comparison of strings: simple, but each step reads a string far from the others, i.e., :math:` O( ( p / B ) log n ) ` transfers of blocks of B characters, which the two-level dictionaries [see FrontCodedDictionary and TwoLevelDictionary] reduce to a search on a sample of the strings and the scan of one bucket;

  • BinnedSearch, the search by interpolation of Demaine, Jones and Patrascu in a sorted array X of m integers: :math:` [ x_1 , x_m ] ` is cut into bins of width :math:` b = lceil ( x_m - x_1 + 1 ) / m rceil , an array gives where each bin starts in X, and y is searched by a binary search in its bin :math: lfloor ( y - x_1 ) / b rfloor ; a bin holds at most :math: Delta ` items, :math:` Delta ` being the ratio between the largest and the smallest gap of X, since b is at most the largest gap (Theorem 9.4 of the notes), so that a search takes :math:` O( log min( Delta , m ) ) ` time in the worst case, never worse than the binary search, and :math:` O( log log m ) ` with high probability on uniform keys, as the search by interpolation [see File InterpolationSearch.h] whose worst case is O( m ), at the price of the array of the bins;

  • BinnedStringSearch, the same on strings, read as the integers of their first 8 characters (padded with the character 0), which keep their order: the bin of a pattern is found by its integer, and the binary search in the bin compares whole strings.

The contracts [see File Contract.h]: the array sorted, an audit (for the strings by the order of std::string, i.e., of the unsigned characters); each position r is such that the items before r are smaller than the pattern and those from r on are not, a postcondition. The functions are defined in PrefixSearch.tpp.

  1. Ferragina, Pearls of Algorithm Engineering, Cambridge University Press, 2023, chapter 9 (sections 9.1 and 9.2)

    1. Demaine, T. Jones, M. Patrascu, Interpolation search for non-independent data, Proceedings of SODA 2004, 529-530, 2004

  1. Perl, A. Itai, H. Avni, Interpolation search: a log log N search, Communications of the ACM 21(7), 550-553, 1978, doi:10.1145/359545.359557

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Included By

Namespaces

Classes

Functions