wait/trunk/levenstein.c

/****  Einfache Levenshtein-Distanz (p0=q0=r0=1) ****/
/****  mit Berücksichtigung von Wildcards        ****/
/****  (geschwindigkeitsoptimiertes C-Programm)  ****/
/****  Autor :  Jörg Michael, Hannover           ****/
/****  Datum :  22. Dezember 1993                ****/

/****  modus = ' ': normale Levenshtein-Distanz  ****/
/****  modus = '+': keine Unterscheidung         ****/
/****               Klein-/Großschreibung        ****/
/****  modus = '*': wie '+', aber zusätzlich     ****/
/****               "symmetrisches" Verhalten    ****/
/****               gemäß der im Text beschrie-  ****/
/****               benen Vorformatierung        ****/

#ifdef __cplusplus
extern          "C" {
#endif
#include "EXTERN.h"
#include "perl.h"
#include "XSUB.h"
#ifdef __cplusplus
}

#endif
#define  maxlen  51 
char          *strchr();

int 
formatierung(char ziel[], char wort[], int n, char modus)
/****  Wandelt "wort" in GROSSschreibung  ****/
/****  um und expandiert Umlaute          ****/
/****  (n = Zeichenzahl von "ziel")       ****/
/****  Zurückgegeben wird: strlen (ziel)  ****/
{
  int             i, k;
  char            c, *s;

  i = 0;
  k = 0;
  while ((c = wort[i++]) != 0 && k < n - 1) {
    if (isupper(c) || isdigit(c)) {
      ziel[k++] = c;
    } else if (islower(c)) {
      ziel[k++] = c - 'a' + 'A';
    } else {
      s = strchr("ÄAEäAEÖOEöOEÜUEüUEßSS", c);
      if (s != NULL) {
        ziel[k++] = *(s + 1);
        if (k < n - 1) {
          ziel[k++] = *(s + 2);
        }
      } else if (modus == '*' && c != '?') {
/****  Aufeinanderfolgende '*'  ****/
/****  zu einem zusammenziehen  ****/
        if (k == 0 || ziel[k - 1] != '*') {
          ziel[k++] = '*';
        }
      } else {
        ziel[k++] = c;
      }
    }
  }
  ziel[k] = 0;
  return (k);
}

