home *** CD-ROM | disk | FTP | other *** search
/ TopWare Tools / TOOLS.iso / tools / top1654 / gepackt.exe / LEV4.C < prev    next >
Encoding:
C/C++ Source or Header  |  1994-01-26  |  3.9 KB  |  187 lines
  1. /****  Einfache Levenshtein-Distanz (p0=q0=r0=1) ****/
  2. /****  mit Berƒcksichtigung von Wildcards        ****/
  3. /****  (geschwindigkeitsoptimiertes C-Programm)  ****/
  4. /****  Autor :  JÜrg Michael, Hannover           ****/
  5. /****  Datum :  22. Dezember 1993                ****/
  6.  
  7. /****  modus = ╒ ╒: normale Levenshtein-Distanz  ****/
  8. /****  modus = ╒+╒: keine Unterscheidung         ****/
  9. /****               Klein-/Groºschreibung        ****/
  10. /****  modus = ╒*╒: wie ╒+╒, aber zusètzlich     ****/
  11. /****               "symmetrisches" Verhalten    ****/
  12. /****               gem躠der im Text beschrie-  ****/
  13. /****               benen Vorformatierung        ****/
  14.  
  15. #define  maxlen  51
  16. char     *strchr();
  17.  
  18. int formatierung (char ziel[], char wort[], int n, char modus)
  19.  
  20. /****  Wandelt "wort" in GROSSschreibung  ****/
  21. /****  um und expandiert Umlaute          ****/
  22. /****  (n = Zeichenzahl von "ziel")       ****/
  23. /****  Zurƒckgegeben wird: strlen (ziel)  ****/
  24. {
  25.  int  i,k;
  26.  char c,*s;
  27.  
  28.  i = 0;
  29.  k = 0;
  30.  while ((c = wort[i++]) != 0  &&  k < n-1)
  31.    {
  32.     if (isupper (c)  ||  isdigit (c))
  33.       {
  34.        ziel [k++] = c;
  35.       }
  36.     else if (islower (c))
  37.       {
  38.        ziel [k++] = c -╒a╒+╒A╒;
  39.       }
  40.  
  41.     else
  42.       {
  43.        s = strchr ("ÇAEèAEàOEÜOEåUEƒUEºSS", c);
  44.        if (*s != NULL)
  45.          {
  46.           ziel [k++] = *(s+1);
  47.           if (k < n-1)
  48.             {
  49.              ziel [k++] = *(s+2);
  50.             } 
  51.          }
  52.        else if (modus == ╒*╒  &&  c != ╒?╒)
  53.          {
  54.           /****  Aufeinanderfolgende ╒*╒  ****/
  55.           /****  zu einem zusammenziehen  ****/
  56.           if (k == 0  ||  ziel [k-1] != ╒*╒)
  57.             {
  58.              ziel [k++] = ╒*╒;
  59.             }
  60.          }
  61.        else
  62.          {
  63.           ziel [k++] = c;
  64.          }
  65.       }
  66.    }
  67.  ziel[k] = 0;
  68.  return (k);
  69. }
  70.  
  71. int WLD (char *wort, char *muster, char modus, int limit)
  72. {
  73.  register int spmin,
  74.               p,q,r,
  75.               lm,lw,
  76.               d1,d2,
  77.               i,k,
  78.               x1,x2,x3;
  79.  char c,
  80.       mm[maxlen],
  81.       ww[maxlen];
  82.  int  d[maxlen];
  83.  
  84.  if (modus == ╒+╒  ||  modus == ╒*╒)
  85.    {
  86.     lw = formatierung (ww, wort, maxlen,modus);
  87.     lm = formatierung (mm,muster,maxlen,modus);
  88.     
  89.     if (modus == ╒*╒  &&  lw < lm-1
  90.     &&  strchr (ww,╒*╒) != NULL)
  91.       {
  92.        /****  Wort und Muster tauschen  ****/
  93.        wort = mm;
  94.        muster = ww;
  95.        strcpy (ww+lw, "*");
  96.        i  = lw;
  97.        lw = lm;
  98.        lm = i+1;
  99.        /****  Limit neu setzen  ****/
  100.        i = (int)(i/3);
  101.        if (i < limit)
  102.          {
  103.           limit = i;
  104.          }
  105.       }
  106.     else
  107.       {
  108.        wort = ww;
  109.        muster = mm;
  110.       }
  111.    }
  112.  else
  113.    {
  114.     lw = strlen (wort);
  115.     lm = strlen (muster);
  116.     if (lw >= maxlen) lw = (maxlen-1);
  117.     if (lm >= maxlen) lm = (maxlen-1);
  118.    }
  119.  
  120.  /****  Anfangswerte berechnen ****/
  121.  if (*muster == ╒*╒)
  122.    {
  123.     for (k=0; k<=lw; k++)
  124.       {
  125.        d[k] = 0;
  126.       }
  127.    }
  128.  else
  129.    {
  130.     d[0] = (*muster == 0) ? 0 : 1;
  131.     i = (*muster == ╒?╒) ? 0 : 1;
  132.     for (k=1; k<=lw; k++)
  133.       {
  134.        if (*muster == *(wort+k-1))
  135.          {
  136.           i = 0;
  137.          }
  138.        d[k] = k-1 + i;
  139.       }
  140.    }
  141.  
  142.  spmin = (d[0] == 0  ||  lw == 0) ?  d[0] : d[1];
  143.  if (spmin > limit)
  144.    {
  145.     return (maxlen);
  146.    }
  147.  
  148.  /****  Distanzmatrix durchrechnen  ****/
  149.  for (i=2; i<=lm; i++)
  150.    {
  151.     c = *(muster+i-1);
  152.     p = (c == ╒*╒  ||  c == ╒?╒) ?  0 : 1;
  153.     q = (c == ╒*╒) ?  0 : 1;
  154.     r = (c == ╒*╒) ?  0 : 1;
  155.     d2 = d[0];
  156.     d[0] = d2 + q;
  157.     spmin = d[0];
  158.  
  159.     for (k=1; k<=lw; k++)
  160.       {
  161.        /****  d[k] = Minimum dreier Zahlen  ****/
  162.        d1 = d2;
  163.        d2 = d[k];
  164.        x1 = d1 + ((c == *(wort+k-1)) ?  0 : p);
  165.        x2 = d2 + q;
  166.        x3 = d[k-1] + r;
  167.  
  168.        if (x1 < x2)
  169.          {
  170.           x2 = x1;
  171.          }
  172.        d[k] = (x2 < x3) ?  x2 : x3;  
  173.  
  174.        if (d[k] < spmin)
  175.          {
  176.           spmin = d[k];
  177.          }
  178.       }
  179.  
  180.     if (spmin > limit)
  181.       {
  182.        return (maxlen);
  183.       }
  184.    } 
  185.  return ((d[lw] <= limit) ?  d[lw] : maxlen); 
  186. }
  187.