]>
Commit | Line | Data |
---|---|---|
8af84dad JS |
1 | #include "cache.h" |
2 | #include "levenshtein.h" | |
3 | ||
4 | int levenshtein(const char *string1, const char *string2, | |
5 | int w, int s, int a, int d) | |
6 | { | |
7 | int len1 = strlen(string1), len2 = strlen(string2); | |
8 | int *row0 = xmalloc(sizeof(int) * (len2 + 1)); | |
9 | int *row1 = xmalloc(sizeof(int) * (len2 + 1)); | |
10 | int *row2 = xmalloc(sizeof(int) * (len2 + 1)); | |
11 | int i, j; | |
12 | ||
13 | for (j = 0; j <= len2; j++) | |
14 | row1[j] = j * a; | |
15 | for (i = 0; i < len1; i++) { | |
16 | int *dummy; | |
17 | ||
18 | row2[0] = (i + 1) * d; | |
19 | for (j = 0; j < len2; j++) { | |
20 | /* substitution */ | |
21 | row2[j + 1] = row1[j] + s * (string1[i] != string2[j]); | |
22 | /* swap */ | |
23 | if (i > 0 && j > 0 && string1[i - 1] == string2[j] && | |
24 | string1[i] == string2[j - 1] && | |
25 | row2[j + 1] > row0[j - 1] + w) | |
26 | row2[j + 1] = row0[j - 1] + w; | |
27 | /* deletion */ | |
28 | if (j + 1 < len2 && row2[j + 1] > row1[j + 1] + d) | |
29 | row2[j + 1] = row1[j + 1] + d; | |
30 | /* insertion */ | |
31 | if (row2[j + 1] > row2[j] + a) | |
32 | row2[j + 1] = row2[j] + a; | |
33 | } | |
34 | ||
35 | dummy = row0; | |
36 | row0 = row1; | |
37 | row1 = row2; | |
38 | row2 = dummy; | |
39 | } | |
40 | ||
41 | i = row1[len2]; | |
42 | free(row0); | |
43 | free(row1); | |
44 | free(row2); | |
45 | ||
46 | return i; | |
47 | } |