Class PaCoTrieDistributor<T>

java.lang.Object
it.unimi.dsi.fastutil.objects.AbstractObject2LongFunction<T>
it.unimi.dsi.sux4j.mph.PaCoTrieDistributor<T>
All Implemented Interfaces:
Function<T,Long>, Object2LongFunction<T>, Size64, Serializable, Function<T,Long>, ToLongFunction<T>

public class PaCoTrieDistributor<T> extends AbstractObject2LongFunction<T> implements Size64
A succinct implementation of a binary partial compacted trie based on a recursive bitstream.

Instances of this class represent a partial compacted trie (PaCo trie). In such a trie, just a prefix of the path at each node is actually stored: then, we just store the number of missing bits.

The main purpose of PaCo tries is to serve as distributors for other data structures: given a set of delimiters D of a set S, a PaCo trie will rank an elements x of S over D, that is, it will return how many elements of D strictly precede x. To do so, a PaCo trie records at each node the smallest possible prefix that make it possible to rank correctly the whole of S: depending on the strings in S, the savings in space can be more or less significant.

An instance of this class stores a trie as a recursive bitstream: a node x with subtrees A and B is stored as

skip pathlen path missing leavesA A B,
where except for path, which is the path at x represented literally, all other components are numbers in δ coding, and the last two components are the recursive encodings of A and B. Leaves are distinguished by having skip equal to zero (in which case, no information after the path is recorded). leavesA is the number of leaves of A.
Author:
Sebastiano Vigna
See Also:
  • Constructor Details

    • PaCoTrieDistributor

      public PaCoTrieDistributor(Iterable<? extends T> elements, int log2BucketSize, TransformationStrategy<? super T> transformationStrategy) throws IOException
      Creates a partial compacted trie using given elements, bucket size and transformation strategy.
      Parameters:
      elements - the elements among which the trie must be able to rank.
      log2BucketSize - the logarithm of the size of a bucket.
      transformationStrategy - a transformation strategy that must turn the elements in elements into a list of distinct, lexicographically increasing (in iteration order) bit vectors.
      Throws:
      IOException
  • Method Details