fptree.c

fp_growth

/*----------------------------------------------------------------------
  File    : fptree.c
  Contents: frequent pattern tree management
  Author  : Christian Borgelt
  History : 21.11.2004 file created
            22.11.2004 second projection added, bonsai pruning added
            09.12.2004 adapted to changed report function
            10.12.2004 adapted to general memory management system
            28.12.2004 bug in function fpt_delete fixed
            06.12.2005 bug in function _project2 fixed
----------------------------------------------------------------------*/
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "fptree.h"
#ifdef STORAGE
#include "storage.h"
#endif

/*----------------------------------------------------------------------
  Preprocessor Definition
----------------------------------------------------------------------*/
#define BLKSIZE    6553         /* block size for memory management */

/*----------------------------------------------------------------------
  Type Definition
----------------------------------------------------------------------*/
typedef FPTREE* PROJFN (FPTREE *fpt, int item);

typedef struct {                /* --- structure for rec. search */
  int      min;                 /* minimum number of items */
  int      max;                 /* maximum number of items */
  int      supp;                /* minimum support (num. of trans.) */
  int      bonsai;              /* flag for pruning to bonsai */
  PROJFN   *proj;               /* projection function */
  FPTREPFN *report;             /* report function for results */
  void     *data;               /* user data for report function */
  int      cnt;                 /* number of frequent item sets */
  int      items[1];            /* item vector for reporting */
} FPRS;                         /* (structure for rec. search) */

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

static FPTREE* _create (MEMSYS *mem, int cnt)
{                               /* --- create a base f.p. tree */
  FPTREE  *fpt;                 /* created frequent pattern tree */
  FPTLIST *list;                /* to traverse the node lists */

  assert(cnt > 0);              /* check the function arguments */
  fpt = (FPTREE*)malloc(sizeof(FPTREE) +(cnt-1) *sizeof(FPTLIST));
  if (!fpt) return NULL;        /* allocate the base structure */
  fpt->cnt = cnt;               /* and note the number of items */
  if (mem) fpt->mem = mem;      /* if a memory management is given, */
  else {                        /* simply store it, otherwise */
    fpt->mem = ms_create(sizeof(FPTNODE), BLKSIZE);
    if (!fpt->mem) { free(fpt); return NULL; }
  }                             /* allocate a memory system */
  for (list = fpt->lists +cnt; --cnt >= 0; ) {
    (--list)->cnt = 0; list->node = NULL; }
  return fpt;                   /* initialize the node lists and */
}  /* _create() */              /* return the created f.p. tree */

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

static int _build (FPTREE *fpt, FPTNODE *parent,
                   TASET *taset, int lft, int rgt, int pos)
{                               /* --- recursively build f.p. tree */
  int     i, k;                 /* loop variable, buffer */
  int     item;                 /* to traverse the items at pos */
  FPTNODE *node;                /* created freq. pattern tree node */

  assert(fpt && taset && (pos >= 0)); /* check the function arguments */
  while ((lft <= rgt) && (tas_tsize(taset, lft) <= pos))
    lft++;                      /* skip trans. that are too short */
  if (lft > rgt) return 0;      /* check for an empty range */
  item = k = tas_tract(taset, i = rgt)[pos];    /* get first item */
  do {                          /* traverse the longer transactions */
    while (--i >= lft) {        /* while not at start of section */
      k = tas_tract(taset, i)[pos];
      if (k != item) break;     /* try to find a transaction */
    }                           /* with a different item */
    node = ms_alloc(fpt->mem);  /* create a new tree node */
    if (!node) return -1;       /* for the current item */
    node->item   = item;        /* and store the item */
    node->succ   = fpt->lists[item].node;
    fpt->lists[item].node = node;
    node->parent = parent;      /* insert the node into the item list */
    node->copy   = NULL;        /* and compute and sum the support */
    fpt->lists[item].cnt += node->cnt = rgt -i;
    if (_build(fpt, node, taset, i+1, rgt, pos+1) != 0)
      return -1;                /* build the child node recursively */
    item = k; rgt = i;          /* remove processed transaction from */
  } while (lft <= rgt);         /* the interval and note next item */
  return 0;                     /* return 'ok' */
}  /* _build() */

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

