bitmat.c

A program to find frequent itemsets (also closed and maximal) with the eclat algorithm ,which carrie

{                               /* --- add a matrix column */
  int i;                        /* loop variable */
  int *v;                       /* buffer for number vector */

  assert(bm);                   /* check the function arguments */
  for (i = n; --i >= 0; ) {     /* traverse the given indices */
    v = bm->rows[ids[i]] -2;    /* get the number vector */
    if ((v[1] & BLKMASK) != 0) continue;
    v = (int*)realloc(v, (v[1] +BLKSIZE +2) *sizeof(int));
    if (!v) return -1;          /* if the number vector is full, */
    bm->rows[ids[i]] = v+2;     /* resize the number vector */
  }                             /* and set the new vector */
  if (_bufrsz(bm, bm->colcnt+1, bm->colcnt+1) != 0)
    return -1;                  /* enlarge the buffers */
  for (i = n; --i >= 0; ) {     /* traverse the given indices */
    v = bm->rows[ids[i]];       /* get the number vector */
    v[(*(v-1))++] = bm->colcnt; /* add the new matrix column */
  }                             /* to the column list */
  return bm->colcnt++;          /* return the column index */
}  /* bm_addcol() */

/*--------------------------------------------------------------------*/

int bm_count (BITMAT *bm, int row)
{                               /* --- count ones in a row vector */
  if (bm->sparse) return *(bm->rows[row] -1);
  return _count(bm->rows[row], (bm->colcnt +BM_MASK) >> BM_SHIFT);
}  /* bm_count() */

/*--------------------------------------------------------------------*/

static int _exists (BITMAT *bm, int *ids, int n, int supp)
{                               /* -- check maximal/closed item sets */
  int i, k, x, m = n;           /* loop variables */
  int b, bb;                    /* support bit mask */
  int *d, *s;                   /* to traverse the bit vectors */
  int r = 0;                    /* result of intersection */

  assert(bm && bm->buf && ids); /* check the function arguments */
  d = bm->buf;                  /* get the intersection buffer */
  if (bm->sparse) {             /* if sparse matrix */
    if (bm->supps) {            /* if to find closed item sets, */
      s = bm->supps;            /* traverse the supports vector */
      for (i = 0; i < bm->colcnt; i++)
        if (*s++ == supp) *d++ = i;
      r = (int)(d -bm->buf); }  /* collect same support sets */
    else {                      /* if to find maximal item sets, */
      s = bm->rows[ids[--m]];   /* traverse vector for last item */
      for (i = r = *(s-1); --i >= 0; )
        *d++ = *s++;            /* copy the transaction/column list */
    }                           /* to the intersection buffer */
    if (r > 0) {                /* if the buffer is not empty */
      *(bm->buf -1) = r;        /* number of entries in the buffer */
      while (--m >= 0) {        /* traverse the remaining items */
        if (_isect2(bm->buf, bm->buf, bm->rows[ids[m]]) <= 0)
          break;                /* intersect with the next list */
      }                         /* and check for an empty result */
      if (m < 0) return 1;      /* if the intersection is not empty, */
    }                           /* return "superset exists" */
    k = bm->colcnt;             /* get the number of columns */
    if (bm_addcol(bm, ids, n) < 0)
      return -1; }              /* enter itemset into the matrix */
  else {                        /* if normal matrix */
    k = (bm->colcnt +BM_MASK) >> BM_SHIFT;
    s = bm->rows[ids[--m]];     /* traverse vector for last item */
    if (bm->supps) {            /* if to find closed item sets */
      for (x = i = 0; i < k; i++) {
        for (bb = 0, b = 1; b & MASK; b <<= 1)
          if (bm->supps[x++] == supp)
            bb |= b;            /* collect same support sets and */
        r |= d[i] = s[i] & bb;  /* combine the resulting bit flags */
      } }                       /* with the last item's vector */
    else {                      /* if to find maximal item sets, */
      for (s += k, d += i = k; --i >= 0; )
        r |= *--d = *--s;       /* copy the last item's vector */
    }                           /* and check for an empty result */
    if (r != 0) {               /* if the buffer is not empty */
      while (--m >= 0) {        /* traverse the remaining items */
        s = bm->rows[ids[m]]+k; /* traverse the item's bit vector */
        for (r = 0, d += i = k; --i >= 0; )
          r |= *--d &= *--s;    /* intersect with the next item */
        if (r == 0) break;      /* and check for an empty result */
      }
      if (m < 0) return 1;      /* if the intersection is not empty, */
    }                           /* return "superset exists" */
    if (bm_resize(bm, bm->rowcnt, (k = bm->colcnt) +1) < 0)
      return -1;                /* enlarge the bit matrix and */
    bm_setcol(bm, k, ids, n);   /* enter itemset into the matrix */
  }
  if (bm->supps)                /* if there is a supports vector, */
    bm->supps[k] = supp;        /* note the item set support */
  return 0;                     /* return "new item set" */
}  /* _exists() */

