bitmat.c

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

/*----------------------------------------------------------------------
  File    : bitmat.c
  Contents: bit matrix management
  Author  : Christian Borgelt
  History : 09.06.2002 file created
            10.12.2002 result report function extended
            19.04.2003 bug in _search fixed (min. number of vectors)
            16.08.2003 bug in bm_resize fixed (slow column clearing)
            18.08.2003 memory benchmarking functionality added
            20.08.2003 closed/maximal item set search added
            22.08.2003 function bm_setcol added
            11.09.2003 sparse matrix representation added
            13.09.2003 sparse matrix representation completed
            20.09.2003 bug in _isect2 fixed (empty transaction list)
            21.09.2003 bug in benchmark version fixed (number of sets)
            25.09.2003 bit count table extended to word values
            09.12.2004 adapted to changed report function
----------------------------------------------------------------------*/
#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     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 */
  BITMAT  *res;                 /* for closed and maximal 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 */
    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)