LevenshteinMethod.java

Go to the documentation of this file.

/*
 * Project: Server for annotations sharing
 * Subproject: Position of fragment of text in XML document
 * Authors: Michael Angelov
 * File: LevenshteinMethod.java
 * Description: Compare class using Levenshtein approximate string matching method
 */

/**
 * @file LevenshteinMethod.java
 *
 * @brief Compare class using Levenshtein approximate string matching method
 */

package cz.vutbr.fit.knot.annotations.fragmentUpdater.compareMethods;

/**
 * Compare class using Levenshtein approximate string matching method
 *
 * @brief Compare class using Levenshtein approximate string matching method
 * @author Michael Angelov
 */
public class LevenshteinMethod extends CompareMethod {

  private double minimumPercentage;

  /**
   * Constructor
   *
   * @param minimumPercentage minimum similarity percentage condition that must be met for strings to match
   */
  public LevenshteinMethod(double minimumPercentage) {
    super();
    this.minimumPercentage = minimumPercentage;
  }

  /**
   * Minimum percentage setter
   *
   * @param minimumPercentage minimum similarity percentage
   */
  public void setMinimumPercentage(double minimumPercentage) {
    this.minimumPercentage = minimumPercentage;
  }

  /**
   * Minimum percentage getter
   *
   * @return minimum similarity percentage
   */
  public double getMinimumPercentage() {
    return minimumPercentage;
  }

  /**
   * Overriden compare() method
   *
   * @param first first string to compare
   * @param second second string to compare
   * @return true if strings match, false if don't
   */
  @Override
  public boolean compare(String first, String second) {
    if (second == null) {
      return false;
    }
    if (similarity(first, second) >= minimumPercentage) {
      return true;
    } else {
      return false;
    }
  }

  /**
   * Overriden toString() method
   *
   * @return string representation of class
   */
  @Override
  public String toString() {
    return "Levenshtein - " + (int)(minimumPercentage * 100) + "%";
  }

  /**
   * Function for choosing minimum of three values
   *
   * @param a first value
   * @param b second value
   * @param c third value
   * @return the minimum value
   */
  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;
  }

  /**
   * Levenshtein's similarity algorithm
   *
   * @param s first string to compare
   * @param t second string to compare
   * @return similarity in interval <0..1> (0-100%)
   */
  private static double similarity(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();

    double max = (double) Math.max(n, m);
    double similarity;

    if (n == 0) {
      return 1 - (m / max);
    }
    if (m == 0) {
      return 1 - (n / max);
    }

    d = new int[n + 1][m + 1];

    for (i = 0; i <= n; i++) {
      d[i][0] = i;
    }

    for (j = 0; j <= m; j++) {
      d[0][j] = j;
    }

    for (i = 1; i <= n; i++) {

      s_i = s.charAt(i - 1);

      for (j = 1; j <= m; j++) {

        t_j = t.charAt(j - 1);

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

        d[i][j] = Minimum(d[i - 1][j] + 1,  // cost for insertion
                          d[i][j - 1] + 1,  // cost for deletion
                          d[i - 1][j - 1] + cost);  // cost for substitution

      }
    }

    // set similarity to interval <0, 1>
    similarity = 1.0f - (double) (d[n][m]) / Math.max(n, m);

    return similarity;
  }

}  // class LevenshteinMethod