Package it.unimi.dsi.sux4j.mph

Class VLLcpMonotoneMinimalPerfectHashFunction<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 VLLcpMonotoneMinimalPerfectHashFunction<T>
extends AbstractHashFunction<T>
implements java.io.Serializable, it.unimi.dsi.fastutil.Size64
    A monotone minimal perfect hash implementation based on fixed-size bucketing that uses longest common prefixes as distributors, and store their lengths using a GOVMinimalPerfectHashFunction indexing an EliasFanoLongBigList. In theory, this function should use less memory than an LcpMonotoneMinimalPerfectHashFunction when the lengths of common prefixes vary wildly, but in practice a TwoStepsLcpMonotoneMinimalPerfectHashFunction is often a better choice.
    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 EliasFanoLongBigList lcpLengths
      A list, indexed by mph, containing for each element the length of the longest common prefix of its bucket.
      protected int log2BucketSize
      Fast.ceilLog2(int) of bucketSize.
      protected GOVMinimalPerfectHashFunction<it.unimi.dsi.bits.BitVector> mph
      A function mapping each element to a distinct index.
      protected long n
      The number of elements.
      protected it.unimi.dsi.fastutil.longs.LongBigList offsets
      A list, indexed by mph, containing the offset of each element inside its bucket.
      static long serialVersionUID  
      protected it.unimi.dsi.bits.TransformationStrategy<? super T> transform
      The transformation strategy.

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

        defRetValue

    • Method Summary

      All Methods Static Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      long getLong​(java.lang.Object o)  
      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 it.unimi.dsi.fastutil.longs.LongBigList offsets
        A list, indexed by mph, containing the offset of each element inside its bucket.

      • lcpLengths

        protected final EliasFanoLongBigList lcpLengths
        A list, indexed by mph, containing for each element 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.

    • Constructor Detail

      • VLLcpMonotoneMinimalPerfectHashFunction

        public VLLcpMonotoneMinimalPerfectHashFunction​(java.lang.Iterable<? extends T> iterable,
                                               it.unimi.dsi.bits.TransformationStrategy<? super T> transform)
                                        throws java.io.IOException
        Throws:
        java.io.IOException

      • VLLcpMonotoneMinimalPerfectHashFunction

        public VLLcpMonotoneMinimalPerfectHashFunction​(java.lang.Iterable<? extends T> iterable,
                                               int numElements,
                                               it.unimi.dsi.bits.TransformationStrategy<? super T> transform)
                                        throws java.io.IOException
        Throws:
        java.io.IOException

    • Method Detail

      • getLong

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

      • 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​(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