package svm.instances.dependency.kernel;

import svm.instances.dependency.TokenSequence;
import base.CachedKernel;

/**
 * Computes a similarity metric between two strings, based on counts
 * of common subsequences of characters. See Lodhi et al "String
 * kernels for text classification." Optionally caches previous kernel
 * computations.
 * Source: Mallet
 */

public class SequenceKernel extends CachedKernel<TokenSequence>
{

	/**
	 * 
	 */
	private static final long serialVersionUID = -7073046738786009982L;

	// all words to lowercase
	static final boolean DEFAULT_NORMALIZE_CASE = true;
	// gap penalty
	static final double DEFAULT_LAMBDA = 0.5;
	// max length of subsequences to compare
	static final int DEFAULT_LENGTH = 6;
	// true if we should cache previous kernel
	// computations. Recommended!
	static final boolean DEFAULT_CACHE = true;

	boolean normalizeCase;
	double lambda;
	int n;
	boolean cache;

	/**
	 * @param norm
	 *            true if we lowercase all strings
	 * @param lam
	 *            0-1 penalty for gaps between matches.
	 * @param length
	 *            max length of subsequences to compare
	 * @param cache
	 *            true if we should cache previous kernel computations. recommended!
	 */
	public SequenceKernel(boolean norm, double lam, int length, boolean cache)
	{
		this.normalizeCase = norm;
		this.lambda = lam;
		this.n = length;
		this.cache = cache;
	}

	public SequenceKernel()
	{
		this(DEFAULT_NORMALIZE_CASE, DEFAULT_LAMBDA, DEFAULT_LENGTH, DEFAULT_CACHE);
	}

	public SequenceKernel(boolean norm, double lam, int length)
	{
		this(norm, lam, length, DEFAULT_CACHE);
	}

	/**
	 * Computes the normalized string kernel between two strings.
	 * 
	 * @param s
	 *            string 1
	 * @param t
	 *            string 2
	 * @return 0-1 value, where 1 is exact match.
	 */
	protected double K(TokenSequence s, TokenSequence t)
	{

		// compute self kernels if not in hashmap
		double ss, tt;
		ss = sK(s, s, n);
		tt = sK(t, t, n);
		double st = sK(s, t, n);
		// normalize
		double bla = st / Math.sqrt(ss * tt);
		return bla + 1;
	}

	private double sK(TokenSequence s, TokenSequence t, int n)
	{
		double sum, r = 0.0;
		int i, j, k;
		int slen = s.tokens.length;
		int tlen = t.tokens.length;

		double[][] K = new double[n + 1][(slen + 1) * (tlen + 1)];

		for (j = 0; j < (slen + 1); j++)
			for (k = 0; k < (tlen + 1); k++)
				K[0][k * (slen + 1) + j] = 1;

		for (i = 0; i < n; i++)
		{
			for (j = 0; j < slen; j++)
			{
				sum = 0.0;
				for (k = 0; k < tlen; k++)
				{
					if (t.tokens[k].equals(s.tokens[j]))
					{
						sum += K[i][k * (slen + 1) + j];
					}
					if (t.lemmas[k].equals(s.lemmas[j]))
					{
						sum += K[i][k * (slen + 1) + j];
					}
					if (t.posTag[k].equals(s.posTag[j]))
					{
						sum += K[i][k * (slen + 1) + j];
					}
					if (t.posTag2[k].equals(s.posTag2[j]))
					{
						sum += K[i][k * (slen + 1) + j];
					}
					if (t.tokens[k].equals(s.tokens[j]) && t.posTag2[k].equals(s.posTag2[j]))
					{
						sum += K[i][k * (slen + 1) + j];
					}
					K[i + 1][(k + 1) * (slen + 1) + j + 1] = K[i + 1][(k + 1) * (slen + 1) + j] + sum;
				}
			}
			r = r + K[i + 1][tlen * (slen + 1) + slen];
		}
		return r;
	}

	public static void main(String[] args)
	{
		SequenceKernel sequenceKernel = new SequenceKernel();
		sequenceKernel.initKernelCache(4);
		TokenSequence t = new TokenSequence(0);
		TokenSequence s = new TokenSequence(1);
		s.tokens[1] = "hallo";
		s.lemmas[1] = "hallo";
		s.posTag[1] = "NOUN";
		s.posTag2[1] = "NOUN";
		System.out.println(sequenceKernel.k(t, s));
	}

}
