tract.c

suanfa工具箱

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

int is_readapp (ITEMSET *iset, FILE *file)
{                               /* --- read appearance indicators */
  int  d;                       /* delimiter type */
  char *buf;                    /* read buffer */
  ITEM *item;                   /* to access the item data */

  assert(iset && file);         /* check the function arguments */
  if (tfs_skip(iset->tfscan, file) < 0)
    return E_FREAD;             /* skip leading comments */
  buf = tfs_buf(iset->tfscan);  /* read the first record (one field) */
  d   = tfs_getfld(iset->tfscan, file, NULL, 0);
  if (d <  0)           return E_FREAD;
  if (d >= TFS_FLD)     return E_FLDCNT;
  iset->app = _appcode(buf);    /* get default appearance code */
  if (iset->app < 0)    return E_UNKAPP;
  while (d > TFS_EOF) {         /* read item/indicator pairs */
    if (tfs_skip(iset->tfscan, file) < 0)
      return E_FREAD;           /* skip more comments */
    d = tfs_getfld(iset->tfscan, file, NULL, 0);
    if (d <= TFS_EOF)           /* read the next item */
      return (d < 0) ? E_FREAD : 0;
    if (buf[0] == '\0')         /* check for end of file */
      return E_ITEMEXP;         /* and for a missing item */
    item = nim_add(iset->nimap, buf, sizeof(ITEM));
    if (item == EXISTS) return E_DUPITEM;  /* add the new item */
    if (item == NULL)   return E_NOMEM;    /* to the name/id map */
    item->frq = 0;              /* clear the frequency counters */
    item->xfq = 0;              /* (occurrence and sum of t.a. sizes) */
    if (d < TFS_FLD)    return E_APPEXP;
    d = tfs_getfld(iset->tfscan, file, NULL, 0);
    if (d <  0)         return E_FREAD;
    if (d >= TFS_FLD)   return E_FLDCNT;
    item->app = _appcode(buf);  /* get the appearance indicator */
    if (item->app <  0)  return E_UNKAPP;
  }
  return 0;                     /* return 'ok' */
}  /* is_readapp() */

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

int is_read (ITEMSET *iset, FILE *file)
{                               /* --- read a transaction */
  int  i, d;                    /* loop variable, delimiter type */
  char *buf;                    /* read buffer */
  ITEM *item;                   /* pointer to item */

  assert(iset && file);         /* check the function arguments */
  iset->cnt = 0;                /* initialize the item counter */
  if (tfs_skip(iset->tfscan, file) < 0)
    return E_FREAD;             /* skip leading comments */
  d   = _get_item(iset, file);  /* read the first item and */
  buf = tfs_buf(iset->tfscan);  /* get the read buffer */
  if ((d      == TFS_EOF)       /* if at the end of the file */
  &&  (buf[0] == '\0'))         /* and no item has been read, */
    return 1;                   /* return 'end of file' */
  while ((d      == TFS_FLD)    /* read the other items */
  &&     (buf[0] != '\0'))      /* of the transaction */
    d = _get_item(iset, file);  /* up to the end of the record */
  if (d < TFS_EOF) return d;    /* check for a read error */
  if ((buf[0] == '\0') && (d == TFS_FLD) && (iset->cnt > 0))
    return E_ITEMEXP;           /* check for an empty field */
  ta_sort(iset->items, iset->cnt); /* prepare the transaction */
  iset->cnt = ta_unique(iset->items, iset->cnt);
  for (i = iset->cnt; --i >= 0; ) {
    item = nim_byid(iset->nimap, iset->items[i]);
    item->frq += 1;             /* count the item and */
    item->xfq += iset->cnt;     /* sum the transaction sizes */
  }                             /* as an importance indicator */
  return 0;                     /* return 'ok' */
}  /* is_read() */

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

int is_recode (ITEMSET *iset, int minfrq, int dir, int *map)
{                               /* --- recode items w.r.t. frequency */
  int      i, k, n, t;          /* loop variables, buffer */
  ITEM     *item;               /* to traverse the items */
  SYMCMPFN *cmp;                /* comparison function */

  assert(iset);                 /* check the function arguments */
  if      (dir >  1) cmp = _asccmpx;  /* get the appropriate */
  else if (dir >  0) cmp = _asccmp;   /* comparison function */
  else if (dir >= 0) cmp = _nocmp;    /* (ascending/descending) */
  else if (dir > -2) cmp = _descmp;   /* and sort the items */
  else               cmp = _descmpx;  /* w.r.t. their frequency */
  nim_sort(iset->nimap, cmp, (void*)minfrq, map, 1);
  for (n = nim_cnt(iset->nimap); --n >= 0; ) {
    item = (ITEM*)nim_byid(iset->nimap, n);
    if (item->frq < minfrq)     /* determine frequent items and */
      item->app = APP_NONE;     /* set all others to 'ignore' */
    else if (item->app != APP_NONE)
      break;                    /* in addition, skip all items */
  }                             /* that have been set to 'ignore' */
  if (map) {                    /* if a map vector is provided */
    for (i = k = 0; i < iset->cnt; i++) {
      t = map[iset->items[i]];  /* traverse the current transaction */
      if (t <= n) iset->items[k++] = t;
    }                           /* recode all items and */
    iset->cnt = k;              /* delete all items to ignore */
    ta_sort(iset->items, k);    /* resort the items */
  }
  return n+1;                   /* return number of frequent items */
}  /* is_recode() */

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

int is_filter (ITEMSET *iset, const char *marks)
{                               /* --- filter items in transaction */
  return iset->cnt = ta_filter(iset->items, iset->cnt, marks);
}  /* is_filter() */

