bitmat.c

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

/*----------------------------------------------------------------------
  File    : bitmat.c
  Contents: bit matrix management
  Author  : Christian Borgelt
  History : 2002.06.09 file created
            2002.12.10 result report function extended
            2003.04.19 bug in _search fixed (min. number of vectors)
            2003.08.16 bug in bm_resize fixed (slow column clearing)
            2003.08.18 memory benchmarking functionality added
            2003.08.20 closed/maximal item set search added
            2003.08.22 function bm_setcol added
            2003.09.11 sparse matrix representation added
            2003.09.13 sparse matrix representation completed
            2003.09.20 bug in _isect2 fixed (empty transaction list)
            2003.09.21 bug in benchmark version fixed (number of sets)
            2003.09.25 bit count table extended to word values
            2004.12.09 adapted to changed report function
            2006.11.26 reuse of item set prefix made possible (output)
            2006.11.28 closed and maximal item sets without repository
----------------------------------------------------------------------*/
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "vecops.h"
#include "bitmat.h"
#ifdef STORAGE
#include "storage.h"
#endif

/*----------------------------------------------------------------------
  Preprocessor Definitions
----------------------------------------------------------------------*/
#define BLKSIZE    256          /* block size for resize */
#define BLKMASK    0xff         /* block size mask for resize */
#define MASK       0xffffffff   /* bit mask 2 for 32 bit integers */
#define NOREPORT   0x80000000   /* flag for no reporting of a set */

/*----------------------------------------------------------------------
  Type Definitions
----------------------------------------------------------------------*/
typedef struct {                /* --- reduced bit matrix --- */
  int     cnt;                  /* number of bit/number vectors */
  int     len;                  /* length of each bit vector */
  int     *vecs[1];             /* array of bit/number vectors */
} REDMAT;                       /* (reduced bit matrix) */

typedef struct {                /* --- all one submatrix search --- */
  int     mode;                 /* search mode (e.g. BM_CLOSED) */
  int     min;                  /* minimum number of rows */
  int     max;                  /* maximum number of rows */
  int     supp;                 /* minimum support (num. of columns) */
  BMREPFN *report;              /* report function for results */
  void    *data;                /* user data for report function */
  REDMAT  *init;                /* initial reduced bit matrix */
  BITMAT  *repos;               /* repository of found item sets */
  #ifdef BENCH                  /* if benchmark version */
  int     mcur;                 /* current memory usage in bytes */
  int     mmax;                 /* maximum memory usage in bytes */
  #endif
  int     rows[1];              /* row ids. vector for reporting */
} ALLONE;                       /* (all one submatrix search) */

/*----------------------------------------------------------------------
  Global Variables
----------------------------------------------------------------------*/
static char _bctab[65536];      /* bit count table */

/*----------------------------------------------------------------------
  Auxiliary Functions
----------------------------------------------------------------------*/

static void _bcinit (void)
{                               /* --- initialize the bit count table */
  register int i, k, n;         /* loop variable, counter */

  for (i = 65536; --i >= 0; ) { /* traverse all word values */
    for (n = 0, k = i; k; k >>= 1)
      n += k & 1;               /* count the bits in the byte value */
    _bctab[i] = (char)n;        /* and store the result in the table */
  }                             /* (tab[i] = number of set bits in i) */
}  /* _bcinit() */

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

static int _count (int *vec, int n)
{                               /* --- count set bits in a bit vector */
  register int c = 0, x;        /* bit counter */

  for (vec += n; --n >= 0; ) {  /* traverse the bit vector */
    x = *--vec;                 /* from back to front */
    c += _bctab[x & 0xffff] +_bctab[(x >> 16) & 0xffff];
  }                             /* count the number of set bits */
  return *--vec = c;            /* and return this number */
}  /* _count() */

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

static int _isect1 (int *res, const int *v1, const int *v2, int n)
{                               /* --- intersect two bit vectors */
  register int c = 0, x;        /* bit counter, intersection result */

  v1 += n; v2 += n;             /* traverse the bit vectors */
  for (res += n; --n >= 0; ) {  /* from back to front and */
    *--res = x = *--v1 & *--v2; /* intersect their elements */
    c += _bctab[x & 0xffff] +_bctab[(x >> 16) & 0xffff];
  }                             /* count the number of set bits */
  return *--res = c;            /* and return this number */
}  /* _isect1() */

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

