ptree2.c

数据挖掘中的一算法 ines算法 c下实现的。适合初学习数据挖掘者借鉴

  /* --- print the condition tree --- */
  root = pt->levels[0].list;    /* get the root node of the tree */
  if (!root || !(root->index & PT_OCCUR))
    fputs(" { }", file);        /* if the tree is empty, do nothing */
  else {                        /* if the tree is not empty, */
    fprintf(file, "\n%s", out.base);    /* start on the next line and */
    out.ind = out.pos = 0;      /* init. the position and indentation */
    _treeout(&out, pt->levels, root);
  }                             /* recursively print the tree */
  fputs(";\n", file);           /* terminate the tree output */

  /* --- print additional information (as a comment) --- */
  if (mode & PT_INFO)           /* if the add. info. flag is set */
    fprintf(file, "%s/* evaluation: %g */\n", out.base, pt->eval);
  return (ferror(file)) ? -1 : 0;
}  /* pt_desc() */              /* return the writing result */

/*----------------------------------------------------------------------
  Parser Functions
----------------------------------------------------------------------*/
#ifdef PT_PARSE

static int _distin (PTREE *pt, SCAN *scan)
{                               /* --- read prob./poss. distribution */
  int    i;                     /* value identifier, buffer */
  PTLVL  *lvl;                  /* to access the leaf level desc. */
  PTLEAF *leaf;                 /* to access the leaf node */
  float  *c;                    /* to traverse the counters */
  double f;                     /* buffer for a value frequency */

  assert(pt && scan);           /* check the function arguments */
  if (pt_setcnt(pt, 0, 0) != 0) /* create a leaf node and the path */
    ERROR(E_NOMEM);             /* to it by setting a counter */
  lvl  = pt->levels+pt->pathlen;/* get the current level */
  leaf = (PTLEAF*)pt->curr;     /* and the leaf node */
  for (c = leaf->cnts +(i = lvl->cnt); --i >= 0; )
    *--c = -1;                  /* clear all counters in the leaf */
  while (1) {                   /* value/frequency read loop */
    i = sc_token(scan);         /* check for a value name */
    if ((i != T_ID) && (i != T_NUM)) ERROR(E_VALEXP);
    i = att_valid(lvl->att, sc_value(scan));
    if (i < 0)                       ERROR(E_UNKVAL);
    if (leaf->cnts[i] >= 0)          ERROR(E_DUPVAL);
    GET_TOK();                  /* get and check the attribute value */
    GET_CHR(':');               /* consume ':' */
    if (sc_token(scan) != T_NUM)     ERROR(E_NUMEXP);
    f = atof(sc_value(scan));   /* get and check the value frequency */
    if ((f < 0) || (f > FLT_MAX))    ERROR(E_ILLNUM);
    leaf->cnts[i] = (float)f;   /* set the value frequency */
    GET_TOK();                  /* and consume it */
    if (sc_token(scan) == '('){ /* if a relative frequency follows */
      GET_TOK();                /* consume '(' */
      if (sc_token(scan) != T_NUM)   ERROR(E_NUMEXP);
      f = atof(sc_value(scan)); /* get and check the rel. frequency */
      if ((f < 0) || (f > 100))      ERROR(E_ILLNUM);
      GET_TOK();                /* consume the rel. frequency */
      GET_CHR('%');             /* consume '%' */
      GET_CHR(')');             /* consume ')' */
    }
    if (sc_token(scan) != ',') break;
    GET_TOK();                  /* if at the end of the list, abort, */
  }                             /* otherwise consume ',' */
  for (c = leaf->cnts +(i = lvl->cnt); --i >= 0; )
    if (*--c < 0) *c = 0;       /* clear all unset counters */
  return 0;                     /* return 'ok' */
}  /* _distin() */

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

