aho.c

   1 #define DRIVER 1
   2
   3 #include <stdio.h>
   4 #include <stdlib.h>
   5 #include <string.h>
   6
   7 #include "code.h"
   8
   9 struct kword {
  10         unsigned char *word;
  11         struct kword *next;
  12 };
  13
  14 #define MAXCHAR 128
  15 //#define MAXCHAR 260
  16 //#define MAXCHAR 1030
  17
  18 static int MaxState;
  19
  20 static int *MatchArray;
  21
  22 #define MULTI_WAY -1
  23 #define EMPTY_SLOT -2
  24
  25 union GotoTable {
  26         int GotoState;
  27         int *BranchTable;
  28 } static *GotoArray;
  29
  30 #define FAIL_STATE -1
  31
  32 static struct kword **OutArray;
  33
  34 static int *FailArray;
  35
  36 static int HighState;
  37
  38 static void AddStateTrans ( int, int ,int );
  39 static void ComputeFail ( void );
  40 static void Enter ( unsigned char * );
  41 static void FindFail ( int state, int s, int a );
  42 static void QueueAdd ( int *queue, int qbeg, int new );
  43
  44 int RetrieveChar ( char **text );
  45
  46 int textcolumn = 0;
  47
  48 void MsrchInit ( struct kword *klist )
  49 {
  50         int i;
  51
  52         struct kword *ktemp;
  53
  54         MaxState = 1;
  55
  56         /* MaxState equals the number of characters */
  57         for ( ktemp = klist; ktemp != NULL; ktemp = ktemp->next)
  58                 MaxState += strlen( ktemp->word );
  59
  60         MatchArray = (int *) malloc ( sizeof(int) * MaxState );
  61         GotoArray = (union GotoTable *)  malloc (sizeof (union GotoTable) * MaxState );
  62         OutArray = (struct kword **)  malloc (sizeof (struct kword *) * MaxState );
  63         FailArray = (int *)  malloc (sizeof (int) * MaxState );
  64
  65         for ( i = 0; i < MaxState; i++) {
  66                 MatchArray[i] = EMPTY_SLOT;
  67                 OutArray[i]   = NULL;
  68                 }
  69
  70         HighState = 0;
  71         AddStateTrans ( 0, 'a', FAIL_STATE );
  72         AddStateTrans ( 0, 'b', FAIL_STATE );
  73
  74         for ( ; klist != NULL; klist = klist->next )
  75                 Enter ( klist->word );
  76
  77         for ( i = 0; i < MAXCHAR; i++)
  78                 if ( GotoArray[0].BranchTable[i] == FAIL_STATE )
  79                         GotoArray[0].BranchTable[i] = 0;
  80
  81         ComputeFail();
  82 }
  83
  84 /* Add transition from OldState to NewState for MatchChar */
  85 static void AddStateTrans ( int OldState, int MatchChar, int NewState )
  86 {
  87         int i, *temp;
  88
  89         if ( MatchArray[OldState] == EMPTY_SLOT ) {
  90                 MatchArray[OldState] = MatchChar;
  91                 GotoArray[OldState].GotoState = NewState;
  92         }
  93
  94         else
  95                 if ( MatchArray[OldState] == MULTI_WAY )
  96                         GotoArray[OldState].BranchTable[MatchChar] = NewState;
  97
  98         else {
  99
 100                 temp = (int *) malloc ( sizeof(int) * MAXCHAR );
 101
 102                 for ( i = 0; i < MAXCHAR; i++ )
 103                         temp[i] = FAIL_STATE;
 104
 105
 106                 temp[MatchArray[OldState]] = GotoArray[OldState].GotoState;
 107
 108                 temp[MatchChar] = NewState;
 109
 110                 MatchArray[OldState] = MULTI_WAY;
 111                 GotoArray[OldState].BranchTable = temp;
 112                 }
 113 }
 114
 115 /* Add word to the list of words the program recognises */
 116 static void Enter ( unsigned char *kword )
 117 {
 118         int state, k;
 119         char *save;
 120         struct kword *ktemp;
 121
 122         state = 0;
 123
 124         /* keep a copy */
 125         save = kword;
 126
 127         for ( ; *kword != '\0'; kword++ ) {
 128                 if ( MatchArray[state] == *kword )
 129                         state = GotoArray[state].GotoState;
 130
 131                 else
 132                         if ( MatchArray[state] == MULTI_WAY ) {
 133                                 if (( k = GotoArray[state].BranchTable[*kword] ) == FAIL_STATE)
 134                                         break;
 135                                 else
 136                                         state = k;
 137                         }
 138                         else
 139                                 break;
 140         }
 141
 142         for ( ; *kword != '\0'; kword++ ) {
 143                 HighState += 1;
 144
 145                 if ( HighState >= MaxState) {
 146                         printf("Too many states!\n");
 147                         exit(EXIT_FAILURE);
 148                 }
 149
 150                 AddStateTrans ( state, *kword, HighState );
 151                 state = HighState;
 152         }
 153
 154         ktemp = (struct kword *) malloc ( sizeof ( struct kword ));
 155         ktemp->word = save;
 156         ktemp->next = OutArray[state];
 157         OutArray[state] = ktemp;
 158 }
 159
 160 static void ComputeFail()
 161 {
 162         int *queue, qbeg, r, s;
 163         int i;
 164
 165         /* Allocate a queue */
 166         queue = (int *) malloc ( sizeof( int ) * MaxState);
 167         qbeg = 0;
 168         queue[0] = 0;
 169
 170         for ( i = 0; i < MAXCHAR; i++ )
 171                 if (( s = GotoArray[0].BranchTable[i] ) != 0 ) {
 172                         FailArray[s] = 0;
 173                         QueueAdd ( queue, qbeg, s );
 174                 }
 175
 176         while ( queue[qbeg] != 0)
 177         {
 178                 r = queue[qbeg];
 179                 qbeg = r;
 180
 181                 if ( MatchArray[r] == EMPTY_SLOT )
 182                         continue;
 183
 184                 else
 185                         if ( MatchArray[r] == MULTI_WAY ) {
 186                                 for ( i = 0; i < MAXCHAR; i++ )
 187                                         if (( s = GotoArray[r].BranchTable[i] ) != FAIL_STATE ) {
 188                                                 QueueAdd ( queue, qbeg, s );
 189                                                 FindFail ( FailArray[r], s, i);
 190                                         }
 191                         }
 192                 else {
 193                         QueueAdd ( queue, qbeg, GotoArray[r].GotoState );
 194                         FindFail ( FailArray[r], GotoArray[r].GotoState, MatchArray[r] );
 195                 }
 196         }
 197         free ( queue );
 198 }
 199
 200
 201 static void FindFail ( int s1, int s2, int a )
 202 {
 203         int on_fail;
 204         struct kword *ktemp, kdummy, *out_copy, *kscan;
 205
 206         for ( ; ; s1 = FailArray[s1] )
 207                 if ( MatchArray[s1] == a ) {
 208                         if (( on_fail = GotoArray[s1].GotoState ) != FAIL_STATE )
 209                                 break;
 210                 }
 211                 else
 212                         if ( MatchArray[s1] == MULTI_WAY )
 213                                 if (( on_fail = GotoArray[s1].BranchTable[a] ) != FAIL_STATE )
 214                                         break;
 215
 216         FailArray[s2] = on_fail;
 217
 218         if( OutArray[on_fail] == NULL )
 219                 out_copy = NULL;
 220         else {
 221
 222                 kscan = OutArray[on_fail];
 223                 out_copy = malloc ( sizeof (struct kword ));
 224                 out_copy->word = kscan->word;
 225                 out_copy->next = NULL;
 226
 227                 for ( kscan = kscan->next; kscan != NULL; kscan = kscan->next ) {
 228
 229                         ktemp = malloc ( sizeof ( struct kword ));
 230                         ktemp->word =  kscan->word;
 231                         ktemp->next = out_copy->next;
 232                         out_copy->next = ktemp;
 233                 }
 234         }
 235
 236         if (( kdummy.next = OutArray[s2] ) != NULL ) {
 237                 ktemp = &kdummy;
 238                 for ( ; ktemp->next->next != NULL; ktemp = ktemp->next )
 239                         ;
 240                 ktemp->next->next = out_copy;
 241         }
 242
 243         else
 244                 OutArray[s2] = out_copy;
 245 }
 246
 247 static void QueueAdd ( int *queue, int qbeg, int new )
 248 {
 249         int q;
 250
 251         q = queue[qbeg];
 252
 253         if ( q == 0 )
 254                 queue[qbeg] = new;
 255         else {
 256                 for ( ; queue[q] != 0; q = queue[q] )
 257                         ;
 258                 queue[q] = new;
 259         }
 260
 261         queue[new] = 0;
 262 }
 263
 264 /* Do the actual search */
 265 int MsrchGo ( char **text )
 266 {
 267         int state, c, g, mm;
 268         struct kword *kscan;
 269
 270         state = 0;
 271
 272         while (( c = RetrieveChar( text ) ) != EOF ) {
 273
 274                 for ( ;; ) {
 275
 276                         if ( state == 0 || ( mm = MatchArray[state] ) == MULTI_WAY )
 277                                 g = GotoArray[state].BranchTable[c];
 278
 279                         else
 280                                 if ( mm == c )
 281                                         g = GotoArray[state].GotoState;
 282
 283                         else
 284                                 g = FAIL_STATE;
 285
 286                         if ( g != FAIL_STATE )
 287                                 break;
 288
 289                         state = FailArray[state];
 290                 }
 291                 state = g;
 292
 293                 /* Output results */
 294                 if (( kscan = OutArray[state] ) != NULL )
 295                         for ( ; kscan != NULL; kscan = kscan->next )
 296                                 /* Break on the first result */
 297                                 return (textcolumn - strlen(kscan->word));
 298         }
 299         return -1;
 300 }
 301
 302 void MsrchEnd ( void )
 303 {
 304         int i;
 305
 306         struct kword *kscan;
 307
 308         for ( i = 0; i < MaxState; i++ )
 309                 if ( MatchArray[i] == MULTI_WAY )
 310                         free ( GotoArray[i].BranchTable );
 311
 312         free ( MatchArray );
 313         free ( GotoArray );
 314         free ( FailArray );
 315
 316         for ( i = 0; i < MaxState; i++ )
 317                 if ( OutArray[i] != NULL )
 318                         for ( kscan = OutArray[i]; kscan != NULL; kscan = kscan->next )
 319                                 free ( kscan );
 320
 321         free ( OutArray );
 322 }
 323
 324
 325 #ifdef DRIVER
 326
 327 #define BUFSIZE 200
 328
 329 FILE *infile;
 330 char inbuf[BUFSIZE];
 331 char *inbufptr;
 332 int linetextcolumn;
 333
 334 int textrow;
 335 int textlength;
 336
 337 int aho( char **text, char **pattern, int m, int n, int trow, int tcolumn, int prow, int tlength )
 338 {
 339         textrow = trow;
 340         textlength = tlength;
 341         textcolumn = tcolumn;
 342
 343         struct kword *khead, *ktemp;
 344
 345         int i;
 346
 347         linetextcolumn = 0;
 348         inbufptr = NULL;
 349
 350         khead = NULL;
 351
 352         char *pattern_small;
 353
 354         pattern_small = malloc (m + 1);
 355
 356         for( i = 0; i < m; i++)
 357                 pattern_small[i] = pattern[prow][i];
 358
 359         ktemp = ( struct kword * ) malloc ( sizeof ( struct kword ));
 360         ktemp->word = pattern_small;
 361         ktemp->next = khead;
 362
 363         if (khead != 0 && khead != ktemp)
 364                 if (khead->word == ktemp->word)
 365                         printf("Words point to the same thing - this is not valid\n");
 366
 367         khead = ktemp;
 368
 369         /* Setup system and pass list of words */
 370         MsrchInit ( khead );
 371
 372         /* Now search */
 373         int result = MsrchGo( text );
 374
 375         /* Do a clean up */
 376         MsrchEnd();
 377
 378         free ( pattern_small );
 379
 380         return ( result );
 381 }
 382
 383 int RetrieveChar( char **text )
 384 {
 385         if ( textcolumn < textlength ) {
 386                 textcolumn ++;
 387                 return text[textrow][textcolumn - 1];
 388         }
 389
 390         else
 391                 return ( EOF );
 392 }
 393
 394 #endif