TwoStepsGOV3Function (Sux4J 4.0.0)

java.lang.Object
- it.unimi.dsi.fastutil.objects.AbstractObject2LongFunction<K>
- - it.unimi.dsi.sux4j.mph.AbstractHashFunction<T>
  - - it.unimi.dsi.sux4j.mph.TwoStepsGOV3Function<T>

All Implemented Interfaces:

Function<T,Long>, Object2LongFunction<T>, Size64, Serializable
```
public class TwoStepsGOV3Function<T>
extends AbstractHashFunction<T>
implements Serializable, Size64
```
A function stored using two GOV3Functions—one for frequent values, and one for infrequent values. This naive idea turns out to be very effective in reducing the function size when the distribution of values is skewed (e.g., as it happens in a TwoStepsLcpMonotoneMinimalPerfectHashFunction).
To create an instance, we perform a pre-scan of the values to be assigned. If possible, we finds the best possible r such that the 2^r − 1 most frequent values can be stored in a GOV3Function and suitably remapped when read. The function uses 2^r − 1 as an escape symbol for all other values, which are stored in a separate function.
Warning: during the construction phase, a filter will be set on the ChunkedHashStore used to store the keys. If you are passing a store, you will have to reset it to its previous state.

Since:

4.0

Author:

Sebastiano Vigna

See Also:

Serialized Form

Nested Class Summary

Nested Classes
Modifier and Type Class and Description

static class TwoStepsGOV3Function.Builder<T>
A builder class for TwoStepsGOV3Function.

Nested Classes
Modifier and Type	Class and Description
`static class`	`TwoStepsGOV3Function.Builder<T>` A builder class for `TwoStepsGOV3Function`.

Field Summary

Fields
Modifier and Type	Field and Description
`protected int`	`escape` The escape value returned by `firstFunction` to suggest that `secondFunction` should be queried instead, provided that there is a first function.
`protected GOV3Function<T>`	`firstFunction` The first function, or `null`.
`protected long`	`n` The number of keys.
`protected double`	`rankMean` The mean of the rank distribution.
`protected long[]`	`remap` A mapping from values of the first function to actual values, provided that there is a first function.
`protected GOV3Function<T>`	`secondFunction` The second function.
`protected long`	`seed` The seed to be used when converting keys to triples.
`static long`	`serialVersionUID`
`protected TransformationStrategy<? super T>`	`transform` The transformation strategy to turn objects of type `T` into bit vectors.
`protected int`	`width` The width of the output of this function, in bits.

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

Constructor Summary

Constructors
Modifier	Constructor and Description
`protected`	`TwoStepsGOV3Function(Iterable<? extends T> keys, TransformationStrategy<? super T> transform, LongBigList values, File tempDir, ChunkedHashStore<T> chunkedHashStore)` Creates a new two-step function for the given keys and values.

Method Summary

All Methods Static Methods Instance Methods Concrete Methods
Modifier and Type	Method and Description
`long`	`getLong(Object o)`
`long`	`getLongByTriple(long[] triple)`
`static void`	`main(String[] arg)`
`long`	`numBits()` Returns the number of bits used by this structure.
`long`	`size64()`

Methods inherited from class it.unimi.dsi.sux4j.mph.AbstractHashFunction
containsKey, size

Methods inherited from class it.unimi.dsi.fastutil.objects.AbstractObject2LongFunction
clear, defaultReturnValue, defaultReturnValue, get, put, put, remove, removeLong

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.Size64
size

- Field Detail
  - serialVersionUID
```
public static final long serialVersionUID
```
    See Also:
    
    Constant Field Values
  - n
```
protected final long n
```
    The number of keys.
  - transform
```
protected final TransformationStrategy<? super T> transform
```
    The transformation strategy to turn objects of type T into bit vectors.
  - firstFunction
```
protected final GOV3Function<T> firstFunction
```
    The first function, or null. The special output value escape denotes that secondFunction should be queried instead.
  - secondFunction
```
protected final GOV3Function<T> secondFunction
```
    The second function. All queries for which firstFunction returns escape (or simply all queries, if firstFunction is null) will be rerouted here.
  - remap
```
protected final long[] remap
```
    A mapping from values of the first function to actual values, provided that there is a first function.
  - escape
```
protected final int escape
```
    The escape value returned by firstFunction to suggest that secondFunction should be queried instead, provided that there is a first function.
  - seed
```
protected long seed
```
    The seed to be used when converting keys to triples.
  - width
```
protected final int width
```
    The width of the output of this function, in bits.
  - rankMean
```
protected final double rankMean
```
    The mean of the rank distribution.
- Constructor Detail
  - TwoStepsGOV3Function
```
protected TwoStepsGOV3Function(Iterable<? extends T> keys,
                               TransformationStrategy<? super T> transform,
                               LongBigList values,
                               File tempDir,
                               ChunkedHashStore<T> chunkedHashStore)
                        throws IOException
```
    Creates a new two-step function for the given keys and values.
    
    Parameters:
    
    keys - the keys in the domain of the function.
    
    transform - a transformation strategy for the keys.
    
    values - values to be assigned to each key, in the same order of the iterator returned by keys; if null, the assigned value will the the ordinal number of each key.
    
    tempDir - a temporary directory for the store files, or null for the standard temporary directory.
    
    chunkedHashStore - a chunked hash store containing the keys associated with their rank, or null; the store can be unchecked, but in this case keys and transform must be non-null.
    
    Throws:
    
    IOException
- Method Detail
  - getLong
```
public long getLong(Object o)
```
    Specified by:
    
    getLong in interface Object2LongFunction<T>
  - getLongByTriple
```
public long getLongByTriple(long[] triple)
```
  - size64
```
public long size64()
```
    Specified by:
    
    size64 in interface Size64
    
    Overrides:
    
    size64 in class AbstractHashFunction<T>
  - numBits
```
public long numBits()
```
    Returns the number of bits used by this structure.
    
    Returns:
    
    the number of bits used by this structure.
  - main
```
public static void main(String[] arg)
                 throws NoSuchMethodException,
                        IOException,
                        JSAPException
```
    Throws:
    
    NoSuchMethodException
    
    IOException
    
    JSAPException

Class TwoStepsGOV3Function<T>

Nested Class Summary

Field Summary

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

Constructor Summary

Method Summary

Methods inherited from class it.unimi.dsi.sux4j.mph.AbstractHashFunction

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

Methods inherited from class java.lang.Object

Methods inherited from interface it.unimi.dsi.fastutil.Size64

Field Detail

serialVersionUID

n

transform

firstFunction

secondFunction

remap

escape

seed

width

rankMean

Constructor Detail

TwoStepsGOV3Function

Method Detail

getLong

getLongByTriple

size64

numBits

main