Struct sucds::mii_sequences::elias_fano::EliasFano

pub struct EliasFano { /* private fields */ }

Compressed monotone increasing sequence through Elias-Fano encoding.

This implements an Elias-Fano representation for monotone increasing sequences. When a sequence stores $n$ integers from $[0, u-1]$, this representation takes $n \lceil \log_2 \frac{u}{n} \rceil + 2n + o(n)$ bits of space, indicating that a sparse sequence can be stored in a very compressed space.

Another attraction of Elias-Fano is several search queries, such as binary search, predecessor, and successor, over the compressed representation.

Example

use sucds::mii_sequences::EliasFanoBuilder;

let mut efb = EliasFanoBuilder::new(8, 4)?;
efb.extend([1, 3, 3, 7])?;
let ef = efb.build();

assert_eq!(ef.len(), 4);
assert_eq!(ef.universe(), 8);

assert_eq!(ef.select(0), Some(1));
assert_eq!(ef.select(1), Some(3));
assert_eq!(ef.select(2), Some(3));
assert_eq!(ef.select(3), Some(7));

assert_eq!(ef.binsearch(7), Some(3));
assert_eq!(ef.binsearch(4), None);

// Builds an index to enable rank, predecessor, and successor.
let ef = ef.enable_rank();

assert_eq!(ef.rank(3), Some(1));
assert_eq!(ef.rank(4), Some(3));
assert_eq!(ef.predecessor(4), Some(3));
assert_eq!(ef.predecessor(3), Some(3));
assert_eq!(ef.successor(3), Some(3));
assert_eq!(ef.successor(4), Some(7));

Credits

This is a yet another Rust port of succinct::elias_fano. The implementation of binary search is based on that in tongrams::fast_ef_sequence.

References

• P. Elias, “Efficient storage and retrieval by content and address of static files,” Journal of the ACM, 1974.
• R. Fano, “On the number of bits required to implement an associative memory,” Memorandum 61. Computer Structures Group, Project MAC, MIT, 1971.
• D. Okanohara, and K. Sadakane, “Practical Entropy-Compressed Rank/Select Dictionary,” In ALENEX, 2007.

Implementations

impl EliasFano

pub fn from_bits<I>(bits: I) -> Result<Self>where I: IntoIterator<Item = bool>,

Creates a new sequence from a bit stream.

Arguments

• bits: Bit stream.

Errors

An error is returned if

• bits is an empty stream, or
• bits contains no set bit.

pub fn enable_rank(self) -> Self

Builds an index to enable operations Self::rank(), Self::predecessor(), and Self::successor().

pub const fn has_rank(&self) -> bool

Checks if Self::enable_rank() is set.

pub fn delta(&self, k: usize) -> Option<usize>

Gets the difference between the k-1-th and k-th integers (i.e., select(k) - select(k-1)), returning None if out of bounds.

Complexity

Constant

Examples

use sucds::mii_sequences::EliasFanoBuilder;

let mut efb = EliasFanoBuilder::new(8, 4)?;
efb.extend([1, 3, 3, 7])?;
let ef = efb.build();

assert_eq!(ef.delta(0), Some(1));
assert_eq!(ef.delta(1), Some(2));
assert_eq!(ef.delta(2), Some(0));
assert_eq!(ef.delta(3), Some(4));
assert_eq!(ef.delta(4), None);

pub fn binsearch(&self, val: usize) -> Option<usize>

Finds the position k such that select(k) == val.

Note that, if there are multiple values of val, one of them is returned.

Arguments

• val: Integer to be searched.

Complexity

$O(\lg n)$

Examples

use sucds::mii_sequences::EliasFanoBuilder;

let mut efb = EliasFanoBuilder::new(11, 6)?;
efb.extend([1, 3, 3, 6, 7, 10])?;
let ef = efb.build();

assert_eq!(ef.binsearch(6), Some(3));
assert_eq!(ef.binsearch(10), Some(5));
assert_eq!(ef.binsearch(9), None);

pub fn binsearch_range(&self, range: Range<usize>, val: usize) -> Option<usize>

Finds the position k such that select(k) == val and k in range.

Note that, if there are multiple values of val, one of them is returned.

Arguments

• range: Position range to be searched.
• val: Integer to be searched.

Complexity

$O(\lg |R|)$ for the range $R$.

Examples

use sucds::mii_sequences::EliasFanoBuilder;

let mut efb = EliasFanoBuilder::new(11, 6)?;
efb.extend([1, 3, 3, 6, 7, 10])?;
let ef = efb.build();