static int _isect2 (int *res, const int *v1, const int *v2)
{                               /* --- intersect two number vectors */
  register int i = 0;           /* bit counter */
  register int n1, n2;          /* number of column identifiers */

  n1 = *(v1-1) & ~NOREPORT;     /* get number of columns/items */
  n2 = *(v2-1) & ~NOREPORT;     /* in the two number vectors */
  if ((n1 <= 0) || (n2 <= 0))   /* check if one transaction list */
    return *--res = 0;          /* is empty */
  while (1) {                   /* intersection loop */
    if      (*v1 <  *v2) {      /* skip bits that are only in v1 */
      v1++; if (--n1 <= 0) break; }
    else if (*v1 >  *v2) {      /* skip bits that are only in v2 */
      v2++; if (--n2 <= 0) break; }
    else {                      /* copy bits that */
      res[i++] = *v1++; v2++;   /* are in both vectors */
      if ((--n1 <= 0) || (--n2 <= 0)) break;
    }                           /* in each case check */
  }                             /* whether one vector gets empty */
  return *--res = i;            /* return the intersection size */
}  /* _isect2() */

/*----------------------------------------------------------------------
  Main Functions
----------------------------------------------------------------------*/

BITMAT* bm_create (int rowcnt, int colcnt, int sparse)
{                               /* --- create a bit matrix */
  BITMAT *bm;                   /* created bit vector set */
  int    *vec;                  /* buffer for a bit vector */
  int    vsz;                   /* size of the rows vector */
  int    n;                     /* number of integers in a bit vector */

  assert((rowcnt >= 0)          /* check the function arguments */
      && (colcnt >= 0));
  bm = (BITMAT*)malloc(sizeof(BITMAT));
  if (!bm) return NULL;         /* allocate the base structure */
  vsz = (rowcnt > 0) ? rowcnt : BLKSIZE;
  bm->rows = (int**)malloc(vsz *sizeof(int*));
  if (!bm->rows) { free(bm); return NULL; }
  bm->rowvsz = vsz;             /* initialize the fields */
  bm->colcnt = colcnt;
  bm->sparse = sparse;
  #ifdef BENCH                  /* if benchmark version, */
  bm->mem    = 0;               /* initialize memory measurement */
  #endif
  if (sparse) {                 /* if sparse version, set empty vecs. */
    n = 2; bm->colvsz = bm->colcnt; }
  else {                        /* if normal version */
    n = ((colcnt > 0) ? (colcnt +BM_MASK) >> BM_SHIFT : BLKSIZE);
    bm->colvsz = n << BM_SHIFT; n += 2;
  }                             /* set default size bit vectors */
  for (bm->rowcnt = 0; bm->rowcnt < rowcnt; bm->rowcnt++) {
    vec = (int*)calloc(n, sizeof(int));
    if (!vec) { bm_delete(bm); return NULL; }
    bm->rows[bm->rowcnt] = vec+2;
    vec[0] = bm->rowcnt;        /* create the bit vectors and */
  }                             /* note the row identifiers */
  bm->buf = bm->supps = NULL;   /* default: no additional buffers */
  if (!_bctab[1]) _bcinit();    /* init. the bit counter table */
  return bm;                    /* return the created bit matrix */
}  /* bm_create() */

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

void bm_delete (BITMAT *bm)
{                               /* --- delete a bit matrix */
  int i;                        /* loop variable */

  assert(bm);                   /* check the function argument */
  if (bm->supps) free(bm->supps);
  if (bm->buf)   free(bm->buf-1); /* delete the additional buffers */
  for (i = bm->rowcnt; --i >= 0; )
    free(bm->rows[i]-2);        /* delete all row bit vectors, */
  free(bm->rows);               /* the vector of matrix rows, */
  free(bm);                     /* and the base structure */
}  /* bm_delete() */

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

static int _bufrsz (BITMAT *bm, int nb, int ns)
{                               /* --- resize the buffers */
  int *vec;                     /* buffer for new bit vectors */

  if (!bm->buf) return 0;       /* check for an intersection buffer */
  vec = (int*)realloc(bm->buf-1, (nb+1) *sizeof(int));
  if (!vec) return -1;          /* enlarge the intersection buffer */
  bm->buf = vec +1;             /* and set the new vector */
  if (!bm->supps) return 0;     /* check for a supports vector */
  vec = (int*)realloc(bm->supps, ns *sizeof(int));
  if (!vec) return -1;          /* enlarge the supports vector */
  bm->supps = vec;              /* and set the new vector */
  return 0;                     /* return 'ok' */
}  /* _bufrsz() */

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

int bm_resize (BITMAT *bm, int rowcnt, int colcnt)
{                               /* --- resize a bit matrix */
  int row, i, k;                /* loop variables, buffers */
  int **rows;                   /* buffer for new rows vector */
  int *vec;                     /* buffer for new bit vectors */
  int n, c;                     /* number of integers in a bit vector */

  assert(bm);                   /* check the function arguments */
  if (rowcnt < 0) rowcnt = bm->rowcnt;
  if (colcnt < 0) colcnt = bm->colcnt;
  if (bm->sparse) c = n = 2;    /* if sparse matrix */
  else {                        /* if normal matrix */
    c = bm->colvsz;             /* get the size of the bit vectors */