KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > eclipse > jdt > internal > ui > text > spelling > engine > DefaultPhoneticDistanceAlgorithm


1 /*******************************************************************************
2  * Copyright (c) 2000, 2007 IBM Corporation and others.
3  * All rights reserved. This program and the accompanying materials
4  * are made available under the terms of the Eclipse Public License v1.0
5  * which accompanies this distribution, and is available at
6  * http://www.eclipse.org/legal/epl-v10.html
7  *
8  * Contributors:
9  * IBM Corporation - initial API and implementation
10  *******************************************************************************/
11
12 package org.eclipse.jdt.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 JavaDoc from, final String JavaDoc 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 }
104
Popular Tags