Class PaCoTrieDistributor<T>
- java.lang.Object
-
- it.unimi.dsi.fastutil.objects.AbstractObject2LongFunction<T>
-
- it.unimi.dsi.sux4j.mph.PaCoTrieDistributor<T>
-
- All Implemented Interfaces:
it.unimi.dsi.fastutil.Function<T,java.lang.Long>
,it.unimi.dsi.fastutil.objects.Object2LongFunction<T>
,it.unimi.dsi.fastutil.Size64
,java.io.Serializable
,java.util.function.Function<T,java.lang.Long>
,java.util.function.ToLongFunction<T>
public class PaCoTrieDistributor<T> extends it.unimi.dsi.fastutil.objects.AbstractObject2LongFunction<T> implements it.unimi.dsi.fastutil.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:
- Serialized Form
-
-
Constructor Summary
Constructors Constructor Description PaCoTrieDistributor(java.lang.Iterable<? extends T> elements, int log2BucketSize, it.unimi.dsi.bits.TransformationStrategy<? super T> transformationStrategy)
Creates a partial compacted trie using given elements, bucket size and transformation strategy.
-
Method Summary
All Methods Instance Methods Concrete Methods Deprecated Methods Modifier and Type Method Description boolean
containsKey(java.lang.Object o)
long
getLong(java.lang.Object o)
long
numBits()
int
size()
Deprecated.long
size64()
-
Methods inherited from class it.unimi.dsi.fastutil.objects.AbstractObject2LongFunction
defaultReturnValue, defaultReturnValue
-
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
-
Methods inherited from interface it.unimi.dsi.fastutil.objects.Object2LongFunction
andThen, andThenByte, andThenChar, andThenDouble, andThenFloat, andThenInt, andThenLong, andThenObject, andThenReference, andThenShort, applyAsLong, composeByte, composeChar, composeDouble, composeFloat, composeInt, composeLong, composeObject, composeReference, composeShort, get, getOrDefault, getOrDefault, put, put, remove, removeLong
-
-
-
-
Constructor Detail
-
PaCoTrieDistributor
public PaCoTrieDistributor(java.lang.Iterable<? extends T> elements, int log2BucketSize, it.unimi.dsi.bits.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.log2BucketSize
- the logarithm of the size of a bucket.transformationStrategy
- a transformation strategy that must turn the elements inelements
into a list of distinct, lexicographically increasing (in iteration order) bit vectors.- Throws:
java.io.IOException
-
-
Method Detail
-
getLong
public long getLong(java.lang.Object o)
- Specified by:
getLong
in interfaceit.unimi.dsi.fastutil.objects.Object2LongFunction<T>
-
numBits
public long numBits()
-
containsKey
public boolean containsKey(java.lang.Object o)
- Specified by:
containsKey
in interfaceit.unimi.dsi.fastutil.Function<T,java.lang.Long>
-
size64
public long size64()
- Specified by:
size64
in interfaceit.unimi.dsi.fastutil.Size64
-
size
@Deprecated public int size()
Deprecated.- Specified by:
size
in interfaceit.unimi.dsi.fastutil.Function<T,java.lang.Long>
- Specified by:
size
in interfaceit.unimi.dsi.fastutil.Size64
-
-