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

   1 /*\r
   2 Jazzy - a Java library for Spell Checking\r
   3 Copyright (C) 2001 Mindaugas Idzelis\r
   4 Full text of license can be found in LICENSE.txt\r
   5 \r
   6 This library is free software; you can redistribute it and/or\r
   7 modify it under the terms of the GNU Lesser General Public\r
   8 License as published by the Free Software Foundation; either\r
   9 version 2.1 of the License, or (at your option) any later version.\r
  10 \r
  11 This library is distributed in the hope that it will be useful,\r
  12 but WITHOUT ANY WARRANTY; without even the implied warranty of\r
  13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU\r
  14 Lesser General Public License for more details.\r
  15 \r
  16 You should have received a copy of the GNU Lesser General Public\r
  17 License along with this library; if not, write to the Free Software\r
  18 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA\r
  19 */\r
  20 package com.swabunga.spell.engine;\r
  21 \r
  22 import java.io.BufferedReader;\r
  23 import java.io.InputStreamReader;\r
  24 \r
  25 /**\r
  26  * This class is based on Levenshtein Distance algorithms, and it calculates how similar two words are.\r
  27  * If the words are identical, then the distance is 0. The more that the words have in common, the lower the distance value.\r
  28  * The distance value is based on how many operations it takes to get from one word to the other. Possible operations are\r
  29  * swapping characters, adding a character, deleting a character, and substituting a character.\r
  30  * The resulting distance is the sum of these operations weighted by their cost, which can be set in the Configuration object.\r
  31  * When there are multiple ways to convert one word into the other, the lowest cost distance is returned.\r
  32  * <br/>\r
  33  * Another way to think about this: what are the cheapest operations that would have to be done on the "original" word to end up\r
  34  * with the "similar" word? Each operation has a cost, and these are added up to get the distance.\r
  35  * <br/>\r
  36  *\r
  37  * @see com.swabunga.spell.engine.Configuration#COST_REMOVE_CHAR\r
  38  * @see com.swabunga.spell.engine.Configuration#COST_INSERT_CHAR\r
  39  * @see com.swabunga.spell.engine.Configuration#COST_SUBST_CHARS\r
  40  * @see com.swabunga.spell.engine.Configuration#COST_SWAP_CHARS\r
  41  *\r
  42  */\r
  43 \r
  44 public class EditDistance {\r
  45 \r
  46   /**\r
  47    * Fetches the spell engine configuration properties.\r
  48    */\r
  49   public static Configuration config = Configuration.getConfiguration();\r
  50 \r
  51   /**\r
  52    * get the weights for each possible operation\r
  53    */\r
  54   static final int costOfDeletingSourceCharacter = config.getInteger(Configuration.COST_REMOVE_CHAR);\r
  55   static final int costOfInsertingSourceCharacter = config.getInteger(Configuration.COST_INSERT_CHAR);\r
  56   static final int costOfSubstitutingLetters = config.getInteger(Configuration.COST_SUBST_CHARS);\r
  57   static final int costOfSwappingLetters = config.getInteger(Configuration.COST_SWAP_CHARS);\r
  58   static final int costOfChangingCase = config.getInteger(Configuration.COST_CHANGE_CASE);  \r
  59 \r
  60   /**\r
  61    * Evaluates the distance between two words.\r
  62    * \r
  63    * @param word One word to evaluates\r
  64    * @param similar The other word to evaluates\r
  65    * @return a number representing how easy or complex it is to transform on\r
  66    * word into a similar one.\r
  67    */\r
  68   public static final int getDistance(String word, String similar) {\r
  69         return getDistance(word,similar,null);\r
  70   }  \r
  71   \r
  72   /**\r
  73    * Evaluates the distance between two words.\r
  74    * \r
  75    * @param word One word to evaluates\r
  76    * @param similar The other word to evaluates\r
  77    * @return a number representing how easy or complex it is to transform on\r
  78    * word into a similar one.\r
  79    */\r
  80   public static final int getDistance(String word, String similar, int[][] matrix) {\r
  81     /* JMH Again, there is no need to have a global class matrix variable\r
  82      *  in this class. I have removed it and made the getDistance static final\r
  83      * DMV: I refactored this method to make it more efficient, more readable, and simpler.\r
  84      * I also fixed a bug with how the distance was being calculated. You could get wrong\r
  85      * distances if you compared ("abc" to "ab") depending on what you had setup your\r
  86      * COST_REMOVE_CHAR and EDIT_INSERTION_COST values to - that is now fixed.\r
  87      * WRS: I added a distance for case comparison, so a misspelling of "i" would be closer to "I" than\r
  88      * to "a".\r
  89      */\r
  90 \r
  91         //Allocate memory outside of the loops. \r
  92         int i;\r
  93         int j;\r
  94         int costOfSubst;\r
  95         int costOfSwap;\r
  96         int costOfDelete;\r
  97         int costOfInsertion;\r
  98         int costOfCaseChange;\r
  99         \r
 100         boolean isSwap;\r
 101         char sourceChar = 0;\r
 102         char otherChar = 0;\r
 103         \r
 104     int a_size = word.length() + 1;\r
 105     int b_size = similar.length() + 1;\r
 106   \r
 107     \r
 108     //Only allocate new memory if we need a bigger matrix. \r
 109     if (matrix == null || matrix.length < a_size || matrix[0].length < b_size)\r
 110         matrix = new int[a_size][b_size];\r
 111       \r
 112     matrix[0][0] = 0;\r
 113 \r
 114     for (i = 1; i != a_size; ++i)\r
 115       matrix[i][0] = matrix[i - 1][0] + costOfInsertingSourceCharacter; //initialize the first column\r
 116 \r
 117     for (j = 1; j != b_size; ++j)\r
 118       matrix[0][j] = matrix[0][j - 1] + costOfDeletingSourceCharacter; //initalize the first row\r
 119 \r
 120     for (i = 1; i != a_size; ++i) {\r
 121       sourceChar = word.charAt(i-1);\r
 122       for (j = 1; j != b_size; ++j) {\r
 123 \r
 124         otherChar = similar.charAt(j-1);\r
 125         if (sourceChar == otherChar) {\r
 126           matrix[i][j] = matrix[i - 1][j - 1]; //no change required, so just carry the current cost up\r
 127           continue;\r
 128         }\r
 129 \r
 130         costOfSubst = costOfSubstitutingLetters + matrix[i - 1][j - 1];\r
 131         //if needed, add up the cost of doing a swap\r
 132         costOfSwap = Integer.MAX_VALUE;\r
 133 \r
 134         isSwap = (i != 1) && (j != 1) && sourceChar == similar.charAt(j - 2) && word.charAt(i - 2) == otherChar;\r
 135         if (isSwap)\r
 136           costOfSwap = costOfSwappingLetters + matrix[i - 2][j - 2];\r
 137 \r
 138         costOfDelete = costOfDeletingSourceCharacter + matrix[i][j - 1];\r
 139         costOfInsertion = costOfInsertingSourceCharacter + matrix[i - 1][j];\r
 140 \r
 141         costOfCaseChange = Integer.MAX_VALUE;\r
 142        \r
 143         if (equalIgnoreCase(sourceChar, otherChar))\r
 144           costOfCaseChange = costOfChangingCase + matrix[i - 1][j - 1];\r
 145         \r
 146         matrix[i][j] = minimum(costOfSubst, costOfSwap, costOfDelete, costOfInsertion, costOfCaseChange);\r
 147       }\r
 148     }\r
 149 \r
 150     return matrix[a_size - 1][b_size - 1];\r
 151   }\r
 152 \r
 153   /**\r
 154    * checks to see if the two charactors are equal ignoring case. \r
 155    * @param ch1\r
 156    * @param ch2\r
 157    * @return boolean\r
 158    */\r
 159   private static boolean equalIgnoreCase(char ch1, char ch2) {\r
 160     if (ch1 == ch2)\r
 161     {\r
 162         return true;\r
 163     }\r
 164     else\r
 165     {\r
 166         return (Character.toLowerCase(ch1) == Character.toLowerCase(ch2));\r
 167     }\r
 168   }\r
 169   \r
 170   /**\r
 171    * For debugging, this creates a string that represents the matrix. To read the matrix, look at any square. That is the cost to get from\r
 172    * the partial letters along the top to the partial letters along the side.\r
 173    * @param src - the source string that the matrix columns are based on\r
 174    * @param dest - the dest string that the matrix rows are based on\r
 175    * @param matrix - a two dimensional array of costs (distances)\r
 176    * @return String\r
 177    */\r
 178   @SuppressWarnings("unused")\r
 179 static private String dumpMatrix(String src, String dest, int matrix[][]) {\r
 180     StringBuffer s = new StringBuffer("");\r
 181 \r
 182     int cols = matrix.length -1;\r
 183     int rows = matrix[0].length -1;\r
 184 \r
 185     for (int i = 0; i < cols + 1; i++) {\r
 186       for (int j = 0; j < rows + 1; j++) {\r
 187         if (i == 0 && j == 0) {\r
 188           s.append("\n ");\r
 189           continue;\r
 190 \r
 191         }\r
 192         if (i == 0) {\r
 193           s.append("|   ");\r
 194           s.append(dest.charAt(j - 1));\r
 195           continue;\r
 196         }\r
 197         if (j == 0) {\r
 198           s.append(src.charAt(i - 1));\r
 199           continue;\r
 200         }\r
 201         String num = Integer.toString(matrix[i - 1][j - 1]);\r
 202         int padding = 4 - num.length();\r
 203         s.append("|");\r
 204         for (int k = 0; k < padding; k++)\r
 205           s.append(' ');\r
 206         s.append(num);\r
 207       }\r
 208       s.append('\n');\r
 209     }\r
 210     return s.toString();\r
 211 \r
 212   }\r
 213 \r
 214 \r
 215   static private int minimum(int a, int b, int c, int d, int e) {\r
 216     int mi = a;\r
 217     if (b < mi)\r
 218       mi = b;\r
 219     if (c < mi)\r
 220       mi = c;\r
 221     if (d < mi)\r
 222       mi = d;\r
 223     if (e < mi)\r
 224       mi = e;\r
 225 \r
 226     return mi;\r
 227   }\r
 228 \r
 229   /**\r
 230    * For testing edit distances\r
 231    * @param args an array of two strings we want to evaluate their distances.\r
 232    * @throws java.lang.Exception when problems occurs during reading args.\r
 233    */\r
 234   public static void main(String[] args) throws Exception {\r
 235     BufferedReader stdin = new BufferedReader(new InputStreamReader(System.in));\r
 236     int[][] matrix = new int[0][0]; \r
 237     while (true) {\r
 238 \r
 239       String input1 = stdin.readLine();\r
 240       if (input1 == null || input1.length() == 0)\r
 241         break;\r
 242 \r
 243       String input2 = stdin.readLine();\r
 244       if (input2 == null || input2.length() == 0)\r
 245         break;\r
 246 \r
 247       System.out.println(EditDistance.getDistance(input1, input2,matrix));\r
 248     }\r
 249     System.out.println("done");\r
 250   }\r
 251 }\r
 252 \r
 253 \r