/*--------------------------------------------------------------------*/

static int _search (ALLONE *ao, REDMAT *mat, int depth)
{                               /* --- search row intersections */
  int    i, k, n;               /* loop variables, bit counter */
  REDMAT *red;                  /* bit vector set for next level */
  int    *vecs, *p;             /* to traverse the bit vectors */
  int    cnt = 0;               /* number of item sets found */
  int    m;                     /* size of memory for new matrix */

  /* --- search recursively --- */
  n = ao->min - ++depth;        /* compute the min. number of vectors */
  if (n <= 0) n = 1;            /* needed to reach the minimum size */
  if ((depth < ao->max)         /* if search depth not yet reached */
  &&  (mat->cnt > n)) {         /* and there are enough vectors left */
    red = (REDMAT*)malloc(sizeof(REDMAT) +(mat->cnt-2) *sizeof(int*));
    if (!red) return -1;        /* allocate matrix for the next level */
    red->len = mat->len;        /* and initialize it */
    if (mat->len >= 0)          /* if normal matrix */
      m = (mat->cnt-1) *(mat->len+2);
    else {                      /* if sparse matrix */
      for (m = 2 *(i = mat->cnt-1); --i >= 0; )
        m += *(mat->vecs[i]-1); /* sum the sizes of the vectors */
    }                           /* (compute size of needed memory) */
    vecs = (int*)malloc(m *sizeof(int));
    if (!vecs) { free(red); return -1; }
    #ifdef BENCH                /* if benchmark version */
    ao->mcur += sizeof(REDMAT) +(mat->cnt-2) *sizeof(int*)
              + m *sizeof(int); /* compute current memory usage */
    if (ao->mcur > ao->mmax) ao->mmax = ao->mcur;
    #endif                      /* adapt maximal memory usage */
    for (i = mat->cnt; --i >= n; ) {
      red->cnt = 0; p = vecs;   /* traverse the bit vectors */
      for (k = 0; k < i; k++) { /* traverse the remaining vectors */
        if (((mat->len >= 0)    /* intersect two bit/number vectors */
        ?   _isect1(p+2, mat->vecs[i], mat->vecs[k], mat->len)
        :   _isect2(p+2, mat->vecs[i], mat->vecs[k])) < ao->supp)
          continue;             /* if the support is too low, skip */
        if (ao->res) {          /* if closed/maximal item sets */
          if (!ao->res->supps){ /* mark non-maximal item sets */
            *(mat->vecs[i]-1) |= NOREPORT;
            *(mat->vecs[k]-1) |= NOREPORT; }
          else {                /* if closed item sets */
            if ((p[1] & ~NOREPORT) == (*(mat->vecs[i]-1) & ~NOREPORT))
              *(mat->vecs[i]-1) |= NOREPORT;
            if ((p[1] & ~NOREPORT) == (*(mat->vecs[k]-1) & ~NOREPORT))
              *(mat->vecs[k]-1) |= NOREPORT;
          }                     /* mark subsets if they have */
        }                       /* the same support as the superset */
        red->vecs[red->cnt++] = p+2;
        *p = *(mat->vecs[k]-2); /* store and count the intersection */
        p += ((mat->len < 0) ? p[1] : mat->len) +2;
      }                         /* advance the vector pointer */
      if (red->cnt <= 0) continue; /* if the matrix is empty, cont. */
      ao->rows[depth-1] = *(mat->vecs[i]-2);
      cnt += k = _search(ao, red, depth);
      if (k < 0) break;         /* recursively search for a submatrix */
    }                           /* (i.e., frequent itemsets) */
    free(vecs); free(red);      /* delete the work buffers */
    #ifdef BENCH                /* if benchmark version */
    ao->mcur -= sizeof(REDMAT) +(mat->cnt-2) *sizeof(int*)
              + m *sizeof(int); /* compute current memory usage */
    #endif
    if (i >= n) return -1;      /* check for a search error */
  }  /* if ((depth < ao->max) .. */

  /* --- report (and record) found item sets --- */
  if (depth >= ao->min) {       /* if minimum number of rows reached */
    for (i = 0; i < mat->cnt; i++) {
      p = mat->vecs[i]-2;       /* traverse the bit vectors */
      ao->rows[depth-1] = p[0]; /* note the last row identifier */
      if      (!ao->res)        n = 0; /* if free item sets, report */
      else if (p[1] & NOREPORT) n = 1; /* skip non-closed/non-maximal */
      else n = _exists(ao->res, ao->rows, depth, p[1] & ~NOREPORT);
      if (n < 0) return -1;     /* record closed/maximal item set */
      if (n > 0) continue;      /* if the item set qualifies */
      k = p[1] & ~NOREPORT;     /* get the item set support */
      cnt += ao->report(ao->rows, depth,
                        (mat->len < 0) ? k:-k, p+2, ao->data);
    }                           /* report the solutions found */
  }                             /* and count the item sets */
  return cnt;                   /* return number of item sets */
}  /* _search() */

