1: /*
2: * Copyright (C) 2013 changedi
3: *
4: * Licensed under the Apache License, Version 2.0 (the "License");
5: * you may not use this file except in compliance with the License.
6: * You may obtain a copy of the License at
7: *
8: * http://www.apache.org/licenses/LICENSE-2.0
9: *
10: * Unless required by applicable law or agreed to in writing, software
11: * distributed under the License is distributed on an "AS IS" BASIS,
12: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13: * See the License for the specific language governing permissions and
14: * limitations under the License.
15: */
16: package com.jybat.dp;
17:
18: //EditDistanceProblem;
19: public class EDP { 20:
21: private static String s1 = "CAN";
22: private static String s2 = "ANN";
23: private static final int insertionCost = 1;
24: private static final int deletionCost = 1;
25: private static final int replacementCost = 1;
26: // it is useful to have the string lengths as symbolic constants
27: private static int s1Length = s1.length();
28: private static int s2Length = s2.length();
29:
30: // The decision space is constant in this example.
31: // It does not depend on the current state.
32: // We chose to code the 3 allowed operations
33: // as follows:
34: // 1 stands for delete
35: // 2 stands for insert
36: // 12 stands for replace
37: private static int[] decisionSet = { 1, 2, 12 }; 38:
39: // costOfOperation()
40: // returns 0 if the specified characters in the 2 strings
41: // match and the decision is to perform
42: // "replacement" operation for matching chars
43: // (whose cost is usually defined as 0)
44: // returns 1 otherwise (if delete, insert, or a real replacement operation
45: // happens)
46: private static int costOfOperation(int i, int j, int dec) { 47: if (dec == 12) { // dec==12 means decision is to replace 48: if (s1.charAt(i - 1) // note: subtract 1 because array
49: // starts at index 0
50: == s2.charAt(j - 1)) { // matching chars, cost is 0 51: return 0;
52: } else { // real replacement 53: return replacementCost; // cost of real replacement
54: }
55: }
56: if (dec == 1) { // dec==1 means decision is to delete 57: return deletionCost;
58: }
59: // otherwise it must be that dec==2, decision to insert
60: return insertionCost;
61: }
62:
63: private static int s1Adjustment(int dec) { 64: if (dec == 2) { // insert 65: return 0;
66: }
67: return 1;
68: }
69:
70: private static int s2Adjustment(int dec) { 71: if (dec == 1) { // delete 72: return 0;
73: }
74: return 1;
75: }
76:
77: public static int d(int i, int j) { 78: if (i == 0)
79: return j;
80: if (j == 0)
81: return i;
82: int min = Integer.MAX_VALUE;
83: for (int dec : decisionSet) { 84: int t = costOfOperation(i, j, dec)
85: + d(i - s1Adjustment(dec), j - s2Adjustment(dec));
86: if (t < min)
87: min = t;
88: }
89: return min;
90: }
91:
92: /**
93: * @param args
94: */
95: public static void main(String[] args) { 96: System.out.println(d(s1Length, s2Length));
97:
98: }
99:
100: }