libvspell/distance.cpp

   1 #include "config.h"
   2 #include <iostream>
   3 #include <string>
   4 #include <values.h>
   5 #include <stdio.h>
   6 #include "distance.h"
   7
   8 #ifndef MAXINT
   9 #define MAXINT 10000000 //2147483647
  10 #endif
  11
  12 int a[MAX_WIDTH+2][MAX_HEIGHT+2];
  13 #define A(i,j) a[(i)+2][(j)+2]
  14 #define min2(a,b) ((a) > (b) ? (b) : (a))
  15 #define min3(a,b,c) ((a) >= (b) && (c) >= (b) ? (b) : ((a) >= (c) && (b) >= (c) ? (c) : (a)))
  16
  17 using namespace std;
  18 #ifdef USE_CACHE
  19 #include <map>
  20 typedef map<pair<string,string>,int> ed_cache_type;
  21 static ed_cache_type ed_cache;
  22 #endif
  23
  24 // the following formula is used:
  25 // a(0,0) = 0                x[0] = y[0]
  26 // a(0,0) = 1                x[0] <> y[0]
  27 // a(0,j) = j                1 <= j <= n
  28 // a(i,0) = i                1 <= i <= m
  29 // a(i,j) = a(i-1,j-1)       x[i] = y[j]
  30 // a(i,j) = 1 + min{a(i-2,j-2),a(i,j-1),a(i-1,j)}
  31 //                           x[i] = y[j-1]
  32 //                           x[i-1] = y[j]
  33 // a(i,j) = 1 + min{a(i-1,j-1),a(i,j-1),a(i-1,j)} otherwise
  34 int ed(const char *s1,int n1,const char *s2,int n2)
  35 {
  36   static int k,i,j;             // static for speed
  37
  38 #ifdef USE_CACHE
  39   // look in cache first
  40   ed_cache_type::iterator iter;
  41   pair<string,string> key = make_pair(string(s1),string(s2));
  42   iter = ed_cache.find(key);
  43   if (iter != ed_cache.end())
  44     return iter->second;
  45 #endif
  46
  47   // case 1,2
  48   A(0,0) = s1[0] == s2[0] ? 0 : 1;
  49   //printf("(%d,%d) = %d\n",1,1,A(0,0));
  50
  51   // case 3,4 are coded on the boundary of a[][].
  52
  53   // k go from upper left to upper right then lower right
  54   for (k = 1;k < n1+n2-1;k ++)
  55     // (i,j) go from upper right to lower left.
  56     for (i = min2(n1-1,k),j = k-i;i >= 0 && j < n2;--i,++j) {
  57       // case 5
  58       if (s1[i] == s2[j]) {
  59         A(i,j) = A(i-1,j-1);
  60         //printf("(%d,%d) = %d\n",i+1,j+1,A(i,j));
  61         continue;
  62       }
  63
  64       // case 6
  65       if ((i > 0 && s1[i-1] == s2[j]) ||
  66           (j > 0 && s1[i] == s2[j-1])) {
  67         A(i,j) = min3(A(i-2,j-2),A(i,j-1),A(i-1,j)) + 1;
  68         //printf("(%d,%d) < %d %d %d -> %d\n",i+1,j+1,A(i-2,j-2),A(i,j-1),A(i-1,j),A(i,j));
  69         continue;
  70       }
  71
  72       // case 7
  73       A(i,j) = min3(A(i-1,j-1),A(i,j-1),A(i-1,j)) + 1;
  74       //printf("(%d,%d) > %d %d %d -> %d\n",i+1,j+1,A(i-1,j-1),A(i,j-1),A(i-1,j),A(i,j));
  75     }
  76 #ifdef USE_CACHE
  77   ed_cache[key] = A(n1-1,n2-1);
  78 #endif
  79   return A(n1-1,n2-1);
  80 }
  81
  82 void ed_init()
  83 {
  84   int i;
  85
  86   for (i = 0;i < MAX_WIDTH+2;i ++)
  87     a[i][0] = MAXINT;
  88   for (i = 0;i < MAX_HEIGHT+2;i ++)
  89     a[0][i] = MAXINT;
  90   a[1][1] = MAXINT;
  91   for (i = 0;i < MAX_WIDTH;i ++)
  92     a[i+2][1] = i+1;
  93   for (i = 0;i < MAX_HEIGHT;i ++)
  94     a[1][i+2] = i+1;
  95 }
  96
  97 void ed_dump(int w,int h)
  98 {
  99   int i,j;
 100   for (i = 0;i < w;i ++) {
 101     for (j = 0;j < h;j ++)
 102       cout << a[i+2][j+2] << " ";
 103     cout << endl;
 104   }
 105 }