Package it.unimi.dsi.sux4j.mph

Class TwoStepsMWHCFunction<T>

java.lang.Object
it.unimi.dsi.fastutil.objects.AbstractObject2LongFunction<K>
it.unimi.dsi.sux4j.mph.AbstractHashFunction<T>
it.unimi.dsi.sux4j.mph.TwoStepsMWHCFunction<T>
All Implemented Interfaces:
Function<T,Long>, Object2LongFunction<T>, Size64, Serializable, Function<T,Long>, ToLongFunction<T>
@Deprecated public class TwoStepsMWHCFunction<T> extends AbstractHashFunction<T> implements Serializable, 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:

  • Field Details

    • serialVersionUID

      public static final long serialVersionUID
      Deprecated.
      See Also:

    • n

      protected final long n
      Deprecated.
      The number of keys.

    • transform

      protected final 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, TransformationStrategy<? super T> transform, 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