code

Backward Nondeterministic DAWG Matching

The Backward Nondeterministic DAWG Matching algorithm
bndml.c

#define CHAR_BIT 8
#define WORD_TYPE unsigned int
#define WORD_BITS (sizeof(WORD_TYPE)*CHAR_BIT)
#define bit_size(bits) (((bits)+WORD_BITS-1)/WORD_BITS)
#define   bit_byte(bit) ((bit) / WORD_BITS)
#define   bit_mask(bit) (1L << ((bit) % WORD_BITS))
#define bit_alloc(bits) calloc(bit_size(bits), sizeof(WORD_TYPE))
#define   bit_set(name, bit) ((name)[bit_byte(bit)] |= bit_mask(bit))
#define   bit_clear(name, bit) ((name)[bit_byte(bit)] &= ~bit_mask(bit))
#define   bit_test(name, bit) ((name)[bit_byte(bit)] & bit_mask(bit))
#define bit_zero(name, bits) memset(name, 0, bit_size(bits) * sizeof(WORD_TYPE))
#define SHIFT_BNDM(a, b, n) ((a << (n)) | (b >> (WORD_BITS-(n))))

static void bit_alloc_n(WORD_TYPE **name, int n, int bits) {
   int i;
   name[0] = calloc(n * bit_size(bits), sizeof(WORD_TYPE));
   for (i = 1; i < n; i++) name[i] = name[0] + i*bit_size(bits);
}

int search(unsigned char *x, int m, unsigned char *y, int n) {
   int B[SIGMA];
   int i, j, s, D, last, count;

   if (m > 32) return search_large(x,m,y,n);

   /* Preprocessing */
   for (i=0; i<SIGMA; i++) B[i]=0;
   s=1;
   for (i=m-1; i>=0; i--) {
      B[x[i]] |= s;
      s <<= 1;
   }

   /* Searching */
   j=0; count=0;
   while (j <= n-m){
      i=m-1; last=m;
      D = ~0;
      while (i>=0 && D!=0) {
         D &= B[y[j+i]];
         i--;
         if (D != 0) {
            if (i >= 0) last = i+1;
            else count ++;
          }
          D <<= 1;
      }
      j += last;
   }
   return count;
}

/*
 * Backward Nondeterministic DAWG Matching Long patterns
 * The present implementation uses the multiword implementation of the BNDM algorithm
 */


int search_large(unsigned char *x, int m, unsigned char *y, int n)
{
   int i, j;
   WORD_TYPE *D, H, M;
   WORD_TYPE *B[SIGMA];
   int count = 0;

   bit_alloc_n(B, SIGMA, m);
   for (i = 0; i < m; i++) bit_set(B[x[m-1-i]], i);

   D = bit_alloc(m);
   j = m-1;
   while (j < n) {
      int k = 1;
      int l = 0;
      int x = 0;
      for (i = 0; i < bit_size(m); i++) {
         D[i] = B[y[j]][i];
         if (D[i]) x = 1;
      }
      while (k < m && x) {
         x = 0;
         if (bit_test(D, m-1)) l = k;
         H = 0;
         for (i = 0; i < bit_size(m); i++) {
            M = D[i];
            D[i] = SHIFT_BNDM(D[i], H, 1) & B[y[j-k]][i];
            if (D[i]) x = 1;
            H = M;
         }
         k++;
      }
      if (x) OUTPUT(j-m+1);
      j += m-l;
   }
   free(D);
   free(B[0]);
   return count;
}