Andrew's git - gitweb.git/blob

   1#include "cache.h"
   2#include "levenshtein.h"
   3
   4int 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}