(String s, String t)
| 117 | } |
| 118 | |
| 119 | public static float levenshteinDistance(String s, String t) { |
| 120 | // degenerate cases |
| 121 | if (s.equals(t)) return 0; |
| 122 | if (s.length() == 0) return t.length(); |
| 123 | if (t.length() == 0) return s.length(); |
| 124 | |
| 125 | // create two work vectors of integer distances |
| 126 | int[] v0 = new int[t.length() + 1]; |
| 127 | int[] v1 = new int[t.length() + 1]; |
| 128 | |
| 129 | // initialize v0 (the previous row of distances) |
| 130 | // this row is A[0][i]: edit distance for an empty s |
| 131 | // the distance is just the number of characters to delete from t |
| 132 | for (int i = 0; i < v0.length; i++) { |
| 133 | v0[i] = i; |
| 134 | } |
| 135 | |
| 136 | for (int i = 0; i < s.length(); i++) { |
| 137 | // calculate v1 (current row distances) from the previous row v0 |
| 138 | |
| 139 | // first element of v1 is A[i+1][0] |
| 140 | // edit distance is delete (i+1) chars from s to match empty t |
| 141 | v1[0] = i + 1; |
| 142 | |
| 143 | // use formula to fill in the rest of the row |
| 144 | for (int j = 0; j < t.length(); j++) |
| 145 | { |
| 146 | int cost = s.charAt(i) == t.charAt(j) ? 0 : 1; |
| 147 | v1[j + 1] = Math.min( |
| 148 | Math.min(v1[j] + 1, v0[j + 1] + 1), |
| 149 | v0[j] + cost); |
| 150 | } |
| 151 | |
| 152 | // copy v1 (current row) to v0 (previous row) for next iteration |
| 153 | System.arraycopy(v1, 0, v0, 0, v0.length); |
| 154 | } |
| 155 | |
| 156 | int d = v1[t.length()]; |
| 157 | return d; |
| 158 | } |
| 159 | |
| 160 | /* Compare whitespace and give an approximate Levenshtein distance / |
| 161 | edit distance. MUCH faster to use this than pure Levenshtein which |
no test coverage detected