/*--------------------------------------------------------------------*/

static int _buffers (BITMAT *bm, int mode)
{                               /* --- add buffers to created matrix */
  bm->buf = (int*)malloc((BLKSIZE+1) *sizeof(int)) +1;
  if (!bm->buf)   { bm_delete(bm); return -1; }
  if (mode != BM_CLOSED) return 0;
  bm->supps = (int*)malloc((BLKSIZE << BM_SHIFT) *sizeof(int));
  if (!bm->supps) { bm_delete(bm); return -1; }
  return 0;                     /* allocate additional buffers */
}  /* _buffers() */

/*--------------------------------------------------------------------*/

int bm_allone (BITMAT *bm, int mode, int supp, int min, int max,
               BMREPFN report, void *data)
{                               /* --- find all one submatrices */
  int    k, n;                  /* loop variable, return code */
  ALLONE *ao;                   /* structure for recursive search */
  REDMAT *mat;                  /* reduced bit matrix for searching */

  assert(bm                     /* check the function arguments */
  &&     (min >= 0) && (max >= min));
  ao = (ALLONE*)malloc(sizeof(ALLONE) +(max-1) *sizeof(int));
  if (!ao) return -1;           /* create a search structure */
  ao->min    = min;            /* and store the parameters */
  ao->max    = max;            /* in this structure */
  ao->supp   = (supp > 0) ? supp : 1;
  ao->report = report;
  ao->data   = data;
  ao->res    = NULL;
  #ifdef BENCH                  /* if benchmark version, */
  ao->mcur   = sizeof(ALLONE) +(max-1)        *sizeof(int)
             + sizeof(REDMAT) +(bm->rowcnt-1) *sizeof(int*)
             + sizeof(BITMAT) +(bm->rowcnt-1) *sizeof(int*);
  #endif                        /* compute initial memory usage */
  mat = (REDMAT*)calloc(1, sizeof(REDMAT) +(bm->rowcnt-1)*sizeof(int*));
  if (!mat) { free(ao); return -1; }
  n = (bm->colcnt +BM_MASK) >> BM_SHIFT;
  mat->len = (bm->sparse) ? -1 : n;
  mat->cnt = 0;                 /* create a reduced bit matrix */
  for (k = 0; k < bm->rowcnt; k++) {
    #ifdef BENCH                /* if benchmark version */
    ao->mcur += ((bm->sparse) ? *(bm->rows[k] -1) : n) +2;
    #endif                      /* sum the vector sizes */
    if (bm_count(bm, k) >= supp)
      mat->vecs[mat->cnt++] = bm->rows[k];
  }                             /* copy the qualifying rows */
  if ((mode == BM_CLOSED)       /* if to find closed */
  ||  (mode == BM_MAXIMAL)) {   /* or maximal item sets */
    ao->res = bm_create(bm->rowcnt, 0, bm->sparse);
    if (!ao->res || (_buffers(ao->res, mode) != 0)) {
      free(mat); free(ao); return -1; }
  }                             /* create result matrix */
  #ifdef BENCH                  /* if benchmark version, */
  ao->mmax = ao->mcur;          /* initialize maximal memory usage */
  #endif
  n = _search(ao, mat, 0);      /* do the recursive search */
  for (k = mat->cnt; --k >= 0;) /* clear 'no report' flags */
    *(mat->vecs[k] -1) &= ~NOREPORT;
  #ifdef BENCH                  /* if benchmark version, */
  bm->mem = ao->mmax;           /* note the maximum amount of memory */
  if (ao->res) {                /* that was used during the search */
    bm->mem += sizeof(BITMAT) +(ao->res->rowcnt+1) *sizeof(int*);
    if (ao->res->supps) bm->mem += ao->res->colvsz *sizeof(int);
    if (ao->res->sparse) {      /* if sparse matrix */
      for (k = ao->res->rowcnt; --k >= 0; )
        bm->mem += *(ao->res->rows[k]-1) +2; }
    else {                      /* if normal matrix */
      bm->mem += ao->res->rowcnt
	*((ao->res->colcnt +BM_MASK) >> BM_SHIFT);
    }                           /* add amount of memory for */
  }                             /* closed/maximal item set matrix */
  #endif
  if (ao->res) bm_delete(ao->res);
  free(mat); free(ao);          /* delete the work buffers */
  return n;                     /* return the error status */
}  /* bm_allone() */

