git
/
levenshtein.c
86 строк · 2.5 Кб
1#include "git-compat-util.h"
2#include "levenshtein.h"
3
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
30* operation is a substitution, a swap, a deletion, or an insertion.
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*/
41int levenshtein(const char *string1, const char *string2,
42int w, int s, int a, int d)
43{
44int len1 = strlen(string1), len2 = strlen(string2);
45int *row0, *row1, *row2;
46int i, j;
47
48ALLOC_ARRAY(row0, len2 + 1);
49ALLOC_ARRAY(row1, len2 + 1);
50ALLOC_ARRAY(row2, len2 + 1);
51
52for (j = 0; j <= len2; j++)
53row1[j] = j * a;
54for (i = 0; i < len1; i++) {
55int *dummy;
56
57row2[0] = (i + 1) * d;
58for (j = 0; j < len2; j++) {
59/* substitution */
60row2[j + 1] = row1[j] + s * (string1[i] != string2[j]);
61/* swap */
62if (i > 0 && j > 0 && string1[i - 1] == string2[j] &&
63string1[i] == string2[j - 1] &&
64row2[j + 1] > row0[j - 1] + w)
65row2[j + 1] = row0[j - 1] + w;
66/* deletion */
67if (row2[j + 1] > row1[j + 1] + d)
68row2[j + 1] = row1[j + 1] + d;
69/* insertion */
70if (row2[j + 1] > row2[j] + a)
71row2[j + 1] = row2[j] + a;
72}
73
74dummy = row0;
75row0 = row1;
76row1 = row2;
77row2 = dummy;
78}
79
80i = row1[len2];
81free(row0);
82free(row1);
83free(row2);
84
85return i;
86}
87