it.unimi.dsi.sux4j.mph
Class BitstreamImmutablePaCoTrie<T>
java.lang.Object
it.unimi.dsi.fastutil.objects.AbstractObject2LongFunction<T>
it.unimi.dsi.sux4j.mph.BitstreamImmutablePaCoTrie<T>
- All Implemented Interfaces:
- Function<T,java.lang.Long>, Object2LongFunction<T>, java.io.Serializable
public class BitstreamImmutablePaCoTrie<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
Constructor Summary |
BitstreamImmutablePaCoTrie(java.lang.Iterable<? extends T> elements,
int bucketSize,
TransformationStrategy<? super T> transformationStrategy)
Creates a partial compacted trie using given elements, bucket size and transformation strategy. |
Methods inherited from class java.lang.Object |
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
BitstreamImmutablePaCoTrie
public BitstreamImmutablePaCoTrie(java.lang.Iterable<? extends T> elements,
int bucketSize,
TransformationStrategy<? super T> transformationStrategy)
throws java.io.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.bucketSize
- 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:
java.io.IOException
getLong
public long getLong(java.lang.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(java.lang.Object o)
size
public int size()