EditDistance (Ukkonen-optimized Levenshtein) [1026090]

/*******************************************************************************
 * Copyright (c) 2010-2019 Haifeng Li
 *
 * Smile is free software: you can redistribute it and/or modify
 * it under the terms of the GNU Lesser General Public License as
 * published by the Free Software Foundation, either version 3 of
 * the License, or (at your option) any later version.
 *
 * Smile is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public License
 * along with Smile.  If not, see <https://www.gnu.org/licenses/>.
 *******************************************************************************/

/**
 * The Edit distance between two strings is a metric for measuring the amount
 * of difference between two sequences. The Levenshtein distance between two
 * strings is given by the minimum number of operations needed to transform one
 * string into the other, where an operation is an insertion, deletion, or
 * substitution of a single character. A generalization of the Levenshtein
 * distance (Damerau-Levenshtein distance) allows the transposition of two
 * characters as an operation.
 * <p>
 * Given two strings x and y of length m and n (suppose n &ge; m), this
 * implementation takes O(ne) time and O(mn) space by an extended Ukkonen's
 * algorithm in case of unit cost, where e is the edit distance between x and y.
 * Thus this algorithm is output sensitive. The smaller the distance, the faster
 * it runs.
 * <p>
 * For weighted cost, this implements the regular dynamic programming algorithm,
 * which takes O(mn) time and O(m) space.
 *
 * @author Haifeng Li
 */
