Class TwoStepsGOV3Function<T>

java.lang.Object
it.unimi.dsi.fastutil.objects.AbstractObject2LongFunction<T>
it.unimi.dsi.sux4j.mph.AbstractHashFunction<T>
it.unimi.dsi.sux4j.mph.TwoStepsGOV3Function<T>
All Implemented Interfaces:
it.unimi.dsi.fastutil.Function<T,Long>, it.unimi.dsi.fastutil.objects.Object2LongFunction<T>, it.unimi.dsi.fastutil.Size64, Serializable, Function<T,Long>, ToLongFunction<T>
public class TwoStepsGOV3Function<T> extends AbstractHashFunction<T> implements Serializable, it.unimi.dsi.fastutil.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 2r − 1 most frequent values can be stored in a GOV3Function and suitably remapped when read. The function uses 2r − 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 BucketedHashStore 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:

  • Nested Class Summary

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

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    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.
    protected final GOV3Function<T>
    firstFunction
    The first function, or null.
    protected final long
    n
    The number of keys.
    protected final double
    rankMean
    The mean of the rank distribution.
    protected final long[]
    remap
    A mapping from values of the first function to actual values, provided that there is a first function.
    protected final GOV3Function<T>
    secondFunction
    The second function.
    protected long
    seed
    The seed to be used when converting keys to signatures.
    static final long
    serialVersionUID
     
    protected final it.unimi.dsi.bits.TransformationStrategy<? super T>
    transform
    The transformation strategy to turn objects of type T into bit vectors.
    protected final 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
    Description
    protected
    TwoStepsGOV3Function(Iterable<? extends T> keys, it.unimi.dsi.bits.TransformationStrategy<? super T> transform, it.unimi.dsi.fastutil.longs.LongBigList values, File tempDir, BucketedHashStore<T> bucketedHashStore)
    Creates a new two-step function for the given keys and values.

  • Method Summary

    Modifier and Type
    Method
    Description
    long
    getLong(Object o)
     
    long
    getLongBySignature(long[] signature)
     
    static void
    main(String[] arg)
     
    long
    numBits()
    Returns the number of bits used by this structure.
    long
    size64()
     

    Methods inherited from class AbstractHashFunction

    containsKey, size

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

    defaultReturnValue, defaultReturnValue

    Methods inherited from class 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 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

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

    size

  • Field Details

    • serialVersionUID

      public static final long serialVersionUID
      See Also:

    • n

      protected final long n
      The number of keys.

    • transform

      protected final it.unimi.dsi.bits.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 signatures.

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

    • TwoStepsGOV3Function

      protected TwoStepsGOV3Function(Iterable<? extends T> keys, it.unimi.dsi.bits.TransformationStrategy<? super T> transform, it.unimi.dsi.fastutil.longs.LongBigList values, File tempDir, BucketedHashStore<T> bucketedHashStore) 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 ordinal number of each key.
      tempDir - a temporary directory for the store files, or null for the standard temporary directory.
      bucketedHashStore - a bucketed 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 Details

    • getLong

      public long getLong(Object o)
      Specified by:
      getLong in interface it.unimi.dsi.fastutil.objects.Object2LongFunction<T>

    • getLongBySignature

      public long getLongBySignature(long[] signature)

    • size64

      public long size64()
      Specified by:
      size64 in interface it.unimi.dsi.fastutil.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, com.martiansoftware.jsap.JSAPException
      Throws:
      NoSuchMethodException
      IOException
      com.martiansoftware.jsap.JSAPException