File TwoLevelDictionary.h

↰ Parent directory (ADS/dictionary)

The two-level dictionary of strings, beyond the book: the lower level is the front coding of the sorted strings with anchors [see FrontCodedDictionary in File FrontCoding.h], the strings that are stored whole, either one every b (the bucketing) or as the locality-preserving coding decides, and the upper level a Patricia trie [see File PatriciaTrie.h] on the anchors alone.

Definition (ADS/dictionary/TwoLevelDictionary.h)

Detailed Description

A search by prefix is the blind search of the pattern among the anchors, which reads one anchor, and the scan of the one bucket where the pattern falls, decoded on the fly: with the trie in memory and the coding on disk, :math:` O( p / B + | s | / B ) ` transfers of blocks for a pattern of p characters, s being the string read by the blind search, plus the bucket (Theorem 9.9 of the notes), in :math:` O( n_a ) ` words of memory for :math:` n_a ` anchors and :math:` ( 1 + epsilon ) FC( D ) ` characters on disk with the locality-preserving coding. The upper level is independent of the lower one: a binary search on the anchors [see FrontCodedDictionary::lexicographicPosition()] costs :math:` O( ( p / B ) log n_a ) ` transfers instead. When even the trie does not fit in memory, the string B-tree of Ferragina and Grossi splits it into Patricia tries of a block each, linked as a B-tree, for :math:` O( ( p + N_{occ} ) / B + log_B n ) ` transfers.

The contracts [see File Contract.h]: those of FrontCodedDictionary and of PatriciaTrie; each position r is such that the strings before r are smaller than the pattern (or than P#) and those from r on are not, a postcondition. The functions are defined in TwoLevelDictionary.tpp.

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

  1. Ferragina, R. Grossi, The string B-tree: a new data structure for string search in external memory and its applications, Journal of the ACM 46(2), 236-280, 1999, doi:10.1145/301970.301973

    1. Bender, M. Farach-Colton, B. C. Kuszmaul, Cache-oblivious string B-trees, Proceedings of PODS 2006, 233-242, 2006, doi:10.1145/1142351.1142385

    1. Morrison, PATRICIA: practical algorithm to retrieve information coded in alphanumeric, Journal of the ACM 15(4), 514-534, 1968, doi:10.1145/321479.321481

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Classes