final sclass EditDistance /*implements Metric<String>*/ {
  /**
   * Weight matrix for weighted Levenshtein distance.
   */
  private IIntArray2D weight;

  /**
   * Radius of Sakoe-Chiba band
   */
  private double r = -1;

  /**
   * Calculate Damerau or basic Levenshitein distance.
   */
  private boolean damerau = false;

  /**
   * Cost matrix. Because Java automatically initialize arrays, it
   * takes O(mn) to declare this cost matrix every time before
   * calculate edit distance. But the whole point of Berghel & Roach
   * algorithm is to calculate fewer cells than O(mn). Therefore,
   * we create this cost matrix here. Therefore, the methods using
   * this cost matrix is not multi-thread safe.
   */
  private IIntArray2D FKP;

  /**
   * The lambda to calculate FKP array.
   */
  private BRF brf;


  /**
   * Constructor. Multi-thread safe Levenshtein distance.
   */
  public EditDistance() {
      this(false);
  }

  /**
   * Constructor. Multi-thread safe Damerau-Levenshtein distance.
   * @param damerau if true, calculate Damerau-Levenshtein distance
   *                instead of plain Levenshtein distance.
   */
  public EditDistance(boolean damerau) {
      this.damerau = damerau;
  }

  /**
   * Constructor. Highly efficient Levenshtein distance but not multi-thread safe.
   * @param maxStringLength the maximum length of strings that will be
   * feed to this algorithm.
   */
  public EditDistance(int maxStringLength) {
      this(maxStringLength, false);
  }

  /**
   * Constructor. Highly efficient Damerau-Levenshtein distance but not multi-thread safe.
   * @param maxStringLength the maximum length of strings that will be
   *                        feed to this algorithm.
   * @param damerau if true, calculate Damerau-Levenshtein distance
   *                instead of plain Levenshtein distance.
   */
  public EditDistance(int maxStringLength, boolean damerau) {
      this.damerau = damerau;
      FKP = new IntArray2D(2*maxStringLength+1, maxStringLength+2);
      brf = damerau ? new DamerauBRF() : new LevenshteinBRF();
  }

  /**
   * Constructor. Weighted Levenshtein distance without path
   * constraints. Only insertion, deletion, and substitution operations are
   * supported.
   */
  public EditDistance(int[][] weight) {
      this(weight, -1);
  }

  /**
   * Constructor. Weighted Levenshtein distance with
   * Sakoe-Chiba band, which improve computational cost. Only
   * insertion, deletion, and substitution operations are supported.
   * @param radius the window width of Sakoe-Chiba band in terms of percentage of sequence length.
   */
  public EditDistance(int[][] weight, double radius) {
      this.weight = new IntArray2D(weight);
      this.r = radius;
  }

  @Override
  public String toString() {
      if (damerau) {
          if (weight != null)
              return String.format("Damerau-Levenshtein Distance(radius = %d, weight = %s)", r, weight.toString());
          else
              return "Damerau-Levenshtein Distance";
      } else {
          if (weight != null)
              return String.format("Levenshtein Distance(radius = %d, weight = %s)", r, weight.toString());
          else
              return  "Levenshtein Distance";
      }
  }

  /**
   * Edit distance between two strings. O(mn) time and O(n) space for weighted
   * edit distance. O(ne) time and O(mn) space for unit cost edit distance.
   * For weighted edit distance, this method is multi-thread safe. However,
   * it is NOT multi-thread safe for unit cost edit distance.
   */
  public double d(String x, String y) {
      if (weight != null)
          return weightedEdit(x, y);
      else if (FKP == null || x.length() == 1 || y.length() == 1)
          return damerau ? damerau(x, y) : levenshtein(x, y);
      else
          return br(x, y);
  }

  /**
   * Edit distance between two strings. O(mn) time and O(n) space for weighted
   * edit distance. O(ne) time and O(mn) space for unit cost edit distance.
   * For weighted edit distance, this method is multi-thread safe. However,
   * it is NOT multi-thread safe for unit cost edit distance.
   */
  public double d(char[] x, char[] y) {
      if (weight != null)
          return weightedEdit(x, y);
      else if (FKP == null || x.length == 1 || y.length == 1)
          return damerau ? damerau(x, y) : levenshtein(x, y);
      else
          return br(x, y);
  }

  /**
   * Weighted edit distance.
   */
  private double weightedEdit(char[] x, char[] y) {
      // switch parameters to use the shorter one as y to save space.
      if (x.length < y.length) {
          char[] swap = x;
          x = y;
          y = swap;
      }

      int radius = (int) Math.round(r * Math.max(x.length, y.length));

      double[][] d = new double[2][y.length + 1];

      d[0][0] = 0.0;
      for (int j = 1; j <= y.length; j++) {
          d[0][j] = d[0][j - 1] + weight.get(0, y[j]);
      }

      for (int i = 1; i <= x.length; i++) {
          d[1][0] = d[0][0] + weight.get(x[i], 0);

          int start = 1;
          int end = y.length;

          if (radius > 0) {
              start = i - radius;
              if (start > 1)
                  d[1][start - 1] = Double.POSITIVE_INFINITY;
              else
                  start = 1;

              end = i + radius;
              if (end < y.length)
                  d[1][end+1] = Double.POSITIVE_INFINITY;
              else
                  end = y.length;
          }

          for (int j = start; j <= end; j++) {
              double cost = weight.get(x[i - 1], y[j - 1]);
              d[1][j] = min3(
                      d[0][j] + weight.get(x[i - 1], 0), // deletion
                      d[1][j - 1] + weight.get(0, y[j - 1]), // insertion
                      d[0][j - 1] + cost); // substitution
          }

          double[] swap = d[0];
          d[0] = d[1];
          d[1] = swap;
      }

      return d[0][y.length];
  }

  /**
   * Weighted edit distance.
   */
  private double weightedEdit(String x, String y) {
      // switch parameters to use the shorter one as y to save space.
      if (x.length() < y.length()) {
          String swap = x;
          x = y;
          y = swap;
      }

      int radius = (int) Math.round(r * Math.max(x.length(), y.length()));

      double[][] d = new double[2][y.length() + 1];

      d[0][0] = 0.0;
      for (int j = 1; j <= y.length(); j++) {
          d[0][j] = d[0][j - 1] + weight.get(0, y.charAt(j));
      }

      for (int i = 1; i <= x.length(); i++) {
          d[1][0] = d[0][0] + weight.get(x.charAt(i), 0);

          int start = 1;
          int end = y.length();

          if (radius > 0) {
              start = i - radius;
              if (start > 1)
                  d[1][start - 1] = Double.POSITIVE_INFINITY;
              else
                  start = 1;

              end = i + radius;
              if (end < y.length())
                  d[1][end+1] = Double.POSITIVE_INFINITY;
              else
                  end = y.length();
          }

          for (int j = start; j <= end; j++) {
              double cost = weight.get(x.charAt(i - 1), y.charAt(j - 1));
              d[1][j] = min3(
                      d[0][j] + weight.get(x.charAt(i - 1), 0), // deletion
                      d[1][j - 1] + weight.get(0, y.charAt(j - 1)), // insertion
                      d[0][j - 1] + cost); // substitution
          }

          double[] swap = d[0];
          d[0] = d[1];
          d[1] = swap;
      }

      return d[0][y.length()];
  }

  /**
   * Berghel & Roach's extended Ukkonen's algorithm.
   */
  private int br(char[] x, char[] y) {
      if (x.length > y.length) {
          char[] swap = x;
          x = y;
          y = swap;
      }

      final int m = x.length;
      final int n = y.length;

      int ZERO_K = n;

      if (n+2 > FKP.ncols())
          FKP = new IntArray2D(2*n+1, n+2);

      for (int k = -ZERO_K; k < 0; k++) {
          int p = -k - 1;
          FKP.set(k + ZERO_K, p + 1, Math.abs(k) - 1);
          FKP.set(k + ZERO_K, p, Integer.MIN_VALUE);
      }

      FKP.set(ZERO_K, 0, -1);

      for (int k = 1; k <= ZERO_K; k++) {
          int p = k - 1;
          FKP.set(k + ZERO_K, p + 1, -1);
          FKP.set(k + ZERO_K, p, Integer.MIN_VALUE);
      }

      int p = n - m - 1;

      do {
          p++;

          for (int i = (p - (n-m))/2; i >= 1; i--) {
              brf.f(x, y, FKP, ZERO_K, n-m+i, p-i);
          }

          for (int i = (n-m+p)/2; i >= 1; i--) {
              brf.f(x, y, FKP, ZERO_K, n-m-i, p-i);
          }

          brf.f(x, y, FKP, ZERO_K, n - m, p);
      } while (FKP.get((n - m) + ZERO_K, p) != m);

      return p - 1;
  }

  /**
   * Berghel & Roach's extended Ukkonen's algorithm.
   */
  private int br(String x, String y) {
      if (x.length() > y.length()) {
          String swap = x;
          x = y;
          y = swap;
      }

      final int m = x.length();
      final int n = y.length();

      int ZERO_K = n;

      if (n+3 > FKP.ncols())
          FKP = new IntArray2D(2*n+1, n+3);

      for (int k = -ZERO_K; k < 0; k++) {
          int p = -k - 1;
          FKP.set(k + ZERO_K, p + 1, Math.abs(k) - 1);
          FKP.set(k + ZERO_K, p, Integer.MIN_VALUE);
      }

      FKP.set(ZERO_K, 0, -1);

      for (int k = 1; k <= ZERO_K; k++) {
          int p = k - 1;
          FKP.set(k + ZERO_K, p + 1, -1);
          FKP.set(k + ZERO_K, p, Integer.MIN_VALUE);
      }

      int p = n - m - 1;

      do {
          p++;

          for (int i = (p - (n-m))/2; i >= 1; i--) {
              brf.f(x, y, FKP, ZERO_K, n-m+i, p-i);
          }

          for (int i = (n-m+p)/2; i >= 1; i--) {
              brf.f(x, y, FKP, ZERO_K, n-m-i, p-i);
          }

          brf.f(x, y, FKP, ZERO_K, n - m, p);
      } while (FKP.get((n - m) + ZERO_K, p) != m);

      return p - 1;
  }

  private static class LevenshteinBRF implements BRF {
      @Override
      public void f(char[] x, char[] y, IIntArray2D FKP, int ZERO_K, int k, int p) {
          int t = max3(FKP.get(k + ZERO_K, p) + 1, FKP.get(k - 1 + ZERO_K, p), FKP.get(k + 1 + ZERO_K, p) + 1);
          int mnk = Math.min(x.length, y.length - k);

          while (t < mnk && x[t] == y[t + k]) {
              t++;
          }

          FKP.set(k + ZERO_K, p + 1, t);
      }

      @Override
      public void f(String x, String y, IIntArray2D FKP, int ZERO_K, int k, int p) {
          int t = max3(FKP.get(k + ZERO_K, p) + 1, FKP.get(k - 1 + ZERO_K, p), FKP.get(k + 1 + ZERO_K, p) + 1);
          int mnk = Math.min(x.length(), y.length() - k);

          while (t < mnk && x.charAt(t) == y.charAt(t + k)) {
              t++;
          }

          FKP.set(k + ZERO_K, p + 1, t);
      }
  }

  /**
   * Calculate FKP arrays in BR's algorithm with support of transposition operation.
   */
  private static class DamerauBRF implements BRF {
      @Override
      public void f(char[] x, char[] y, IIntArray2D FKP, int ZERO_K, int k, int p) {
          int t = FKP.get(k + ZERO_K, p) + 1;
          int mnk = Math.min(x.length, y.length - k);

          if (t >= 1 && k + t >= 1 && t < mnk) {
              if (x[t - 1] == y[k + t] && x[t] == y[k + t - 1]) {
                  t++;
              }
          }

          t = max3(FKP.get(k - 1 + ZERO_K, p), FKP.get(k + 1 + ZERO_K, p) + 1, t);

          while (t < mnk && x[t] == y[t + k]) {
              t++;
          }

          FKP.set(k + ZERO_K, p + 1, t);
      }

      @Override
      public void f(String x, String y, IIntArray2D FKP, int ZERO_K, int k, int p) {
          int t = FKP.get(k + ZERO_K, p) + 1;
          int mnk = Math.min(x.length(), y.length() - k);

          if (t >= 1 && k + t >= 1 && t < mnk) {
              if (x.charAt(t - 1) == y.charAt(k + t) && x.charAt(t) == y.charAt(k + t - 1)) {
                  t++;
              }
          }

          t = max3(FKP.get(k - 1 + ZERO_K, p), FKP.get(k + 1 + ZERO_K, p) + 1, t);

          while (t < mnk && x.charAt(t) == y.charAt(t + k)) {
              t++;
          }

          FKP.set(k + ZERO_K, p + 1, t);
      }
  }
  
  static interface BRF {
      /**
       * Calculate FKP arrays in BR's algorithm.
       */
      void f(char[] x, char[] y, IIntArray2D FKP, int ZERO_K, int k, int p);
      /**
       * Calculate FKP arrays in BR's algorithm.
       */
      void f(String x, String y, IIntArray2D FKP, int ZERO_K, int k, int p);
  }

    /**
     * Levenshtein distance between two strings allows insertion, deletion,
     * or substitution of characters. O(mn) time and O(n) space.
     * Multi-thread safe.
     */
    public static int levenshtein(String x, String y) {
        // switch parameters to use the shorter one as y to save space.
        if (x.length() < y.length()) {
            String swap = x;
            x = y;
            y = swap;
        }

        int[][] d = new int[2][y.length() + 1];

        for (int j = 0; j <= y.length(); j++) {
            d[0][j] = j;
        }

        for (int i = 1; i <= x.length(); i++) {
            d[1][0] = i;

            for (int j = 1; j <= y.length(); j++) {
                int cost = x.charAt(i - 1) == y.charAt(j - 1) ? 0 : 1;
                d[1][j] = min3(
                        d[0][j] + 1, // deletion
                        d[1][j - 1] + 1, // insertion
                        d[0][j - 1] + cost); // substitution
            }
            int[] swap = d[0];
            d[0] = d[1];
            d[1] = swap;
        }

        return d[0][y.length()];
    }

    /**
     * Levenshtein distance between two strings allows insertion, deletion,
     * or substitution of characters. O(mn) time and O(n) space.
     * Multi-thread safe.
     */
    public static int levenshtein(char[] x, char[] y) {
        // switch parameters to use the shorter one as y to save space.
        if (x.length < y.length) {
            char[] swap = x;
            x = y;
            y = swap;
        }

        int[][] d = new int[2][y.length + 1];

        for (int j = 0; j <= y.length; j++) {
            d[0][j] = j;
        }

        for (int i = 1; i <= x.length; i++) {
            d[1][0] = i;

            for (int j = 1; j <= y.length; j++) {
                int cost = x[i - 1] == y[j - 1] ? 0 : 1;
                d[1][j] = min3(
                        d[0][j] + 1, // deletion
                        d[1][j - 1] + 1, // insertion
                        d[0][j - 1] + cost); // substitution
            }
            int[] swap = d[0];
            d[0] = d[1];
            d[1] = swap;
        }

        return d[0][y.length];
    }

    /**
     * Damerau-Levenshtein distance between two strings allows insertion,
     * deletion, substitution, or transposition of characters.
     * O(mn) time and O(n) space. Multi-thread safe.
     */
    public static int damerau(String x, String y) {
        // switch parameters to use the shorter one as y to save space.
        if (x.length() < y.length()) {
            String swap = x;
            x = y;
            y = swap;
        }

        int[][] d = new int[3][y.length() + 1];

        for (int j = 0; j <= y.length(); j++) {
            d[1][j] = j;
        }

        for (int i = 1; i <= x.length(); i++) {
            d[2][0] = i;

            for (int j = 1; j <= y.length(); j++) {
                int cost = x.charAt(i-1) == y.charAt(j-1) ? 0 : 1;
                d[2][j] = min3(
                        d[1][j] + 1,       // deletion
                        d[2][j-1] + 1,       // insertion
                        d[1][j-1] + cost); // substitution

                if (i > 1 && j > 1) {
                    if (x.charAt(i-1) == y.charAt(j-2) && x.charAt(i-2) == y.charAt(j-1))
                        d[2][j] = Math.min(d[2][j], d[0][j-2] + cost);   // damerau
                }
            }

            int[] swap = d[0];
            d[0] = d[1];
            d[1] = d[2];
            d[2] = swap;
        }

        return d[1][y.length()];
    }

    /**
     * Damerau-Levenshtein distance between two strings allows insertion,
     * deletion, substitution, or transposition of characters.
     * O(mn) time and O(n) space. Multi-thread safe.
     */
    public static int damerau(char[] x, char[] y) {
        // switch parameters to use the shorter one as y to save space.
        if (x.length < y.length) {
            char[] swap = x;
            x = y;
            y = swap;
        }

        int[][] d = new int[3][y.length + 1];

        for (int j = 0; j <= y.length; j++) {
            d[1][j] = j;
        }

        for (int i = 1; i <= x.length; i++) {
            d[2][0] = i;

            for (int j = 1; j <= y.length; j++) {
                int cost = x[i-1] == y[j-1] ? 0 : 1;
                d[2][j] = min3(
                        d[1][j] + 1,       // deletion
                        d[2][j-1] + 1,       // insertion
                        d[1][j-1] + cost); // substitution

                if (i > 1 && j > 1) {
                    if (x[i-1] == y[j-2] && x[i-2] == y[j-1])
                        d[2][j] = Math.min(d[2][j], d[0][j-2] + cost);   // damerau
                }
            }

            int[] swap = d[0];
            d[0] = d[1];
            d[1] = d[2];
            d[2] = swap;
        }

        return d[1][y.length];
    }
}

