Package it.unimi.dsi.sux4j.mph

Class TwoStepsLcpMonotoneMinimalPerfectHashFunction<T>

  • All Implemented Interfaces:
    it.unimi.dsi.fastutil.Function<T,​java.lang.Long>, it.unimi.dsi.fastutil.objects.Object2LongFunction<T>, it.unimi.dsi.fastutil.Size64, java.io.Serializable, java.util.function.Function<T,​java.lang.Long>, java.util.function.ToLongFunction<T>
    public class TwoStepsLcpMonotoneMinimalPerfectHashFunction<T>
extends AbstractHashFunction<T>
implements it.unimi.dsi.fastutil.Size64, java.io.Serializable
    A monotone minimal perfect hash implementation based on fixed-size bucketing that uses longest common prefixes as distributors, and store their lengths using a TwoStepsGOV3Function.

    This implementation should use a few less bits per elements than LcpMonotoneMinimalPerfectHashFunction, but it is a bit slower as one or two additional functions must be queried.

    See the package overview for a comparison with other implementations. Similarly to a GOV3Function, an instance of this class may be signed.

    See Also:
    Serialized Form

    • Field Summary

      Fields 
      Modifier and Type Field Description
      protected int bucketSize
      The size of a bucket.
      protected int bucketSizeMask
      The mask for log2BucketSize bits.
      protected GOV3Function<it.unimi.dsi.bits.BitVector> lcp2Bucket
      A function mapping each longest common prefix to its bucket.
      protected TwoStepsGOV3Function<it.unimi.dsi.bits.BitVector> lcpLengths
      A function mapping each element to the length of the longest common prefix of its bucket.
      protected int log2BucketSize
      Fast.ceilLog2(int) of bucketSize.
      protected long n
      The number of elements.
      protected GOV3Function<it.unimi.dsi.bits.BitVector> offsets
      A function mapping each element to the offset inside its bucket.
      protected long seed
      The seed returned by the BucketedHashStore.
      static long serialVersionUID  
      protected long signatureMask
      The mask to compare signatures, or zero for no signatures.
      protected it.unimi.dsi.fastutil.longs.LongBigList signatures
      The signatures.
      protected it.unimi.dsi.bits.TransformationStrategy<? super T> transform
      The transformation strategy.

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

        defRetValue

    • Constructor Summary

      Constructors 
      Modifier Constructor Description
      protected TwoStepsLcpMonotoneMinimalPerfectHashFunction​(java.lang.Iterable<? extends T> keys, long numKeys, it.unimi.dsi.bits.TransformationStrategy<? super T> transform, int signatureWidth, java.io.File tempDir)
      Creates a new two-steps LCP monotone minimal perfect hash function for the given keys.

    • Method Summary

      All Methods Static Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      long getLong​(java.lang.Object o)  
      long getLongByBitVectorAndSignature​(it.unimi.dsi.bits.BitVector bitVector, long[] signature)  
      static void main​(java.lang.String[] arg)  
      long numBits()
      Returns the number of bits used by this structure.
      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

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

        size

    • Field Detail

      • n

        protected final long n
        The number of elements.

      • bucketSize

        protected final int bucketSize
        The size of a bucket.

      • log2BucketSize

        protected final int log2BucketSize
        Fast.ceilLog2(int) of bucketSize.

      • bucketSizeMask

        protected final int bucketSizeMask
        The mask for log2BucketSize bits.

      • offsets

        protected final GOV3Function<it.unimi.dsi.bits.BitVector> offsets
        A function mapping each element to the offset inside its bucket.

      • lcpLengths

        protected final TwoStepsGOV3Function<it.unimi.dsi.bits.BitVector> lcpLengths
        A function mapping each element to the length of the longest common prefix of its bucket.

      • lcp2Bucket

        protected final GOV3Function<it.unimi.dsi.bits.BitVector> lcp2Bucket
        A function mapping each longest common prefix to its bucket.

      • transform

        protected final it.unimi.dsi.bits.TransformationStrategy<? super T> transform
        The transformation strategy.

      • signatureMask

        protected final long signatureMask
        The mask to compare signatures, or zero for no signatures.

      • signatures

        protected final it.unimi.dsi.fastutil.longs.LongBigList signatures
        The signatures.

    • Constructor Detail

      • TwoStepsLcpMonotoneMinimalPerfectHashFunction

        protected TwoStepsLcpMonotoneMinimalPerfectHashFunction​(java.lang.Iterable<? extends T> keys,
                                                        long numKeys,
                                                        it.unimi.dsi.bits.TransformationStrategy<? super T> transform,
                                                        int signatureWidth,
                                                        java.io.File tempDir)
                                                 throws java.io.IOException
        Creates a new two-steps LCP monotone minimal perfect hash function for the given keys.
        Parameters:
        keys - the keys to hash.
        numKeys - the number of keys, or -1 if the number of keys is not known (will be computed).
        transform - a transformation strategy for the keys.
        signatureWidth - a signature width, or 0 for no signature.
        tempDir - a temporary directory for the store files, or null for the standard temporary directory.
        Throws:
        java.io.IOException

    • Method Detail

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

      • getLong

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

      • getLongByBitVectorAndSignature

        public long getLongByBitVectorAndSignature​(it.unimi.dsi.bits.BitVector bitVector,
                                           long[] signature)

      • main

        public static void main​(java.lang.String[] arg)
                 throws java.lang.NoSuchMethodException,
                        java.io.IOException,
                        com.martiansoftware.jsap.JSAPException
        Throws:
        java.lang.NoSuchMethodException
        java.io.IOException
        com.martiansoftware.jsap.JSAPException