assert_eq!(ef.binsearch_range(1..4, 6), Some(3));
assert_eq!(ef.binsearch_range(5..6, 10), Some(5));
assert_eq!(ef.binsearch_range(1..3, 6), None);

pub fn rank(&self, pos: usize) -> Option<usize>

Returns the number of integers less than pos, or None if self.universe() < pos.

Complexity

$O(\lg \frac{u}{n})$

Panics

It panics if the index is not built by Self::enable_rank().

Examples

use sucds::mii_sequences::EliasFanoBuilder;

let mut efb = EliasFanoBuilder::new(8, 4)?;
efb.extend([1, 3, 3, 7])?;
let ef = efb.build().enable_rank();

assert_eq!(ef.rank(3), Some(1));
assert_eq!(ef.rank(4), Some(3));
assert_eq!(ef.rank(8), Some(4));
assert_eq!(ef.rank(9), None);

pub fn select(&self, k: usize) -> Option<usize>

Returns the position of the k-th smallest integer, or None if self.len() <= k.

Complexity

Constant

Examples

use sucds::mii_sequences::EliasFanoBuilder;

let mut efb = EliasFanoBuilder::new(8, 4)?;
efb.extend([1, 3, 3, 7])?;
let ef = efb.build();

assert_eq!(ef.select(0), Some(1));
assert_eq!(ef.select(1), Some(3));
assert_eq!(ef.select(2), Some(3));
assert_eq!(ef.select(3), Some(7));
assert_eq!(ef.select(4), None);

pub fn predecessor(&self, pos: usize) -> Option<usize>

Gets the largest element pred such that pred <= pos, or None if self.universe() <= pos.

Arguments

• pos: Predecessor query.

Complexity

$O(\lg \frac{u}{n})$

Examples

use sucds::mii_sequences::EliasFanoBuilder;

let mut efb = EliasFanoBuilder::new(8, 4)?;
efb.extend([1, 3, 3, 7])?;
let ef = efb.build().enable_rank();

assert_eq!(ef.predecessor(4), Some(3));
assert_eq!(ef.predecessor(3), Some(3));
assert_eq!(ef.predecessor(2), Some(1));
assert_eq!(ef.predecessor(0), None);

pub fn successor(&self, pos: usize) -> Option<usize>

Gets the smallest element succ such that succ >= pos, or None if self.universe() <= pos.

Arguments

• pos: Successor query.

Complexity

$O(\lg \frac{u}{n})$

Examples

use sucds::mii_sequences::EliasFanoBuilder;

let mut efb = EliasFanoBuilder::new(8, 4)?;
efb.extend([1, 3, 3, 7])?;
let ef = efb.build().enable_rank();

assert_eq!(ef.successor(0), Some(1));
assert_eq!(ef.successor(2), Some(3));
assert_eq!(ef.successor(3), Some(3));
assert_eq!(ef.successor(8), None);

pub fn iter(&self, k: usize) -> Iter<'_>

Creates an iterator of Iter to enumerate integers from the k-th one.

Arguments

• k: Select query.

Examples

use sucds::mii_sequences::EliasFanoBuilder;

let mut efb = EliasFanoBuilder::new(8, 4)?;
efb.extend([1, 3, 3, 7])?;
let ef = efb.build();

let mut it = ef.iter(1);
assert_eq!(it.next(), Some(3));
assert_eq!(it.next(), Some(3));
assert_eq!(it.next(), Some(7));
assert_eq!(it.next(), None);

pub fn len(&self) -> usize

Gets the number of integers.

pub fn is_empty(&self) -> bool

Checks if the sequence is empty.

pub const fn universe(&self) -> usize

Returns the universe, i.e., the (exclusive) upper bound of possible integers.

Trait Implementations

impl Clone for EliasFano

fn clone(&self) -> EliasFano

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for EliasFano

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Default for EliasFano

fn default() -> EliasFano

Returns the “default value” for a type.

impl PartialEq for EliasFano

fn eq(&self, other: &EliasFano) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

This method tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl Serializable for EliasFano

fn serialize_into<W: Write>(&self, writer: W) -> Result<usize>

Serializes the data structure into the writer, returning the number of serialized bytes.

fn deserialize_from<R: Read>(reader: R) -> Result<Self>

Deserializes the data structure from the reader.

fn size_in_bytes(&self) -> usize

Returns the number of bytes to serialize the data structure.

fn size_of() -> Option<usize>

Returns the size of a primitive type in bytes (if the type is so).

impl Eq for EliasFano

impl StructuralEq for EliasFano

impl StructuralPartialEq for EliasFano