it.unimi.dsi.sux4j.mph
Class TwoStepsLcpMonotoneMinimalPerfectHashFunction<T>

java.lang.Object
  extended by it.unimi.dsi.fastutil.objects.AbstractObject2LongFunction<K>
      extended by it.unimi.dsi.sux4j.mph.AbstractHashFunction<T>
          extended by it.unimi.dsi.sux4j.mph.TwoStepsLcpMonotoneMinimalPerfectHashFunction<T>
All Implemented Interfaces:
Function<T,Long>, Object2LongFunction<T>, Serializable

public class TwoStepsLcpMonotoneMinimalPerfectHashFunction<T>
extends AbstractHashFunction<T>
implements 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 TwoStepsMWHCFunction.

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 Also:
Serialized Form

Field Summary
protected  int bucketSize
          The size of a bucket.
protected  int bucketSizeMask
          The mask for log2BucketSize bits.
protected  MWHCFunction<BitVector> lcp2Bucket
          A function mapping each longest common prefix to its bucket.
protected  TwoStepsMWHCFunction<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  int n
          The number of elements.
protected  MWHCFunction<BitVector> offsets
          A function mapping each element to the offset inside its bucket.
static long serialVersionUID
           
protected  TransformationStrategy<? super T> transform
          The transformation strategy.
 
Fields inherited from class it.unimi.dsi.fastutil.objects.AbstractObject2LongFunction
defRetValue
 
Constructor Summary
TwoStepsLcpMonotoneMinimalPerfectHashFunction(Iterable<? extends T> iterable, int numElements, TransformationStrategy<? super T> transform)
           
TwoStepsLcpMonotoneMinimalPerfectHashFunction(Iterable<? extends T> iterable, TransformationStrategy<? super T> transform)
           
 
Method Summary
 long getLong(Object o)
           
 boolean hasTerms()
           
static void main(String[] arg)
           
 long numBits()
          Returns the number of bits used by this structure.
 int size()
          Returns the number of terms hashed.
 
Methods inherited from class it.unimi.dsi.sux4j.mph.AbstractHashFunction
containsKey
 
Methods inherited from class it.unimi.dsi.fastutil.objects.AbstractObject2LongFunction
clear, defaultReturnValue, defaultReturnValue, get, put, put, remove, removeLong
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

serialVersionUID

public static final long serialVersionUID
See Also:
Constant Field Values

n

protected final int 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 MWHCFunction<BitVector> offsets
A function mapping each element to the offset inside its bucket.


lcpLengths

protected final TwoStepsMWHCFunction<BitVector> lcpLengths
A function mapping each element to the length of the longest common prefix of its bucket.


lcp2Bucket

protected final MWHCFunction<BitVector> lcp2Bucket
A function mapping each longest common prefix to its bucket.


transform

protected final TransformationStrategy<? super T> transform
The transformation strategy.

Constructor Detail

TwoStepsLcpMonotoneMinimalPerfectHashFunction

public TwoStepsLcpMonotoneMinimalPerfectHashFunction(Iterable<? extends T> iterable,
                                                     TransformationStrategy<? super T> transform)
                                              throws IOException
Throws:
IOException

TwoStepsLcpMonotoneMinimalPerfectHashFunction

public TwoStepsLcpMonotoneMinimalPerfectHashFunction(Iterable<? extends T> iterable,
                                                     int numElements,
                                                     TransformationStrategy<? super T> transform)
                                              throws IOException
Throws:
IOException
Method Detail

getLong

public long getLong(Object o)
Specified by:
getLong in interface Object2LongFunction<T>

size

public int size()
Returns the number of terms hashed.

Specified by:
size in interface Function<T,Long>
Overrides:
size in class AbstractHashFunction<T>
Returns:
the number of terms hashed.

numBits

public long numBits()
Returns the number of bits used by this structure.

Returns:
the number of bits used by this structure.

hasTerms

public boolean hasTerms()

main

public static void main(String[] arg)
                 throws NoSuchMethodException,
                        IOException,
                        JSAPException
Throws:
NoSuchMethodException
IOException
JSAPException