static int _linkin (PTREE *pt, SCAN *scan, int index)
{                               /* --- read a link to another node */
  int   i, k;                   /* value identifier and loop variable */
  PTLVL *lvl;                   /* to traverse the tree levels */

  assert(pt && scan);           /* check the function arguments */
  GET_TOK();                    /* consume '->' */
  GET_CHR('(');                 /* consume '(' */
  lvl = pt->levels;             /* traverse the tree levels */
  for (k = pt->pathlen +1; --k >= 0; ) {
    i = sc_token(scan);         /* check for a value name */
    if ((i != T_ID) && (i != T_NUM)) ERROR(E_VALEXP);
    i = att_valid(lvl->att, sc_value(scan));
    if (i < 0)                       ERROR(E_UNKVAL);
    lvl->link = i; lvl++;       /* get and store the identifier */
    GET_TOK();                  /* and consume the value name */
    if (k > 0) { GET_CHR(',');} /* check for a separator if necessary */
  }
  GET_CHR(')');                 /* consume ')' */
  if (pt_link(pt, index, NULL) != 0) ERROR(E_NOMEM);
  return 0;                     /* install the link and return 'ok' */
}  /* _linkin() */

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

static int _treein (PTREE *pt, SCAN *scan)
{                               /* --- read condition tree */
  int    i, k;                  /* value identifier, counter */
  PTLVL  *lvl;                  /* to access the current level */
  PTNODE *node;                 /* to access the child nodes */
  int    err;                   /* parse error status */

  assert(pt && scan);           /* check the function arguments */
  GET_CHR('{');                 /* consume '{' */
  if (sc_token(scan) == '}') {  /* if the (sub)tree is empty, */
    GET_TOK(); return 0; }      /* consume '}' and abort */

  /* --- read a value distribution (a leaf) --- */
  if (pt_atleaf(pt)) {          /* if the current node is a leaf, */
    i = _distin(pt, scan);      /* read a probability or */
    if (i) return i;            /* possibility distribution */
    GET_CHR('}'); return 0;     /* consume the closing '}' */
  }                             /* and abort the function */

  /* --- read subtrees --- */
  lvl = pt->levels +pt->pathlen;/* get the current level and */
  err = k = 0;                  /* initialize the read counter */
  while (sc_token(scan) != '}'){/* attribute value read loop */
    if (k++ > 0) {              /* if this is not the first value, */
      GET_CHR(','); }           /* consume ',' (separator) */
    i = sc_token(scan);         /* check for a value name */
    if ((i != T_ID) && (i != T_NUM))      ERROR(E_VALEXP);
    i = att_valid(lvl->att, sc_value(scan));
    if (i < 0)                            ERROR(E_UNKVAL);
    node = (pt->curr) ? pt->curr->children[i] : NULL;
    if (node && (node->index & PT_OCCUR)) ERROR(E_DUPVAL);
    GET_TOK();                  /* consume the attribute value */
    GET_CHR(':');               /* consume ':' */
    if (sc_token(scan) == T_RGT) {
      if (node) ERR_CHR('{');   /* if an arrow '->' follows, */
      i = _linkin(pt, scan, i); /* read a link to another node */
      if (i) return i; }
    else {                      /* if a subtree follows */
      pt_down(pt, i);           /* go down in the tree and */
      i = _treein(pt, scan);    /* read the subtree recursively */
      if (pt->curr)             /* mark the current node as read */
        pt->curr->index |= PT_OCCUR;
      pt_up(pt, PT_DESCENT);    /* go back up in the tree */
      if (i) {                  /* if an error occurred */
        if      (i < E_FWRITE) {
          if (sc_recover(scan, ';', '{', '}', 1) == T_EOF) return 1; }
        else if (i < 0) return i;
        err = 1;                /* try to recover on errors, */
      }                         /* but abort on fatal errors */
    }
  }
  GET_TOK();                    /* consume '}' */
  return err;                   /* return parse error status */
}  /* _treein() */

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

