Elijah Newren | 15db4e7 | 2023-02-24 00:09:23 +0000 | [diff] [blame] | 1 | #include "git-compat-util.h" |
Johannes Schindelin | 8af84da | 2008-08-31 15:50:23 +0200 | [diff] [blame] | 2 | #include "levenshtein.h" |
| 3 | |
Johannes Schindelin | 850fb6f | 2008-11-20 14:27:27 +0100 | [diff] [blame] | 4 | /* |
| 5 | * This function implements the Damerau-Levenshtein algorithm to |
| 6 | * calculate a distance between strings. |
| 7 | * |
| 8 | * Basically, it says how many letters need to be swapped, substituted, |
| 9 | * deleted from, or added to string1, at least, to get string2. |
| 10 | * |
| 11 | * The idea is to build a distance matrix for the substrings of both |
| 12 | * strings. To avoid a large space complexity, only the last three rows |
| 13 | * are kept in memory (if swaps had the same or higher cost as one deletion |
| 14 | * plus one insertion, only two rows would be needed). |
| 15 | * |
| 16 | * At any stage, "i + 1" denotes the length of the current substring of |
| 17 | * string1 that the distance is calculated for. |
| 18 | * |
| 19 | * row2 holds the current row, row1 the previous row (i.e. for the substring |
| 20 | * of string1 of length "i"), and row0 the row before that. |
| 21 | * |
| 22 | * In other words, at the start of the big loop, row2[j + 1] contains the |
| 23 | * Damerau-Levenshtein distance between the substring of string1 of length |
| 24 | * "i" and the substring of string2 of length "j + 1". |
| 25 | * |
| 26 | * All the big loop does is determine the partial minimum-cost paths. |
| 27 | * |
| 28 | * It does so by calculating the costs of the path ending in characters |
| 29 | * i (in string1) and j (in string2), respectively, given that the last |
Mike Ralphson | 3ea3c21 | 2009-04-17 19:13:30 +0100 | [diff] [blame] | 30 | * operation is a substitution, a swap, a deletion, or an insertion. |
Johannes Schindelin | 850fb6f | 2008-11-20 14:27:27 +0100 | [diff] [blame] | 31 | * |
| 32 | * This implementation allows the costs to be weighted: |
| 33 | * |
| 34 | * - w (as in "sWap") |
| 35 | * - s (as in "Substitution") |
| 36 | * - a (for insertion, AKA "Add") |
| 37 | * - d (as in "Deletion") |
| 38 | * |
| 39 | * Note that this algorithm calculates a distance _iff_ d == a. |
| 40 | */ |
Johannes Schindelin | 8af84da | 2008-08-31 15:50:23 +0200 | [diff] [blame] | 41 | int levenshtein(const char *string1, const char *string2, |
| 42 | int w, int s, int a, int d) |
| 43 | { |
| 44 | int len1 = strlen(string1), len2 = strlen(string2); |
Jeff King | b32fa95 | 2016-02-22 17:44:25 -0500 | [diff] [blame] | 45 | int *row0, *row1, *row2; |
Johannes Schindelin | 8af84da | 2008-08-31 15:50:23 +0200 | [diff] [blame] | 46 | int i, j; |
| 47 | |
Jeff King | b32fa95 | 2016-02-22 17:44:25 -0500 | [diff] [blame] | 48 | ALLOC_ARRAY(row0, len2 + 1); |
| 49 | ALLOC_ARRAY(row1, len2 + 1); |
| 50 | ALLOC_ARRAY(row2, len2 + 1); |
| 51 | |
Johannes Schindelin | 8af84da | 2008-08-31 15:50:23 +0200 | [diff] [blame] | 52 | for (j = 0; j <= len2; j++) |
| 53 | row1[j] = j * a; |
| 54 | for (i = 0; i < len1; i++) { |
| 55 | int *dummy; |
| 56 | |
| 57 | row2[0] = (i + 1) * d; |
| 58 | for (j = 0; j < len2; j++) { |
| 59 | /* substitution */ |
| 60 | row2[j + 1] = row1[j] + s * (string1[i] != string2[j]); |
| 61 | /* swap */ |
| 62 | if (i > 0 && j > 0 && string1[i - 1] == string2[j] && |
| 63 | string1[i] == string2[j - 1] && |
| 64 | row2[j + 1] > row0[j - 1] + w) |
| 65 | row2[j + 1] = row0[j - 1] + w; |
| 66 | /* deletion */ |
Samuel Tardieu | 13c6bcd | 2008-11-18 19:53:26 +0100 | [diff] [blame] | 67 | if (row2[j + 1] > row1[j + 1] + d) |
Johannes Schindelin | 8af84da | 2008-08-31 15:50:23 +0200 | [diff] [blame] | 68 | row2[j + 1] = row1[j + 1] + d; |
| 69 | /* insertion */ |
| 70 | if (row2[j + 1] > row2[j] + a) |
| 71 | row2[j + 1] = row2[j] + a; |
| 72 | } |
| 73 | |
| 74 | dummy = row0; |
| 75 | row0 = row1; |
| 76 | row1 = row2; |
| 77 | row2 = dummy; |
| 78 | } |
| 79 | |
| 80 | i = row1[len2]; |
| 81 | free(row0); |
| 82 | free(row1); |
| 83 | free(row2); |
| 84 | |
| 85 | return i; |
| 86 | } |