/*
 * SimMetrics - SimMetrics is a java library of Similarity or Distance Metrics,
 * e.g. Levenshtein Distance, that provide float based similarity measures
 * between String Data. All metrics return consistent measures rather than
 * unbounded similarity scores.
 * 
 * Copyright (C) 2014 SimMetrics authors
 * 
 * This file is part of SimMetrics. This program is free software: you can
 * redistribute it and/or modify it under the terms of the GNU General Public
 * License as published by the Free Software Foundation, either version 3 of the
 * License, or (at your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
 * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
 * details.
 * 
 * You should have received a copy of the GNU General Public License along with
 * SimMetrics. If not, see <http://www.gnu.org/licenses/>.
 */
package org.simmetrics.metrics;

import static java.lang.Math.max;
import static java.lang.Math.sqrt;

import java.util.List;

import org.simmetrics.StringMetric;
import org.simmetrics.ListMetric;

/**
 * Implements the Monge Elkan algorithm providing an matching style similarity
 * measure between two strings.
 * <p>
 * <code>similarity(a,b) = sum( for s in a | max( for q in b | metric(s,q))</code>
 * </p>
 * Implementation note: Because the matches of a in b are not symmetric with the
 * matches of b in a and because the whole operation is not symmetric when a and
 * b have a different length the asymmetry is normalized by
 * 
 * <p>
 * <code>normalized_similarity(a,b) = sqrt(similarity(a,b) * similarity(b,a))</code>
 * </p>
 * 
 * @author Sam Chapman
 * @author M.P. Korstanje
 */
public class MongeElkan implements ListMetric<String> {

	private final StringMetric metric;

	/**
	 * Constructs a MongeElkan metric with metric.
	 * 
	 * @param metric
	 *            metric to use
	 */
	public MongeElkan(final StringMetric metric) {
		this.metric = metric;
	}

	@Override
	public float compare(List<String> a, List<String> b) {

		if (a.isEmpty() && b.isEmpty()) {
			return 1.0f;
		}

		if (a.isEmpty() || b.isEmpty()) {
			return 0.0f;
		}

		float sumMatchesAB = sumMatches(a, b);
		float sumMatchesBA = sumMatches(b, a);

		return (float) sqrt(sumMatchesAB * sumMatchesBA);
	}

	private float sumMatches(List<String> a, List<String> b) {
		float sumMatches = 0.0f;

		for (String aToken : a) {
			float maxFound = 0.0f;
			for (String bToken : b) {
				maxFound = max(maxFound, metric.compare(aToken, bToken));
			}
			sumMatches += maxFound;
		}
		return sumMatches / a.size();
	}

	@Override
	public String toString() {
		return "MongeElkan [metric=" + metric + "]";
	}

}

@@ -1370,19 +1370,23 @@
 (a,b) = 
-sum
+average
 ( for s 
@@ -1422,16 +1422,17 @@
 ic(s,q))
+ 
 %3C/code%3E%0D
@@ -1783,32 +1783,8 @@
 * %0D%0A
- * @author Sam Chapman%0D%0A
  * @
@@ -2304,141 +2304,107 @@
 %0D%0A%09%09
-float sumMatchesAB = sumMatches(a, b);%0D%0A%09%09float sumMatchesBA = sumMatches(b, a);%0D%0A%0D%0A%09%09return (float) sqrt(sumMatchesAB * sumMatchesBA
+// calculates normalized_similarity(a,b)%0D%0A%09%09return (float) sqrt(similarity(a, b) * similarity(b, a)
 );%0D%0A
@@ -2425,25 +2425,25 @@
  float s
-umMatches
+imilarity
 (List%3CSt
@@ -2472,16 +2472,88 @@
 b) %7B%0D%0A%09%09
+// calculates average( for s in a %7C max( for q in b %7C metric(s,q))%0D%0A%0D%0A%09%09
 float su
@@ -2553,23 +2553,16 @@
 loat sum
-Matches
  = 0.0f;
@@ -2579,22 +2579,17 @@
 (String 
-aToken
+s
  : a) %7B%0D
@@ -2601,21 +2601,16 @@
 loat max
-Found
  = 0.0f;
@@ -2626,22 +2626,17 @@
 (String 
-bToken
+q
  : b) %7B%0D
@@ -2643,21 +2643,16 @@
 %0A%09%09%09%09max
-Found
  = max(m
@@ -2653,21 +2653,16 @@
  max(max
-Found
 , metric
@@ -2674,22 +2674,12 @@
 are(
-aToken, bToken
+s, q
 ));%0D
@@ -2695,27 +2695,15 @@
 %09sum
-Matches
  += max
-Found
 ;%0D%0A%09
@@ -2722,15 +2722,8 @@
  sum
-Matches
  / a

Clean up