Class TwoStepsMWHCFunction<T>

java.lang.Object
it.unimi.dsi.fastutil.objects.AbstractObject2LongFunction<T>
it.unimi.dsi.sux4j.mph.AbstractHashFunction<T>
it.unimi.dsi.sux4j.mph.TwoStepsMWHCFunction<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>
@Deprecated public class TwoStepsMWHCFunction<T> extends AbstractHashFunction<T> implements Serializable, it.unimi.dsi.fastutil.Size64
Deprecated.
Please use TwoStepsGOV3Function.
A function stored using two Majewski-Wormald-Havas-Czech functions—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 MWHCFunction 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 ChunkedHashStore used to store the keys. If you are passing a store, you will have to reset it to its previous state.

Since:
1.0.2
Author:
Sebastiano Vigna
See Also:

  • Nested Class Summary

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

  • Field Summary

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

  • Method Summary

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

    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
      Deprecated.
      See Also:

    • n

      protected final long n
      Deprecated.
      The number of keys.

    • transform

      protected final it.unimi.dsi.bits.TransformationStrategy<? super T> transform
      Deprecated.
      The transformation strategy to turn objects of type T into bit vectors.

    • firstFunction

      protected final MWHCFunction<T> firstFunction
      Deprecated.
      The first function, or null. The special output value escape denotes that secondFunction should be queried instead.

    • secondFunction

      protected final MWHCFunction<T> secondFunction
      Deprecated.
      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
      Deprecated.
      A mapping from values of the first function to actual values, provided that there is a first function.

    • escape

      protected final int escape
      Deprecated.
      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
      Deprecated.
      The seed to be used when converting keys to triples.

    • width

      protected final int width
      Deprecated.
      The width of the output of this function, in bits.

    • rankMean

      protected final double rankMean
      Deprecated.
      The mean of the rank distribution.

  • Constructor Details

    • TwoStepsMWHCFunction

      protected TwoStepsMWHCFunction(Iterable<? extends T> keys, it.unimi.dsi.bits.TransformationStrategy<? super T> transform, it.unimi.dsi.fastutil.longs.LongBigList values, File tempDir, ChunkedHashStore<T> chunkedHashStore) throws IOException
      Deprecated.
      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.
      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 Details

    • getLong

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

    • getLongBySignature

      public long getLongBySignature(long[] triple)
      Deprecated.

    • size64

      public long size64()
      Deprecated.
      Specified by:
      size64 in interface it.unimi.dsi.fastutil.Size64
      Overrides:
      size64 in class AbstractHashFunction<T>

    • numBits

      public long numBits()
      Deprecated.
      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
      Deprecated.
      Throws:
      NoSuchMethodException
      IOException
      com.martiansoftware.jsap.JSAPException