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 
#ifndef strchr
char          *strchr();
# endif

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