1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
8 *
9 * https://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17 package org.apache.commons.text.similarity;
18
19 /**
20 * An algorithm for measuring the difference between two character sequences using the
21 * <a href="https://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance">Damerau-Levenshtein Distance</a>.
22 *
23 * <p>
24 * This is the number of changes needed to change one sequence into another, where each change is a single character
25 * modification (deletion, insertion, substitution, or transposition of two adjacent characters).
26 * </p>
27 *
28 * @see <a href="https://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance">Damerau-Levenshtein Distance on Wikipedia</a>
29 * @since 1.15.0
30 */
31 public class DamerauLevenshteinDistance implements EditDistance<Integer> {
32
33 private static <E> int calculateCost(final SimilarityInput<E> left, final SimilarityInput<E> right, final int leftIndex, final int rightIndex,
34 final int[] curr, final int[] prev, final int[] prevPrev) {
35 final int cost = left.at(leftIndex - 1) == right.at(rightIndex - 1) ? 0 : 1;
36 // Select cheapest operation
37 int value = Math.min(
38 Math.min(
39 prev[rightIndex] + 1, // Delete current character
40 curr[rightIndex - 1] + 1 // Insert current character
41 ),
42 prev[rightIndex - 1] + cost // Replace (or no cost if same character)
43 );
44 // Check if adjacent characters are the same -> transpose if cheaper
45 if (leftIndex > 1
46 && rightIndex > 1
47 && left.at(leftIndex - 1) == right.at(rightIndex - 2)
48 && left.at(leftIndex - 2) == right.at(rightIndex - 1)) {
49 // Use cost here, to properly handle two subsequent equal letters
50 value = Math.min(value, prevPrev[rightIndex - 2] + cost);
51 }
52 return value;
53 }
54
55 /**
56 * Utility function to ensure distance is valid according to threshold.
57 *
58 * @param distance The distance value.
59 * @param threshold The threshold value.
60 * @return The distance value, or {@code -1} if distance is greater than threshold.
61 */
62 private static int clampDistance(final int distance, final int threshold) {
63 return distance > threshold ? -1 : distance;
64 }
65
66 /**
67 * Finds the Damerau-Levenshtein distance between two CharSequences if it's less than or equal to a given threshold.
68 *
69 * @param left The first SimilarityInput, must not be null.
70 * @param right The second SimilarityInput, must not be null.
71 * @param threshold The target threshold, must not be negative.
72 * @return result distance, or -1 if distance exceeds threshold.
73 */
74 private static <E> int limitedCompare(SimilarityInput<E> left, SimilarityInput<E> right, final int threshold) {
75 if (left == null || right == null) {
76 throw new IllegalArgumentException("Left/right inputs must not be null");
77 }
78
79 // Implementation based on https://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance#Optimal_string_alignment_distance
80
81 int leftLength = left.length();
82 int rightLength = right.length();
83
84 if (leftLength == 0) {
85 return clampDistance(rightLength, threshold);
86 }
87
88 if (rightLength == 0) {
89 return clampDistance(leftLength, threshold);
90 }
91
92 // Inspired by LevenshteinDistance impl; swap the input strings to consume less memory
93 if (rightLength > leftLength) {
94 final SimilarityInput<E> tmp = left;
95 left = right;
96 right = tmp;
97 leftLength = rightLength;
98 rightLength = right.length();
99 }
100
101 // If the difference between the lengths of the strings is greater than the threshold, we must at least do
102 // threshold operations so we can return early
103 if (leftLength - rightLength > threshold) {
104 return -1;
105 }
106
107 // Use three arrays of minimum possible size to reduce memory usage. This avoids having to create a 2D
108 // array of size leftLength * rightLength
109 int[] curr = new int[rightLength + 1];
110 int[] prev = new int[rightLength + 1];
111 int[] prevPrev = new int[rightLength + 1];
112 int[] temp; // Temp variable use to shuffle arrays at the end of each iteration
113
114 int rightIndex, leftIndex, minCost;
115
116 // Changing empty sequence to [0..i] requires i insertions
117 for (rightIndex = 0; rightIndex <= rightLength; rightIndex++) {
118 prev[rightIndex] = rightIndex;
119 }
120
121 // Calculate how many operations it takes to change right[0..rightIndex] into left[0..leftIndex]
122 // For each iteration
123 // - curr[i] contains the cost of changing right[0..i] into left[0..leftIndex]
124 // (computed in current iteration)
125 // - prev[i] contains the cost of changing right[0..i] into left[0..leftIndex - 1]
126 // (computed in previous iteration)
127 // - prevPrev[i] contains the cost of changing right[0..i] into left[0..leftIndex - 2]
128 // (computed in iteration before previous)
129 for (leftIndex = 1; leftIndex <= leftLength; leftIndex++) {
130 // For right[0..0] we must insert leftIndex characters, which means the cost is always leftIndex
131 curr[0] = leftIndex;
132
133 minCost = Integer.MAX_VALUE;
134
135 for (rightIndex = 1; rightIndex <= rightLength; rightIndex++) {
136 curr[rightIndex] = calculateCost(left, right, leftIndex, rightIndex, curr, prev, prevPrev);
137
138 minCost = Math.min(curr[rightIndex], minCost);
139 }
140
141 // If there was no total cost for this entire iteration to transform right to left[0..leftIndex], there
142 // can not be a way to do it below threshold. This is because we have no way to reduce the overall cost
143 // in later operations.
144 if (minCost > threshold) {
145 return -1;
146 }
147
148 // Rotate arrays for next iteration
149 temp = prevPrev;
150 prevPrev = prev;
151 prev = curr;
152 curr = temp;
153 }
154
155 // Prev contains the value computed in the latest iteration
156 return clampDistance(prev[rightLength], threshold);
157 }
158
159 /**
160 * Finds the Damerau-Levenshtein distance between two inputs using optimal string alignment.
161 *
162 * @param left The first CharSequence, must not be null.
163 * @param right The second CharSequence, must not be null.
164 * @return result distance.
165 * @throws IllegalArgumentException if either CharSequence input is {@code null}.
166 */
167 private static <E> int unlimitedCompare(SimilarityInput<E> left, SimilarityInput<E> right) {
168 if (left == null || right == null) {
169 throw new IllegalArgumentException("Left/right inputs must not be null");
170 }
171
172 /*
173 * Implementation based on https://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance#Optimal_string_alignment_distance
174 */
175
176 int leftLength = left.length();
177 int rightLength = right.length();
178
179 if (leftLength == 0) {
180 return rightLength;
181 }
182
183 if (rightLength == 0) {
184 return leftLength;
185 }
186
187 // Inspired by LevenshteinDistance impl; swap the input strings to consume less memory
188 if (rightLength > leftLength) {
189 final SimilarityInput<E> tmp = left;
190 left = right;
191 right = tmp;
192 leftLength = rightLength;
193 rightLength = right.length();
194 }
195
196 // Use three arrays of minimum possible size to reduce memory usage. This avoids having to create a 2D
197 // array of size leftLength * rightLength
198 int[] curr = new int[rightLength + 1];
199 int[] prev = new int[rightLength + 1];
200 int[] prevPrev = new int[rightLength + 1];
201 int[] temp; // Temp variable use to shuffle arrays at the end of each iteration
202
203 int rightIndex, leftIndex;
204
205 // Changing empty sequence to [0..i] requires i insertions
206 for (rightIndex = 0; rightIndex <= rightLength; rightIndex++) {
207 prev[rightIndex] = rightIndex;
208 }
209
210 // Calculate how many operations it takes to change right[0..rightIndex] into left[0..leftIndex]
211 // For each iteration
212 // - curr[i] contains the cost of changing right[0..i] into left[0..leftIndex]
213 // (computed in current iteration)
214 // - prev[i] contains the cost of changing right[0..i] into left[0..leftIndex - 1]
215 // (computed in previous iteration)
216 // - prevPrev[i] contains the cost of changing right[0..i] into left[0..leftIndex - 2]
217 // (computed in iteration before previous)
218 for (leftIndex = 1; leftIndex <= leftLength; leftIndex++) {
219 // For right[0..0] we must insert leftIndex characters, which means the cost is always leftIndex
220 curr[0] = leftIndex;
221
222 for (rightIndex = 1; rightIndex <= rightLength; rightIndex++) {
223 curr[rightIndex] = calculateCost(left, right, leftIndex, rightIndex, curr, prev, prevPrev);
224 }
225
226 // Rotate arrays for next iteration
227 temp = prevPrev;
228 prevPrev = prev;
229 prev = curr;
230 curr = temp;
231 }
232
233 // Prev contains the value computed in the latest iteration
234 return prev[rightLength];
235 }
236
237 /**
238 * Threshold.
239 */
240 private final Integer threshold;
241
242 /**
243 * Constructs a default instance that uses a version of the algorithm that does not use a threshold parameter.
244 */
245 public DamerauLevenshteinDistance() {
246 this(null);
247 }
248
249 /**
250 * Constructs a new instance. If the threshold is not null, distance calculations will be limited to a maximum length.
251 * If the threshold is null, the unlimited version of the algorithm will be used.
252 *
253 * @param threshold If this is null then distances calculations will not be limited. This may not be negative.
254 */
255 public DamerauLevenshteinDistance(final Integer threshold) {
256 if (threshold != null && threshold < 0) {
257 throw new IllegalArgumentException("Threshold must not be negative");
258 }
259 this.threshold = threshold;
260 }
261
262 /**
263 * Computes the Damerau-Levenshtein distance between two Strings.
264 *
265 * <p>
266 * A higher score indicates a greater distance.
267 * </p>
268 *
269 * @param left The first input, must not be null.
270 * @param right The second input, must not be null.
271 * @return result distance, or -1 if threshold is exceeded.
272 * @throws IllegalArgumentException if either String input {@code null}.
273 */
274 @Override
275 public Integer apply(final CharSequence left, final CharSequence right) {
276 return apply(SimilarityInput.input(left), SimilarityInput.input(right));
277 }
278
279 /**
280 * Computes the Damerau-Levenshtein distance between two inputs.
281 *
282 * <p>
283 * A higher score indicates a greater distance.
284 * </p>
285 *
286 * @param <E> The type of similarity score unit.
287 * @param left The first input, must not be null.
288 * @param right The second input, must not be null.
289 * @return result distance, or -1 if threshold is exceeded.
290 * @throws IllegalArgumentException if either String input {@code null}.
291 * @since 1.13.0
292 */
293 public <E> Integer apply(final SimilarityInput<E> left, final SimilarityInput<E> right) {
294 if (threshold != null) {
295 return limitedCompare(left, right, threshold);
296 }
297 return unlimitedCompare(left, right);
298 }
299
300 /**
301 * Gets the distance threshold.
302 *
303 * @return The distance threshold.
304 */
305 public Integer getThreshold() {
306 return threshold;
307 }
308 }