it.unimi.dsi.sux4j.mph
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>, Serializable
public class PaCoTrieDistributor<T>
- extends AbstractObject2LongFunction<T>
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:
- Serialized Form
Methods inherited from class java.lang.Object |
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
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
getLong
public long getLong(Object o)
numBits
public long numBits()
numberOfLeaves
public int numberOfLeaves()
- Returns the number of leaves in this trie.
- Returns:
- the number of leaves in this trie.
containsKey
public boolean containsKey(Object o)
size
public int size()