Class FrontCodedDictionary
Defined in File FrontCoding.h
Nested Relationships
Nested Types
Class Documentation
-
class FrontCodedDictionary
a sorted dictionary of strings in the front coding, with anchors
Public Types
-
using value_type = std::string
-
using size_type = std::size_t
-
using difference_type = std::ptrdiff_t
-
using reference = const std::string&
-
using const_reference = const std::string&
-
using iterator = const_iterator
Public Functions
-
std::string access(std::size_t i) const
the string i, decoded from the anchor before it
- Pre:
i < size()
-
std::size_t lexicographicPosition(std::string_view Q) const
the number of strings smaller than Q
-
std::size_t prefixEnd(std::string_view P) const
the number of strings smaller than P#
-
std::pair<std::size_t, std::size_t> prefixRange(std::string_view P) const
the range [ l , r ) of the strings prefixed by P
-
std::size_t rankInBucket(std::size_t k, std::string_view P, bool upper) const
the number of strings smaller than P (or P# if upper), given that k anchors are: the scan of the bucket k - 1
- Pre:
k <= anchors(), and k is right
-
std::size_t size(void) const
-
std::size_t anchors(void) const
the number of anchors, the strings stored whole
-
std::size_t anchor(std::size_t k) const
the place in the dictionary of the anchor k
- Pre:
k < anchors()
-
std::size_t characters(void) const
the characters of the coding, those of the rests and of the anchors
-
std::size_t bytes(void) const
the bytes of the coding, the characters and the codes of the lengths
-
inline const_iterator begin(void) const
-
inline const_iterator end(void) const
-
inline const_iterator cbegin(void) const
-
inline const_iterator cend(void) const
Public Static Functions
-
static FrontCodedDictionary bucketed(const std::vector<std::string> &D, std::size_t b)
the front coding with an anchor every b strings
- Pre:
D is sorted (an audit) and b >= 1
-
static FrontCodedDictionary localityPreserving(const std::vector<std::string> &D, double c)
the locality-preserving front coding of parameter c
- Pre:
D is sorted (an audit) and c > 0
- Post:
for c > 2, characters() <= ( 1 + 2 / ( c - 2 ) ) FC( D ) and decodeCost( i ) <= ( c + 1 ) | s_i |
-
class const_iterator
Public Types
-
using reference = const std::string&
-
using value_type = std::string
-
using difference_type = std::ptrdiff_t
-
using iterator_concept = std::forward_iterator_tag
-
using iterator_category = std::input_iterator_tag
Public Functions
-
const_iterator(void) = default
-
inline const_iterator(const FrontCodedDictionary *d, std::size_t i)
-
inline const_iterator &operator++(void)
-
inline const_iterator operator++(int)
-
inline bool operator==(const const_iterator &o) const
-
using reference = const std::string&
-
using value_type = std::string