bitmat.c

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

      }
      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, int pfx)
{                               /* --- 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->mode & BM_MAXIMAL) {  /* if maximal item sets, */
          *(mat->vecs[i]-1) |= NOREPORT;   /* mark non-maximal */
          *(mat->vecs[k]-1) |= NOREPORT; } /* item sets */
        else if (ao->mode & BM_CLOSED) {   /* 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 non-maximal item sets */
        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)        /* if the new matrix is empty, */
        continue;               /* no recursion is needed */
      ao->rows[depth-1] = *(mat->vecs[i]-2);
      cnt += k = _search(ao, red, depth, pfx);
      if (k < 0) break;         /* recursively search for a submatrix */
      if (k > 0) pfx = depth-1; /* (i.e., frequent item sets), */
    }                           /* then update the prefix length */
    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 below minimum number of items, */
    return cnt;                 /* no reporting is needed */
  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->mode == 0)     /* if to find free item sets, */
      n = 0;                    /* definitely report the item set */
    else if (p[1] & NOREPORT)   /* if already known to be non-closed */
      n = 1;                    /* or non-maximal, skip the item set */
    else if (ao->repos)         /* if to filter with repository */
      n = _exists(ao->repos, ao->rows, depth, p[1] & ~NOREPORT);
    else if (ao->mode & BM_CLOSED) /* if to filter closed item sets */
      n = _closed (ao, ao->rows, depth, p+2) ? 0 : 1;
    else                        /* if to filter maximal item sets */
      n = _maximal(ao, ao->rows, depth, p+2) ? 0 : 1;
    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, pfx,
                      (mat->len < 0) ? k:-k, p+2, ao->data);
  }                             /* report 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->mode   = (mode & (BM_CLOSED|BM_MAXIMAL)) ? mode : 0;
  ao->min    = min;             /* store the parameters */
  ao->max    = max;             /* in the search structure */
  ao->supp   = (supp > 0) ? supp : 1;
  ao->report = report;
  ao->data   = data;
  ao->repos  = 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 */
  ao->init = mat;               /* and note it in the structure */
  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|BM_MAXIMAL))
  &&  (mode & BM_REPOS)) {      /* if to use a repository */
    ao->repos = bm_create(bm->rowcnt, 0, bm->sparse);
    if (!ao->repos || (_buffers(ao->repos, 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, 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->repos) {              /* that was used during the search */
    bm->mem += sizeof(BITMAT) +(ao->repos->rowcnt+1) *sizeof(int*);
    if (ao->repos->supps) bm->mem += ao->repos->colvsz *sizeof(int);
    if (ao->repos->sparse) {    /* if sparse matrix */
      for (k = ao->repos->rowcnt; --k >= 0; )
        bm->mem += *(ao->repos->rows[k]-1) +2; }
    else {                      /* if normal matrix */
      bm->mem += ao->repos->rowcnt
	*((ao->repos->colcnt +BM_MASK) >> BM_SHIFT);
    }                           /* add amount of memory for */
  }                             /* closed/maximal item set matrix */
  #endif
  if (ao->repos) bm_delete(ao->repos);
  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.
----------------------------------------------------------------------*/