Travelled to 6 computer(s): bhatertpkbcr, mqqgnosmbjvj, pyentgdyhuwx, pzhvpgtvlbxg, tvejysmllsmz, vouqrxazstgt

Snippet ID:	#1026090
Snippet name:	EditDistance (Ukkonen-optimized Levenshtein)
Eternal ID of this version:	#1026090/12
Text MD5:	8de66b6e60486cf7a6446e083e8525bd
Transpilation MD5:	f930147f105ecf72101cc5439315c298
Author:	stefan
Category:	javax
Type:	JavaX fragment (include)
Public (visible to everyone):	Yes
Archived (hidden from active list):	No
Created/modified:	2019-11-27 03:02:26
Source code size:	19786 bytes / 630 lines
Pitched / IR pitched:	No / No
Views / Downloads:	265 / 654
Version history:	11 change(s)
Referenced in:	[show references]

< > BotCompany Repo | #1026090 // EditDistance (Ukkonen-optimized Levenshtein)

JavaX fragment (include) [tags: use-pretranspiled]

1	/*******************************************************************************
2	* Copyright (c) 2010-2019 Haifeng Li
3	*
4	* Smile is free software: you can redistribute it and/or modify
5	* it under the terms of the GNU Lesser General Public License as
6	* published by the Free Software Foundation, either version 3 of
7	* the License, or (at your option) any later version.
8	*
9	* Smile is distributed in the hope that it will be useful,
10	* but WITHOUT ANY WARRANTY; without even the implied warranty of
11	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12	* GNU Lesser General Public License for more details.
13	*
14	* You should have received a copy of the GNU Lesser General Public License
15	* along with Smile. If not, see <https://www.gnu.org/licenses/>.
16	*******************************************************************************/
17
18	/**
19	* The Edit distance between two strings is a metric for measuring the amount
20	* of difference between two sequences. The Levenshtein distance between two
21	* strings is given by the minimum number of operations needed to transform one
22	* string into the other, where an operation is an insertion, deletion, or
23	* substitution of a single character. A generalization of the Levenshtein
24	* distance (Damerau-Levenshtein distance) allows the transposition of two
25	* characters as an operation.
26	* <p>
27	* Given two strings x and y of length m and n (suppose n ≥ m), this
28	* implementation takes O(ne) time and O(mn) space by an extended Ukkonen's
29	* algorithm in case of unit cost, where e is the edit distance between x and y.
30	* Thus this algorithm is output sensitive. The smaller the distance, the faster
31	* it runs.
32	* <p>
33	* For weighted cost, this implements the regular dynamic programming algorithm,
34	* which takes O(mn) time and O(m) space.
35	*
36	* @author Haifeng Li
37	*/
38	final sclass EditDistance /implements Metric<String>/ {
39	/**
40	* Weight matrix for weighted Levenshtein distance.
41	*/
42	private IIntArray2D weight;
43
44	/**
45	* Radius of Sakoe-Chiba band
46	*/
47	private double r = -1;
48
49	/**
50	* Calculate Damerau or basic Levenshitein distance.
51	*/
52	private boolean damerau = false;
53
54	/**
55	* Cost matrix. Because Java automatically initialize arrays, it
56	* takes O(mn) to declare this cost matrix every time before
57	* calculate edit distance. But the whole point of Berghel & Roach
58	* algorithm is to calculate fewer cells than O(mn). Therefore,
59	* we create this cost matrix here. Therefore, the methods using
60	* this cost matrix is not multi-thread safe.
61	*/
62	private IIntArray2D FKP;
63
64	/**
65	* The lambda to calculate FKP array.
66	*/
67	private BRF brf;
68
69
70	/**
71	* Constructor. Multi-thread safe Levenshtein distance.
72	*/
73	public EditDistance() {
74	this(false);
75	}
76
77	/**
78	* Constructor. Multi-thread safe Damerau-Levenshtein distance.
79	* @param damerau if true, calculate Damerau-Levenshtein distance
80	* instead of plain Levenshtein distance.
81	*/
82	public EditDistance(boolean damerau) {
83	this.damerau = damerau;
84	}
85
86	/**
87	* Constructor. Highly efficient Levenshtein distance but not multi-thread safe.
88	* @param maxStringLength the maximum length of strings that will be
89	* feed to this algorithm.
90	*/
91	public EditDistance(int maxStringLength) {
92	this(maxStringLength, false);
93	}
94
95	/**
96	* Constructor. Highly efficient Damerau-Levenshtein distance but not multi-thread safe.
97	* @param maxStringLength the maximum length of strings that will be
98	* feed to this algorithm.
99	* @param damerau if true, calculate Damerau-Levenshtein distance
100	* instead of plain Levenshtein distance.
101	*/
102	public EditDistance(int maxStringLength, boolean damerau) {
103	this.damerau = damerau;
104	FKP = new IntArray2D(2*maxStringLength+1, maxStringLength+2);
105	brf = damerau ? new DamerauBRF() : new LevenshteinBRF();
106	}
107
108	/**
109	* Constructor. Weighted Levenshtein distance without path
110	* constraints. Only insertion, deletion, and substitution operations are
111	* supported.
112	*/
113	public EditDistance(int[][] weight) {
114	this(weight, -1);
115	}
116
117	/**
118	* Constructor. Weighted Levenshtein distance with
119	* Sakoe-Chiba band, which improve computational cost. Only
120	* insertion, deletion, and substitution operations are supported.
121	* @param radius the window width of Sakoe-Chiba band in terms of percentage of sequence length.
122	*/
123	public EditDistance(int[][] weight, double radius) {
124	this.weight = new IntArray2D(weight);
125	this.r = radius;
126	}
127
128	@Override
129	public String toString() {
130	if (damerau) {
131	if (weight != null)
132	return String.format("Damerau-Levenshtein Distance(radius = %d, weight = %s)", r, weight.toString());
133	else
134	return "Damerau-Levenshtein Distance";
135	} else {
136	if (weight != null)
137	return String.format("Levenshtein Distance(radius = %d, weight = %s)", r, weight.toString());
138	else
139	return "Levenshtein Distance";
140	}
141	}
142
143	/**
144	* Edit distance between two strings. O(mn) time and O(n) space for weighted
145	* edit distance. O(ne) time and O(mn) space for unit cost edit distance.
146	* For weighted edit distance, this method is multi-thread safe. However,
147	* it is NOT multi-thread safe for unit cost edit distance.
148	*/
149	public double d(String x, String y) {
150	if (weight != null)
151	return weightedEdit(x, y);
152	else if (FKP == null \|\| x.length() == 1 \|\| y.length() == 1)
153	return damerau ? damerau(x, y) : levenshtein(x, y);
154	else
155	return br(x, y);
156	}
157
158	/**
159	* Edit distance between two strings. O(mn) time and O(n) space for weighted
160	* edit distance. O(ne) time and O(mn) space for unit cost edit distance.
161	* For weighted edit distance, this method is multi-thread safe. However,
162	* it is NOT multi-thread safe for unit cost edit distance.
163	*/
164	public double d(char[] x, char[] y) {
165	if (weight != null)
166	return weightedEdit(x, y);
167	else if (FKP == null \|\| x.length == 1 \|\| y.length == 1)
168	return damerau ? damerau(x, y) : levenshtein(x, y);
169	else
170	return br(x, y);
171	}
172
173	/**
174	* Weighted edit distance.
175	*/
176	private double weightedEdit(char[] x, char[] y) {
177	// switch parameters to use the shorter one as y to save space.
178	if (x.length < y.length) {
179	char[] swap = x;
180	x = y;
181	y = swap;
182	}
183
184	int radius = (int) Math.round(r * Math.max(x.length, y.length));
185
186	double[][] d = new double[2][y.length + 1];
187
188	d[0][0] = 0.0;
189	for (int j = 1; j <= y.length; j++) {
190	d[0][j] = d[0][j - 1] + weight.get(0, y[j]);
191	}
192
193	for (int i = 1; i <= x.length; i++) {
194	d[1][0] = d[0][0] + weight.get(x[i], 0);
195
196	int start = 1;
197	int end = y.length;
198
199	if (radius > 0) {
200	start = i - radius;
201	if (start > 1)
202	d[1][start - 1] = Double.POSITIVE_INFINITY;
203	else
204	start = 1;
205
206	end = i + radius;
207	if (end < y.length)
208	d[1][end+1] = Double.POSITIVE_INFINITY;
209	else
210	end = y.length;
211	}
212
213	for (int j = start; j <= end; j++) {
214	double cost = weight.get(x[i - 1], y[j - 1]);
215	d[1][j] = min3(
216	d[0][j] + weight.get(x[i - 1], 0), // deletion
217	d[1][j - 1] + weight.get(0, y[j - 1]), // insertion
218	d[0][j - 1] + cost); // substitution
219	}
220
221	double[] swap = d[0];
222	d[0] = d[1];
223	d[1] = swap;
224	}
225
226	return d[0][y.length];
227	}
228
229	/**
230	* Weighted edit distance.
231	*/
232	private double weightedEdit(String x, String y) {
233	// switch parameters to use the shorter one as y to save space.
234	if (x.length() < y.length()) {
235	String swap = x;
236	x = y;
237	y = swap;
238	}
239
240	int radius = (int) Math.round(r * Math.max(x.length(), y.length()));
241
242	double[][] d = new double[2][y.length() + 1];
243
244	d[0][0] = 0.0;
245	for (int j = 1; j <= y.length(); j++) {
246	d[0][j] = d[0][j - 1] + weight.get(0, y.charAt(j));
247	}
248
249	for (int i = 1; i <= x.length(); i++) {
250	d[1][0] = d[0][0] + weight.get(x.charAt(i), 0);
251
252	int start = 1;
253	int end = y.length();
254
255	if (radius > 0) {
256	start = i - radius;
257	if (start > 1)
258	d[1][start - 1] = Double.POSITIVE_INFINITY;
259	else
260	start = 1;
261
262	end = i + radius;
263	if (end < y.length())
264	d[1][end+1] = Double.POSITIVE_INFINITY;
265	else
266	end = y.length();
267	}
268
269	for (int j = start; j <= end; j++) {
270	double cost = weight.get(x.charAt(i - 1), y.charAt(j - 1));
271	d[1][j] = min3(
272	d[0][j] + weight.get(x.charAt(i - 1), 0), // deletion
273	d[1][j - 1] + weight.get(0, y.charAt(j - 1)), // insertion
274	d[0][j - 1] + cost); // substitution
275	}
276
277	double[] swap = d[0];
278	d[0] = d[1];
279	d[1] = swap;
280	}
281
282	return d[0][y.length()];
283	}
284
285	/**
286	* Berghel & Roach's extended Ukkonen's algorithm.
287	*/
288	private int br(char[] x, char[] y) {
289	if (x.length > y.length) {
290	char[] swap = x;
291	x = y;
292	y = swap;
293	}
294
295	final int m = x.length;
296	final int n = y.length;
297
298	int ZERO_K = n;
299
300	if (n+2 > FKP.ncols())
301	FKP = new IntArray2D(2*n+1, n+2);
302
303	for (int k = -ZERO_K; k < 0; k++) {
304	int p = -k - 1;
305	FKP.set(k + ZERO_K, p + 1, Math.abs(k) - 1);
306	FKP.set(k + ZERO_K, p, Integer.MIN_VALUE);
307	}
308
309	FKP.set(ZERO_K, 0, -1);
310
311	for (int k = 1; k <= ZERO_K; k++) {
312	int p = k - 1;
313	FKP.set(k + ZERO_K, p + 1, -1);
314	FKP.set(k + ZERO_K, p, Integer.MIN_VALUE);
315	}
316
317	int p = n - m - 1;
318
319	do {
320	p++;
321
322	for (int i = (p - (n-m))/2; i >= 1; i--) {
323	brf.f(x, y, FKP, ZERO_K, n-m+i, p-i);
324	}
325
326	for (int i = (n-m+p)/2; i >= 1; i--) {
327	brf.f(x, y, FKP, ZERO_K, n-m-i, p-i);
328	}
329
330	brf.f(x, y, FKP, ZERO_K, n - m, p);
331	} while (FKP.get((n - m) + ZERO_K, p) != m);
332
333	return p - 1;
334	}
335
336	/**
337	* Berghel & Roach's extended Ukkonen's algorithm.
338	*/
339	private int br(String x, String y) {
340	if (x.length() > y.length()) {
341	String swap = x;
342	x = y;
343	y = swap;
344	}
345
346	final int m = x.length();
347	final int n = y.length();
348
349	int ZERO_K = n;
350
351	if (n+3 > FKP.ncols())
352	FKP = new IntArray2D(2*n+1, n+3);
353
354	for (int k = -ZERO_K; k < 0; k++) {
355	int p = -k - 1;
356	FKP.set(k + ZERO_K, p + 1, Math.abs(k) - 1);
357	FKP.set(k + ZERO_K, p, Integer.MIN_VALUE);
358	}
359
360	FKP.set(ZERO_K, 0, -1);
361
362	for (int k = 1; k <= ZERO_K; k++) {
363	int p = k - 1;
364	FKP.set(k + ZERO_K, p + 1, -1);
365	FKP.set(k + ZERO_K, p, Integer.MIN_VALUE);
366	}
367
368	int p = n - m - 1;
369
370	do {
371	p++;
372
373	for (int i = (p - (n-m))/2; i >= 1; i--) {
374	brf.f(x, y, FKP, ZERO_K, n-m+i, p-i);
375	}
376
377	for (int i = (n-m+p)/2; i >= 1; i--) {
378	brf.f(x, y, FKP, ZERO_K, n-m-i, p-i);
379	}
380
381	brf.f(x, y, FKP, ZERO_K, n - m, p);
382	} while (FKP.get((n - m) + ZERO_K, p) != m);
383
384	return p - 1;
385	}
386
387	private static class LevenshteinBRF implements BRF {
388	@Override
389	public void f(char[] x, char[] y, IIntArray2D FKP, int ZERO_K, int k, int p) {
390	int t = max3(FKP.get(k + ZERO_K, p) + 1, FKP.get(k - 1 + ZERO_K, p), FKP.get(k + 1 + ZERO_K, p) + 1);
391	int mnk = Math.min(x.length, y.length - k);
392
393	while (t < mnk && x[t] == y[t + k]) {
394	t++;
395	}
396
397	FKP.set(k + ZERO_K, p + 1, t);
398	}
399
400	@Override
401	public void f(String x, String y, IIntArray2D FKP, int ZERO_K, int k, int p) {
402	int t = max3(FKP.get(k + ZERO_K, p) + 1, FKP.get(k - 1 + ZERO_K, p), FKP.get(k + 1 + ZERO_K, p) + 1);
403	int mnk = Math.min(x.length(), y.length() - k);
404
405	while (t < mnk && x.charAt(t) == y.charAt(t + k)) {
406	t++;
407	}
408
409	FKP.set(k + ZERO_K, p + 1, t);
410	}
411	}
412
413	/**
414	* Calculate FKP arrays in BR's algorithm with support of transposition operation.
415	*/
416	private static class DamerauBRF implements BRF {
417	@Override
418	public void f(char[] x, char[] y, IIntArray2D FKP, int ZERO_K, int k, int p) {
419	int t = FKP.get(k + ZERO_K, p) + 1;
420	int mnk = Math.min(x.length, y.length - k);
421
422	if (t >= 1 && k + t >= 1 && t < mnk) {
423	if (x[t - 1] == y[k + t] && x[t] == y[k + t - 1]) {
424	t++;
425	}
426	}
427
428	t = max3(FKP.get(k - 1 + ZERO_K, p), FKP.get(k + 1 + ZERO_K, p) + 1, t);
429
430	while (t < mnk && x[t] == y[t + k]) {
431	t++;
432	}
433
434	FKP.set(k + ZERO_K, p + 1, t);
435	}
436
437	@Override
438	public void f(String x, String y, IIntArray2D FKP, int ZERO_K, int k, int p) {
439	int t = FKP.get(k + ZERO_K, p) + 1;
440	int mnk = Math.min(x.length(), y.length() - k);
441
442	if (t >= 1 && k + t >= 1 && t < mnk) {
443	if (x.charAt(t - 1) == y.charAt(k + t) && x.charAt(t) == y.charAt(k + t - 1)) {
444	t++;
445	}
446	}
447
448	t = max3(FKP.get(k - 1 + ZERO_K, p), FKP.get(k + 1 + ZERO_K, p) + 1, t);
449
450	while (t < mnk && x.charAt(t) == y.charAt(t + k)) {
451	t++;
452	}
453
454	FKP.set(k + ZERO_K, p + 1, t);
455	}
456	}
457
458	static interface BRF {
459	/**
460	* Calculate FKP arrays in BR's algorithm.
461	*/
462	void f(char[] x, char[] y, IIntArray2D FKP, int ZERO_K, int k, int p);
463	/**
464	* Calculate FKP arrays in BR's algorithm.
465	*/
466	void f(String x, String y, IIntArray2D FKP, int ZERO_K, int k, int p);
467	}
468
469	/**
470	* Levenshtein distance between two strings allows insertion, deletion,
471	* or substitution of characters. O(mn) time and O(n) space.
472	* Multi-thread safe.
473	*/
474	public static int levenshtein(String x, String y) {
475	// switch parameters to use the shorter one as y to save space.
476	if (x.length() < y.length()) {
477	String swap = x;
478	x = y;
479	y = swap;
480	}
481
482	int[][] d = new int[2][y.length() + 1];
483
484	for (int j = 0; j <= y.length(); j++) {
485	d[0][j] = j;
486	}
487
488	for (int i = 1; i <= x.length(); i++) {
489	d[1][0] = i;
490
491	for (int j = 1; j <= y.length(); j++) {
492	int cost = x.charAt(i - 1) == y.charAt(j - 1) ? 0 : 1;
493	d[1][j] = min3(
494	d[0][j] + 1, // deletion
495	d[1][j - 1] + 1, // insertion
496	d[0][j - 1] + cost); // substitution
497	}
498	int[] swap = d[0];
499	d[0] = d[1];
500	d[1] = swap;
501	}
502
503	return d[0][y.length()];
504	}
505
506	/**
507	* Levenshtein distance between two strings allows insertion, deletion,
508	* or substitution of characters. O(mn) time and O(n) space.
509	* Multi-thread safe.
510	*/
511	public static int levenshtein(char[] x, char[] y) {
512	// switch parameters to use the shorter one as y to save space.
513	if (x.length < y.length) {
514	char[] swap = x;
515	x = y;
516	y = swap;
517	}
518
519	int[][] d = new int[2][y.length + 1];
520
521	for (int j = 0; j <= y.length; j++) {
522	d[0][j] = j;
523	}
524
525	for (int i = 1; i <= x.length; i++) {
526	d[1][0] = i;
527
528	for (int j = 1; j <= y.length; j++) {
529	int cost = x[i - 1] == y[j - 1] ? 0 : 1;
530	d[1][j] = min3(
531	d[0][j] + 1, // deletion
532	d[1][j - 1] + 1, // insertion
533	d[0][j - 1] + cost); // substitution
534	}
535	int[] swap = d[0];
536	d[0] = d[1];
537	d[1] = swap;
538	}
539
540	return d[0][y.length];
541	}
542
543	/**
544	* Damerau-Levenshtein distance between two strings allows insertion,
545	* deletion, substitution, or transposition of characters.
546	* O(mn) time and O(n) space. Multi-thread safe.
547	*/
548	public static int damerau(String x, String y) {
549	// switch parameters to use the shorter one as y to save space.
550	if (x.length() < y.length()) {
551	String swap = x;
552	x = y;
553	y = swap;
554	}
555
556	int[][] d = new int[3][y.length() + 1];
557
558	for (int j = 0; j <= y.length(); j++) {
559	d[1][j] = j;
560	}
561
562	for (int i = 1; i <= x.length(); i++) {
563	d[2][0] = i;
564
565	for (int j = 1; j <= y.length(); j++) {
566	int cost = x.charAt(i-1) == y.charAt(j-1) ? 0 : 1;
567	d[2][j] = min3(
568	d[1][j] + 1, // deletion
569	d[2][j-1] + 1, // insertion
570	d[1][j-1] + cost); // substitution
571
572	if (i > 1 && j > 1) {
573	if (x.charAt(i-1) == y.charAt(j-2) && x.charAt(i-2) == y.charAt(j-1))
574	d[2][j] = Math.min(d[2][j], d[0][j-2] + cost); // damerau
575	}
576	}
577
578	int[] swap = d[0];
579	d[0] = d[1];
580	d[1] = d[2];
581	d[2] = swap;
582	}
583
584	return d[1][y.length()];
585	}
586
587	/**
588	* Damerau-Levenshtein distance between two strings allows insertion,
589	* deletion, substitution, or transposition of characters.
590	* O(mn) time and O(n) space. Multi-thread safe.
591	*/
592	public static int damerau(char[] x, char[] y) {
593	// switch parameters to use the shorter one as y to save space.
594	if (x.length < y.length) {
595	char[] swap = x;
596	x = y;
597	y = swap;
598	}
599
600	int[][] d = new int[3][y.length + 1];
601
602	for (int j = 0; j <= y.length; j++) {
603	d[1][j] = j;
604	}
605
606	for (int i = 1; i <= x.length; i++) {
607	d[2][0] = i;
608
609	for (int j = 1; j <= y.length; j++) {
610	int cost = x[i-1] == y[j-1] ? 0 : 1;
611	d[2][j] = min3(
612	d[1][j] + 1, // deletion
613	d[2][j-1] + 1, // insertion
614	d[1][j-1] + cost); // substitution
615
616	if (i > 1 && j > 1) {
617	if (x[i-1] == y[j-2] && x[i-2] == y[j-1])
618	d[2][j] = Math.min(d[2][j], d[0][j-2] + cost); // damerau
619	}
620	}
621
622	int[] swap = d[0];
623	d[0] = d[1];
624	d[1] = d[2];
625	d[2] = swap;
626	}
627
628	return d[1][y.length];
629	}
630	}