| /******************************************************************************* |
| * Copyright (c) 2000, 2005 IBM Corporation and others. |
| * All rights reserved. This program and the accompanying materials |
| * are made available under the terms of the Eclipse Public License v1.0 |
| * which accompanies this distribution, and is available at |
| * http://www.eclipse.org/legal/epl-v10.html |
| * |
| * Contributors: |
| * IBM Corporation - initial API and implementation |
| *******************************************************************************/ |
| |
| package org.eclipse.jdt.internal.ui.text.spelling.engine; |
| |
| /** |
| * Default phonetic distance algorithm for english words. |
| * <p> |
| * This algorithm implements the Levenshtein text edit distance. |
| * </p> |
| * |
| * @since 3.0 |
| */ |
| public final class DefaultPhoneticDistanceAlgorithm implements IPhoneticDistanceAlgorithm { |
| |
| /** The change case cost */ |
| public static final int COST_CASE= 10; |
| |
| /** The insert character cost */ |
| public static final int COST_INSERT= 95; |
| |
| /** The remove character cost */ |
| public static final int COST_REMOVE= 95; |
| |
| /** The substitute characters cost */ |
| public static final int COST_SUBSTITUTE= 100; |
| |
| /** The swap characters cost */ |
| public static final int COST_SWAP= 90; |
| |
| /* |
| * @see org.eclipse.spelling.done.IPhoneticDistanceAlgorithm#getDistance(java.lang.String,java.lang.String) |
| */ |
| public final int getDistance(final String from, final String to) { |
| |
| final char[] first= (" " + from).toCharArray(); //$NON-NLS-1$ |
| final char[] second= (" " + to).toCharArray(); //$NON-NLS-1$ |
| |
| final int rows= first.length; |
| final int columns= second.length; |
| |
| final int[][] metric= new int[rows][columns]; |
| for (int column= 1; column < columns; column++) |
| metric[0][column]= metric[0][column - 1] + COST_REMOVE; |
| |
| for (int row= 1; row < rows; row++) |
| metric[row][0]= metric[row - 1][0] + COST_INSERT; |
| |
| char source, target; |
| |
| int swap= Integer.MAX_VALUE; |
| int change= Integer.MAX_VALUE; |
| |
| int minimum, diagonal, insert, remove; |
| for (int row= 1; row < rows; row++) { |
| |
| source= first[row]; |
| for (int column= 1; column < columns; column++) { |
| |
| target= second[column]; |
| diagonal= metric[row - 1][column - 1]; |
| |
| if (source == target) { |
| metric[row][column]= diagonal; |
| continue; |
| } |
| |
| change= Integer.MAX_VALUE; |
| if (Character.toLowerCase(source) == Character.toLowerCase(target)) |
| change= COST_CASE + diagonal; |
| |
| swap= Integer.MAX_VALUE; |
| if (row != 1 && column != 1 && source == second[column - 1] && first[row - 1] == target) |
| swap= COST_SWAP + metric[row - 2][column - 2]; |
| |
| minimum= COST_SUBSTITUTE + diagonal; |
| if (swap < minimum) |
| minimum= swap; |
| |
| remove= metric[row][column - 1]; |
| if (COST_REMOVE + remove < minimum) |
| minimum= COST_REMOVE + remove; |
| |
| insert= metric[row - 1][column]; |
| if (COST_INSERT + insert < minimum) |
| minimum= COST_INSERT + insert; |
| if (change < minimum) |
| minimum= change; |
| |
| metric[row][column]= minimum; |
| } |
| } |
| return metric[rows - 1][columns - 1]; |
| } |
| } |