public class MySqlDB
{
	//String url, usr, passwd;
	Connection con=null;
	Statement st=null;

	public MySqlDB(String url, String user, String passwd) {
		try {
			Class.forName("com.mysql.jdbc.Driver").newInstance();
		}
		catch (Exception E) {
			System.err.println("Unable to load driver.");
			E.printStackTrace();
			System.exit(1);
		}
		try {
			Connection con2 = DriverManager.getConnection(url, user, passwd);
			//System.out.println(url+" "+user+" "+passwd);
			con = con2;
		}
		catch (SQLException E) {
			System.out.println("SQLException: " + E.getMessage());
			System.out.println("SQLState:     " + E.getSQLState());
			System.out.println("VendorError:  " + E.getErrorCode());
			E.printStackTrace();
			con=null;
			System.exit(1);
		}



	}

	public ResultSet executeQuery(String query) throws java.lang.Exception {
		return con.createStatement().executeQuery(query);
	}

	public DatabaseMetaData getMetaData() throws java.lang.Exception {
		return con.getMetaData();
	}

	public int executeUpdate(String query) throws java.lang.Exception {
		return con.createStatement().executeUpdate(query);
	}

	public PreparedStatement prepareStatement(String query)
		throws java.lang.Exception {
			return con.prepareStatement(query);
		}