FPTREE* fpt_create (TASET *taset)
{                               /* --- create a freq. pattern tree */
  FPTREE *fpt;                  /* created frequent pattern tree */

  assert(taset);                /* check the function argument */
  fpt = _create(NULL, is_cnt(tas_itemset(taset)));
  if (!fpt) return NULL;        /* allocate a base f.p. tree */
  fpt->itemset = tas_itemset(taset);
  fpt->tra     = tas_cnt(taset);
  if ((fpt->tra > 0)            /* if there is at least one trans. */
  &&  (_build(fpt, NULL, taset, 0, fpt->tra -1, 0) != 0)) {
    fpt_delete(fpt); return NULL; }
  return fpt;                   /* recursively build the frequent */
}  /* fpt_create() */           /* pattern tree and return it */

/*----------------------------------------------------------------------
The above function assumes that the items in each transaction in taset
are sorted and that the transactions are sorted accordingly.
----------------------------------------------------------------------*/

void fpt_delete (FPTREE *fpt)
{                               /* --- delete a freq. pattern tree */
  assert(fpt);                  /* check the function argument */
  ms_delete(fpt->mem);          /* delete the memory system */
  free(fpt);                    /* and the base structure */
}  /* fpt_delete() */

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

static void _prune (FPTREE *fpt)
{                               /* --- prune nodes for last item */
  FPTNODE *node, *buf;          /* to traverse the nodes to delete */

  assert(fpt);                  /* check the function argument */
  for (node = fpt->lists[--fpt->cnt].node; node; ) {
    buf  = node;                /* while there is another node */
    node = node->succ;          /* note the current node and */
    ms_free(fpt->mem, buf);     /* remove it from the list, */
  }                             /* and then delete the node */
}  /* _prune() */

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

static void _detach (FPTREE *fpt)
{                               /* --- detach a projection */
  FPTNODE *node, *anc;          /* to traverse the ancestors */

  assert(fpt);                  /* check the function argument */
  node = fpt->lists[--fpt->cnt].node;
  while (node) {                /* while there is another node */
    for (anc = node->parent; anc && anc->copy; anc = anc->parent)
      anc->copy = NULL;         /* clear the copy pointers */
    anc  = node;                /* note the current node and */
    node = node->succ;          /* remove it from the list, */
    ms_free(fpt->mem, anc);     /* then delete the node */
  }                             /* (prune deepest tree level) */
}  /* _detach() */

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

static void _cleanup (FPTREE *fpt, FPTREE *proj)
{                               /* --- clean up after failure */
  assert(fpt && proj);          /* check the function argument */
  _detach(fpt);                 /* detach projection from tree */
  while (proj->cnt > 0) _prune(proj);
  free(proj);                   /* delete the projection */
}  /* _cleanup() */             /* (only called on failure) */

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

static FPTREE* _project1 (FPTREE *fpt, int item)
{                               /* --- project a freq. pattern tree */
  int     i;                    /* loop variable */
  FPTREE  *proj;                /* projected frequent pattern tree */
  FPTNODE *node, *anc, *copy;   /* to traverse the tree nodes */
  FPTNODE **prev;               /* to link copies to their ancestors */
  FPTLIST *lists;               /* to access the node lists */

  assert(fpt);                  /* check the function argument */
  proj = _create(fpt->mem, item);
  if (!proj) return NULL;       /* create a base freq. pattern tree */
  proj->itemset = fpt->itemset; /* note the underlying item set */
  lists = proj->lists;          /* get the node lists of the proj. */
  for (node = fpt->lists[item].node; node; node = node->succ) {
    prev = NULL;                /* traverse the nodes for the item */
    for (anc = node->parent; anc && !anc->copy; anc = anc->parent) {
      anc->copy =               /* traverse and copy all ancestors */
      copy = ms_alloc(fpt->mem);        /* that are not yet copied */
      if (!copy) { _cleanup(fpt, proj); return NULL; }
      if (prev) *prev = copy;   /* set parent link from child */
      copy->item = i = anc->item;
      copy->succ = lists[i].node;
      lists[i].node = copy;     /* insert copy into corresp. list */
      lists[i].cnt += copy->cnt = node->cnt;
      copy->copy = NULL;        /* set the support of the node */
      prev = &copy->parent;     /* and note the parent pointer */
    }                           /* for later linking */
    if (prev)                   /* set last parent pointer */
      *prev = (anc) ? anc->copy : NULL;
    for ( ; anc; anc = anc->parent) {
      anc->copy->cnt       += node->cnt;
      lists[anc->item].cnt += node->cnt;