net.sourceforge.phpeclipse.ui/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
  23                 IPhoneticDistanceAlgorithm {
  24
  25         /** The change case cost */
  26         public static final int COST_CASE = 10;
  27
  28         /** The insert character cost */
  29         public static final int COST_INSERT = 95;
  30
  31         /** The remove character cost */
  32         public static final int COST_REMOVE = 95;
  33
  34         /** The substitute characters cost */
  35         public static final int COST_SUBSTITUTE = 100;
  36
  37         /** The swap characters cost */
  38         public static final int COST_SWAP = 90;
  39
  40         /*
  41          * @see org.eclipse.spelling.done.IPhoneticDistanceAlgorithm#getDistance(java.lang.String,java.lang.String)
  42          */
  43         public final int getDistance(final String from, final String to) {
  44
  45                 final char[] first = (" " + from).toCharArray(); //$NON-NLS-1$
  46                 final char[] second = (" " + to).toCharArray(); //$NON-NLS-1$
  47
  48                 final int rows = first.length;
  49                 final int columns = second.length;
  50
  51                 final int[][] metric = new int[rows][columns];
  52                 for (int column = 1; column < columns; column++)
  53                         metric[0][column] = metric[0][column - 1] + COST_REMOVE;
  54
  55                 for (int row = 1; row < rows; row++)
  56                         metric[row][0] = metric[row - 1][0] + COST_INSERT;
  57
  58                 char source, target;
  59
  60                 int swap = Integer.MAX_VALUE;
  61                 int change = Integer.MAX_VALUE;
  62
  63                 int minimum, diagonal, insert, remove;
  64                 for (int row = 1; row < rows; row++) {
  65
  66                         source = first[row];
  67                         for (int column = 1; column < columns; column++) {
  68
  69                                 target = second[column];
  70                                 diagonal = metric[row - 1][column - 1];
  71
  72                                 if (source == target) {
  73                                         metric[row][column] = diagonal;
  74                                         continue;
  75                                 }
  76
  77                                 change = Integer.MAX_VALUE;
  78                                 if (Character.toLowerCase(source) == Character
  79                                                 .toLowerCase(target))
  80                                         change = COST_CASE + diagonal;
  81
  82                                 swap = Integer.MAX_VALUE;
  83                                 if (row != 1 && column != 1 && source == second[column - 1]
  84                                                 && first[row - 1] == target)
  85                                         swap = COST_SWAP + metric[row - 2][column - 2];
  86
  87                                 minimum = COST_SUBSTITUTE + diagonal;
  88                                 if (swap < minimum)
  89                                         minimum = swap;
  90
  91                                 remove = metric[row][column - 1];
  92                                 if (COST_REMOVE + remove < minimum)
  93                                         minimum = COST_REMOVE + remove;
  94
  95                                 insert = metric[row - 1][column];
  96                                 if (COST_INSERT + insert < minimum)
  97                                         minimum = COST_INSERT + insert;
  98                                 if (change < minimum)
  99                                         minimum = change;
 100
 101                                 metric[row][column] = minimum;
 102                         }
 103                 }
 104                 return metric[rows - 1][columns - 1];
 105         }
 106 }