Merge branch 'bw/shortref'
[git] / levenshtein.c
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 }