/*--------------------------------------------------------------------*/
#ifndef NDEBUG

void bm_show (BITMAT *bm, FILE *file, int transpose)
{                               /* --- show a bit matrix */
  int row, col, i, k, n, b;     /* loop variables, bit mask */
  int *p;                       /* to traverse a bit vector */

  assert(bm);                   /* check the function argument */
  if (transpose) {              /* if to transpose the matrix */
    for (col = 0; col < bm->colcnt; col++) {
      i = col >> BM_SHIFT; b = 1 << (col & BM_MASK);
      for (row = 0; row < bm->rowcnt; row++)
        putc((bm->rows[row][i] & b) ? '1' : '0', file);
      putc('\n', file);         /* print one column per row */
    } }
  else {                        /* if not to transpose the matrix */
    n = bm->colcnt >> BM_SHIFT; /* get the number of full integers */
    k = bm->colcnt &  BM_MASK;  /* and the number of bits in the last */
    for (row = 0; row < bm->rowcnt; row++) {
      p = bm->rows[row];        /* traverse the matrix rows */
      for (i = n; --i >= 0; p++)/* traverse the integers in a row */
        for (b = 1; b & MASK; b <<= 1)
          putc((*p & b) ? '1' : '0', file);
      for (b = 0; b < k; b++)   /* process last integer separately */
        putc((*p & (1 << b)) ? '1' : '0', file);
      putc('\n', file);         /* print one row */
    }
  }
}  /* bm_show() */

#endif
/*----------------------------------------------------------------------
Note that the above function works only for non-sparse representations.
----------------------------------------------------------------------*/