
Jazzy example source code file (EditDistance.java)
The Jazzy EditDistance.java source code/* Jazzy  a Java library for Spell Checking Copyright (C) 2001 Mindaugas Idzelis Full text of license can be found in LICENSE.txt This library 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 2.1 of the License, or (at your option) any later version. This library 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 this library; if not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 021101301 USA */ package com.swabunga.spell.engine; import java.io.BufferedReader; import java.io.InputStreamReader; /** * This class is based on Levenshtein Distance algorithms, and it calculates how similar two words are. * If the words are identitical, then the distance is 0. The more that the words have in common, the lower the distance value. * The distance value is based on how many operations it takes to get from one word to the other. Possible operations are * swapping characters, adding a character, deleting a character, and substituting a character. * The resulting distance is the sum of these operations weighted by their cost, which can be set in the Configuration object. * When there are multiple ways to convert one word into the other, the lowest cost distance is returned. * <br/> * Another way to think about this: what are the cheapest operations that would have to be done on the "original" word to end up * with the "similar" word? Each operation has a cost, and these are added up to get the distance. * <br/> * * @see com.swabunga.spell.engine.Configuration#COST_REMOVE_CHAR * @see com.swabunga.spell.engine.Configuration#COST_INSERT_CHAR * @see com.swabunga.spell.engine.Configuration#COST_SUBST_CHARS * @see com.swabunga.spell.engine.Configuration#COST_SWAP_CHARS * */ public class EditDistance { /** * JMH Again, there is no need to have a global class matrix variable * in this class. I have removed it and made the getDistance static final * * DMV: I refactored this method to make it more efficient, more readable, and simpler. * I also fixed a bug with how the distance was being calculated. You could get wrong * distances if you compared ("abc" to "ab") depending on what you had setup your * COST_REMOVE_CHAR and EDIT_INSERTION_COST values to  that is now fixed. * * WRS: I added a distance for case comparison, so a misspelling of "i" would be closer to "I" than * to "a". */ public static Configuration config = Configuration.getConfiguration(); public static final int getDistance(String word, String similar) { //get the weights for each possible operation final int costOfDeletingSourceCharacter = config.getInteger(Configuration.COST_REMOVE_CHAR); final int costOfInsertingSourceCharacter = config.getInteger(Configuration.COST_INSERT_CHAR); final int costOfSubstitutingLetters = config.getInteger(Configuration.COST_SUBST_CHARS); final int costOfSwappingLetters = config.getInteger(Configuration.COST_SWAP_CHARS); final int costOfChangingCase = config.getInteger(Configuration.COST_CHANGE_CASE); int a_size = word.length() + 1; int b_size = similar.length() + 1; int[][] matrix = new int[a_size][b_size]; matrix[0][0] = 0; for (int i = 1; i != a_size; ++i) matrix[i][0] = matrix[i  1][0] + costOfInsertingSourceCharacter; //initialize the first column for (int j = 1; j != b_size; ++j) matrix[0][j] = matrix[0][j  1] + costOfDeletingSourceCharacter; //initalize the first row word = " " + word; similar = " " + similar; for (int i = 1; i != a_size; ++i) { char sourceChar = word.charAt(i); for (int j = 1; j != b_size; ++j) { char otherChar = similar.charAt(j); if (sourceChar == otherChar) { matrix[i][j] = matrix[i  1][j  1]; //no change required, so just carry the current cost up continue; } int costOfSubst = costOfSubstitutingLetters + matrix[i  1][j  1]; //if needed, add up the cost of doing a swap int costOfSwap = Integer.MAX_VALUE; boolean isSwap = (i != 1) && (j != 1) && sourceChar == similar.charAt(j  1) && word.charAt(i  1) == otherChar; if (isSwap) costOfSwap = costOfSwappingLetters + matrix[i  2][j  2]; int costOfDelete = costOfDeletingSourceCharacter + matrix[i][j  1]; int costOfInsertion = costOfInsertingSourceCharacter + matrix[i  1][j]; int costOfCaseChange = Integer.MAX_VALUE; String strSrcChar = "" + sourceChar; String strOtherChar = "" + otherChar; if (strSrcChar.compareToIgnoreCase(strOtherChar) == 0) costOfCaseChange = costOfChangingCase + matrix[i  1][j  1]; matrix[i][j] = minimum(costOfSubst, costOfSwap, costOfDelete, costOfInsertion, costOfCaseChange); } } int cost = matrix[a_size  1][b_size  1]; if (false) System.out.println(dumpMatrix(word, similar, matrix)); return cost; } /** * 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 * the partial letters along the top to the partial letters along the side. * @param src  the source string that the matrix columns are based on * @param dest  the dest string that the matrix rows are based on * @param matrix  a two dimensional array of costs (distances) * @return String */ static private String dumpMatrix(String src, String dest, int matrix[][]) { StringBuffer s = new StringBuffer(""); int cols = matrix.length; int rows = matrix[0].length; for (int i = 0; i < cols + 1; i++) { for (int j = 0; j < rows + 1; j++) { if (i == 0 && j == 0) { s.append("\n "); continue; } if (i == 0) { s.append(" "); s.append(dest.charAt(j  1)); continue; } if (j == 0) { s.append(src.charAt(i  1)); continue; } String num = Integer.toString(matrix[i  1][j  1]); int padding = 4  num.length(); s.append(""); for (int k = 0; k < padding; k++) s.append(' '); s.append(num); } s.append('\n'); } return s.toString(); } static private int minimum(int a, int b, int c, int d, int e) { int mi = a; if (b < mi) mi = b; if (c < mi) mi = c; if (d < mi) mi = d; if (e < mi) mi = e; return mi; } public static void main(String[] args) throws Exception { BufferedReader stdin = new BufferedReader(new InputStreamReader(System.in)); while (true) { String input1 = stdin.readLine(); if (input1 == null  input1.length() == 0) break; String input2 = stdin.readLine(); if (input2 == null  input2.length() == 0) break; System.out.println(EditDistance.getDistance(input1, input2)); } System.out.println("done"); } } Other Jazzy examples (source code examples)Here is a short list of links related to this Jazzy EditDistance.java source code file: 
... this post is sponsored by my books ...  
#1 New Release! 
FP Best Seller 
Copyright 19982021 Alvin Alexander, alvinalexander.com
All Rights Reserved.
A percentage of advertising revenue from
pages under the /java/jwarehouse
URI on this website is
paid back to open source projects.