home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / ctcoll95.zip / AEHNLICH / AFIND.C < prev    next >
C/C++ Source or Header  |  1995-04-06  |  6KB  |  161 lines
  1. /* afind.c: Approximative Suche mit dem Shift-AND-Algotithmus
  2.  * (c) Guido Gronek, Lion Ges. f. Systementwicklung m.b.H. & c't 5/95
  3.  */
  4. #include <stddef.h>
  5. #include <stdio.h>
  6. #include <string.h>
  7. #include <ctype.h>
  8. #include <limits.h>
  9. #include "bitfld.h"
  10. #include "parser.h"
  11. #include "afind.h"
  12.  
  13. static BITFLD MATCH,                         /* Matching Maske */
  14.           P,     /* 1-bit fuer fehlerfreie Musterteile */
  15.            STAR,     /* 0-bit hinter *-Wildcards im Muster */
  16.           N,   /* 0-bit, wenn erstes Zeichen im Muster */
  17.      T[UCHAR_MAX+1],        /* charakt. Vektoren aller Zeichen */
  18.      TT[UCHAR_MAX+1];     /* ... modifiziert fuer Multipattern */
  19.  
  20. static int M;                                  /* Musterlaenge */
  21. static int Withstars;             /* flag: Muster enthaelt '*' */
  22. static int Laststar;    /* flag: letztes Musterzeichen ist '*' */
  23. static int Leftstar;    /* Position-1 des ersten '*' im Muster */
  24. static int Ignore;       /* flag: Gross- gleich Kleinbuchstabe */
  25.  
  26. int amatcherr;                  /* Zahl der Fehler des Matches */
  27.  
  28. #define cap(c)     ( islower(c) ? toupper(c) : tolower(c) )
  29. #define strlast(t) ( t + strlen(t) - 1 )
  30.  
  31. /* user() wird vom Parser aufgerufen, wenn entweder ein Zeichen,
  32.  * eine Zeichenklasse, ein Wildcard oder die Token vom Typ
  33.  * T_LBRAC, T_RBRAC oder T_OR erkannt wurden.
  34.  */
  35. int user(void)
  36. { static int index;      /* Nummer des akt. Zeichens im Muster */
  37.   BITFLD *TC;
  38.   int c,j;
  39.  
  40.   if ( M < 0 ) {                              /* erster Aufruf */
  41.     for ( c=UCHAR_MAX+1, TC=T; --c>=0; ++TC )
  42.       *TC = BFALL();
  43.     MATCH = STAR = BFALL();
  44.     N = BFALL(); BITCLR(N,0); P = BFNULL();
  45.     Withstars = 0; Leftstar = -2;
  46.     M = 0; index = 0;
  47.   }
  48.   j = index;
  49.   if ( M > BITFLD_MAX ) return 1;       /* Muster ist zu lang! */
  50.   switch ( Token.type ) {
  51.     case T_STAR:                               /* '*'-Wildcard */
  52.       if ( Lasttoken.type == T_STAR || M==0 )
  53.     return 0;            /* am Anfang und vor * ignorieren */
  54.       if ( Withstars == 0 ) {
  55.     Withstars = 1;
  56.     Leftstar = j;                     /* erstes '*' merken */
  57.       }
  58.       Laststar = j;
  59.       if ( j>=0 && j<=BITFLD_MAX)
  60.     BITCLR(STAR,j);
  61.     break;
  62.     case T_QM:                                 /* '?'-Wildcard */
  63.       memset(Cset,1,sizeof(Cset));  /* steht fuer alle Zeichen */
  64.     case T_RPAREN:                            /* Zeichenklasse */
  65.       Laststar = 0;
  66.       for ( c=UCHAR_MAX+1; --c>0;  )
  67.     if ( Cset[c] ) {           /* wenn Zeichen i in Klasse */
  68.       BITCLR( *(T+c) ,j );            /* dann Bit loeschen */
  69.       if ( Ignore )              /* case-insensitive Suche */
  70.         BITCLR( *(T+cap(c)) ,j );
  71.     }
  72.       if (Protected) BITSET(P,j);
  73.       ++j; ++M;
  74.     break;
  75.     case T_LBRAC:               /* fehlerfreier Bereich Anfang */
  76.       if ( Protected ) return 1;                   /* Fehler ! */
  77.       else Protected = 1;
  78.     break;
  79.     case T_RBRAC:                 /* fehlerfreier Bereich Ende */
  80.       if ( Protected ) Protected = 0;
  81.       else return 1;                               /* Fehler ! */
  82.     break;
  83.     case T_OR:                         /* neues Parallelmuster */
  84.       if ( Protected ) return 1;                   /* Fehler ! */
  85.       BITCLR(N,j);
  86.     break;
  87.     default:                                    /* ein Zeichen */
  88.       Laststar = 0;                   /* ist kein '*'-Wildcard */
  89.       c = Token.value;
  90.       BITCLR( *(T + c) ,j );
  91.       if ( Ignore )                  /* case-insensitive Suche */
  92.     BITCLR( *(T + cap(c)) ,j );
  93.       if ( Protected ) BITSET(P,j);
  94.       ++j; ++M;
  95.     break;
  96.   }
  97.   index = j;
  98.   return 0;
  99. }
  100.  
  101. /* init_afind() bereitet die Suche vor
  102.  * Ergebnis: 0, falls alles O.K.
  103.  *           1, falls das Muster zu lang oder fehlerhaft ist
  104.  */
  105. int init_afind(char **pattern, int ignore)
  106. { int c,state;
  107.  
  108.   M = -1;
  109.   Ignore = ignore;
  110.   state = parsepattern(pattern);
  111.   Laststar = (Laststar==M-1);
  112.   for ( c=UCHAR_MAX+1; --c>=0; )
  113.     TT[c] = BFOR(T[c],N);    /* modifizierte charakt. Vektoren */
  114.   MATCH = BFRSHIFT(N,1);  /* Matching-Maske mit 0-bits, wo ein */
  115.   BITCLR(MATCH,M-1);    /* .. Zeichen das letzte im Muster ist */
  116.   return (M > BITFLD_MAX) ? 1 : state;
  117. }
  118.  
  119. /* afind:   durchsucht Text nach dem vorbereiteten Muster
  120.  * Eingabe: text:     Suchtext
  121.  *          errors:   Maximal zugelassene Fehler
  122.  *          minimize: flag: Match mit moeglichst wenig Fehlern
  123.  * Ausgabe: Zeiger auf Textstelle am Ende des Matches, oder NULL
  124.  *          die globale Variable amatcherr enthaelt die Zahl
  125.  *          der Fehler beim Match
  126.  */
  127. char *afind(char *text, int errors, int minimize)
  128. { static BITFLD STATES[MISMATCH_MAX+2];
  129.   BITFLD S, SS, SOR, TC, *SP;
  130.   char *t, *match = NULL;
  131.   int d;
  132.  
  133.   if ( text ==NULL ) return NULL;
  134.   amatcherr = 0;
  135.   SS = BFALL();                            /* SS ist S<j><d-1> */
  136.   SP = STATES;           /* Initialisiere die Zustandsvektoren */
  137.   for ( d=errors+1; --d>=0; SP[d] = SS ) ;
  138.   for ( t=text; *t; ++t ) {          /* fuer jedes Textzeichen */
  139.     TC = *(T + *t);        /* charakt. Vektor fuer das Zeichen */
  140.     for ( d=0; d<=errors; ++d )    /* fuer jeden moegl. Fehler */
  141.     { S = SP[d];                              /* S ist S<j><d> */
  142.       SOR = BFOR(BFLSHIFT(S,1),TC);
  143.       SOR = BFAND(SOR,TT[*t]);
  144.       if ( d>0 ) {
  145.     SS = BFAND( SP[d-1], BFLSHIFT(BFAND(SS,SP[d-1]),1) );
  146.     SS = BFAND( BFOR(P,SS), SOR );
  147.       }
  148.       else SS = SOR;
  149.       if (Withstars) SS = BFAND(SS,BFOR(S,STAR));
  150.       if ( BFOR(SS,MATCH) != BFALL() ) { /* Match mit d Fehlern */
  151.     amatcherr = d;
  152.     if ( d==0 || !minimize ) return t;
  153.     match = t; errors = d-1;
  154.       }
  155.       SP[d] = SS;
  156.       SS = S;
  157.     }
  158.   }
  159.   return match;
  160. }
  161.