/*----------------------------------------------------------------------
  Transaction Functions
----------------------------------------------------------------------*/

int ta_unique (int *items, int n)
{                               /* --- remove duplicate items */
  int *s, *d;                   /* to traverse the item vector */

  assert(items && (n >= 0));    /* check the function arguments */
  if (n <= 1) return n;         /* check for 0 or 1 item */
  for (d = s = items; --n > 0;) /* traverse the sorted vector */
    if (*++s != *d) *++d = *s;  /* and remove duplicate items */ 
  return (int)(++d -items);     /* return the new number of items */
}  /* ta_unique() */

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

int ta_filter (int *items, int n, const char *marks)
{                               /* --- filter items in a transaction */
  int i, k;                     /* loop variables */

  assert(items && (n >= 0));    /* check the function arguments */
  for (i = k = 0; i < n; i++)   /* remove all unmarked items */
    if (marks[items[i]]) items[k++] = items[i];
  return k;                     /* return the new number of items */
}  /* ta_filter() */

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

static int ta_cmp (const void *p1, const void *p2, void *data)
{                               /* --- compare transactions */
  int       k, k1, k2;          /* loop variable, counters */
  const int *i1, *i2;           /* to traverse the item identifiers */

  assert(p1 && p2);             /* check the function arguments */
  i1 = ((const TRACT*)p1)->items;
  i2 = ((const TRACT*)p2)->items;
  k1 = ((const TRACT*)p1)->cnt; /* get the item vectors */
  k2 = ((const TRACT*)p2)->cnt; /* and the numbers of items */
  for (k  = (k1 < k2) ? k1 : k2; --k >= 0; i1++, i2++) {
    if (*i1 > *i2) return  1;   /* compare corresponding items */
    if (*i1 < *i2) return -1;   /* and abort the comparison */
  }                             /* if one of them is greater */
  if (k1 > k2) return  1;       /* if one of the transactions */
  if (k1 < k2) return -1;       /* is not empty, it is greater */
  return 0;                     /* otherwise the two trans. are equal */
}  /* ta_cmp() */

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

static int ta_cmpx (const TRACT *ta, const int *items, int n)
{                               /* --- compare transactions */
  int       k, m;               /* loop variable, counter */
  const int *p;                 /* to traverse the item identifiers */

  assert(ta && items);          /* check the function arguments */
  p = ta->items; m = ta->cnt;   /* traverse the item vector */
  m = ta->cnt;
  for (k = (n < m) ? n : m; --k >= 0; p++, items++) {
    if (*p > *items) return  1; /* compare corresponding items */
    if (*p < *items) return -1; /* and abort the comparison */
  }                             /* if one of them is greater */
  if (m > n) return  1;         /* if one of the transactions */
  if (m < n) return -1;         /* is not empty, it is greater */
  return 0;                     /* otherwise the two trans. are equal */
}  /* ta_cmpx() */

/*----------------------------------------------------------------------
  Transaction Set Functions
----------------------------------------------------------------------*/

TASET* tas_create (ITEMSET *itemset)
{                               /* --- create a transaction set */
  TASET *taset;                 /* created transaction set */

  assert(itemset);              /* check the function argument */
  taset = malloc(sizeof(TASET));
  if (!taset) return NULL;      /* create a transaction set */
  taset->itemset = itemset;     /* and store the item set */
  taset->cnt     = taset->vsz = taset->max = taset->total = 0;
  taset->tracts  = NULL;        /* initialize the other fields */
  return taset;                 /* return the created t.a. set */
}  /* tas_create() */

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

void tas_delete (TASET *taset, int delis)
{                               /* --- delete a transaction set */
  assert(taset);                /* check the function argument */
  if (taset->tracts) {          /* if there are loaded transactions */
    while (--taset->cnt >= 0)   /* traverse the transaction vector */
      free(taset->tracts[taset->cnt]);
    free(taset->tracts);        /* delete all transactions */
  }                             /* and the transaction vector */
  if (delis && taset->itemset) is_delete(taset->itemset);
  free(taset);                  /* delete the item set and */
}  /* tas_delete() */           /* the transaction set body */

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

int tas_add (TASET *taset, const int *items, int n)
{                               /* --- add a transaction */
  TRACT *ta;                    /* new transaction */
  int   *p;                     /* to traverse the transaction */
  TRACT **vec;                  /* new transaction vector */
  int   size;                   /* new transaction vector size */

  assert(taset);                /* check the function arguments */
  size = taset->vsz;            /* get the transaction vector size */
  if (taset->cnt >= size) {     /* if the transaction vector is full */
    size += (size > BLKSIZE) ? (size >> 1) : BLKSIZE;
    vec   = (TRACT**)realloc(taset->tracts, size *sizeof(TRACT*));
    if (!vec) return -1;        /* enlarge the transaction vector */
    taset->tracts = vec; taset->vsz = size;
  }                             /* set the new vector and its size */
  if (!items) {                 /* if no transaction is given */
    items = is_tract(taset->itemset);
    n     = is_tsize(taset->itemset);
  }                             /* get it from the item set */
  ta = (TRACT*)malloc(sizeof(TRACT) +(n-1) *sizeof(int));
  if (!ta) return -1;           /* create a new transaction */
  taset->tracts[taset->cnt++]  = ta;
  if (n > taset->max)           /* store the transaction and */
    taset->max = n;             /* update maximal transaction size */
  taset->total += n;            /* sum the number of items */
  for (p = ta->items +(ta->cnt = n); --n >= 0; )
    *--p = items[n];            /* copy the items of the t.a. */
  return 0;                     /* return 'ok' */
}  /* tas_add() */

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

void tas_recode (TASET *taset, int *map, int cnt)