shiftaddxorsignedminimalperfecthash.java

MG4J (Managing Gigabytes for Java) is a free full-text search engine for large document collections

package it.unimi.dsi.mg4j.util;

/*		 
 * MG4J: Managing Gigabytes for Java
 *
 * Copyright (C) 2006-2007 Sebastiano Vigna 
 *
 *  This library is free software; you can redistribute it and/or modify it
 *  under the terms of the GNU Lesser General Public License as published by the Free
 *  Software Foundation; either version 2.1 of the License, or (at your option)
 *  any later version.
 *
 *  This library is distributed in the hope that it will be useful, but
 *  WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
 *  or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public License
 *  for more details.
 *
 *  You should have received a copy of the GNU Lesser General Public License
 *  along with this program; if not, write to the Free Software
 *  Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
 *
 */

import java.io.IOException;
import java.lang.reflect.InvocationTargetException;
import java.util.Iterator;
import java.util.zip.GZIPInputStream;

import com.martiansoftware.jsap.JSAPException;

/** Order-preserving minimal perfect hash tables signed using Shift-Add-Xor hashes. See
 * “Performance in practice of string hashing functions”, by
 * M.V. Ramakrishna and Justin Zobel, <i>Proc. of the Fifth International Conference on 
 * Database Systems for Advanced Applications</i>, 1997, pages 215&minus;223.
 *
 * @author Sebastiano Vigna
 * @since 1.1.2
 * @deprecated Use the new hashing stuff in Sux4J.
 */

@Deprecated
public class ShiftAddXorSignedMinimalPerfectHash extends SignedMinimalPerfectHash {
	private static final long serialVersionUID = 1L;

	/** The array of signatures. */
    protected int[] signature;

    
    /** Creates a new Shift-Add-Xor-signed order-preserving minimal perfect hash table 
	 * for the given terms using the given number of weights.
	 *
	 * @param terms some terms to hash; it is assumed that no terms share a common prefix of
	 * <code>weightLength</code> characters.
	 * @param weightLength the number of weights used generating the
	 * intermediate hash functions.
	 * @see MinimalPerfectHash#MinimalPerfectHash(Iterable, int)
	 */
	public ShiftAddXorSignedMinimalPerfectHash( final Iterable<? extends CharSequence> terms, final int weightLength ) {
		super( terms, weightLength );
	}

	/** Creates a new Shift-Add-Xor-signed order-preserving minimal perfect hash table for the given
	 * terms, using as many weights as the longest term in the collection.
     *
	 * @param terms some terms to hash; it is assumed that there are no duplicates.
	 * @see MinimalPerfectHash#MinimalPerfectHash(Iterable)
	 *	 
	 */
    public ShiftAddXorSignedMinimalPerfectHash( final Iterable<? extends CharSequence> terms ) {
		super( terms );
    }

	/** Creates a new Shift-Add-Xor-signed order-preserving minimal perfect hash table for the given file 
	 * of terms using the given number of weights.
	 *
	 * @param termFile an UTF-8 file containing one term on each line; it is assumed that 
	 * it does not contain terms with a common prefix of
	 * <code>weightLength</code> characters.
	 * @param encoding the encoding of <code>wordFile</code>; if <code>null</code>, it
	 * is assumed to be the platform default encoding.
	 * @param weightLength the number of weights used generating the
	 * intermediate hash functions.
	 * @see MinimalPerfectHash#MinimalPerfectHash(String, String, int)
	 */
	public ShiftAddXorSignedMinimalPerfectHash( final String termFile, final String encoding, final int weightLength ) {
		super( termFile, encoding, weightLength );
	}


	/** Creates a new Shift-Add-Xor-signed order-preserving minimal perfect hash table for the (possibly <samp>gzip</samp>'d) given file 
	 * of terms.
	 *
	 * @param termFile an UTF-8 file containing one term on each line; it is assumed that 
	 * it does not contain terms with a common prefix of
	 * <code>weightLength</code> characters.
	 * @param encoding the encoding of <code>wordFile</code>; if <code>null</code>, it
	 * is assumed to be the platform default encoding.
	 * @see MinimalPerfectHash#MinimalPerfectHash(String, String, int)
	 */
	public ShiftAddXorSignedMinimalPerfectHash( final String termFile, final String encoding ) {
		super( termFile, encoding );
	}

	/** Creates a new Shift-Add-Xor-signed order-preserving minimal perfect hash table for the (possibly <samp>gzip</samp>'d) given file 
	 * of terms using the given number of weights.
	 *
	 * @param termFile an UTF-8 file containing one term on each line; it is assumed that 
	 * it does not contain terms with a common prefix of
	 * <code>weightLength</code> characters.
	 * @param encoding the encoding of <code>wordFile</code>; if <code>null</code>, it
	 * is assumed to be the platform default encoding.
	 * @param weightLength the number of weights used generating the
	 * intermediate hash functions.
	 * @param zipped if true, the provided file is zipped and will be opened using a {@link GZIPInputStream}.
	 * @see MinimalPerfectHash#MinimalPerfectHash(String, String, int)
	 */
	public ShiftAddXorSignedMinimalPerfectHash( final String termFile, final String encoding, final int weightLength, final boolean zipped ) {
		super( termFile, encoding, weightLength, zipped );
	}


	/** Creates a new Shift-Add-Xor-signed order-preserving minimal perfect hash table for the given file 
	 * of terms.
	 *
	 * @param termFile an UTF-8 file containing one term on each line; it is assumed that 
	 * it does not contain terms with a common prefix of
	 * <code>weightLength</code> characters.
	 * @param encoding the encoding of <code>wordFile</code>; if <code>null</code>, it
	 * is assumed to be the platform default encoding.
	 * @param zipped if true, the provided file is zipped and will be opened using a {@link GZIPInputStream}.
	 * @see MinimalPerfectHash#MinimalPerfectHash(String, String, int)
	 */
	public ShiftAddXorSignedMinimalPerfectHash( final String termFile, final String encoding, final boolean zipped ) {
		super( termFile, encoding, zipped );
	}


	@Override
	public void initSignatures( final Iterable<? extends CharSequence> terms ) {
		CharSequence s;
		int i, j, h, l;
	
		signature = new int[ n ];
	
		j = 0;
		for ( Iterator<? extends CharSequence> e = terms.iterator(); e.hasNext(); j++ ) {
			s = e.next();
			l = s.length();
			h = 42;
			for ( i = l; i-- != 0; ) h ^= ( h << 5 ) + s.charAt( i ) + ( h >>> 2 );
			signature[ j ] = h;
		}
	}

	@Override
	public boolean checkSignature( final CharSequence word, final int index ) {
		if ( n == 0 ) return false; // Empty maps contain no word
		int i, h = 42, l = word.length();
		for ( i = l; i-- != 0; ) h ^= ( h << 5 ) + word.charAt( i ) + ( h >>> 2 );
		return signature[ index ] == h;
	}

	@Override
	public boolean checkSignature( final byte[] a, int off, int len, final int index ) {
		if ( n == 0 ) return false; // Empty maps contain no word
		int h = 42;
		while( len-- != 0 ) h ^= ( h << 5 ) + a[ off + len ] + ( h >>> 2 );
		return signature[ index ] == h;
	}

    public static void main( final String[] arg ) throws InstantiationException, IllegalAccessException, InvocationTargetException, NoSuchMethodException, IOException, JSAPException, ClassNotFoundException {
    	MinimalPerfectHash.main( ShiftAddXorSignedMinimalPerfectHash.class, arg );
    }

}