static int _parse (ATTSET *attset, SCAN *scan, int type, PTREE **ppt)
{                               /* --- read prob./poss. distributions */
  int i, k, n, t = -1;          /* loop variables, number of conds. */
  ATT *att;                     /* conditioned attribute */

  assert(attset && scan);       /* check the function arguments */
  if (sc_token(scan) == T_ID) { /* check for 'prob' or 'poss' */
    if     ((strcmp(sc_value(scan), "prob") == 0)
    ||      (strcmp(sc_value(scan), "P")    == 0)) t = PT_PROB;
    else if (strcmp(sc_value(scan), "poss") == 0)  t = PT_POSS;
  }                             /* determine the tree type */
  if ((t < 0)                   /* if no proper token found */
  ||  (!(type & PT_AUTO)        /* or not in automatic mode */
  &&  ((type ^ t) & PT_POSS)))  /* and wrong token found, abort */
    ERR_STR((type == PT_PROB) ? "prob" : "poss");
  if (type & PT_AUTO) type = t; /* set the proper tree type */
  GET_TOK();                    /* consume 'prob' or 'poss' */
  GET_CHR('(');                 /* consume '(' */
  i = sc_token(scan);           /* check for a name */
  if ((i != T_ID) && (i != T_NUM)) ERROR(E_ATTEXP);
  i = as_attid(attset, sc_value(scan));
  if (i < 0) ERROR(E_UNKATT);   /* get and check the attribute id. */
  att = as_att(attset, i);      /* get the conditioned attribute */
  k   = att_getmark(att);       /* and its read marker */
  if (k != 0) ERROR((k > 0) ? E_DUPATT : E_ILLATT);
  GET_TOK();                    /* and consume the attribute name */
  *ppt = pt_create(att, type);  /* create a prob./poss. tree */
  if (!*ppt) ERROR(E_NOMEM);    /* for this attribute */
  if (sc_token(scan) == '|') {  /* if there are conditions */
    do {                        /* attribute read loop */
      n = pt_concnt(*ppt);      /* get the number of conditions */
      if (n >= PT_MAXCON) ERR_CHR(')');
      GET_TOK();                /* consume '|' or ',' */
      i = sc_token(scan);       /* check for a name */
      if ((i != T_ID) && (i != T_NUM))  ERROR(E_ATTEXP);
      i = as_attid(attset, sc_value(scan));
      if (i < 0)                        ERROR(E_UNKATT);
      if (pt_attid(*ppt) == i)          ERROR(E_DUPATT);
      for (k = n; --k >= 0; )   /* check the attribute identifier */
        if (pt_conid(*ppt, k) == i)     ERROR(E_DUPATT);
      att = as_att(attset, i);  /* add the attribute as a condition */
      if (pt_conadd(*ppt, n, att) != 0) ERROR(E_NOMEM);
      GET_TOK();                /* consume the attribute name */
    } while (sc_token(scan) == ',');
  }                             /* while end of list not reached */
  GET_CHR(')');                 /* consume ')' */
  GET_CHR('=');                 /* consume '=' */
  if (_treein(*ppt, scan) != 0) /* read the prob./poss. tree */
    return -1;                  /* recursively */
  GET_CHR(';');                 /* consume ';' */
  return 0;                     /* return 'ok' */
}  /* _parse() */

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

PTREE* pt_parse (ATTSET *attset, SCAN *scan, int type)
{                               /* --- parse a prob./poss. tree */
  PTREE *pt = NULL;             /* created prob./poss. tree */

  assert(attset && scan);       /* check the function arguments */
  pa_init(scan);                /* initialize parsing */
  if (_parse(attset, scan, type, &pt) != 0) {
    if (pt) pt_delete(pt, 0);   /* parse a prob./poss. tree */
    return NULL;                /* if an error occurred, */
  }                             /* delete the tree and abort */
  pt->parcnt =  0;              /* number of parameters is invalid */
  pt->occur  =  0;              /* occurrence flags are invalid */
  pt->total  = -1;              /* counter totals are invalid */
  pt_total(pt);                 /* compute the totals and */
  return pt;                    /* return the created tree */
}  /* pt_parse() */

#endif