All Implemented Interfaces:
Closeable, AutoCloseable, Unwrappable<TokenStream>

public class MinHashFilter extends TokenFilter
Generate min hash tokens from an incoming stream of tokens. The incoming tokens would typically be 5 word shingles.

The number of hashes used and the number of minimum values for each hash can be set. You could have 1 hash and keep the 100 lowest values or 100 hashes and keep the lowest one for each. Hashes can also be bucketed in ranges over the 128-bit hash space,

A 128-bit hash is used internally. 5 word shingles from 10e5 words generate 10e25 combinations So a 64 bit hash would have collisions (1.8e19)

When using different hashes 32 bits are used for the hash position leaving scope for 8e28 unique hashes. A single hash will use all 128 bits.

  • Field Details

  • Constructor Details

    • MinHashFilter

      public MinHashFilter(TokenStream input, int hashCount, int bucketCount, int hashSetSize, boolean withRotation)
      create a MinHash filter
      Parameters:
      input - the token stream
      hashCount - the no. of hashes
      bucketCount - the no. of buckets for hashing
      hashSetSize - the no. of min hashes to keep
      withRotation - whether rotate or not hashes while incrementing tokens
  • Method Details

    • getBytes

      static byte[] getBytes(int i)
    • incrementToken

      public final boolean incrementToken() throws IOException
      Description copied from class: TokenStream
      Consumers (i.e., IndexWriter) use this method to advance the stream to the next token. Implementing classes must implement this method and update the appropriate AttributeImpls with the attributes of the next token.

      The producer must make no assumptions about the attributes after the method has been returned: the caller may arbitrarily change it. If the producer needs to preserve the state for subsequent calls, it can use AttributeSource.captureState() to create a copy of the current attribute state.

      This method is called for every token of a document, so an efficient implementation is crucial for good performance. To avoid calls to AttributeSource.addAttribute(Class) and AttributeSource.getAttribute(Class), references to all AttributeImpls that this stream uses should be retrieved during instantiation.

      To ensure that filters and consumers know which attributes are available, the attributes must be added during instantiation. Filters and consumers are not required to check for availability of attributes in TokenStream.incrementToken().

      Specified by:
      incrementToken in class TokenStream
      Returns:
      false for end of stream; true otherwise
      Throws:
      IOException
    • getIntHash

      private static MinHashFilter.LongPair getIntHash(int i)
    • end

      public void end() throws IOException
      Description copied from class: TokenFilter
      This method is called by the consumer after the last token has been consumed, after TokenStream.incrementToken() returned false (using the new TokenStream API). Streams implementing the old API should upgrade to use this feature.

      This method can be used to perform any end-of-stream operations, such as setting the final offset of a stream. The final offset of a stream might differ from the offset of the last token eg in case one or more whitespaces followed after the last token, but a WhitespaceTokenizer was used.

      Additionally any skipped positions (such as those removed by a stopfilter) can be applied to the position increment, or any adjustment of other attributes where the end-of-stream value may be important.

      If you override this method, always call super.end().

      NOTE: The default implementation chains the call to the input TokenStream, so be sure to call super.end() first when overriding this method.

      Overrides:
      end in class TokenFilter
      Throws:
      IOException - If an I/O error occurs
    • reset

      public void reset() throws IOException
      Description copied from class: TokenFilter
      This method is called by a consumer before it begins consumption using TokenStream.incrementToken().

      Resets this stream to a clean state. Stateful implementations must implement this method so that they can be reused, just as if they had been created fresh.

      If you override this method, always call super.reset(), otherwise some internal state will not be correctly reset (e.g., Tokenizer will throw IllegalStateException on further usage).

      NOTE: The default implementation chains the call to the input TokenStream, so be sure to call super.reset() when overriding this method.

      Overrides:
      reset in class TokenFilter
      Throws:
      IOException
    • doRest

      private void doRest()
    • long0

      private static char long0(long x)
    • long1

      private static char long1(long x)
    • long2

      private static char long2(long x)
    • long3

      private static char long3(long x)
    • int0

      private static char int0(int x)
    • int1

      private static char int1(int x)
    • isLessThanUnsigned

      static boolean isLessThanUnsigned(long n1, long n2)
    • combineOrdered

      private static MinHashFilter.LongPair combineOrdered(MinHashFilter.LongPair... hashCodes)
    • getLongLittleEndian

      private static long getLongLittleEndian(byte[] buf, int offset)
      Gets a long from a byte buffer in little endian byte order.
    • murmurhash3_x64_128

      static void murmurhash3_x64_128(byte[] key, int offset, int len, int seed, MinHashFilter.LongPair out)
      Returns the MurmurHash3_x64_128 hash, placing the result in "out".
    • fmix64

      private static long fmix64(long k)