net.sourceforge.phpeclipse/src/net/sourceforge/phpdt/internal/ui/text/spelling/engine/DefaultPhoneticDistanceAlgorithm.java

   1 /*******************************************************************************
   2  * Copyright (c) 2000, 2003 IBM Corporation and others.
   3  * All rights reserved. This program and the accompanying materials
   4  * are made available under the terms of the Common Public License v1.0
   5  * which accompanies this distribution, and is available at
   6  * http://www.eclipse.org/legal/cpl-v10.html
   7  *
   8  * Contributors:
   9  *     IBM Corporation - initial API and implementation
  10  *******************************************************************************/
  11
  12 package net.sourceforge.phpdt.internal.ui.text.spelling.engine;
  13
  14 /**
  15  * Default phonetic distance algorithm for english words.
  16  * <p>
  17  * This algorithm implements the Levenshtein text edit distance.
  18  * </p>
  19  *
  20  * @since 3.0
  21  */
  22 public final class DefaultPhoneticDistanceAlgorithm implements IPhoneticDistanceAlgorithm {
  23
  24         /** The change case cost */
  25         public static final int COST_CASE= 10;
  26
  27         /** The insert character cost */
  28         public static final int COST_INSERT= 95;
  29
  30         /** The remove character cost */
  31         public static final int COST_REMOVE= 95;
  32
  33         /** The substitute characters cost */
  34         public static final int COST_SUBSTITUTE= 100;
  35
  36         /** The swap characters cost */
  37         public static final int COST_SWAP= 90;
  38
  39         /*
  40          * @see org.eclipse.spelling.done.IPhoneticDistanceAlgorithm#getDistance(java.lang.String,java.lang.String)
  41          */
  42         public final int getDistance(final String from, final String to) {
  43
  44                 final char[] first= (" " + from).toCharArray(); //$NON-NLS-1$
  45                 final char[] second= (" " + to).toCharArray(); //$NON-NLS-1$
  46
  47                 final int rows= first.length;
  48                 final int columns= second.length;
  49
  50                 final int[][] metric= new int[rows][columns];
  51                 for (int column= 1; column < columns; column++)
  52                         metric[0][column]= metric[0][column - 1] + COST_REMOVE;
  53
  54                 for (int row= 1; row < rows; row++)
  55                         metric[row][0]= metric[row - 1][0] + COST_INSERT;
  56
  57                 char source, target;
  58
  59                 int swap= Integer.MAX_VALUE;
  60                 int change= Integer.MAX_VALUE;
  61
  62                 int minimum, diagonal, insert, remove;
  63                 for (int row= 1; row < rows; row++) {
  64
  65                         source= first[row];
  66                         for (int column= 1; column < columns; column++) {
  67
  68                                 target= second[column];
  69                                 diagonal= metric[row - 1][column - 1];
  70
  71                                 if (source == target) {
  72                                         metric[row][column]= diagonal;
  73                                         continue;
  74                                 }
  75
  76                                 change= Integer.MAX_VALUE;
  77                                 if (Character.toLowerCase(source) == Character.toLowerCase(target))
  78                                         change= COST_CASE + diagonal;
  79
  80                                 swap= Integer.MAX_VALUE;
  81                                 if (row != 1 && column != 1 && source == second[column - 1] && first[row - 1] == target)
  82                                         swap= COST_SWAP + metric[row - 2][column - 2];
  83
  84                                 minimum= COST_SUBSTITUTE + diagonal;
  85                                 if (swap < minimum)
  86                                         minimum= swap;
  87
  88                                 remove= metric[row][column - 1];
  89                                 if (COST_REMOVE + remove < minimum)
  90                                         minimum= COST_REMOVE + remove;
  91
  92                                 insert= metric[row - 1][column];
  93                                 if (COST_INSERT + insert < minimum)
  94                                         minimum= COST_INSERT + insert;
  95                                 if (change < minimum)
  96                                         minimum= change;
  97
  98                                 metric[row][column]= minimum;
  99                         }
 100                 }
 101                 return metric[rows - 1][columns - 1];
 102         }
 103 }