ekit/com/swabunga/spell/engine/EditDistance.java

   1 package com.swabunga.spell.engine;
   2
   3 import java.io.BufferedReader;
   4 import java.io.InputStreamReader;
   5
   6 /** JMH Again, there is no need to have a global class matrix variable
   7  *  in this class. I have removed it and made the getDistance static final
   8  */
   9 public class EditDistance {
  10
  11         public static Configuration config = Configuration.getConfiguration();
  12
  13     public static final int getDistance(String word, String similar) {
  14         int a_size = word.length() + 1;
  15         int b_size = similar.length() + 1;
  16         int[][] matrix = new int[a_size][b_size];
  17         matrix[0][0] = 0;
  18         for (int j = 1; j != b_size; ++j)
  19             matrix[0][j] = matrix[0][j - 1] + config.getInteger(Configuration.EDIT_DEL1);
  20         word = " " + word;
  21         similar = " " + similar;
  22         int te;
  23         for (int i = 1; i != a_size; ++i) {
  24             matrix[i][0] = matrix[i - 1][0] + config.getInteger(Configuration.EDIT_DEL2);
  25             for (int j = 1; j != b_size; ++j) {
  26                 if (word.charAt(i) == similar.charAt(j)) {
  27                     matrix[i][j] = matrix[i - 1][j - 1];
  28                 } else {
  29                     matrix[i][j] = config.getInteger(Configuration.EDIT_SUB) + matrix[i - 1][j - 1];
  30                     if (i != 1 && j != 1 &&
  31                             word.charAt(i) == similar.charAt(j - 1) && word.charAt(i - 1) == similar.charAt(j)) {
  32                         te = config.getInteger(Configuration.EDIT_SWAP) + matrix[i - 2][j - 2];
  33                         if (te < matrix[i][j]) matrix[i][j] = te;
  34                     }
  35                     te = config.getInteger(Configuration.EDIT_DEL1) + matrix[i - 1][j];
  36                     if (te < matrix[i][j]) matrix[i][j] = te;
  37                     te = config.getInteger(Configuration.EDIT_DEL2) + matrix[i][j - 1];
  38                     if (te < matrix[i][j]) matrix[i][j] = te;
  39                 }
  40             }
  41         }
  42         return matrix[a_size - 1][b_size - 1];
  43     }
  44
  45     public static void main(String[] args) throws Exception {
  46         EditDistance ed = new EditDistance();
  47         BufferedReader stdin = new BufferedReader(new InputStreamReader(System.in));
  48         String input = "";
  49         String input2 = "";
  50         while (input != null) {
  51             input = stdin.readLine();
  52             input2 = stdin.readLine();
  53             System.out.println(ed.getDistance(input, input2));
  54         }
  55     }
  56 }
  57
  58