int 
WLD(wort, muster, modus, limit)
char *wort; 
char *muster; 
char modus; 
int limit;
{
  register int    spmin, p, q, r, lm, lw, d1, d2, i, k, x1, x2, x3;
  char            c, mm[maxlen], ww[maxlen];
  int             d[maxlen];

  if (limit == 0) {
    limit = maxlen;
  }
  if (modus == '+' || modus == '*') {
    lw = formatierung(ww, wort, maxlen, modus);
    lm = formatierung(mm, muster, maxlen, modus);

    if (modus == '*' && lw < lm - 1
        && strchr(ww, '*') != NULL) {
/****  Wort und Muster tauschen  ****/
      wort = mm;
      muster = ww;
      strcpy(ww + lw, "*");
      i = lw;
      lw = lm;
      lm = i + 1;
/****  Limit neu setzen  ****/
      i = (int) (i / 3);
      if (i < limit) {
        limit = i;
      }
    } else {
      wort = ww;
      muster = mm;
    }
  } else {
    lw = strlen(wort);
    lm = strlen(muster);
    if (lw >= maxlen)
      lw = (maxlen - 1);
    if (lm >= maxlen)
      lm = (maxlen - 1);
  }

/****  Anfangswerte berechnen ****/
  if (*muster == '*') {
    for (k = 0; k <= lw; k++) {
      d[k] = 0;
    }
  } else {
    d[0] = (*muster == 0) ? 0 : 1;
    i = (*muster == '?') ? 0 : 1;
    for (k = 1; k <= lw; k++) {
      if (*muster == *(wort + k - 1)) {
        i = 0;
      }
      d[k] = k - 1 + i;
    }
  }

  spmin = (d[0] == 0 || lw == 0) ? d[0] : d[1];
  if (spmin > limit) {
    return (maxlen);
  }
/****  Distanzmatrix durchrechnen  ****/
  for (i = 2; i <= lm; i++) {
    c = *(muster + i - 1);
    p = (c == '*' || c == '?') ? 0 : 1;
    q = (c == '*') ? 0 : 1;
    r = (c == '*') ? 0 : 1;
    d2 = d[0];
    d[0] = d2 + q;
    spmin = d[0];

    for (k = 1; k <= lw; k++) {
/****  d[k] = Minimum dreier Zahlen  ****/
      d1 = d2;
      d2 = d[k];
      x1 = d1 + ((c == *(wort + k - 1)) ? 0 : p);
      x2 = d2 + q;
      x3 = d[k - 1] + r;

      if (x1 < x2) {
        x2 = x1;
      }
      d[k] = (x2 < x3) ? x2 : x3;

      if (d[k] < spmin) {
        spmin = d[k];
      }
    }

    if (spmin > limit) {
      return (maxlen);
    }
  }
  return ((d[lw] <= limit) ? d[lw] : maxlen);
}
1	ulpfr	10	/** 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			#ifdef __cplusplus
16			extern "C" {
17			#endif
18			#include "EXTERN.h"
19			#include "perl.h"
20			#include "XSUB.h"
21			#ifdef __cplusplus
22			}
23
24			#endif
25			#define maxlen 51
26			char *strchr();
27
28			int
29			formatierung(char ziel[], char wort[], int n, char modus)
30			/** Wandelt "wort" in GROSSschreibung **/
31			/** um und expandiert Umlaute **/
32			/** (n = Zeichenzahl von "ziel") **/
33			/** Zurückgegeben wird: strlen (ziel) **/
34			{
35			int i, k;
36			char c, *s;
37
38			i = 0;
39			k = 0;
40			while ((c = wort[i++]) != 0 && k < n - 1) {
41			if (isupper(c) \|\| isdigit(c)) {
42			ziel[k++] = c;
43			} else if (islower(c)) {
44			ziel[k++] = c - 'a' + 'A';
45			} else {
46			s = strchr("ÄAEäAEÖOEöOEÜUEüUEßSS", c);
47			if (s != NULL) {
48			ziel[k++] = *(s + 1);
49			if (k < n - 1) {
50			ziel[k++] = *(s + 2);
51			}
52			} else if (modus == '*' && c != '?') {
53			/**** Aufeinanderfolgende '' ***/
54			/** zu einem zusammenziehen **/
55			if (k == 0 \|\| ziel[k - 1] != '*') {
56			ziel[k++] = '*';
57			}
58			} else {
59			ziel[k++] = c;
60			}
61			}
62			}
63			ziel[k] = 0;
64			return (k);
65			}
66
67			int
68			WLD(wort, muster, modus, limit)
69			char *wort;
70			char *muster;
71			char modus;
72			int limit;
73			{
74			register int spmin, p, q, r, lm, lw, d1, d2, i, k, x1, x2, x3;
75			char c, mm[maxlen], ww[maxlen];
76			int d[maxlen];
77
78			if (limit == 0) {
79			limit = maxlen;
80			}
81			if (modus == '+' \|\| modus == '*') {
82			lw = formatierung(ww, wort, maxlen, modus);
83			lm = formatierung(mm, muster, maxlen, modus);
84
85			if (modus == '*' && lw < lm - 1
86			&& strchr(ww, '*') != NULL) {
87			/** Wort und Muster tauschen **/
88			wort = mm;
89			muster = ww;
90			strcpy(ww + lw, "*");
91			i = lw;
92			lw = lm;
93			lm = i + 1;
94			/** Limit neu setzen **/
95			i = (int) (i / 3);
96			if (i < limit) {
97			limit = i;
98			}
99			} else {
100			wort = ww;
101			muster = mm;
102			}
103			} else {
104			lw = strlen(wort);
105			lm = strlen(muster);
106			if (lw >= maxlen)
107			lw = (maxlen - 1);
108			if (lm >= maxlen)
109			lm = (maxlen - 1);
110			}
111
112			/** Anfangswerte berechnen **/
113			if (muster == '') {
114			for (k = 0; k <= lw; k++) {
115			d[k] = 0;
116			}
117			} else {
118			d[0] = (*muster == 0) ? 0 : 1;
119			i = (*muster == '?') ? 0 : 1;
120			for (k = 1; k <= lw; k++) {
121			if (muster == (wort + k - 1)) {
122			i = 0;
123			}
124			d[k] = k - 1 + i;
125			}
126			}
127
128			spmin = (d[0] == 0 \|\| lw == 0) ? d[0] : d[1];
129			if (spmin > limit) {
130			return (maxlen);
131			}
132			/** Distanzmatrix durchrechnen **/
133			for (i = 2; i <= lm; i++) {
134			c = *(muster + i - 1);
135			p = (c == '*' \|\| c == '?') ? 0 : 1;
136			q = (c == '*') ? 0 : 1;
137			r = (c == '*') ? 0 : 1;
138			d2 = d[0];
139			d[0] = d2 + q;
140			spmin = d[0];
141
142			for (k = 1; k <= lw; k++) {
143			/** d[k] = Minimum dreier Zahlen **/
144			d1 = d2;
145			d2 = d[k];
146			x1 = d1 + ((c == *(wort + k - 1)) ? 0 : p);
147			x2 = d2 + q;
148			x3 = d[k - 1] + r;
149
150			if (x1 < x2) {
151			x2 = x1;
152			}
153			d[k] = (x2 < x3) ? x2 : x3;
154
155			if (d[k] < spmin) {
156			spmin = d[k];
157			}
158			}
159
160			if (spmin > limit) {
161			return (maxlen);
162			}
163			}
164			return ((d[lw] <= limit) ? d[lw] : maxlen);
165			}