bitmat.c

数据挖掘中的eclat算法,很好的代码

    if (colcnt > c) {           /* if the bit vectors are full */
      c += (c > (BLKSIZE << BM_SHIFT)) ? c >> 1 : (BLKSIZE << BM_SHIFT);
      if (colcnt > c) c = colcnt;
    }                           /* compute a new size for the vectors */
    n = ((c +BM_MASK) >> BM_SHIFT) +2;
  }                             /* and the number of integers in them */
  if (rowcnt > bm->rowcnt) {    /* if to add rows to the matrix */
    k = bm->rowvsz;             /* get the size of the rows vector */
    if (rowcnt > k) {           /* if the rows vector is full */
      k += (k > BLKSIZE) ? k >> 1 : BLKSIZE;
      if (rowcnt > k) k = rowcnt;  /* compute new number of rows */
      rows = (int**)realloc(bm->rows, k *sizeof(int*));
      if (!rows) return -1;     /* resize the rows vector */
      bm->rows = rows; bm->rowvsz = k;
    }                           /* set the new vector and its size */
    for (row = bm->rowcnt; row < rowcnt; row++) {
      vec = (int*)calloc(n, sizeof(int));
      if (!vec) break;          /* allocate bit vectors */
      bm->rows[row] = vec+2;    /* for the new rows */
      vec[0] = row;             /* note the row identifier */
    }
    if (row < rowcnt) {         /* if the row allocation failed */
      while (--row >= bm->rowcnt) free(bm->rows[row]-2);
      return -1;                /* delete the row vectors */
    }                           /* that could be allocated */
  }                             /* and abort the function */
  if (!bm->sparse               /* if not a sparse bit matrix */
  &&  (colcnt > bm->colvsz)) {  /* and to add columns to the matrix */
    for (row = bm->rowcnt; --row >= 0; ) {
      vec = (int*)realloc(bm->rows[row]-2, n *sizeof(int));
      if (!vec) break;          /* enlarge the already existing */
      bm->rows[row] = vec+2;    /* vectors and set the new ones */
      vec += i = ((bm->colvsz +BM_MASK) >> BM_SHIFT) +2;
      for (k = n-i; --k >= 0; ) *vec++ = 0;
    }                           /* clear new columns */
    if ((row < 0)               /* if reallocation succeeded */
    &&  (_bufrsz(bm, n-2, c) == 0))
      bm->colvsz = c;           /* set the new column vector size */
    else {                      /* if the reallocation failed */
      if (rowcnt > bm->rowcnt){ /* if rows have been added */
        for (row = rowcnt; --row >= bm->rowcnt; )
          free(bm->rows[row]-2);/* delete the newly */
      }                         /* allocated matrix rows */
      n = ((bm->colvsz +BM_MASK) >> BM_SHIFT) +2;
      while (++row < bm->rowcnt)
        bm->rows[row] = (int*)realloc(bm->rows[row]-2, n*sizeof(int))+2;
      return -1;                /* shrink the bit vectors */
    }                           /* to their original size */
  }                             /* and abort the function */
  if (bm->sparse && (_bufrsz(bm, colcnt, colcnt) != 0))
    return -1;                  /* enlarge buffers of sparse matrix */
  if (rowcnt < bm->rowcnt) {    /* if to remove rows */
    for (row = bm->rowcnt; --row >= rowcnt; )
      free(bm->rows[row] -2);   /* delete superfluous rows */
  }
  bm->rowcnt = rowcnt;          /* set the new number of rows */
  bm->colcnt = colcnt;          /* and the new number of columns */
  return 0;                     /* return 'ok' */
}  /* bm_resize() */

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

void bm_setcol (BITMAT *bm, int col, const int *ids, int n)
{                               /* --- set a matrix column */
  int b;                        /* bit mask */

  assert(bm && ids);            /* check the function arguments */
  b = 1 << (col & BM_MASK);     /* compute bit mask and */
  col >>= BM_SHIFT;             /* index for the new column */
  while (--n >= 0)              /* traverse the given indices and */
    bm->rows[*ids++][col] |= b; /* set the corresponding rows */
}  /* bm_setcol() */

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

int bm_addcol (BITMAT *bm, const int *ids, int n)
{                               /* --- 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 _closed (ALLONE *ao, int *ids, int n, int *tal)
{                               /* --- check for a closed item set */
  int i, j, k;                  /* loop variables */
  int *row;                     /* to traverse the rows */

  if (n >= ao->max) return -1;  /* all maximum size sets are closed */
  for (i = ao->init->cnt; --i >= 0; ) {
    row = ao->init->vecs[i];    /* traverse all rows that */
    if (row == NULL) continue;  /* have not been added before */
    if (*ids == *(row-2)) { if (--n <= 0) break; ids++; continue; }
    if (ao->init->len <= 0) {   /* if sparse representation */
      j = *(row-1) & ~NOREPORT; /* get the number of column ids */
      k = *(tal-1)-1;           /* (i.e. the item set support) */
      while ((--j >= 0) && (k >= 0)) {
        if (row[j] <  tal[k]) break;
        if (row[j] == tal[k]) --k;
      } }                       /* check for a column subset */
    else {                      /* if normal representation */
      for (k = ao->init->len; --k >= 0; )
        if ((row[k] & tal[k]) != tal[k]) break;
    }                           /* check for a column subset */
    if (k < 0) return 0;        /* if column subset of some row, */
  }                             /* the item set is not closed */
  return -1;                    /* otherwise it is */
}  /* _closed() */

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

static int _maximal (ALLONE *ao, int *ids, int n, int *tal)
{                               /* --- check for a maximal item set */
  int i, j, k, x;               /* loop variables, buffer */
  int *row;                     /* to traverse the rows */
  int supp;                     /* support of extension */

  if (n >= ao->max) return -1;  /* all maximum size sets are maximal */
  for (i = ao->init->cnt; --i >= 0; ) {
    row = ao->init->vecs[i];    /* traverse all rows/items that */
    if (row == NULL) continue;  /* have not been added before */
    if (*ids == *(row-2)) { if (--n <= 0) break; ids++; continue; }
    supp = 0;                   /* initialize the support counter */
    if (ao->init->len <= 0) {   /* if sparse representation */
      j = (*(row-1) & ~NOREPORT)-1;
      k = *(tal-1)-1;           /* get the number of column ids */
      while ((j >= 0) && (k >= 0)) {
        if      (row[j] > tal[k]) --j;
        else if (row[j] < tal[k]) --k;
        else if (++supp >= ao->supp) return 0;
        else { --j; --k; }      /* count the common elements and */
      } }                       /* thus compute extension support */
    else {                      /* if normal representation */
      for (k = ao->init->len; --k >= 0; ) {
        x = row[k] & tal[k];    /* traverse the row */
        supp += _bctab[x & 0xffff] +_bctab[(x >> 16) & 0xffff];
        if (supp >= ao->supp) return 0;
      }                         /* count bits in intersection and */
    }                           /* thus compute extension support */
    if (supp >= ao->supp) return 0;
  }
  return -1;                    /* return 'item set is maximal' */
}  /* _maximal() */

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

static int _exists (BITMAT *bm, int *ids, int n, int supp)
{                               /* -- check existence in repository */
  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 */