Package 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>, 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 leaves_A 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). leaves_A is the number of leaves of A.

Author:

Sebastiano Vigna

See Also:

• Serialized Form

Field Summary

Fields inherited from class it.unimi.dsi.fastutil.objects.AbstractObject2LongFunction

defRetValue

Constructor Summary

Constructors

Constructor	Description
PaCoTrieDistributor(Iterable<? extends T> elements, int log2BucketSize, TransformationStrategy<? super T> transformationStrategy)	Creates a partial compacted trie using given elements, bucket size and transformation strategy.

Method Summary

Modifier and Type	Method	Description
boolean	containsKey(Object o)
long	getLong(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.Function

apply, clear

Methods inherited from interface java.util.function.Function

compose

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 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

getLong

public long getLong(Object o)

Specified by:

getLong in interface Object2LongFunction<T>

numBits

public long numBits()

containsKey

public boolean containsKey(Object o)

Specified by:

containsKey in interface Function<T,Long>

size64

public long size64()

Specified by:

size64 in interface Size64

size

@Deprecated
public int size()

Deprecated.

Specified by:

size in interface Function<T,Long>

Specified by:

size in interface Size64