in src/main/java/org/apache/commons/text/similarity/LevenshteinDetailedDistance.java [358:442]
private static <E> LevenshteinResults unlimitedCompare(SimilarityInput<E> left, SimilarityInput<E> right) {
if (left == null || right == null) {
throw new IllegalArgumentException("CharSequences must not be null");
}
/*
The difference between this impl. and the previous is that, rather
than creating and retaining a matrix of size s.length() + 1 by t.length() + 1,
we maintain two single-dimensional arrays of length s.length() + 1. The first, d,
is the 'current working' distance array that maintains the newest distance cost
counts as we iterate through the characters of String s. Each time we increment
the index of String t we are comparing, d is copied to p, the second int[]. Doing so
allows us to retain the previous cost counts as required by the algorithm (taking
the minimum of the cost count to the left, up one, and diagonally up and to the left
of the current cost count being calculated). (Note that the arrays aren't really
copied anymore, just switched...this is clearly much better than cloning an array
or doing a System.arraycopy() each time through the outer loop.)
Effectively, the difference between the two implementations is this one does not
cause an out of memory condition when calculating the LD over two very large strings.
*/
int n = left.length(); // length of left
int m = right.length(); // length of right
if (n == 0) {
return new LevenshteinResults(m, m, 0, 0);
}
if (m == 0) {
return new LevenshteinResults(n, 0, n, 0);
}
boolean swapped = false;
if (n > m) {
// swap the input strings to consume less memory
final SimilarityInput<E> tmp = left;
left = right;
right = tmp;
n = m;
m = right.length();
swapped = true;
}
int[] p = new int[n + 1]; // 'previous' cost array, horizontally
int[] d = new int[n + 1]; // cost array, horizontally
int[] tempD; //placeholder to assist in swapping p and d
final int[][] matrix = new int[m + 1][n + 1];
// filling the first row and first column values in the matrix
for (int index = 0; index <= n; index++) {
matrix[0][index] = index;
}
for (int index = 0; index <= m; index++) {
matrix[index][0] = index;
}
// indexes into strings left and right
int i; // iterates through left
int j; // iterates through right
E rightJ; // jth character of right
int cost; // cost
for (i = 0; i <= n; i++) {
p[i] = i;
}
for (j = 1; j <= m; j++) {
rightJ = right.at(j - 1);
d[0] = j;
for (i = 1; i <= n; i++) {
cost = left.at(i - 1).equals(rightJ) ? 0 : 1;
// minimum of cell to the left+1, to the top+1, diagonally left and up +cost
d[i] = Math.min(Math.min(d[i - 1] + 1, p[i] + 1), p[i - 1] + cost);
//filling the matrix
matrix[j][i] = d[i];
}
// copy current distance counts to 'previous row' distance counts
tempD = p;
p = d;
d = tempD;
}
return findDetailedResults(left, right, matrix, swapped);
}