code

Simplified Backward Nondeterministic DAWG Matching with q-grams

The Simplified Backward Nondeterministic DAWG Matching with q-grams algorithm
sbndmq8.c
#define F_8(j) (B[y[j]]<<7)&(B[y[j-1]]<<6)&(B[y[j-2]]<<5)&(B[y[j-3]]<<4)&(B[y[j-4]]<<3)&(B[y[j-5]]<<2)&(B[y[j-6]]<<1)&B[y[j-7]]

int search(unsigned char *x, int m, unsigned char *y, int n) {
   unsigned int B[SIGMA], D, q, shift;
   int i, j, pos, mMinusq, mq, count;
   q = 8;

   if (m<q) return -1;
   if (m>32) return search_large(x,m,y,n);

   /* Preprocessing */
   count = 0;
   mMinusq = m - q +1;
   mq = m - q;
   for (i=0; i<SIGMA; i++) B[i]=0;
   for (i = 1; i <= m; ++i)
      B[x[m-i]] |= (1<<(i-1));

   D = B[x[m-2]]; j=1; shift=0;
   if (D & (1<<(m-1))) shift = m-j;
   for (i=m-3; i>=0; i--) {
      D = (D<<1) & B[x[i]];
      j++;
      if (D & (1<<(m-1))) shift = m-j;
   }

   /* Searching */
   if ( !memcmp(x,y,m) ) OUTPUT(0);
   j = m;
   while (j < n) {
      D = F_8(j);
      if (D != 0) {
         pos = j;
         while (D=(D<<1) & B[y[j-q]]) --j;
         j += mq;
         if (j == pos) {
            OUTPUT(j);
            j+=shift;
         }
      }
      else j+=mMinusq;
   }
   return count;
}

/*
 * Simplified Backward Nondeterministic DAWG Matching using q-grams designed for large patterns
 * The present implementation searches for prefixes of the pattern of length 32.
 * When an occurrence is found the algorithm tests for the whole occurrence of the pattern
 */


int search_large(unsigned char *x, int m, unsigned char *y, int n) {
   unsigned int B[SIGMA], D, q, shift;
   int i, j, pos, mMinusq, mq, count, p_len;
   q = 8;

   if (m<q) return 0;
   p_len = m;
   m = 32;
   int diff = p_len-m;
   
   /* Preprocessing */
   count = 0;
   mMinusq = m - q +1;
   mq = m - q;
   for (i=0; i<SIGMA; i++) B[i]=0;
   for (i = 1; i <= m; ++i)
      B[x[m-i]] |= (1<<(i-1));

   D = B[x[m-2]]; j=1; shift=0;
   if (D & (1<<(m-1))) shift = m-j;
   for (i=m-3; i>=0; i--) {
      D = (D<<1) & B[x[i]];
      j++;
      if (D & (1<<(m-1))) shift = m-j;
   }

   /* Searching */
   if ( !memcmp(x,y,p_len) ) OUTPUT(0);
   j = m;
   while (j+diff < n) {
      D = F_8(j);
      if (D != 0) {
         pos = j;
         while (D=(D<<1)&B[y[j-q]]) --j;
         j += mq;
         if (j == pos) {
            for (i=m+1; i<p_len && x[i]==y[j-m+1+i]; i++);
            if (i==p_len) OUTPUT(j-m+1);
            j+=shift;
         }
      }
      else j+=mMinusq;
   }
   return count;
}