File FrontCoding.h

↰ Parent directory (ADS/string)

The front coding of a sorted dictionary of strings, beyond the book: adjacent strings share a prefix, and frontCode() writes the string :math:` s_i ` as the pair :math:` ( ell_i , hat s_i ) , :math: ell_i ` being the length of the longest common prefix of :math:` s_i ` and :math:` s_{i-1} ` (0 for the first one) and :math:` hat s_i ` the rest of :math:` s_i ; frontDecode() copies :math: ell_i ` characters of the string before and appends :math:` hat s_i `.

Definition (ADS/string/FrontCoding.h)

Detailed Description

The length goes in the byte-aligned code of the notes [see encodeLength()]: the binary of :math:` ell ` padded to a whole number of bytes, the first two bits of the padding giving the number of bytes, so that :math:` ell < 2^{30} ` takes 1 to 4 bytes instead of the :math:` ell ` characters of the prefix. On the dictionaries of URLs the shared prefixes are up to 70 % of the characters.

A string is decoded from the last one stored whole, and with no more of them the decoding of :math:` s_i ` may scan the whole dictionary before it; FrontCodedDictionary stores some strings whole (the anchors) and decodes a string from the anchor before it, copying only the :math:` ell ` characters that each pair takes from the previous one:

  • bucketed() is the front coding with bucketing :math:` FC_B ` of the notes: an anchor every b strings, i.e., buckets of b strings coded on their own; a larger b compresses better and scans more (up to :math:` Theta( b^2 ) ` characters for a bucket like a , aa , aaa , …);

  • localityPreserving() is the locality-preserving front coding of Bender, Farach-Colton and Kuszmaul: :math:` s_i ` is front coded only if the anchor before it begins within the last :math:` c | s_i | ` characters of the coding, else it is stored whole; a string is then decoded by reading at most :math:` ( c + 1 ) | s_i | ` characters, the optimal :math:` O( | s_i | / B ) ` transfers of blocks, and the coding takes at most :math:` ( 1 + 2 / ( c - 2 ) ) FC( D ) ` characters for :math:` c > 2 `, FC( D ) being those of the front coding (Theorem 9.5 of the notes): the time controls the space.

Both search by prefix as the two-level scheme of section 9.1 of the notes: a binary search on the anchors, which are whole, and the scan of the one bucket where the pattern falls, decoded on the fly; the binary search may be replaced by a Patricia trie on the anchors [see File TwoLevelDictionary.h]. The string B-tree of Ferragina and Grossi and its cache-oblivious version by Bender, Farach-Colton and Kuszmaul, which also works on the locality-preserving coding, bring the search in external memory to :math:` O( ( p + N_{occ} ) / B + log_B n ) ` transfers.

The contracts [see File Contract.h]: :math:` ell < 2^{30} ` for encodeLength(), a pair that takes at most the characters of the string before for frontDecode(), the dictionary sorted for FrontCodedDictionary (an audit), b >= 1 and c > 0; the decoding of the coding gives the strings back, an audit, and the locality-preserving coding is within its bounds of space and time, a postcondition for c > 2. The functions are defined in FrontCoding.tpp.

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

    1. Witten, A. Moffat, T. C. Bell, Managing Gigabytes, 2nd ed., Morgan Kaufmann, 1999 (the front coding of a lexicon)

    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. 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. 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

Included By

Namespaces

Classes

Functions

Typedefs