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 }