	public void close() throws Exception {
		if(con != null)
			con.close();
	}
}  public class AccuracyMeasure {

	/**
	 *  Calculates precision at the recall levels 0.1, 0.2, ... ,.09 , 1 and
	 *  returns all these precision values in a ordered array where first element 
	 *  is the precision at the greatest recall-level less than than 0.1; second 
	 *  element is the precision at the greatest recall-level >= 0.1 and < 0.2 and so on .
	 * 
	 * @param orderedList 
	 * @param expectedRecords 
	 * @return double[] 
	 * 
	 */
	public static double[] elevenPointPreciosn(int[] orderedList, int expectedRecords){
		double[] precisionArray = {0,0,0,0,0,0,0,0,0,0,0};
		double[] allOnes = {1,1,1,1,1,1,1,1,1,1,1};
		if(expectedRecords <= 0){
			return allOnes;
		}else if(orderedList == null){
			return precisionArray;
		}else if(orderedList.length == 0){
			return precisionArray;
		}else{
			double currentPrecisionValue = 0.0;
			int lastUpdatedIndex = -1;
			int indexToUpdate = 0;
			int relevantRecordsTillNow = 0;
			int recordsTillNow = 0;
			for(int i: orderedList){
				recordsTillNow++;
				if(i==1){
					relevantRecordsTillNow++;
					indexToUpdate = (int) (relevantRecordsTillNow*10.0)/(expectedRecords);
					currentPrecisionValue = (relevantRecordsTillNow*1.0)/recordsTillNow;
					for(int k=lastUpdatedIndex+1; k< indexToUpdate; k++){
						precisionArray[k] = currentPrecisionValue;
					}
					precisionArray[indexToUpdate] = currentPrecisionValue;
					lastUpdatedIndex = indexToUpdate;
				}
			}
			return precisionArray;
		}
	}
	
	/**
	 * 
	 *  Calculates precision at the recall levels 0.1, 0.2, ... ,.09 , 1 and
	 *  returns all these precision values in a ordered array where first element 
	 *  is the precision at recall-level equal or greater than 0.1 and so on.
	 *  It just finds the expected number of relevant records (expectedRecords) 
	 *  and calls the function elevenPointPreciosn(orderedList, expectedRecords).
	 *  
	 * @param orderedList  
	 * @return double[] 
	 * 
	 */
	public static double[] elevenPointPreciosn(int[] orderedList){
		double[] precisionArray = {1,1,1,1,1,1,1,1,1,1,1};
		if(orderedList == null){
			return precisionArray;
		}else if(orderedList.length == 0){
			return precisionArray;
		}else{
			int expectedRecords = 0;
			for(int i: orderedList){
				if(i==1){
					expectedRecords++;
				}
			}
			return elevenPointPreciosn(orderedList, expectedRecords);
		}
	}

	/**
	 *  To find the precision at the positionK. If the argument positionK is 0, it returns 0.
	 *  if the list is empty, it returns 0. positionK = 1 means the first element of the orderedList.
	 * 
	 * @param orderedList
	 * @param positionK
	 * @return
	 */
	public static double precisionAtTopK(int[] orderedList, int positionK){
		double precision=0.0;
		int relevantRecords = 0;
		if((orderedList != null) && (orderedList.length > 0) && (positionK > 0)){
			int finalPosition = Math.min(positionK, orderedList.length);
			for(int i=0;i < finalPosition; i++){
				if(orderedList[i] == 1){
					relevantRecords++;
				}
			}
			return (relevantRecords*1.0)/positionK;
		}else{
			return precision;
		}
	}
	/**
	 * 
	 *  Calculates precision at each point a relevant record is found and then 
	 *  takes an average over all the precision values and return the average.
	 *  expectedRecord argument is just required for efficiency so that it can 
	 *  stop iterating over the array once it has found expectedRecords relevant
	 *  records.
	 *  
	 * @param orderedList 
	 * @param expectedRecords 
	 * @return double 
	 * 
	 */	
	public static double meanAveragePrecision(int[] orderedList, int expectedRecords){
		if(orderedList == null){
			return 0.0;
		}		
		double sumPrecision = 0.0;
		int relevantRecords = 0;
		int records=0;
		for(int i:orderedList){
			records++;
			if(i==1){
				relevantRecords++;
				sumPrecision += ( relevantRecords*1.0 )/records;
				if(relevantRecords >= expectedRecords){
					break;
				}
			}
		}
		if(relevantRecords > 0){
			return sumPrecision/expectedRecords;
		}else{
			return 0.0;
		}
	}

	/**
	 * 
	 *  Calculates precision at each point a relevant record is found and then 
	 *  takes an average over all the precision vlaues and return the average.
	 *  It just calls the function 
	 *  meanAveragePrecision(orderedList, orderedList.length).
	 *  
	 *  
	 * @param orderedList 
	 * @param expectedRecords 
	 * @return double 
	 * @see meanAveragePrecision(int[] orderedList)
	 * 
	 */		
	/* fix this to find exppectedRecords
	 * public static double meanAveragePrecision(int[] orderedList){
		if(orderedList == null){
			return 0.0;
		}
		return meanAveragePrecision(orderedList, orderedList.length);
	}
	*/
	/**
	 *  Finds the position (k) of the first occurrence of a relevant record 
	 *  and return (1/k) i.e. the reciprocal rank. if no relevant record 
	 *  occur then it returns 0.
	 * 
	 * @param orderedList
	 * @return double
	 * 
	 */
	public static double reciprocalRank(int[] orderedList){
		if(orderedList == null){
			return 0.0;
		}
		double rank = 0.0;
		int position =0;
		boolean relevantRecordFound=false;
		for(int i: orderedList){
			position++;
			if(i==1){
				relevantRecordFound=true;
				break;
			}
		}
		if(relevantRecordFound){
			rank = 1.0/position;
		}
		return rank;
	}
	
	/**
	 * 
	 * To print the integer array.
	 * 
	 * @param list
	 * 
	 */
	public static void printList(int[] list){
		System.out.print("[");
		if(list != null){
			for(int i: list){
				System.out.print(i+", ");
			}
		}
		System.out.println("]");
	}
	
	/**
	 * 
	 * To print the double array.
	 * 
	 * @param list
	 * 
	 */
	public static void printList(double[] list){
		System.out.print("[");
		if(list != null){
			for(double i: list){
				System.out.print(i+", ");
			}
		}
		System.out.println("]");
	}
	
	/*
	 *  Just to check the implementation of the above functions.
	*/ 
	public static void main(String[] args){
		int myList1[] = {1,0,1,0,1,1,1,1,1,0,1,1,1};
		int[] myList2 = {0,0,1,0};
		double rank=0.0, map=0.0, precitionAtTopK=0.0;
		double[] elevenPtPrecision = null;
		System.out.print("Ordered List:  ");
		AccuracyMeasure.printList(myList1);
		rank = AccuracyMeasure.reciprocalRank(myList1);
		System.out.println("Reciprocal Rank: "+rank);
		//map = AccuracyMeasure.meanAveragePrecision(myList1);
		System.out.println("MAP: "+map);
		elevenPtPrecision = AccuracyMeasure.elevenPointPreciosn(myList1);
		AccuracyMeasure.printList(elevenPtPrecision);
		for(int j=0; j< myList1.length; j++){
			precitionAtTopK = AccuracyMeasure.precisionAtTopK(myList1, j+1);
			System.out.println("Precision at Top "+(j+1)+" : "+precitionAtTopK);
		}
		
		System.out.println();
		
		System.out.print("Ordered List:  ");
		AccuracyMeasure.printList(myList2);
		rank = AccuracyMeasure.reciprocalRank(myList2);
		System.out.println("Reciprocal Rank: "+rank);
		//map = AccuracyMeasure.meanAveragePrecision(myList2);
		System.out.println("MAP: "+map);
		elevenPtPrecision = AccuracyMeasure.elevenPointPreciosn(myList2);
		AccuracyMeasure.printList(elevenPtPrecision);
	}
	
} public class ApproximateGES extends Preprocess {

	public static double insertionCost = 0.5;

	public String similarityMetric = "editdistance";

	public static boolean localDebugMode = true;
	
	public void printDebug(String str){
	//	if(localDebugMode)
	//		System.out.print(str);
	}
	
	// Tokenizer based on whitespace; every token is a word
	// Its not required for Edit-Distance metric
	public HashMap<String, Double> getTF(String str) {
		tokenizeUsingQgrams = false;
		return getTokenTFMultiple(str);
	}

	public Vector<String> getTokenVector(String str) {
		// Generalized edit distance considers word based tokens at the first
		// level
		Vector<String> tokenVector = new Vector<String>();
		String[] tokens = str.toLowerCase().split(" ");
		for (int i = 0; i < tokens.length; i++) {
			tokenVector.add(tokens[i]);
		}
		return tokenVector;
	}
	
	public void preprocessTable(Vector<String> records, HashMap<String, Double> qgramIDF,
			Vector<HashMap<String, Double>> recordTokenWeights, String tableName) {
		Config config = new Config();
		MySqlDB mysqlDB = new MySqlDB(config.returnURL(), config.user, config.passwd);
		int numberOfRecords = 0, k = 0;
		try {
			String query = "select tid, " + config.preprocessingColumn + " from " + config.dbName + "." + tableName
					+ " order by tid asc";
			ResultSet rs = mysqlDB.executeQuery(query);
			if (rs != null) {
				while (rs.next()) {
					String str = rs.getString(config.preprocessingColumn);
					k = rs.getInt("tid");
					str=str.toLowerCase();
					if ((str != null) && (!str.equals(""))) {
						records.insertElementAt(str, k - 1);
						// Find the tf's of all the qgrams
						getDFandTFweight(k - 1, str, qgramIDF, recordTokenWeights);
					}
					numberOfRecords++;
				}
			}
			mysqlDB.close();
		} catch (Exception e) {
			System.out.println("database error: cannot read table");
			e.printStackTrace();
		}
		if (logToDB) {
			storePreprocessedDataToDB(tableName, recordTokenWeights, extractMetricName(this.getClass().getName())
					+ "_tf");
		}
		// convert the df into IDF
		convertDFtoIDF(qgramIDF, numberOfRecords, recordTokenWeights);
		if (logToDB) {
			storePreprocessedIDF(tableName, qgramIDF, extractMetricName(this.getClass().getName()) + "_idf");
		}
		// Now convert the tf in fileQrmanWeight to tfidf weights
		/*
		 * convertTFtoWeights(records, qgramIDF, recordTokenWeights); if
		 * (logToDB) { storePreprocessedDataToDB(tableName, recordTokenWeights,
		 * extractMetricName(this.getClass().getName()) + "_wt"); }
		 */
	}

	// This function is for the metrics which has to go iteratively through all
	// the records to get the final scoreList
	public List<IdScore> getSimilarRecords(String query, HashMap<String, Double> qgramIDF,
			Vector<HashMap<String, Double>> recordTokenWeights, Vector<String> recordVector) {
		List<IdScore> scoreList = new ArrayList<IdScore>();
		//t1 = System.currentTimeMillis();
		//initializeTokenTokenEDMap(query, qgramIDF);
		//t2 = System.currentTimeMillis();
		//System.out.println("intialization time: "+(t2-t1));
		double meanIDF = 0;
		for (double idf : qgramIDF.values()) {
			meanIDF += idf;
		}
		meanIDF = meanIDF / qgramIDF.size();
		// System.out.println("meanIDF: "+meanIDF);
		// find the weighted sum for the tokens in query

		for (int k = 0; k < recordVector.size(); k++) {
			
			
			if(recordVector.get(k).toLowerCase().contains("union")){
				localDebugMode = true;
			}else{
				localDebugMode = false;
			}
			printDebug("QUERY: "+query+"   RECORD: "+(k+1) + "=====================================\n");
			
			// find meanIDF value
			double score = generalizedEditSimilarity(query, recordVector.get(k), qgramIDF, meanIDF);
			
			if(score > 0.5){
				localDebugMode = true;
			}
			printDebug("QUERY: "+query+"   RECORD: "+(k+1) + "=====================================\n");
			printDebug("final Score: "+score+"\n");
			printDebug("===========================================================================\n");
			// for similar records score must be greater than zero
			if (score > 0) {
				scoreList.add(new IdScore(k, score));
			}
		}
		// // System.gc();
		Collections.sort(scoreList);
		//t3 = System.currentTimeMillis();
		//System.out.println("Query time: "+(t3-t1));
		return scoreList;
	}

	public double generalizedEditSimilarity(String s, String t, HashMap<String, Double> qgramIDF, double meanIDF) {
		Vector<String> queryVector = getTokenVector(s);
		Vector<String> recordVector = getTokenVector(t);
		double queryTokenWeightSum=0, tokenweight=0, score = 0, scoreContribution=0;
		for(int i=0; i < queryVector.size(); i++){
			tokenweight = getIDFWeight(queryVector.get(i), qgramIDF, meanIDF);
			queryTokenWeightSum += tokenweight;
			printDebug(queryVector.get(i)+" : "+tokenweight+" \n");
			scoreContribution = getMaxAdjustedJaccardScore(queryVector.get(i), recordVector);
			score += scoreContribution* tokenweight;
			printDebug(queryVector.get(i)+" "+qgramIDF.get(queryVector.get(i))+" :: ");
			printDebug(" ::  adjustedJaccardScore "+ scoreContribution +"\n");
		}
		return score/ queryTokenWeightSum;
	}

	public double getMaxAdjustedJaccardScore(String token, Vector<String> recordVector){
		double maxScore=0, curScore=0;
		String maxSimilarToken = "";
		for(String tok: recordVector){
			curScore = getJaccardScore(token, tok);
			printDebug(tok+" "+curScore+" :: ");
			if(curScore>maxScore){
				maxScore = curScore;
				maxSimilarToken = tok;
			}
		}
		printDebug("\nMaxSimilar  "+maxSimilarToken+" "+maxScore+" :: \n");
		return ( (maxScore*2.0/qgramSize) + (1 - 1.0/qgramSize) );
	}
	
	public double getJaccardScore(String tok1, String tok2){
		HashSet<String> tokenSet1 = generateQgrams(tok1);
		HashSet<String> tokenSet2 = generateQgrams(tok2);
		int intersect=0;
		for(String tok: tokenSet1){
			if(tokenSet2.contains(tok)){
				intersect++;
			}
		}
		int denominator = tokenSet1.size() + tokenSet2.size() - intersect;
		if(denominator > 0)
			return intersect*1.0/denominator;
		else
			return 0;
	}
	
	public HashSet<String> generateQgrams(String str){
		HashSet<String> qgramSet = new HashSet<String>();
		str = str.toLowerCase();
		for (int i = 0; i <= str.length() - qgramSize; i++) {
			String qgram = str.substring(i, i + qgramSize);
			qgramSet.add(qgram);
		}
		return qgramSet;
	}

	public double getIDFWeight(String token, HashMap<String, Double> qgramIDF, double meanIDF) {
		if (qgramIDF.containsKey(token)) {
			return qgramIDF.get(token);
		} else {
			return meanIDF;
		}
	}

	public void printTokenIDFs(Vector<String> tokenVector, HashMap<String, Double> qgramIDF, double meanIDF) {
		for (String token : tokenVector) {
			System.out.print(token + ": " + getIDFWeight(token, qgramIDF, meanIDF) + "  ");
		}
		System.out.println();
	}

} public class BM25 extends Preprocess {

	static double k1 = 1.5, b = 0.675, k3 = 8;

	// Tokenizer based on whitespace; evry token is a word
	public HashMap<String, Double> getTF(String str) {
	//	System.out.println("BM25-getTF::  ["+str+"] "+str.length());
		HashMap<String, Double> tokenTF = getTokenTFMultiple(str);
	//	System.out.println("BM25-getTF:: "+tokenTF+"\n"+ tokenTF.size() + " sum_tf:"+ getTotalTokens(tokenTF));
		return tokenTF;
	}

	public void convertDFtoIDF(HashMap<String, Double> qgramIDF, int size) {
		for (String qgram : qgramIDF.keySet()) {
			qgramIDF.put(qgram, Math.log((size - qgramIDF.get(qgram) + 0.5) / (qgramIDF.get(qgram) + 0.5)));
		}
	}

	public HashMap<String, Double> getWeights(HashMap<String, Double> tokenTF, HashMap<String, Double> qgramIDF,
			double averageLength) {
		double bm25Weight, recordLength = 0, normFactor;
		recordLength = getTotalTokens(tokenTF);
		normFactor = k1 * ((1 - b) + b * recordLength / averageLength);
		for (String qgram : tokenTF.keySet()) {
			if (qgramIDF.containsKey(qgram)) {
				bm25Weight = tokenTF.get(qgram);
				bm25Weight = (1 + k1) * bm25Weight / (normFactor + bm25Weight);
				tokenTF.put(qgram, bm25Weight * qgramIDF.get(qgram));
			}
		}
		return tokenTF;
	}

	public HashMap<String, Double> getQueryWeights(String str, HashMap<String, Double> qgramIDF) {
		HashMap<String, Double> tokenTF = getTF(str);
		double bm25Weight;
		for (String qgram : tokenTF.keySet()) {
			bm25Weight = tokenTF.get(qgram);
			bm25Weight = (1 + k3) * bm25Weight / (k3 + bm25Weight);
			tokenTF.put(qgram, bm25Weight);
		}
		return tokenTF;
	}
} public class EditDistance extends Preprocess {

	// Tokenizer based on whitespace; every token is a word
	// Its not required for Edit-Distance metric
	public HashMap<String, Double> getTF(String str) {
		return getTokenTFMultiple(str);
	}
	
	public void preprocessTable(Vector<String> records, HashMap<String, Double> qgramIDF,
			Vector<HashMap<String, Double>> recordTokenWeights, String tableName) {
		Config config = new Config();
		MySqlDB mysqlDB = new MySqlDB(config.returnURL(), config.user, config.passwd);
		int numberOfRecords = 0, k = 0;
		try {
			String query = "select tid, "+config.preprocessingColumn+" from " + config.dbName + "." + tableName + " order by tid asc";
			ResultSet rs = mysqlDB.executeQuery(query);
			if (rs != null) {
				while (rs.next()) {
					String str = rs.getString(config.preprocessingColumn);
					k = rs.getInt("tid");
					if ((str != null) && (!str.equals(""))) {
						records.insertElementAt(str, k - 1);
						// Find the tf's of all the qgrams
						//getDFandTFweight(k - 1, str, qgramIDF, recordTokenWeights);
					}
					numberOfRecords++;
				}
			}
			mysqlDB.close();
		} catch (Exception e) {
			System.out.println("database error: cannot read table");
			e.printStackTrace();
		}
	}

	// This function is for the metrics which has to go iteratively through all
	// the records to get the final scoreList
	public List<IdScore> getSimilarRecords(String query, HashMap<String, Double> qgramIDF,
			Vector<HashMap<String, Double>> recordTokenWeights, Vector<String> recordVector) {
		List<IdScore> scoreList = new ArrayList<IdScore>();
		//HashMap<String, Double> queryWeights = getQueryWeights(query, qgramIDF);
		for (int k = 0; k < recordVector.size(); k++) {
			double score = editSimilarity(query, recordVector.get(k));
			// for similar records score must be greater than zero
			
			//if(score > 0){
				scoreList.add(new IdScore(k, score));
			//}
		}
		// // System.gc();
		Collections.sort(scoreList);
		return scoreList;
	}

	// This function is for the metrics which has to go iteratively through all
	// the records to get the final scoreList
	public List<IdScore> getSimilarRecordsTH(String query, HashMap<String, Double> qgramIDF,
			Vector<HashMap<String, Double>> recordTokenWeights, Vector<String> recordVector, Double thr, int begin) {
		List<IdScore> scoreList = new ArrayList<IdScore>();
		//HashMap<String, Double> queryWeights = getQueryWeights(query, qgramIDF);
		for (int k = (begin-1); k < recordVector.size(); k++) {
		
		//for (int k = (begin-1); k < recordTokenWeights.size(); k++) {
			double score = editSimilarity(query, recordVector.get(k));
			//System.out.println(" GOOOOZ " + score);
			// for similar records score must be greater than zero
			
			if(score >= thr){
				scoreList.add(new IdScore(k, score));
			}
		}
		// // System.gc();
		Collections.sort(scoreList);
		return scoreList;
	}

	public double editSimilarity(String s, String t){
		//return 1.0 - normalizedEditDistance(s,t);
		/*
		 *  Taking just the negative of the EditDistance
		 *  Note that its not normalized
		 */
		
		return 1-normalizedEditDistance(s, t);
	}
	
	public double normalizedEditDistance(String s, String t) {
		int ed = LD(s,t);
		return ed*1.0/Math.max(s.length(), t.length());
	}
	/*
	 * The code below has been copied from
	 * http://www.merriampark.com/ld.htm#JAVA
	 */
	public static void print2DMatrix(int[][] matrix, String s, String t) {
		System.out.print("- - ");
		for(int i=0; i < t.length(); i++){
			System.out.print(t.charAt(i) + " ");
		}
		System.out.println();
		
		for (int i = 0; i < Math.min(matrix.length, s.length()+1); i++) {
			if(i==0){
				System.out.print("- ");
			}else{
				System.out.print(s.charAt(i-1) + " ");
			}
			for (int j = 0; j < matrix[i].length; j++) {
				System.out.print(matrix[i][j] + " ");
			}
			System.out.println();
		}
	}
	
	private static int Minimum(int a, int b, int c) {
		int mi;
		mi = a;
		if (b < mi) {
			mi = b;
		}
		if (c < mi) {
			mi = c;
		}
		return mi;
	}

	// *****************************
	// Compute Levenshtein distance
	// *****************************

	public static int LD(String s, String t) {
		int d[][]; // matrix
		int n; // length of s
		int m; // length of t
		int i; // iterates through s
		int j; // iterates through t
		char s_i; // ith character of s
		char t_j; // jth character of t
		int cost; // cost

		// Step 1
		n = s.length();
		m = t.length();
		if (n == 0) {
			return m;
		}
		if (m == 0) {
			return n;
		}
		d = new int[n + 1][m + 1];

		// Step 2
		for (i = 0; i <= n; i++) {
			d[i][0] = i;
		}
		for (j = 0; j <= m; j++) {
			d[0][j] = j;
		}
		// Step 3
		for (i = 1; i <= n; i++) {
			s_i = s.charAt(i - 1);
			
			// Step 4
			for (j = 1; j <= m; j++) {
				t_j = t.charAt(j - 1);

				// Step 5
				if (s_i == t_j) {
					cost = 0;
				} else {
					cost = 1;
				}

				// Step 6
				d[i][j] = Minimum(d[i - 1][j] + 1, d[i][j - 1] + 1, d[i - 1][j - 1] + cost);
			}
		}
		// For debug purpose
		//print2DMatrix(d, s, t);
		// Step 7
		return d[n][m];
	}
} public class EvaluateSJoinThread extends Thread{

	private String tablename;
	private String result_tablename;
	private Preprocess measure;
	private double thr = 0.8;
	
	public static int queryTokenLength = 2;
	
	public EvaluateSJoinThread(String inputtablename, Preprocess inputmeasure, double threshold, String resultTable){
		tablename = inputtablename;
		measure = inputmeasure;
		thr = threshold;
		result_tablename = resultTable;
	}

	public static Vector<Vector<Integer>> subsets(Vector<Integer> set, int size){
		Vector<Vector<Integer>> output = new Vector<Vector<Integer>>();
		
		if (size == 1) {
			for (Integer vi: set){
				Vector<Integer> v = new Vector<Integer>();
				v.add(vi);
				output.add(v);
			}
		}
		else {
			for (int i = 1; i <= set.size()-(size-1); i++){
				Vector<Integer> set2 = new Vector<Integer>();
				for (int j = i+1; j <= set.size(); j++) set2.add(set.elementAt(j-1));
				for (Vector<Integer> sset : subsets(set2, size-1)){
					Vector<Integer> v = new Vector<Integer>();
					v.add(set.elementAt(i-1));
					for (Integer vi:sset) v.add(vi);
					output.add(v);
				}
			}
		}

		return output;
	}
	
	public void findTrueClusters(String tablename, 
			                            HashMap<Integer,Integer> trueCluster,	
			                            HashMap<Integer,BitSet> trueMembers) {
		Config config = new Config();
		MySqlDB mysqlDB = new MySqlDB(config.returnURL(), config.user, config.passwd);
		String sql = "";
		try {
			sql = " SELECT c1.tid as tid1, c2.tid as tid2 FROM " + config.dbName +
			      "." + tablename + " c1," + config.dbName + "." + tablename + " c2" +
				  " where c1.id=c2.id ";
			ResultSet rs = mysqlDB.executeQuery(sql);

			
			//t4 = System.currentTimeMillis();
			//System.out.println("DEBUG INFO: " + (t4-t3) + "ms");
			//BitSet isThere = new BitSet(count); 
			BitSet isThere = new BitSet();
			int maxId = 0;
			
			rs.beforeFirst();
			while (rs.next()){
				//System.out.println(rs.getInt(1) + " " + rs.getInt(2));
				int tid1 = rs.getInt(1);
				int tid2 = rs.getInt(2);
				
				if (!isThere.get(tid1)) {
					if (!isThere.get(tid2)) {
						maxId++;
						trueCluster.put(tid1,maxId);
						trueCluster.put(tid2,maxId);
						
						BitSet mems = new BitSet();
						mems.set(tid1);
						mems.set(tid2);
						trueMembers.put(maxId, mems);
						
						isThere.set(tid1);
						isThere.set(tid2);
					}
					else {
						int cId = trueCluster.get(tid2);
						
						trueCluster.put(tid1, cId);
						
						BitSet mems = trueMembers.get(cId);
						mems.set(tid1);
						trueMembers.put(cId, mems);
						
						isThere.set(tid1);
					}
				}
				else {
					if (!isThere.get(tid2)) {
						int cId = trueCluster.get(tid1);
						
						trueCluster.put(tid2, cId);
												
						BitSet mems = trueMembers.get(cId);
						mems.set(tid2);
						trueMembers.put(cId, mems);
						
						isThere.set(tid2);
					}
				}
			}
			
			//System.out.println(trueCluster);
			//System.out.println(trueMembers);
			
			
		} catch (Exception e) {
			System.out.println("Database error"); e.printStackTrace();
		}

	}
	
	public static void findPairsWSign(String tablename, Preprocess measure, String pairTable){
		
		Config config = new Config();
		MySqlDB mysqlDB = new MySqlDB(config.returnURL(), config.user, config.passwd);
		
		long t2, t3;
		t2 = System.currentTimeMillis();
		boolean log_pairs_to_db = true;
		
		String sql = " SELECT s1.tid as tid1, s2.tid as tid2 " +
                     " FROM cnamesu.`sign` s1, cnamesu.`sign` s2 " +
                     " WHERE  s1.sign = s2.sign and s1.tid <= s2.tid " +
                     " GROUP BY tid1,tid2 ";
		
		try {
			
			if (log_pairs_to_db){
				String query = "drop table if exists " + config.dbName + "." + pairTable;
				mysqlDB.executeUpdate(query);
				
				query = "create table " + config.dbName + "." + pairTable +
				        " (tid1 int, tid2 int)";
				mysqlDB.executeUpdate(query);
				
				query = "INSERT INTO " + config.dbName + "." + pairTable +
				        "( " + sql + " )";
				mysqlDB.executeUpdate(query);
				
				t3 = System.currentTimeMillis();
				System.out.println("Similar Pairs Generation: " + (t3-t2) + "ms");
			}

		} catch (Exception e) {
			System.out.println("Database error"); e.printStackTrace();
		}
	}
	
	public void findPairs(String tablename, Preprocess measure, String pairTable, Double thr){
		
		Config config = new Config();
		MySqlDB mysqlDB = new MySqlDB(config.returnURL(), config.user, config.passwd);
		
		String scoreTable = "scores_" + tablename + "_" + Preprocess.extractMetricName(measure.getClass().getName());
		boolean log_pairs_to_db = true;
		long t2, t3;
		t2 = System.currentTimeMillis();
		
		
		String sql = " SELECT s.tid1 as tid1, s.tid2 as tid2 " +
                     " FROM " + scoreTable + " s " +
                     " WHERE  s.score >= " + thr ;
		
		try {
			
			if (log_pairs_to_db){
				String query = "drop table if exists " + config.dbName + "." + pairTable;
				mysqlDB.executeUpdate(query);
				
				query = "create table " + config.dbName + "." + pairTable +
				        " (tid1 int, tid2 int)";
				mysqlDB.executeUpdate(query);
				
				query = "INSERT INTO " + config.dbName + "." + pairTable +
				        "( " + sql + " )";
				mysqlDB.executeUpdate(query);
				
				t3 = System.currentTimeMillis();
				System.out.println("Similar Pairs Generation: " + (t3-t2) + "ms");
			}

		} catch (Exception e) {
			System.out.println("Database error"); e.printStackTrace();
		}
	}
	
	public void evaluateJoin(String tablename, String pairTable, Vector<Double> output){
		
		int pr = 0, re = 0, total = 0, totalr = 0;
		
		Config config = new Config();
		MySqlDB mysqlDB = new MySqlDB(config.returnURL(), config.user, config.passwd);
		ResultSet rs;
		
		HashMap<Integer, BitSet> truePairs = new HashMap<Integer, BitSet>();
		HashMap<Integer, BitSet> pairs = new HashMap<Integer, BitSet>();
		
		String sql = " SELECT c1.tid as tid1, c2.tid as tid2 FROM " 
			          + config.dbName + "." + tablename + " c1, " + config.dbName + "." + tablename + " c2 " +
				     " WHERE  c1.id = c2.id and c1.tid < c2.tid ";
		
		try {
			rs = mysqlDB.executeQuery(sql);
			
			while (rs.next()){
				
				int tid1 = rs.getInt(1);
				int tid2 = rs.getInt(2);
				BitSet b = new BitSet();				
				
				if (!(truePairs.keySet().contains(tid1))) {
					b.set(tid2);
					truePairs.put(tid1, b);
				}
				else {
					b.set(tid2);
					b.or(truePairs.get(tid1));
					truePairs.put(tid1, b);
				}
			}
			
			sql = " SELECT * FROM " + config.dbName + "." + pairTable +
			      " WHERE tid1 < tid2 ";
			rs = mysqlDB.executeQuery(sql);
			
			
			while (rs.next()){
				
				total++;
				int tid1 = rs.getInt(1);
				int tid2 = rs.getInt(2);
				BitSet b = new BitSet();

				//System.out.println(tid1 + "," + tid2);
				if ((truePairs.keySet().contains(tid1)))
				if (truePairs.get(tid1).get(tid2)){
					pr++;
				}
				
				if (!(pairs.keySet().contains(tid1))) {
					b.set(tid2);
					pairs.put(tid1, b);
				}
				else {
					b.set(tid2);
					b.or(pairs.get(tid1));
					pairs.put(tid1, b);
				}
				
			}
			
			for (Integer tid1:truePairs.keySet()){
				int tid2 = truePairs.get(tid1).nextSetBit(0);
				while (tid2 != -1){
					totalr ++;
					if ((pairs.keySet().contains(tid1)))
					if (pairs.get(tid1).get(tid2)){
							re++;
						}
					tid2 = truePairs.get(tid1).nextSetBit(tid2+1);
				}
			}

			
			
		} catch (Exception e) {
			System.out.println("Database error"); e.printStackTrace();
		}
		//System.out.println(pairs);
		
		double Precision = (total!=0) ? ((double)pr/(double)total) : 1;
		double Recall = (totalr!=0) ? ((double)re/(double)totalr) : 0;
		//System.out.println((double)pr);
		//System.out.println((double)total);
		//System.out.print(" Precision: "  + Precision);
		//System.out.println();
		//System.out.println((double)re);
		//System.out.println((double)totalr);
		//System.out.println(" Recall: "  + Recall );
		
		Double F1 = 0.0;
		if ((Precision!=0) && (Recall!=0)) F1 = (2*Precision*Recall / (Precision+Recall));
		//System.out.println(" F1: "  + F1 );
		output.add(Precision);
		output.add(Recall);
		output.add(F1);
		
	}
	
	public void findClusters(String pairTable, HashMap<Integer,Integer> cluster, 
                                    HashMap<Integer,BitSet> members){
		ResultSet rs;			
		
		Config config = new Config();
		MySqlDB mysqlDB = new MySqlDB(config.returnURL(), config.user, config.passwd);
		
		try {	
			/*
			 * 
			 * From output of similarity join, i.e., (tid1,tid2)'s 
			 * form clusters of related records
			 * 
			 */
			
			String sql = "SELECT * from " + config.dbName + "." + pairTable;
			
			rs = mysqlDB.executeQuery(sql);
			
			//t4 = System.currentTimeMillis();
			//System.out.println("DEBUG INFO: " + (t4-t3) + "ms");
			//BitSet isThere = new BitSet(count); 
			BitSet isThere = new BitSet();
			int maxId = 0;
			
			rs.beforeFirst();
			while (rs.next()){
				//System.out.println(rs.getInt(1) + " " + rs.getInt(2));
				int tid1 = rs.getInt(1);
				int tid2 = rs.getInt(2);
				
				if (!isThere.get(tid1)) {
					if (!isThere.get(tid2)) {
						maxId++;
						cluster.put(tid1,maxId);
						cluster.put(tid2,maxId);
						
						BitSet mems = new BitSet();
						mems.set(tid1);
						mems.set(tid2);
						members.put(maxId, mems);
						
						isThere.set(tid1);
						isThere.set(tid2);
					}
					else {
						int cId = cluster.get(tid2);
						
						cluster.put(tid1, cId);
						
						BitSet mems = members.get(cId);
						mems.set(tid1);
						members.put(cId, mems);
						
						isThere.set(tid1);
					}
				}
				else {
					if (!isThere.get(tid2)) {
						int cId = cluster.get(tid1);
						
						cluster.put(tid2, cId);
												
						BitSet mems = members.get(cId);
						mems.set(tid2);
						members.put(cId, mems);
						
						isThere.set(tid2);
					}
				}
			}
			
			//System.out.println(cluster);
			//System.out.println(members);
			
			
		} catch (Exception e) {
			System.out.println("Database error"); e.printStackTrace();
		}

	}
	
	public void run() {

		long t1, t2, t3, t4, t5, tf;
		t1 = System.currentTimeMillis();
		/*
		 * 
		 * Call Similarity Join
		 * 
		 * /
		
		t1 = System.currentTimeMillis();
		SimilarityJoin simjoin = new SimilarityJoin();
		simjoin.run(tablename, measure, 0.2);
		t2 = System.currentTimeMillis();
		System.out.println("Similarity Join: " + (t2-t1) + "ms");
		*/
		t2 = System.currentTimeMillis();
		
		System.out.println("Evaluating Join for: " + tablename + "," + Preprocess.extractMetricName(measure.getClass().getName()));
		
		String pairTable = "pairs_" + tablename + "_" + Preprocess.extractMetricName(measure.getClass().getName());
		findPairs(tablename, measure, pairTable, thr);
		t3 = System.currentTimeMillis();
		System.out.println("Finding Pairs took: " + (t3-t2) + "ms");

		/*		 Finding clusters from pairs:
		HashMap<Integer,Integer> cluster = new HashMap<Integer,Integer>();
		HashMap<Integer,BitSet> members = new HashMap<Integer,BitSet>();

		findClusters(pairTable, cluster, members);
		
		t4 = System.currentTimeMillis();
		System.out.println("Time for clustering: " + (t4-t1) + "ms");
		
		/*
		 * Evaluation of clustering - Precision and Recall
		 */
		
		/* Finding true clusters:
		HashMap<Integer,Integer> trueCluster = new HashMap<Integer,Integer>();
		HashMap<Integer,BitSet> trueMembers = new HashMap<Integer,BitSet>();
		findTrueClusters(tablename, trueCluster, trueMembers);
		
		evaluate(cluster, members, trueCluster, trueMembers);
		*/
		
		//System.out.println();
		//System.out.println();
		System.out.println("T/M/Thr: " + tablename + " / " + Preprocess.extractMetricName(measure.getClass().getName()) + " / " + thr);
		Vector<Double> output = new Vector<Double>();
		evaluateJoin(tablename, pairTable, output);
				
		System.out.print(" Precision: "  + output.get(0));
		System.out.println(" Recall: "  + output.get(1) );
		System.out.println(" F1: "  + output.get(2) );
		
		Config config = new Config();
		MySqlDB mysqlDB = new MySqlDB(config.returnURL(), config.user, config.passwd);
		//String resultTable = "sjoinresults";
		String resultTable = result_tablename;
		try {
			String query = "REPLACE INTO " + config.dbName + "." + resultTable 
					+ " VALUES ( \"" + tablename + "\", \""
					+ Preprocess.extractMetricName(measure.getClass().getName())
					+ "\" , " + thr + " , " +  output.get(0) + " , " +  output.get(1)
					+ " , " + output.get(2) +  " )";
			//System.out.println(query);
			mysqlDB.executeUpdate(query);
			
			mysqlDB.close();
		} catch (Exception e) {
			System.err.println("DB Error");
			e.printStackTrace();
		}

		
		//tf = System.currentTimeMillis();
		//System.out.println("Total Time: " + (tf-t1) + "ms");
		//System.err.println();
		
	}

} public class GeneralizedEditSimilarity extends Preprocess {

	public static double insertionCost = 0.5;

	public String similarityMetric = "editdistance";

	public static HashMap<String, HashMap<String, Double>> tokenStokenTEDst=null;
	
	// Tokenizer based on whitespace; every token is a word
	// Its not required for Edit-Distance metric
	public HashMap<String, Double> getTF(String str) {
		tokenizeUsingQgrams = false;
		return getTokenTFMultiple(str);
	}

	public Vector<String> getTokenVector(String str) {
		// Generalized edit distance considers word based tokens at the first
		// level
		Vector<String> tokenVector = new Vector<String>();
		String[] tokens = str.toLowerCase().split(" ");
		for (int i = 0; i < tokens.length; i++) {
			tokenVector.add(tokens[i]);
		}
		return tokenVector;
	}

	//This stores the normalized ed for querytokens with all other tokens
	public static void initializeTokenTokenEDMap(String query, HashMap<String, Double> qgramIDF){
		tokenStokenTEDst = new HashMap<String, HashMap<String, Double>>();
		String[] tokens = query.toLowerCase().split(" ");
		for(int i=0; i < tokens.length; i++){
			HashMap<String, Double> tokenEDMap = new HashMap<String, Double>();
			for(String token: qgramIDF.keySet()){
				tokenEDMap.put(token, normalizedEditDistance(tokens[i], token));
			}
			tokenStokenTEDst.put(tokens[i], tokenEDMap);
		}
	}
	
	public double getNormalizedEditDistanceFromEDMap(String s, String t){
		double ed =0;
		try{
			ed = tokenStokenTEDst.get(s).get(t);
		}catch (Exception e) {
			System.err.println("The ED MAP does not contain entry for "+s+" and "+t);
			// TODO: handle exception
			ed = normalizedEditDistance(s, t);
		}
		return ed; 
	}
	
	public void preprocessTable(Vector<String> records, HashMap<String, Double> qgramIDF,
			Vector<HashMap<String, Double>> recordTokenWeights, String tableName) {
		Config config = new Config();
		MySqlDB mysqlDB = new MySqlDB(config.returnURL(), config.user, config.passwd);
		int numberOfRecords = 0, k = 0;
		try {
			String query = "select tid, " + config.preprocessingColumn + " from " + config.dbName + "." + tableName
					+ " order by tid asc";
			ResultSet rs = mysqlDB.executeQuery(query);
			if (rs != null) {
				while (rs.next()) {
					String str = rs.getString(config.preprocessingColumn);
					k = rs.getInt("tid");
					str=str.toLowerCase();
					if ((str != null) && (!str.equals(""))) {
						records.insertElementAt(str, k - 1);
						// Find the tf's of all the qgrams
						getDFandTFweight(k - 1, str, qgramIDF, recordTokenWeights);
					}
					numberOfRecords++;
				}
			}
			mysqlDB.close();
		} catch (Exception e) {
			System.out.println("database error: cannot read table");
			e.printStackTrace();
		}
		if (logToDB) {
			storePreprocessedDataToDB(tableName, recordTokenWeights, extractMetricName(this.getClass().getName())
					+ "_tf");
		}
		// convert the df into IDF
		convertDFtoIDF(qgramIDF, numberOfRecords, recordTokenWeights);
		if (logToDB) {
			storePreprocessedIDF(tableName, qgramIDF, extractMetricName(this.getClass().getName()) + "_idf");
		}
		// Now convert the tf in fileQrmanWeight to tfidf weights
		/*
		 * convertTFtoWeights(records, qgramIDF, recordTokenWeights); if
		 * (logToDB) { storePreprocessedDataToDB(tableName, recordTokenWeights,
		 * extractMetricName(this.getClass().getName()) + "_wt"); }
		 */
	}

	// This function is for the metrics which has to go iteratively through all
	// the records to get the final scoreList
	public List<IdScore> getSimilarRecords(String query, HashMap<String, Double> qgramIDF,
			Vector<HashMap<String, Double>> recordTokenWeights, Vector<String> recordVector) {
		List<IdScore> scoreList = new ArrayList<IdScore>();
		//t1 = System.currentTimeMillis();
		initializeTokenTokenEDMap(query, qgramIDF);
		//t2 = System.currentTimeMillis();
		//System.out.println("intialization time: "+(t2-t1));
		double meanIDF = 0;
		for (double idf : qgramIDF.values()) {
			meanIDF += idf;
		}
		meanIDF = meanIDF / qgramIDF.size();
		// System.out.println("meanIDF: "+meanIDF);
		// find the weighted sum for the tokens in query
		Vector<String> inputTokenVector = getTokenVector(query);
		Vector<Double> weightedTokenVector = incrementalWeightedSumVector(inputTokenVector, qgramIDF, meanIDF);
	
		for (int k = 0; k < recordVector.size(); k++) {
			// find meanIDF value		
			double score = generalizedEditSimilarity(query, recordVector.get(k), qgramIDF, meanIDF, weightedTokenVector);
			// for similar records score must be greater than zero
			if (score > 0) {
				scoreList.add(new IdScore(k, score));
			}
		}
		// // System.gc();
		Collections.sort(scoreList);
		//t3 = System.currentTimeMillis();
		//System.out.println("Query time: "+(t3-t1));
		return scoreList;
	}

	public double generalizedEditSimilarity(String s, String t, HashMap<String, Double> qgramIDF, double meanIDF,
			Vector<Double> weightedTokenVector) {
		int weightVectorSize = weightedTokenVector.size();
		if ((weightVectorSize <= 1) || (weightedTokenVector.get(weightVectorSize - 1) <= 0)) {
			return 0;
		} else {
			double transformationCost = weightedLD(s, t, qgramIDF, meanIDF, weightedTokenVector);
			
			return 1.0 - Math.min(1, transformationCost / weightedTokenVector.get(weightVectorSize - 1));
		}
	}

	public double weightedSumTokens(Vector<String> tokenVector, HashMap<String, Double> qgramIDF, double meanIDF) {
		double weightedTokenVectorSum = 0;
		for (String token : tokenVector) {
			if (qgramIDF.containsKey(token)) {
				weightedTokenVectorSum += qgramIDF.get(token);
			} else {
				weightedTokenVectorSum += meanIDF;
			}
		}
		return weightedTokenVectorSum;
	}

	// it returns the vector "v" such that v(i) = \sum_{0 <= j < i} weight(u(j))
	// where u is the vector of tokens
	public Vector<Double> incrementalWeightedSumVector(Vector<String> tokenVector, HashMap<String, Double> qgramIDF,
			double meanIDF) {
		Vector<Double> incrementalTokenWeightSumVector = new Vector<Double>();
		double weightedTokenVectorSum = 0;
		incrementalTokenWeightSumVector.add(0.0);
		for (int i = 0; i < tokenVector.size(); i++) {
			String token = tokenVector.get(i);
			weightedTokenVectorSum += getIDFWeight(token, qgramIDF, meanIDF);
			incrementalTokenWeightSumVector.add(weightedTokenVectorSum);
		}
		return incrementalTokenWeightSumVector;
	}

	public double getIDFWeight(String token, HashMap<String, Double> qgramIDF, double meanIDF) {
		if (qgramIDF.containsKey(token)) {
			return qgramIDF.get(token);
		} else {
			return meanIDF;
		}

	}

	public double weightedLD(String s, String t, HashMap<String, Double> qgramIDF, double meanIDF,
			Vector<Double> weightedTokenVector) {
		Vector<String> inputTokenVector = getTokenVector(s);
		Vector<String> tupleTokenVector = getTokenVector(t);
		Vector<Double> tupleTokenIncrementalWeightedSum = incrementalWeightedSumVector(tupleTokenVector, qgramIDF,
				meanIDF);
		double d[][];
		double ed[][];
		double track[][];
		int n, m, i, j;
		String tok_i, tok_j;
		double cost = 0, wt_i, wt_j;
		// Step 1
		n = inputTokenVector.size();
		m = tupleTokenVector.size();

		if (n == 0) {
			return insertionCost * tupleTokenIncrementalWeightedSum.get(m);
		}
		if (m == 0) {
			return weightedTokenVector.get(n);
		}
		d = new double[n + 1][m + 1];
		//FOR DEBUG PURPOSE
		ed = new double[n][m];
		track = new double[n][m];

		// Step 2
		for (i = 0; i <= n; i++) {
			d[i][0] = weightedTokenVector.get(i);
		}
		for (j = 0; j <= m; j++) {
			d[0][j] = insertionCost * tupleTokenIncrementalWeightedSum.get(j);
		}
		// Step 3
		for (i = 1; i <= n; i++) {
			tok_i = inputTokenVector.get(i - 1);
			wt_i = getIDFWeight(tok_i, qgramIDF, meanIDF);
			// Step 4
			for (j = 1; j <= m; j++) {
				tok_j = tupleTokenVector.get(j - 1);
				wt_j = getIDFWeight(tok_j, qgramIDF, meanIDF);
				ed[i - 1][j - 1] = normalizedEditDistance(tok_i, tok_j);
				cost = wt_i * ed[i - 1][j - 1];
				//cost = wt_i* normalizedEditDistance(tok_i, tok_j);
				//cost = wt_i*getNormalizedEditDistanceFromEDMap(tok_i, tok_j);
				// Step 6
				d[i][j] = Minimum(d[i - 1][j] + wt_i, d[i][j - 1] + insertionCost*wt_j, d[i - 1][j - 1] + cost);
				// to track the path FOR DEBUG PURPOSE
				
				track[i - 1][j - 1] = trackMinimum(d[i - 1][j] + wt_i, d[i][j - 1] + insertionCost*wt_j, d[i - 1][j - 1] + cost);
				
				if ((track[i - 1][j - 1] == 211) && (ed[i - 1][j - 1] == 0)) {
					track[i - 1][j - 1] = 200;
				}
				
			}
		}

		/*
		 * FOR DEBUGGING PURPOSE
		 */
		
		if (s.contains("union") && t.contains("union") && t.contains("elec")) {
			System.out.println("QUERY TOKENS");
			printTokenIDFs(inputTokenVector, qgramIDF, meanIDF);
			System.out.println("TUPLE TOKENS");
			printTokenIDFs(tupleTokenVector, qgramIDF, meanIDF);
			System.out.println("Edit Distance Metric");
			print2DMatrix(ed);
			System.out.println("GENERALIZED Edit Distance Metric");
			print2DMatrix(d);
			System.out.println("GENERALIZED Edit Distance TRACK Metric");
			print2DMatrix(track);
		}
		
		// Step 7
		return d[n][m];
	}

	public void printTokenIDFs(Vector<String> tokenVector, HashMap<String, Double> qgramIDF, double meanIDF) {
		for (String token : tokenVector) {
			System.out.print(token + ": " + getIDFWeight(token, qgramIDF, meanIDF) + "  ");
		}
		System.out.println();
	}

	public void print2DMatrix(double[][] matrix) {
		for (int i = 0; i < matrix.length; i++) {
			for (int j = 0; j < matrix[i].length; j++) {
				System.out.print(matrix[i][j] + " ");
			}
			System.out.println();
		}
	}

	private double trackMinimum(double a, double b, double c) {
		/*
		 * 211 fro diagonal, 210 for up, 201 for left
		 */
		double mi, mj;
		mi = a;
		mj = 210;
		if (b < mi) {
			mj = 201;
			mi = b;
		}
		if (c < mi) {
			mj = 211;
		}
		return mj;
	}

	/*
	 * The code below has been copied from
	 * http://www.merriampark.com/ld.htm#JAVA
	 */
	private double Minimum(double a, double b, double c) {
		double mi;
		mi = a;
		if (b < mi) {
			mi = b;
		}
		if (c < mi) {
			mi = c;
		}
		return mi;
	}

	public static double normalizedEditDistance(String s, String t) {
		int ed = LD(s, t);
		return ed * 1.0 / Math.max(s.length(), t.length());
	}

	private static int Minimum(int a, int b, int c) {
		int mi;
		mi = a;
		if (b < mi) {
			mi = b;
		}
		if (c < mi) {
			mi = c;
		}
		return mi;
	}

	// *****************************
	// Compute Levenshtein distance
	// *****************************

	public static int LD(String s, String t) {
		int d[][]; // matrix
		int n; // length of s
		int m; // length of t
		int i; // iterates through s
		int j; // iterates through t
		char s_i; // ith character of s
		char t_j; // jth character of t
		int cost; // cost

		// Step 1
		n = s.length();
		m = t.length();
		if (n == 0) {
			return m;
		}
		if (m == 0) {
			return n;
		}
		d = new int[n + 1][m + 1];

		// Step 2
		for (i = 0; i <= n; i++) {
			d[i][0] = i;
		}
		for (j = 0; j <= m; j++) {
			d[0][j] = j;
		}
		// Step 3
		for (i = 1; i <= n; i++) {
			s_i = s.charAt(i - 1);

			// Step 4
			for (j = 1; j <= m; j++) {
				t_j = t.charAt(j - 1);

				// Step 5
				if (s_i == t_j) {
					cost = 0;
				} else {
					cost = 1;
				}

				// Step 6
				d[i][j] = Minimum(d[i - 1][j] + 1, d[i][j - 1] + 1, d[i - 1][j - 1] + cost);
			}
		}

		// Step 7
		return d[n][m];
	}
} public class HMM extends Preprocess {

	private static double a0 = 0.8;

	private static double a1 = 0.2;

	public HashMap<String, Double> getTF(String str) {
		return getTokenTFMultiple(str);
	}

	public void incrementDFCount(String qgram, HashMap<String, Double> tokenCount, double qgramTF) {
		if (tokenCount.containsKey(qgram)) {
			tokenCount.put(qgram, tokenCount.get(qgram) + qgramTF);
		} else {
			tokenCount.put(qgram, qgramTF);
		}
	}

	public void convertDFtoIDF(HashMap<String, Double> qgramIDF, int size) {
		double numTokens = 0;
		for (String qgram : qgramIDF.keySet()) {
			numTokens += qgramIDF.get(qgram);
		}
		for (String qgram : qgramIDF.keySet()) {
			qgramIDF.put(qgram, qgramIDF.get(qgram) / numTokens);
		}
	}

	public HashMap<String, Double> getWeights(HashMap<String, Double> tokenTF, HashMap<String, Double> qgramIDF) {
		double sum = 0;
		double weight=0;
		for (String qgram : tokenTF.keySet()) {
			sum += tokenTF.get(qgram);
		}
		for (String qgram : tokenTF.keySet()) {
			weight = ( a1 * tokenTF.get(qgram) / sum )/( a0 * qgramIDF.get(qgram));
			tokenTF.put(qgram, Math.log( 1 +  weight ) );
		}
		return tokenTF;
	}

	public HashMap<String, Double> getQueryWeights(String str, HashMap<String, Double> qgramIDF) {
		HashMap<String, Double> tokenTF = getTF(str);
		for (String qgram : tokenTF.keySet()) {
			tokenTF.put(qgram, 1.0);
		}
		return tokenTF;
	}

	public static void main(String[] args) {
		double[] mapArray;
		int maxQueries = 100;
		HMM hmm = new HMM();
		long t1, t4, t2, t3, prepTime = 0, queryTime = 0;
		Vector<String> files = new Vector<String>();
		Vector<HashMap<String, Double>> baseTableTokenWeights = new Vector<HashMap<String, Double>>();
		HashMap<String, Double> qgramIDF = new HashMap<String, Double>();

		t1 = System.currentTimeMillis();
		// Toggle this variable to log the preprocessing info to DB
		Preprocess.setLogToDB(false);
		hmm.preprocessTable(files, qgramIDF, baseTableTokenWeights, args[0]);
		t2 = System.currentTimeMillis();
		prepTime = t2 - t1;
		System.err.println("Preprocessing Done: took " + prepTime + " ms");

		// System.gc();
		// For each query, order the filenames by their jaccard score
		int i = 1;
		String query;
		t1 = System.currentTimeMillis();
		HashMap<Integer, String> queries = SimilarityMatch.testQueries();
		t2 = System.currentTimeMillis();
		System.err.println("Collected Random Queries: took " + (t2 - t1) + " ms");

		
		//If due to some reason we cant get maxQueries qeuries then readjust this number
		maxQueries = queries.size();

		mapArray = new double[maxQueries];
		for (int a = 0; a < maxQueries; a++) {
			mapArray[a] = 0;
		}

		Vector<String> queryVector = new Vector<String>();
		Vector<Integer> queryIdVector = new Vector<Integer>();
		String baseDir = "/home/oktie/dcp-workspace/log/res/" + args[0] + "/";
		File baseDirPath = new File(baseDir);
		baseDirPath.mkdirs();

		for (Integer queryId : queries.keySet()) {
			query = queries.get(queryId);
			HashSet<Integer> actualResult = SimilarityMatch.getAllTidsHavingId(queryId, args[1]);
			queryVector.add(query);
			queryIdVector.add(queryId);

			t3 = System.currentTimeMillis();
			// The tids in the scoreList is 1 less than the actual tid e.g.
			// tid=1 willl be having id=0 in IdScore object
			List<IdScore> scoreList = hmm.getSimilarRecords(query, qgramIDF, baseTableTokenWeights);
			SimilarityMatch.logOutput(baseDir + i + "." + hmm.getClass().getName() + ".txt", query, files, scoreList);
			t4 = System.currentTimeMillis();
			queryTime += (t4 - t3);
			// Compute Accuracy
			int[] booleanList = SimilarityMatch.generateBooleanList(actualResult, scoreList);
			double map = AccuracyMeasure.meanAveragePrecision(booleanList, actualResult.size());
			mapArray[i - 1] = map;
			// System.err.println("Query Time: " + (t4-t1));
			System.err.println("query: " + i + "  metric: " + hmm.getClass().getName() + "      MAP: " + map);

			System.err.println("DONE QUERY: " + i);
			i++;
		}

		System.err.println("\nQuery Time: " + queryTime + " ms     Preprocess Time : " + prepTime + " ms ");
	}

} public class Intersect extends Preprocess {

	double meanIDF=0;
	
	// Tokenizer based on whitespace; every token is a word
	// Its not required for Edit-Distance metric
	public HashMap<String, Double> getTF(String str) {
		return gettokenTFSingle(str);
	}
	
	public void getDFandTFweight(int recordId, String str, HashMap<String, Double> qgramIDF,
			Vector<HashMap<String, Double>> recordTokenWeights) {
		HashMap<String, Double> tokenTF = getTF(str);
		//recordTokenWeights.insertElementAt(tokenTF, recordId);
		// Set df's
		for (String qgram : tokenTF.keySet()) {
			incrementDFCount(qgram, qgramIDF, tokenTF.get(qgram));
		}
	}
	
	public void preprocessTable(Vector<String> records, HashMap<String, Double> qgramIDF,
			Vector<HashMap<String, Double>> recordTokenWeights, String tableName) {
		Config config = new Config();
		MySqlDB mysqlDB = new MySqlDB(config.returnURL(), config.user, config.passwd);
		int numberOfRecords = 0, k = 0;
		try {
			String query = "select tid, "+config.preprocessingColumn+" from " + config.dbName + "." + tableName + " order by tid asc";
			ResultSet rs = mysqlDB.executeQuery(query);
			if (rs != null) {
				while (rs.next()) {
					String str = rs.getString(config.preprocessingColumn);
					k = rs.getInt("tid");
					if ((str != null) && (!str.equals(""))) {
						records.insertElementAt(str, k - 1);
						// Find the tf's of all the qgrams
						//getDFandTFweight(k - 1, str, qgramIDF, recordTokenWeights);
					}
					numberOfRecords++;
				}
			}
			mysqlDB.close();
		} catch (Exception e) {
			System.out.println("database error: cannot read table");
			e.printStackTrace();
		}
		//convert the Df to IDF
		//convertDFtoIDF(qgramIDF, numberOfRecords);
	}

	// This function is for the metrics which has to go iteratively through all
	// the records to get the final scoreList
	public List<IdScore> getSimilarRecords(String query, HashMap<String, Double> qgramIDF,
			Vector<HashMap<String, Double>> recordTokenWeights, Vector<String> recordVector) {
		List<IdScore> scoreList = new ArrayList<IdScore>();
		//HashMap<String, Double> queryWeights = getQueryWeights(query, qgramIDF);
		for (int k = 0; k < recordVector.size(); k++) {
			double score = intersectScore(query, recordVector.get(k));
			if(score > 0){
				scoreList.add(new IdScore(k, score));
			}
		}
		// // System.gc();
		Collections.sort(scoreList);
		return scoreList;
	}

	public double intersectScore(String s, String t){
		//System.out.println("wj called");
		double sizeS = 0;
		double intersectScore=0;
		Set<String> setS = gettokenTFSingle(s).keySet();
		sizeS = setS.size();
		//double weightedSumS = Util.getWeightedSumForTokenSet(setS, qgramIDF, meanIDF);
		Set<String> setT = gettokenTFSingle(t).keySet();
		
		Util.printlnDebug(setS);
		Util.printlnDebug(setT);
		//double weightedSumT = Util.getWeightedSumForTokenSet(setS, qgramIDF, meanIDF);
		setS.retainAll(setT);
		Util.printlnDebug(setS);
		//double weightedSumSandT = Util.getWeightedSumForTokenSet(setS, qgramIDF, meanIDF);
		if(setS.size() > 0){
			intersectScore = setS.size(); 
				//weightedSumSandT / (weightedSumS + weightedSumT - weightedSumSandT);
		}
		Util.printlnDebug("Intersect: "+intersectScore);
		Util.printlnDebug("Jaccard: "+( setS.size()/ (sizeS + setT.size() - setS.size())));
		return intersectScore;
	}
	
	
} public class Jaccard extends Preprocess {

	double meanIDF=0;
	
	// Tokenizer based on whitespace; every token is a word
	// Its not required for Edit-Distance metric
	public HashMap<String, Double> getTF(String str) {
		return gettokenTFSingle(str);
	}
	
	public void getDFandTFweight(int recordId, String str, HashMap<String, Double> qgramIDF,
			Vector<HashMap<String, Double>> recordTokenWeights) {
		HashMap<String, Double> tokenTF = getTF(str);
		//recordTokenWeights.insertElementAt(tokenTF, recordId);
		// Set df's
		for (String qgram : tokenTF.keySet()) {
			incrementDFCount(qgram, qgramIDF, tokenTF.get(qgram));
		}
	}
	
	public void preprocessTable(Vector<String> records, HashMap<String, Double> qgramIDF,
			Vector<HashMap<String, Double>> recordTokenWeights, String tableName) {
		Config config = new Config();
		MySqlDB mysqlDB = new MySqlDB(config.returnURL(), config.user, config.passwd);
		int numberOfRecords = 0, k = 0;
		try {
			String query = "select tid, "+config.preprocessingColumn+" from " + config.dbName + "." + tableName + " order by tid asc";
			ResultSet rs = mysqlDB.executeQuery(query);
			if (rs != null) {
				while (rs.next()) {
					String str = rs.getString(config.preprocessingColumn);
					k = rs.getInt("tid");
					if ((str != null) && (!str.equals(""))) {
						records.insertElementAt(str, k - 1);
						// Find the tf's of all the qgrams
						//getDFandTFweight(k - 1, str, qgramIDF, recordTokenWeights);
					}
					numberOfRecords++;
				}
			}
			mysqlDB.close();
		} catch (Exception e) {
			System.out.println("database error: cannot read table");
			e.printStackTrace();
		}
		//convert the Df to IDF
		//convertDFtoIDF(qgramIDF, numberOfRecords);
	}

	// This function is for the metrics which has to go iteratively through all
	// the records to get the final scoreList
	public List<IdScore> getSimilarRecords(String query, HashMap<String, Double> qgramIDF,
			Vector<HashMap<String, Double>> recordTokenWeights, Vector<String> recordVector) {
		List<IdScore> scoreList = new ArrayList<IdScore>();
		//HashMap<String, Double> queryWeights = getQueryWeights(query, qgramIDF);
		for (int k = 0; k < recordVector.size(); k++) {
			double score = jaccardScore(query, recordVector.get(k));
			if(score > 0){
				scoreList.add(new IdScore(k, score));
			}
		}
		// // System.gc();
		Collections.sort(scoreList);
		return scoreList;
	}
	
	// This function is for the metrics which has to go iteratively through all
	// the records to get the final scoreList
	public List<IdScore> getSimilarRecordsTH(String query, HashMap<String, Double> qgramIDF,
			Vector<HashMap<String, Double>> recordTokenWeights, Vector<String> recordVector,
			Double thr, int begin) {
		List<IdScore> scoreList = new ArrayList<IdScore>();
		//HashMap<String, Double> queryWeights = getQueryWeights(query, qgramIDF);
		for (int k = (begin-1); k < recordVector.size(); k++) {
			double score = jaccardScore(query, recordVector.get(k));
			if(score >= thr){
				scoreList.add(new IdScore(k, score));
			}
		}
		// // System.gc();
		Collections.sort(scoreList);
		return scoreList;
	}

	public double jaccardScore(String s, String t){
		//System.out.println("wj called");
		double sizeS = 0;
		double jaccardScore=0;
		Set<String> setS = gettokenTFSingle(s).keySet();
		sizeS = setS.size();
		//double weightedSumS = Util.getWeightedSumForTokenSet(setS, qgramIDF, meanIDF);
		Set<String> setT = gettokenTFSingle(t).keySet();
		
		Util.printlnDebug(setS);
		Util.printlnDebug(setT);
		//double weightedSumT = Util.getWeightedSumForTokenSet(setS, qgramIDF, meanIDF);
		setS.retainAll(setT);
		Util.printlnDebug(setS);
		//double weightedSumSandT = Util.getWeightedSumForTokenSet(setS, qgramIDF, meanIDF);
		if(setS.size() > 0){
			jaccardScore = setS.size()/( sizeS + setT.size() - setS.size()); 
				//weightedSumSandT / (weightedSumS + weightedSumT - weightedSumSandT);
		}
		Util.printlnDebug("Jaccard: "+jaccardScore);
		Util.printlnDebug("Intersect: "+setS.size() );
		return jaccardScore;
	}

	public IdScore getMaxSimilarRecord(String query, HashMap<String, Double> qgramIDF,
			HashMap<Integer,String> records, Double thr) {
		IdScore max = null;
		//double meanIDF = Util.getMeanIDF(qgramIDF);
		double maxscore = thr;
		for (int k:records.keySet()) {
			double score = jaccardScore(query, records.get(k));
			//System.out.println(score);
			if(score >= maxscore){
				max = new IdScore(k, score);
				maxscore = score;
			}
		}
		// // System.gc();
		
		//if (scoreList.size()!=0) max = Collections.max(scoreList);
		return max;
	}

	public void preprocessTable(HashMap<Integer,String> records, HashMap<String, Double> qgramIDF,
			Vector<HashMap<String, Double>> recordTokenWeights, String tableName) {
		Config config = new Config();
		MySqlDB mysqlDB = new MySqlDB(config.returnURL(), config.user, config.passwd);
		int numberOfRecords = 0, k = 0;
		try {
			String query = "select tid, "+config.preprocessingColumn+" from " + config.dbName + "." + tableName + " order by tid asc";
			ResultSet rs = mysqlDB.executeQuery(query);
			if (rs != null) {
				while (rs.next()) {
					String str = rs.getString(config.preprocessingColumn);
					k = rs.getInt("tid");
					if ((str != null) && (!str.equals(""))) {
						records.put(k, str);
						// Find the tf's of all the qgrams
						//getDFandTFweight(k - 1, str, qgramIDF, recordTokenWeights);
					}
					numberOfRecords++;
				}
				
			}
			mysqlDB.close();
		} catch (Exception e) {
			System.out.println("database error: cannot read table");
			e.printStackTrace();
		}
		//convert the Df to IDF
		convertDFtoIDF(qgramIDF, numberOfRecords);
		//System.out.println(qgramIDF);
		//recordTokenWeights.clear();
	}
	
	
} public class Preprocess {

	public static boolean logToDB = false;
	
	public boolean tokenizeUsingQgrams = true;
	
	public int qgramSize = 2;
	
	public static boolean debugModeOn = true;
	
	public static boolean replaceSpaceWithSpecialCharacter = true; 
	
	public static void setLogToDB(boolean logToDB) {
		Preprocess.logToDB = logToDB;
	}

	public static boolean logToDB() {
		return logToDB;
	}
	
	public boolean tokenizeUsingQgrams(){
		return tokenizeUsingQgrams;
	}
	
	public static String generateSpecialCharacters(int qgSize){
		String str="";
		for(int i=0; i < qgSize-1; i++){
			str += "#";
		}
		//System.out.println(str);
		return str;
	}
	
	public static String extractMetricName(String fullMetricName){
		String str[] = fullMetricName.toLowerCase().split("\\.");
		return str[str.length-1];
	}
	
	public void incrementCount(String qgram, HashMap<String, Double> tokenCount) {
		if (tokenCount.containsKey(qgram)) {
			tokenCount.put(qgram, tokenCount.get(qgram) + 1);
		} else {
			tokenCount.put(qgram, 1.0);
		}
	}

	public void incrementDFCount(String qgram, HashMap<String, Double> tokenCount, double qgramTF) {
		incrementCount(qgram, tokenCount);
	}

	// Tokenization function
	public HashMap<String, Double> getTF(String str) {
		HashMap<String, Double> tokenTF = new HashMap<String, Double>();
		/*
		 * String[] tokens = str.split("\\s+"); for (int i = 0; i <
		 * tokens.length; i++) { incrementCount(tokens[i], tokenTF); }
		 */
		str = str.toLowerCase();
		if(replaceSpaceWithSpecialCharacter){
			str = str.replaceAll(" ", generateSpecialCharacters(qgramSize));
			str = generateSpecialCharacters(qgramSize) + str + generateSpecialCharacters(qgramSize); 
		}
		for (int i = 0; i <= str.length() - qgramSize; i++) {
			String qgram = str.substring(i, i + qgramSize);
			incrementCount(qgram, tokenTF);
		}
		return tokenTF;
	}


	// Tokenizer based on whitespace; every token is a word
	public HashMap<String, Double> gettokenTFSingle(String str) {
		HashMap<String, Double> tokenTF = new HashMap<String, Double>();
		if (!tokenizeUsingQgrams ) {
			String[] tokens = str.toLowerCase().split(" ");
			for (int i = 0; i < tokens.length; i++) {
				// incrementCount(tokens[i], tokenTF);
				tokenTF.put(tokens[i], 1.0);
			}
		} else {
			str = str.toLowerCase();
			if(replaceSpaceWithSpecialCharacter){
				str = str.replaceAll(" ", generateSpecialCharacters(qgramSize));
				str = generateSpecialCharacters(qgramSize) + str + generateSpecialCharacters(qgramSize); 
			}
			for (int i = 0; i <= str.length() - qgramSize; i++) {
				String qgram = str.substring(i, i + qgramSize);
				tokenTF.put(qgram, 1.0);
			}
		}
		return tokenTF;
	}

	

	// Tokenizer based on whitespace; every token is a word
	public HashMap<String, Double> getTFWsign(String str, Long signature) {
		HashMap<String, Double> tokenTF = new HashMap<String, Double>();
		if (!tokenizeUsingQgrams ) {
			String[] tokens = str.toLowerCase().split(" ");
			for (int i = 0; i < tokens.length; i++) {
				// incrementCount(tokens[i], tokenTF);
				tokenTF.put(tokens[i], 1.0);
			}
		} else {
			str = str.toLowerCase();
			if(replaceSpaceWithSpecialCharacter){
				str = str.replaceAll(" ", generateSpecialCharacters(qgramSize));
				str = generateSpecialCharacters(qgramSize) + str + generateSpecialCharacters(qgramSize); 
			}
			for (int i = 0; i <= str.length() - qgramSize; i++) {
				String qgram = str.substring(i, i + qgramSize);
				tokenTF.put(qgram, 1.0);
			}
		}
		return tokenTF;
	}
	
	
	
	// Tokenizer based on whitespace; evry token is a word
	public HashMap<String, Double> getTokenTFMultiple(String str) {
		HashMap<String, Double> tokenTF = new HashMap<String, Double>();
		if (! tokenizeUsingQgrams) {
			String[] tokens = str.toLowerCase().split(" ");
			for (int i = 0; i < tokens.length; i++) {
				incrementCount(tokens[i], tokenTF);
			}
		} else {
			str = str.toLowerCase();
			if(replaceSpaceWithSpecialCharacter){
				str = str.replaceAll(" ", generateSpecialCharacters(qgramSize));
				str = generateSpecialCharacters(qgramSize) + str + generateSpecialCharacters(qgramSize); 
			}
			for (int i = 0; i <= str.length() - qgramSize; i++) {
				String qgram = str.substring(i, i + qgramSize);
				incrementCount(qgram, tokenTF);
			}
		}
		return tokenTF;
	}

	// Tokenizer based on conditional occurance; evry token is a word
	public HashMap<String, Double> getConditionalTF(String str) {
		HashMap<String, Double> tokenTF = new HashMap<String, Double>();
		if (! tokenizeUsingQgrams ) {
			String[] tokens = str.toLowerCase().split(" ");
			for (int i = 0; i < tokens.length; i++) {
				// incrementCount(tokens[i], tokenTF);
				int j=1;
				String modToken = tokens[i]+"_"+j;
				while(tokenTF.containsKey(modToken)){
					j++;
					modToken = tokens[i]+"_"+j;
				}
				tokenTF.put(modToken, 1.0);
			}
		} else {
			str = str.toLowerCase();
			if(replaceSpaceWithSpecialCharacter){
				str = str.replaceAll(" ", generateSpecialCharacters(qgramSize));
				str = generateSpecialCharacters(qgramSize) + str + generateSpecialCharacters(qgramSize); 
			}
			for (int i = 0; i <= str.length() - qgramSize; i++) {
				String qgram = str.substring(i, i + qgramSize);
				int j=1;
				String modToken = qgram+"_"+j;
				while(tokenTF.containsKey(modToken)){
					j++;
					modToken = qgram+"_"+j;
				}
				tokenTF.put(modToken, 1.0);
			}
		}
		return tokenTF;
	}

	// This is an implementation for tfidf weights
	public HashMap<String, Double> getWeights(HashMap<String, Double> tokenTF, HashMap<String, Double> qgramIDF) {
		double sum = 0, tfidf;
		for (String qgram : tokenTF.keySet()) {
			if (qgramIDF.containsKey(qgram)) {
				// This is a slight variant of TfIdf
				// w(u,C) = log(1 + tf)*idf
            /*
               Lets change this formula to w(u,c) = tf*idf , tf is raw tf
            */
				//tfidf =(1 + Math.log( tokenTF.get(qgram)) ) * qgramIDF.get(qgram);
				tfidf =  tokenTF.get(qgram) * qgramIDF.get(qgram);
				sum += tfidf * tfidf;
				tokenTF.put(qgram, tfidf);
			}
		}
		sum = Math.sqrt(sum);
		for (String qgram : tokenTF.keySet()) {
			tokenTF.put(qgram, tokenTF.get(qgram) / sum);
		}
		return tokenTF;
	}

	public HashMap<String, Double> getWeights(HashMap<String, Double> tokenTF, HashMap<String, Double> qgramIDF,
			double averageLength) {
		return getWeights(tokenTF, qgramIDF);
	}

	public HashMap<String, Double> getWeights(String str, HashMap<String, Double> qgramIDF) {
		return getWeights(getTF(str), qgramIDF);
	}

	public HashMap<String, Double> getQueryWeights(String str, HashMap<String, Double> qgramIDF) {
		return getWeights(getTF(str), qgramIDF);
	}

	public void convertDFtoIDF(HashMap<String, Double> qgramIDF, int size) {
		for (String qgram : qgramIDF.keySet()) {
         // changing idf to log(N/n)
			//qgramIDF.put(qgram, Math.log(1 + size / qgramIDF.get(qgram)));
			qgramIDF.put(qgram, Math.log( size / qgramIDF.get(qgram)));
		}
	}

	public void convertDFtoIDF(HashMap<String, Double> qgramIDF, int size, Vector<HashMap<String, Double>> recordTokenWeights) {
		convertDFtoIDF(qgramIDF, size);
	}

	
	public void getDFandTFweight(int recordId, String str, HashMap<String, Double> qgramIDF,
			Vector<HashMap<String, Double>> recordTokenWeights) {
		HashMap<String, Double> tokenTF = getTF(str);
		recordTokenWeights.insertElementAt(tokenTF, recordId);
		// Set df's
		for (String qgram : tokenTF.keySet()) {
			incrementDFCount(qgram, qgramIDF, tokenTF.get(qgram));
		}
	}

	public double getTotalTokens(HashMap<String, Double> tokenTf) {
		double totalTF = 0;
		for (String str : tokenTf.keySet()) {
			totalTF += tokenTf.get(str);
		}
		return totalTF;
	}

	public double getAverageRecordLength(Vector<HashMap<String, Double>> recordTokenWeights) {
		double aveLength = 0;
		for (int i = 0; i < recordTokenWeights.size(); i++) {
			HashMap<String, Double> tokenTf = recordTokenWeights.get(i);
			aveLength += getTotalTokens(tokenTf);
		}
		return aveLength/recordTokenWeights.size();
	}

	public void convertTFtoWeights(Vector<String> records, HashMap<String, Double> qgramIDF,
			Vector<HashMap<String, Double>> recordTokenWeights) {
		double averageLength = 0;
		averageLength = getAverageRecordLength(recordTokenWeights);
		//System.out.println(" avgDL: "+averageLength);
		for (int i = 0; i < records.size(); i++) {
			HashMap<String, Double> tokenTfidf = recordTokenWeights.get(i);
			tokenTfidf = getWeights(tokenTfidf, qgramIDF, averageLength);
			recordTokenWeights.setElementAt(tokenTfidf, i);
		}
	}

	public void preprocessTable(HashMap<Integer,String> records, HashMap<String, Double> qgramIDF,
			Vector<HashMap<String, Double>> recordTokenWeights, String tableName) {
	
	}

	public void preprocessTable(Vector<String> records, HashMap<String, Double> qgramIDF,
			Vector<HashMap<String, Double>> recordTokenWeights, String tableName) {
		Config config = new Config();
		MySqlDB mysqlDB = new MySqlDB(config.returnURL(), config.user, config.passwd);
		int numberOfRecords = 0, k = 0;
		try {
			String query = "select tid, "+config.preprocessingColumn+" from " + config.dbName + "." + tableName + " order by tid asc";
			ResultSet rs = mysqlDB.executeQuery(query);
			if (rs != null) {
				while (rs.next()) {
					String str = rs.getString(config.preprocessingColumn);
					k = rs.getInt("tid");
					if ((str != null) && (!str.equals(""))) {
						//System.out.println(k+":  ["+str+"]  :"+str.length() +"   {"+str.trim()+"} "+str.trim().length());
						//str = str.replaceAll("'", "''");
						str = str.toLowerCase();
						records.insertElementAt(str, k - 1);
						// Find the tf's of all the qgrams
						getDFandTFweight(k - 1, str, qgramIDF, recordTokenWeights);
					}
					numberOfRecords++;
				}
			}
			mysqlDB.close();
		} catch (Exception e) {
			System.out.println("database error: cannot read table");
			e.printStackTrace();
		}
		
		if(logToDB){
			storePreprocessedDataToDB(tableName, recordTokenWeights, extractMetricName(this.getClass().getName())+"_tf" );
		}
		// convert the df into IDF
		//System.out.println("N: " + numberOfRecords);
		convertDFtoIDF(qgramIDF, numberOfRecords, recordTokenWeights);
		if(logToDB){
			storePreprocessedIDF(tableName, qgramIDF, extractMetricName(this.getClass().getName())+"_idf" );
		}
		// Now convert the tf in fileQrmanWeight to tfidf weights
		convertTFtoWeights(records, qgramIDF, recordTokenWeights);
		if(logToDB){
			storePreprocessedDataToDB(tableName, recordTokenWeights, extractMetricName(this.getClass().getName())+"_wt" );
		}
		//System.exit(0);
	}

	public void preprocessTableWSign(Vector<String> records, HashMap<String, Double> qgramIDF,
			Vector<HashMap<String, Double>> recordTokenWeights, 
			HashMap<Integer, Long> signature, 
			Integer par1,
			Integer par2,
			Integer par3,
			String tableName) {
	}
	
	
	
	
	
	public List<IdScore> getSimilarRecords(String query, HashMap<String, Double> qgramIDF,
			Vector<HashMap<String, Double>> recordTokenWeights) {
		//query = query.replaceAll("'", "''");
		List<IdScore> scoreList = new ArrayList<IdScore>();
		HashMap<String, Double> queryWeights = getQueryWeights(query, qgramIDF);
		for (int k = 0; k < recordTokenWeights.size(); k++) {
			double score = 0;
			boolean haveCommonToken = false;
			HashMap<String, Double> fileWeights = recordTokenWeights.get(k);
			for (String qgram : queryWeights.keySet()) {
				if (fileWeights.containsKey(qgram)) {
					score += fileWeights.get(qgram) * queryWeights.get(qgram);
					haveCommonToken = true;
				}
			}
			if (haveCommonToken) {
				scoreList.add(new IdScore(k, score));
			}
		}
		// // System.gc();
		Collections.sort(scoreList);
		
		return scoreList;
	}

	// This function is for the metrics which has to go iteratively through all the records to get the final scoreList
	public List<IdScore> getSimilarRecords(String query, HashMap<String, Double> qgramIDF,
			Vector<HashMap<String, Double>> recordTokenWeights, Vector<String> recordVector) {
		return getSimilarRecords(query, qgramIDF, recordTokenWeights);
	}
	
	// TODO: Check if the threshold version works
	public List<IdScore> getSimilarRecordsTH(String query, HashMap<String, Double> qgramIDF,
			Vector<HashMap<String, Double>> recordTokenWeights, Vector<String> recordVector, Double thr, int begin) {
		List<IdScore> scoreList = new ArrayList<IdScore>();
		HashMap<String, Double> queryWeights = getQueryWeights(query, qgramIDF);
		for (int k = (begin-1); k < recordTokenWeights.size(); k++) {
			double score = 0;
			//boolean haveCommonToken = false;
			HashMap<String, Double> fileWeights = recordTokenWeights.get(k);
			for (String qgram : queryWeights.keySet()) {
				if (fileWeights.containsKey(qgram)) {
					score += fileWeights.get(qgram) * queryWeights.get(qgram);
					//haveCommonToken = true;
				}
			}
			if (score >= thr) {
				scoreList.add(new IdScore(k, score));
			}
		}
		// // System.gc();
		Collections.sort(scoreList);
		
		return scoreList;	
	}

	// TODO: Check if the threshold version works
	public List<IdScore> getSimilarRecordsTH2(String query, HashMap<String, Double> qgramIDF,
			HashMap<Integer, String> records, Double thr) {
		return null;
	}

	public IdScore getMaxSimilarRecord(String query, HashMap<String, Double> qgramIDF,
			HashMap<Integer, String> records, Double thr) {
		return null;		
	}	
	
	
	public IdScore getMaxSimilarRecord2(String query, HashMap<String, Double> qgramIDF,
			HashMap<Integer, String> records, Vector<HashMap<String, Double>> recordTokenWeights, Double thr) {
		IdScore max = null;
		HashMap<String, Double> queryWeights = getQueryWeights(query, qgramIDF);
		//double meanIDF = Util.getMeanIDF(qgramIDF);
		double maxscore = thr;
		for (int k:records.keySet()) {
			double score = 0;
			HashMap<String, Double> fileWeights = recordTokenWeights.get(k);
			for (String qgram : queryWeights.keySet()) {
				if (fileWeights.containsKey(qgram)) {
					score += fileWeights.get(qgram) * queryWeights.get(qgram);
					//haveCommonToken = true;
				}
			}
			//System.out.println(score);
			if(score >= maxscore){
				max = new IdScore(k, score);
				maxscore = score;
			}
		}
		// // System.gc();
		
		//if (scoreList.size()!=0) max = Collections.max(scoreList);
		return max;		
	}	
	

	
	
	// Returns single score
	// TODO: check
	public double getSimilarityScore(String query, HashMap<String, Double> qgramIDF,
			Vector<HashMap<String, Double>> recordTokenWeights, int tid, String record) {
		HashMap<String, Double> queryWeights = getQueryWeights(query, qgramIDF);
		double score = 0;
		HashMap<String, Double> fileWeights = recordTokenWeights.get(tid-1);
		for (String qgram : queryWeights.keySet()) {
			if (fileWeights.containsKey(qgram)) {
				score += fileWeights.get(qgram) * queryWeights.get(qgram);
			}
		}
		return score;
	}
	
	public double getSimilarityScore(String query, HashMap<String, Double> qgramIDF, double meanIDF,
			Vector<HashMap<String, Double>> recordTokenWeights, int tid, String record) {
		HashMap<String, Double> queryWeights = getQueryWeights(query, qgramIDF);
		double score = 0;
		HashMap<String, Double> fileWeights = recordTokenWeights.get(tid-1);
		for (String qgram : queryWeights.keySet()) {
			if (fileWeights.containsKey(qgram)) {
				score += fileWeights.get(qgram) * queryWeights.get(qgram);
			}
		}
		return score;
	}
	
	public static void storePreprocessedDataToDB(String tableName, Vector<HashMap<String, Double>> recordTokenWeights,
			String metric) {
		Config config = new Config();
		MySqlDB mysqlDB = new MySqlDB(config.returnURL(), config.user, config.passwd);
		String query = "";
		try {
			query = "drop table if exists " + config.dbName + ".PP_" + tableName + "_" + metric;
			mysqlDB.executeUpdate(query);

			query = "create table " + config.dbName + ".PP_" + tableName + "_" + metric
					+ " (rid int, token varchar(255), weight double)";
			mysqlDB.executeUpdate(query);

			System.err.println("Executing " + query);
			for (int a = 0; a < recordTokenWeights.size(); a++) {
				HashMap<String, Double> tokenWeights = recordTokenWeights.get(a);
				for (String token : tokenWeights.keySet()) {
					query = "insert into " + config.dbName + ".PP_" + tableName + "_" + metric + " values (" + (a + 1)
							+ " ,'" + token.replaceAll("'", "''") + "', "+ tokenWeights.get(token) + ")";
					mysqlDB.executeUpdate(query);
				}
			}
			mysqlDB.close();
		} catch (Exception e) {
			System.err.println("Can't execute Query: " + query);
			e.printStackTrace();
		}
	}

	public static void storePreprocessedIDF(String tableName, HashMap<String, Double> qgramIDF, String metric) {
		Config config = new Config();
		MySqlDB mysqlDB = new MySqlDB(config.returnURL(), config.user, config.passwd);
		String query = "";
		try {
			query = "drop table if exists " + config.dbName + ".PP_" + tableName + "_" + metric;
			mysqlDB.executeUpdate(query);

			query = "create table " + config.dbName + ".PP_" + tableName + "_" + metric
					+ " (token varchar(255), idf double)";
			mysqlDB.executeUpdate(query);

			System.err.println("Executing " + query);
			for (String token: qgramIDF.keySet()) {
					query = "insert into " + config.dbName + ".PP_" + tableName + "_" + metric + " values ('" 
							 + token.replaceAll("'", "''") + "', "+ qgramIDF.get(token) + ")";
					mysqlDB.executeUpdate(query);
			}
			mysqlDB.close();
		} catch (Exception e) {
			System.err.println("Can't execute Query: " + query);
			e.printStackTrace();
		}
	}
} public class SoftTfIdf extends TfIdf {

	public static boolean localDebugMode = true;
	public static double jwSimilarityThreshold = 0.8;
	
	public HashMap<String, Double> getTF(String str) {
		tokenizeUsingQgrams = false;
		return getTokenTFMultiple(str);
	}
	
	public void printDebug(String str){
		//if(localDebugMode)
		//	System.out.print(str);
	}
	
	// Returns the maximum similar token based on Jaro-Wrinkler score
	public String getMaximumSimilarToken(String token, Set<String> tupleTokens, JaroWinkler jw) {
		double currentScore = 0, maxScore = 0;
		boolean isFirstToken = true;
		String maxSimilarToken = "";
		printDebug(token+"\n");
		for (String tok : tupleTokens) {
			if(isFirstToken){
				maxSimilarToken = tok;
				isFirstToken = false;
			}
			currentScore = jw.score(jw.prepare(token), jw.prepare(tok));
			printDebug(tok+" "+currentScore+" :: ");
			if (currentScore > maxScore) {
				maxScore = currentScore;
				maxSimilarToken = tok;
			}
		}
		printDebug("\nMaxSimilar  "+maxSimilarToken+" "+maxScore+" :: \n");
		return maxSimilarToken;
	}

	public List<IdScore> getSimilarRecords(String query, HashMap<String, Double> qgramIDF,
			Vector<HashMap<String, Double>> recordTokenWeights) {
		// query = query.replaceAll("'", "''");
		JaroWinkler jw = new JaroWinkler();
		// double score = jw.score(jw.prepare(str1), jw.prepare(str2));

		List<IdScore> scoreList = new ArrayList<IdScore>();
		HashMap<String, Double> queryWeights = getQueryWeights(query, qgramIDF);
		for (int k = 0; k < recordTokenWeights.size(); k++) {
			double score = 0;
			HashMap<String, Double> fileWeights = recordTokenWeights.get(k);
			
			if(fileWeights.containsKey("union")){
				localDebugMode = true;
			}else{
				localDebugMode = false;
			}
			if((k > 320) && (k < 325)){
				localDebugMode = true;
			}else{
				localDebugMode = false;
			}
			printDebug("QUERY: "+query+"   RECORD: "+(k+1) + "=====================================\n");
			for (String qgram : queryWeights.keySet()) {
				// if (fileWeights.containsKey(qgram)) {
				String maxSimilarToken = getMaximumSimilarToken(qgram, fileWeights.keySet(), jw);
				double jaroWinklerSimilarityScore = jw.score(jw.prepare(qgram), jw.prepare(maxSimilarToken));

            // A match is considered only when JWsim-score > 0.8 thats the threshold
            if(jaroWinklerSimilarityScore > jwSimilarityThreshold){
   				score += fileWeights.get(maxSimilarToken) * queryWeights.get(qgram) * jaroWinklerSimilarityScore;
   				printDebug(qgram+" "+queryWeights.get(qgram)+" :: ");
	   			printDebug(maxSimilarToken+" "+fileWeights.get(maxSimilarToken)+" ::  jwSim "+jaroWinklerSimilarityScore+"\n");
            }

				// }
			}
			if(score > 0.5){
				localDebugMode = true;
			}
			printDebug("QUERY: "+query+"   RECORD: "+(k+1) + "=====================================\n");
			printDebug("final Score: "+score+"\n");
			printDebug("===========================================================================\n");
			scoreList.add(new IdScore(k, score));
		}
		// // System.gc();
		Collections.sort(scoreList);
		return scoreList;
	}
} public class TfIdf extends Preprocess {

	// Tokenizer based on whitespace; evry token is a word
	public HashMap<String, Double> getTF(String str) {
		return getTokenTFMultiple(str);
	}

} public class WeightedIntersect extends Preprocess {

	double meanIDF=0;
	
	// Tokenizer based on whitespace; every token is a word
	// Its not required for Edit-Distance metric
	public HashMap<String, Double> getTF(String str) {
		return gettokenTFSingle(str);
	}
	
	public void getDFandTFweight(int recordId, String str, HashMap<String, Double> qgramIDF,
			Vector<HashMap<String, Double>> recordTokenWeights) {
		HashMap<String, Double> tokenTF = getTF(str);
		//recordTokenWeights.insertElementAt(tokenTF, recordId);
		// Set df's
		for (String qgram : tokenTF.keySet()) {
			incrementDFCount(qgram, qgramIDF, tokenTF.get(qgram));
		}
	}
	
	public void preprocessTable(Vector<String> records, HashMap<String, Double> qgramIDF,
			Vector<HashMap<String, Double>> recordTokenWeights, String tableName) {
		Config config = new Config();
		MySqlDB mysqlDB = new MySqlDB(config.returnURL(), config.user, config.passwd);
		int numberOfRecords = 0, k = 0;
		try {
			String query = "select tid, "+config.preprocessingColumn+" from " + config.dbName + "." + tableName + " order by tid asc";
			ResultSet rs = mysqlDB.executeQuery(query);
			if (rs != null) {
				while (rs.next()) {
					String str = rs.getString(config.preprocessingColumn);
					k = rs.getInt("tid");
					if ((str != null) && (!str.equals(""))) {
						records.insertElementAt(str, k - 1);
						// Find the tf's of all the qgrams
						getDFandTFweight(k - 1, str, qgramIDF, recordTokenWeights);
					}
					numberOfRecords++;
				}
			}
			mysqlDB.close();
		} catch (Exception e) {
			System.out.println("database error: cannot read table");
			e.printStackTrace();
		}
		//convert the Df to IDF
		convertDFtoIDF(qgramIDF, numberOfRecords);
		if(logToDB){
			storePreprocessedIDF(tableName, qgramIDF, extractMetricName(this.getClass().getName())+"_idf" );
		}
		recordTokenWeights.clear();
	}

	// This function is for the metrics which has to go iteratively through all
	// the records to get the final scoreList
	public List<IdScore> getSimilarRecords(String query, HashMap<String, Double> qgramIDF,
			Vector<HashMap<String, Double>> recordTokenWeights, Vector<String> recordVector) {
		List<IdScore> scoreList = new ArrayList<IdScore>();
		//HashMap<String, Double> queryWeights = getQueryWeights(query, qgramIDF);
		double meanIDF = Util.getMeanIDF(qgramIDF);
		for (int k = 0; k < recordVector.size(); k++) {
			double score = weightedIntersect(query, recordVector.get(k), qgramIDF, meanIDF);
			if(score > 0){
				scoreList.add(new IdScore(k, score));
			}
		}
		// // System.gc();
		Collections.sort(scoreList);
		
		/*for(int k=0; k < scoreList.size(); k++){
			System.out.println(k +"  " +scoreList.get(k));
		}*/
		
		return scoreList;
	}

	public double weightedIntersect(String s, String t, HashMap<String, Double> qgramIDF, double meanIDF){
		//System.out.println("wj called");
		double weightedIntersectScore=0;
		Set<String> setS = gettokenTFSingle(s).keySet();
		Set<String> setT = gettokenTFSingle(t).keySet();
		
		Util.printlnDebug(setS);
		Util.printlnDebug(setT);
		
		setS.retainAll(setT);
		Util.printlnDebug(setS);
		double weightedSumSandT = Util.getWeightedSumForTokenSet(setS, qgramIDF, meanIDF);
		if(setS.size() > 0){
			weightedIntersectScore = weightedSumSandT;
		}
		Util.printlnDebug("Weighted Intersect Score: "+weightedIntersectScore);
		Util.printlnDebug("Intersect : "+ setS.size() );
		return weightedIntersectScore;
	}
	
	
} public class WeightedIntersectBM25 extends Preprocess {

	double meanIDF=0;
	
	// Tokenizer based on whitespace; every token is a word
	// Its not required for Edit-Distance metric
	public HashMap<String, Double> getTF(String str) {
		return gettokenTFSingle(str);
	}
	
	public void convertDFtoIDF(HashMap<String, Double> qgramIDF, int size) {
		for (String qgram : qgramIDF.keySet()) {
			qgramIDF.put(qgram, Math.log((size - qgramIDF.get(qgram) + 0.5) / (qgramIDF.get(qgram) + 0.5)));
		}
	}
	
	public void getDFandTFweight(int recordId, String str, HashMap<String, Double> qgramIDF,
			Vector<HashMap<String, Double>> recordTokenWeights) {
		HashMap<String, Double> tokenTF = getTF(str);
		//recordTokenWeights.insertElementAt(tokenTF, recordId);
		// Set df's
		for (String qgram : tokenTF.keySet()) {
			incrementDFCount(qgram, qgramIDF, tokenTF.get(qgram));
		}
	}
	
	public void preprocessTable(Vector<String> records, HashMap<String, Double> qgramIDF,
			Vector<HashMap<String, Double>> recordTokenWeights, String tableName) {
		Config config = new Config();
		MySqlDB mysqlDB = new MySqlDB(config.returnURL(), config.user, config.passwd);
		int numberOfRecords = 0, k = 0;
		try {
			String query = "select tid, "+config.preprocessingColumn+" from " + config.dbName + "." + tableName + " order by tid asc";
			ResultSet rs = mysqlDB.executeQuery(query);
			if (rs != null) {
				while (rs.next()) {
					String str = rs.getString(config.preprocessingColumn);
					k = rs.getInt("tid");
					if ((str != null) && (!str.equals(""))) {
						records.insertElementAt(str, k - 1);
						// Find the tf's of all the qgrams
						getDFandTFweight(k - 1, str, qgramIDF, recordTokenWeights);
					}
					numberOfRecords++;
				}
			}
			mysqlDB.close();
		} catch (Exception e) {
			System.out.println("database error: cannot read table");
			e.printStackTrace();
		}
		//convert the Df to IDF
		convertDFtoIDF(qgramIDF, numberOfRecords);
		if(logToDB){
			storePreprocessedIDF(tableName, qgramIDF, extractMetricName(this.getClass().getName())+"_idf" );
		}
		recordTokenWeights.clear();
	}

	// This function is for the metrics which has to go iteratively through all
	// the records to get the final scoreList
	public List<IdScore> getSimilarRecords(String query, HashMap<String, Double> qgramIDF,
			Vector<HashMap<String, Double>> recordTokenWeights, Vector<String> recordVector) {
		List<IdScore> scoreList = new ArrayList<IdScore>();
		//HashMap<String, Double> queryWeights = getQueryWeights(query, qgramIDF);
		double meanIDF = Util.getMeanIDF(qgramIDF);
		for (int k = 0; k < recordVector.size(); k++) {
			double score = weightedIntersect(query, recordVector.get(k), qgramIDF, meanIDF);
			if(score > 0){
				scoreList.add(new IdScore(k, score));
			}
		}
		// // System.gc();
		Collections.sort(scoreList);
		
		/*for(int k=0; k < scoreList.size(); k++){
			System.out.println(k +"  " +scoreList.get(k));
		}*/
		
		return scoreList;
	}

	public double weightedIntersect(String s, String t, HashMap<String, Double> qgramIDF, double meanIDF){
		//System.out.println("wj called");
		double weightedIntersectScore=0;
		Set<String> setS = gettokenTFSingle(s).keySet();
		Set<String> setT = gettokenTFSingle(t).keySet();
		
		Util.printlnDebug(setS);
		Util.printlnDebug(setT);
		
		setS.retainAll(setT);
		Util.printlnDebug(setS);
		double weightedSumSandT = Util.getWeightedSumForTokenSet(setS, qgramIDF, meanIDF);
		if(setS.size() > 0){
			weightedIntersectScore = weightedSumSandT;
		}
		Util.printlnDebug("Weighted Intersect Score: "+weightedIntersectScore);
		Util.printlnDebug("Intersect : "+ setS.size() );
		return weightedIntersectScore;
	}
	
	
} public class WeightedJaccard extends Preprocess {

	double meanIDF=0;
	
	// Tokenizer based on whitespace; every token is a word
	// Its not required for Edit-Distance metric
	public HashMap<String, Double> getTF(String str) {
		return gettokenTFSingle(str);
	}
	
	public void getDFandTFweight(int recordId, String str, HashMap<String, Double> qgramIDF,
			Vector<HashMap<String, Double>> recordTokenWeights) {
		HashMap<String, Double> tokenTF = getTF(str);
		//recordTokenWeights.insertElementAt(tokenTF, recordId);
		// Set df's
		for (String qgram : tokenTF.keySet()) {
			incrementDFCount(qgram, qgramIDF, tokenTF.get(qgram));
		}
	}
	
	public void preprocessTable(Vector<String> records, HashMap<String, Double> qgramIDF,
			Vector<HashMap<String, Double>> recordTokenWeights, String tableName) {
		Config config = new Config();
		MySqlDB mysqlDB = new MySqlDB(config.returnURL(), config.user, config.passwd);
		int numberOfRecords = 0, k = 0;
		try {
			String query = "select tid, "+config.preprocessingColumn+" from " + config.dbName + "." + tableName + " order by tid asc";
			ResultSet rs = mysqlDB.executeQuery(query);
			if (rs != null) {
				while (rs.next()) {
					String str = rs.getString(config.preprocessingColumn);
					k = rs.getInt("tid");
					if ((str != null) && (!str.equals(""))) {
						records.insertElementAt(str, k - 1);
						// Find the tf's of all the qgrams
						getDFandTFweight(k - 1, str, qgramIDF, recordTokenWeights);
					}
					numberOfRecords++;
				}
			}
			mysqlDB.close();
		} catch (Exception e) {
			System.out.println("database error: cannot read table");
			e.printStackTrace();
		}
		//convert the Df to IDF
		convertDFtoIDF(qgramIDF, numberOfRecords);
		//recordTokenWeights.clear();
	}

	// This function is for the metrics which has to go iteratively through all
	// the records to get the final scoreList
	public List<IdScore> getSimilarRecords(String query, HashMap<String, Double> qgramIDF,
			Vector<HashMap<String, Double>> recordTokenWeights, Vector<String> recordVector) {
		List<IdScore> scoreList = new ArrayList<IdScore>();
		//HashMap<String, Double> queryWeights = getQueryWeights(query, qgramIDF);
		double meanIDF = Util.getMeanIDF(qgramIDF);
		for (int k = 0; k < recordVector.size(); k++) {
			double score = weightedJaccard(query, recordVector.get(k), qgramIDF, meanIDF);
			if(score > 0){
				scoreList.add(new IdScore(k, score));
			}
		}
		// // System.gc();
		Collections.sort(scoreList);
		//System.err.println(" result size: "+scoreList.size());
		return scoreList;
	}

	public double weightedJaccard(String s, String t, HashMap<String, Double> qgramIDF, double meanIDF){
		//System.out.println("wj called");
		double sizeS = 0;
		double weightedJaccardScore=0;
		Set<String> setS = gettokenTFSingle(s).keySet();
		sizeS = setS.size();
		double weightedSumS = Util.getWeightedSumForTokenSet(setS, qgramIDF, meanIDF);
		Set<String> setT = gettokenTFSingle(t).keySet();
		double weightedSumT = Util.getWeightedSumForTokenSet(setT, qgramIDF, meanIDF);
		
		Util.printlnDebug(setS);
		Util.printlnDebug(setT);
		
		setS.retainAll(setT);
		Util.printlnDebug(setS);
		double weightedSumSandT = Util.getWeightedSumForTokenSet(setS, qgramIDF, meanIDF);
		if(setS.size() > 0){
			weightedJaccardScore = weightedSumSandT / (weightedSumS + weightedSumT - weightedSumSandT);
		}
		Util.printlnDebug("Weighted Jaccard Score: "+weightedJaccardScore);
		Util.printlnDebug("Jaccard : "+( setS.size()/ (sizeS + setT.size() - setS.size())));
		return weightedJaccardScore;
	}
	
	
} public class WeightedJaccardBM25 extends Preprocess {

	double meanIDF=0;
	
	// Tokenizer based on whitespace; every token is a word
	// Its not required for Edit-Distance metric
	public HashMap<String, Double> getTF(String str) {
		return gettokenTFSingle(str);
	}
	
	public void convertDFtoIDF(HashMap<String, Double> qgramIDF, int size) {
		for (String qgram : qgramIDF.keySet()) {
			qgramIDF.put(qgram, Math.log((size - qgramIDF.get(qgram) + 0.5) / (qgramIDF.get(qgram) + 0.5)));
		}
	}

	public void getDFandTFweight(int recordId, String str, HashMap<String, Double> qgramIDF,
			Vector<HashMap<String, Double>> recordTokenWeights) {
		HashMap<String, Double> tokenTF = getTF(str);
		//recordTokenWeights.insertElementAt(tokenTF, recordId);
		// Set df's
		for (String qgram : tokenTF.keySet()) {
			incrementDFCount(qgram, qgramIDF, tokenTF.get(qgram));
		}
	}
	
	public void preprocessTable(Vector<String> records, HashMap<String, Double> qgramIDF,
			Vector<HashMap<String, Double>> recordTokenWeights, String tableName) {
		Config config = new Config();
		MySqlDB mysqlDB = new MySqlDB(config.returnURL(), config.user, config.passwd);
		int numberOfRecords = 0, k = 0;
		try {
			String query = "select tid, "+config.preprocessingColumn+" from " + config.dbName + "." + tableName + " order by tid asc";
			ResultSet rs = mysqlDB.executeQuery(query);
			if (rs != null) {
				while (rs.next()) {
					String str = rs.getString(config.preprocessingColumn);
					k = rs.getInt("tid");
					if ((str != null) && (!str.equals(""))) {
						//System.out.println(str);
						records.insertElementAt(str, k - 1);
						// Find the tf's of all the qgrams
						getDFandTFweight(k - 1, str, qgramIDF, recordTokenWeights);
					}
					else if (str.equals("")) records.insertElementAt("NULL", k - 1); // todo: oktie: check! is NULL a good idea? 
					numberOfRecords++;
				}
				
			}
			mysqlDB.close();
		} catch (Exception e) {
			System.out.println("database error: cannot read table");
			e.printStackTrace();
		}
		//convert the Df to IDF
		convertDFtoIDF(qgramIDF, numberOfRecords);
		//System.out.println(qgramIDF);
		//recordTokenWeights.clear();
	}

	// This function is for the metrics which has to go iteratively through all
	// the records to get the final scoreList
	public List<IdScore> getSimilarRecords(String query, HashMap<String, Double> qgramIDF,
			Vector<HashMap<String, Double>> recordTokenWeights, Vector<String> recordVector) {
		List<IdScore> scoreList = new ArrayList<IdScore>();
		//HashMap<String, Double> queryWeights = getQueryWeights(query, qgramIDF);
		double meanIDF = Util.getMeanIDF(qgramIDF);
		for (int k = 0; k < recordVector.size(); k++) {
			double score = weightedJaccard(query, recordVector.get(k), qgramIDF, meanIDF);
			if(score > 0){
				scoreList.add(new IdScore(k, score));
			}
		}
		// // System.gc();
		Collections.sort(scoreList);
		//System.err.println(" result size: "+scoreList.size());
		return scoreList;
	}
	
	public List<IdScore> getSimilarRecordsTH(String query, HashMap<String, Double> qgramIDF,
			Vector<HashMap<String, Double>> recordTokenWeights, Vector<String> recordVector, Double thr, int begin) {
		List<IdScore> scoreList = new ArrayList<IdScore>();
		//HashMap<String, Double> queryWeights = getQueryWeights(query, qgramIDF);
		double meanIDF = Util.getMeanIDF(qgramIDF);
		for (int k = (begin-1); k < recordVector.size(); k++) {
			double score = weightedJaccard(query, recordVector.get(k), qgramIDF, meanIDF);
			if(score >= thr){
				scoreList.add(new IdScore(k, score));
			}
		}
		// // System.gc();
		Collections.sort(scoreList);
		//System.err.println(" result size: "+scoreList.size());
		return scoreList;
	}
	
	// Returns single score
	public double getSimilarityScore(String query, HashMap<String, Double> qgramIDF,
			Vector<HashMap<String, Double>> recordTokenWeights, int tid, String record) {
		double meanIDF = Util.getMeanIDF(qgramIDF);
		double score = weightedJaccard(query, record, qgramIDF, meanIDF);
		return score;
	}

	public double weightedJaccard(String s, String t, HashMap<String, Double> qgramIDF, double meanIDF){
		//System.out.println("wj called");
		//long time=System.currentTimeMillis();
		double weightedJaccardScore=0;
		Set<String> setS = gettokenTFSingle(s).keySet();
		double weightedSumS = Util.getWeightedSumForTokenSet(setS, qgramIDF, meanIDF);
		Set<String> setT = gettokenTFSingle(t).keySet();
		double weightedSumT = Util.getWeightedSumForTokenSet(setT, qgramIDF, meanIDF);
		
		Util.printlnDebug(setS);
		Util.printlnDebug(setT);
		
		setS.retainAll(setT);
		//Util.printlnDebug(setS);
		double weightedSumSandT = Util.getWeightedSumForTokenSet(setS, qgramIDF, meanIDF);
		if(setS.size() > 0){
			//System.out.println(s + " "  + weightedSumS);
			//System.out.println(t + " "  + weightedSumT);
			//System.out.println("qgram" + " "  + qgramIDF);
			//System.out.println("sum" + " "  + (weightedSumS + weightedSumT));
			//System.out.println("intersect" + " "  + weightedSumSandT);
			//System.out.println("union" + " "  + (weightedSumS + weightedSumT - weightedSumSandT));
			weightedJaccardScore = weightedSumSandT / (weightedSumS + weightedSumT - weightedSumSandT);
			//System.out.println("score" + " "  + weightedJaccardScore);
			//System.out.println("*** " + (Math.exp(-2.1972245773362196)));
		}
		//Util.printlnDebug("Weighted Jaccard Score: "+weightedJaccardScore);
		//Util.printlnDebug("Jaccard : "+( setS.size()/ (sizeS + setT.size() - setS.size())));
		//System.out.println((System.currentTimeMillis() - time));
		return weightedJaccardScore;
	}
	
	
} public class Config 
{
	public String cfgFileName;
	public String dbName;
	public String host ;
	public String user ;
	public String passwd;
	public String port ;
	public String url ;
	public boolean useFile;
	public String fileName;
	public String dbServer;
	public String outputFile;
    public String preprocessingColumn;
	public boolean debugMode;
	public int dbOption;
	
	public static String storeResultDirectory = "c:/Users/admin/dcp-workspace/log/";
    public static String queryFileName = "c:/Users/admin/dcp-workspace/data/_fixedQueries_";
    public static String expResultTablePrefix = "_ExpRes_"; 
	public static String queryClass = "dcp.clean";
    
	public static boolean tokenizeUsingQgrams = true;
    public int numHeaders;
    

	public String bm25WeightTable = "$Aux$_BM253_0_cu1_string_BMBaseWeights";
	public String tfidfWeightTable = "$Aux$_TfIdf3_0_cu1_string_Weights";
	// Class constructor 
	public Config() {
		outputFile = "geneRatios.txt";
		
		host = "localhost";
		user = "root";
		passwd = "";
		port = "3306";
		url = "";
		useFile = false;
	    fileName = "tmpFile";
	    dbServer = "mysql";
	    numHeaders = 7;
	    dbName = "midas";
	    preprocessingColumn = "name";
	    
	    //dbName = "probtest";
	    //preprocessingColumn = "title";
	}
	
	public String returnURL(){
		if(dbOption == 1)
			url = "jdbc:postgres://"+ host + ":"+ port +"/"+ dbName;
		else
			url = "jdbc:mysql://"+host+":"+port+"/"+dbName ;
		return url;
	}
	
	public void setDebugMode(boolean val){
		debugMode = val;
	}

	public void setDbName(String name){
		dbName = name;
	}
	
} public class Util
{
	public static boolean localDebugMode = false;
	
	public static double getIDFWeight(String token, HashMap<String, Double> qgramIDF, double meanIDF) {
		if (qgramIDF.containsKey(token)) {
			return qgramIDF.get(token);
		} else {
			return meanIDF;
		}
	}	
	
	public static double getMeanIDF(HashMap<String, Double> qgramIDF){
		double meanIDF=0;
		if(qgramIDF.size() <= 0){
			return 0;
		}
		for(String token: qgramIDF.keySet()){
			meanIDF += qgramIDF.get(token);
		}
		return meanIDF/qgramIDF.size();
	}

	public static double getWeightedSumForTokenSet(Set<String> tokenSet, HashMap<String, Double> qgramIDF, double meanIDF){
		double weightedSum=0;
		for(String token: tokenSet){
			weightedSum += getIDFWeight(token, qgramIDF, meanIDF);
		}
		return weightedSum;
	}
	
	public static void printDebug(String str){
		if(localDebugMode)
			System.out.print(str);
	}

	public static void printlnDebug(String str){
		if(localDebugMode)
			System.out.println(str);
	}
	
	public static void printlnDebug(Set<String> tokenSet){
		if(localDebugMode){
			System.out.print(tokenSet.size()+"   ");
			System.out.print("[ ");
			for(String token: tokenSet)
				System.out.print(token+" , ");
			System.out.println(" ]");
		}
	}
}
import java.io.File;
import java.sql.ResultSet;
import java.util.ArrayList;
import java.util.BitSet;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Vector;
import java.util.Set;
import java.util.Random;
import java.util.Arrays;
import java.util.Map;
import java.util.TreeMap;
import dbdriver.MySqlDB;
import evaluation.AccuracyMeasure;
import simfunctions.ApproximateGES;
import simfunctions.BM25;
import simfunctions.EditDistance;
import simfunctions.EvaluateSJoinThread;
import simfunctions.GeneralizedEditSimilarity;
import simfunctions.HMM;
import simfunctions.Intersect;
import simfunctions.Jaccard;
import simfunctions.Preprocess;
import simfunctions.SoftTfIdf;
import simfunctions.TfIdf;
import simfunctions.WeightedIntersect;
import simfunctions.WeightedIntersectBM25;
import simfunctions.WeightedJaccard;
import simfunctions.WeightedJaccardBM25;
import utility.Config;
import utility.Util;
				i++;
			}
			allnums.clear(i);
			//System.out.println(i);
			output.put(k, i);
			//System.out.println(output.get(k));
			k++;
		}
		
		return output;
	}
	
	public static HashMap<Integer, Integer> permutation(int n, int rnd){
		HashMap<Integer, Integer> output = new HashMap<Integer, Integer>();
		
		BitSet allnums = new BitSet();
		allnums.set(1, n+1, true);
		
		Random rand = new Random(rnd);
		int k=1;
		while (!allnums.isEmpty()){
			int i = rand.nextInt(n);
			//System.out.print(k + " " + i + " ");
			while (!allnums.get(i)) {
				if (i > n) i=0;
				i++;
			}
			allnums.clear(i);
			//System.out.println(i);
			output.put(k, i);
			//System.out.println(output.get(k));
			k++;
		}
		
		return output;
	}
	
	public static int b(int i, int j, int n1, int n2, int N){
		int n = N + ( (N % (n1*n2) == 0) ? 0 : ((n1*n2)-(N%(n1*n2))) ); // make N divisable by n1xn2
		return n * ( n2*(i-1)+j-1 ) / (n1*n2) + 1; // ?? +1
	}
	public static int e(int i, int j, int n1, int n2, int N){
		int n = N + ( (N % (n1*n2) == 0) ? 0 : ((n1*n2)-(N%(n1*n2))) ); // make N divisable by n1xn2
		return n * ( n2*(i-1)+j ) / (n1*n2) + 1; // ?? +1
	}
	public static BitSet p(int i, int j, int n1, int n2, int N){
		BitSet output = new BitSet();
		//System.out.println("i:" + i + " j:" + j + " e:"+ e(i,j,n1,n2,N));
		for (int t = b(i,j,n1,n2,N); t< e(i,j,n1,n2,N); t++){
			output.set(perm.get(t));
		}
		return output;
	}
	
	public static Vector<Vector<Integer>> subsets(Vector<Integer> set, int size){
		Vector<Vector<Integer>> output = new Vector<Vector<Integer>>();
		//System.out.println();
		
		if (size == 1) {
			for (Integer vi: set){
				Vector<Integer> v = new Vector<Integer>();
				v.add(vi);
				output.add(v);
			}
		}
		else {
			for (int i = 1; i <= set.size()-(size-1); i++){
				Vector<Integer> set2 = new Vector<Integer>();
				for (int j = i+1; j <= set.size(); j++) set2.add(set.elementAt(j-1));
				for (Vector<Integer> sset : subsets(set2, size-1)){
					Vector<Integer> v = new Vector<Integer>();
					v.add(set.elementAt(i-1));
					for (Integer vi:sset) v.add(vi);
					output.add(v);
				}
			}
		}

		return output;
	}
	
	public static void tst(int i, Integer j, Vector<String> vStr, HashMap<Integer, Double> hm){
		i = 1;
		j = 0;
		vStr.add("ey baba!");
		hm.put(1, 2.2);
	}
	
	class pair {
	    private float x;
	    private float y;

	    public pair(float x, float y) {
	        this.x = x;
	        this.y = y;
	    }

	    public float getX() { return x; }
	    public float getY() { return y; }

	    public void setX(float x) { this.x = x; }
	    public void setY(float y) { this.y = y; }
	}
	
	public static void main(String[] args) {
		
		
		Config config = new Config();
		MySqlDB mysqlDB = new MySqlDB(config.returnURL(), config.user, config.passwd);
		
		
		Preprocess tfidf = new TfIdf();
		Preprocess bm25 = new BM25();
		Preprocess hmm = new HMM();
		Preprocess ed = new EditDistance();
		Preprocess ges = new GeneralizedEditSimilarity();
		Preprocess softtfidf = new SoftTfIdf();
		Preprocess fms = new ApproximateGES();
		Preprocess weightedJaccard = new WeightedJaccard();
		Preprocess jaccard = new Jaccard();
		Preprocess weightedIntersect = new WeightedIntersect();