relim.c

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

static void error (int code, ...)
{                               /* --- print an error message */
  #ifndef QUIET                 /* if not quiet version */
  va_list    args;              /* list of variable arguments */
  const char *msg;              /* error message */

  assert(prgname);              /* check the program name */
  if (code < E_UNKNOWN) code = E_UNKNOWN;
  if (code < 0) {               /* if to report an error, */
    msg = errmsgs[-code];       /* get the error message */
    if (!msg) msg = errmsgs[-E_UNKNOWN];
    fprintf(stderr, "\n%s: ", prgname);
    va_start(args, code);       /* get variable arguments */
    vfprintf(stderr, msg, args);/* print error message */
    va_end(args);               /* end argument evaluation */
  }
  #endif
  #ifndef NDEBUG                /* if debug version */
  if (isfmt)   isf_delete(isfmt);  /* clean up memory */
  if (isevl)   ise_delete(isevl);  /* and close files */
  if (tatree)  tat_delete(tatree);
  if (taset)   tas_delete(taset, 0);
  if (itemset) is_delete(itemset);
  if (in  && (in  != stdin))  fclose(in);
  if (out && (out != stdout)) fclose(out);
  #endif
  #ifdef STORAGE                /* if storage debugging */
  showmem("at end of program"); /* check memory usage */
  #endif
  exit(code);                   /* abort the program */
}  /* error() */

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

int main (int argc, char *argv[])
{                               /* --- main function */
  int     i, k = 0, n;          /* loop variables, counters */
  char    *s;                   /* to traverse the options */
  char    **optarg = NULL;      /* option argument */
  char    *fn_in   = NULL;      /* name of input  file */
  char    *fn_out  = NULL;      /* name of output file */
  char    *blanks  = NULL;      /* blanks */
  char    *fldseps = NULL;      /* field  separators */
  char    *recseps = NULL;      /* record separators */
  char    *cominds = NULL;      /* comment indicators */
  double  supp     = 0.1;       /* minimal support (in percent) */
  int     min      = 1;         /* minimal size of item set */
  int     max      = 5;         /* maximal size of item set */
  int     sort     = 2;         /* flag for item sorting and recoding */
  int     tree     = 0;         /* flag for transaction tree */
  int     heap     = 1;         /* flag for heap sort vs. quick sort */
  int     *map;                 /* identifier map for recoding */
  clock_t t;                    /* timer for measurements */

  #ifndef QUIET                 /* if not quiet version */
  prgname = argv[0];            /* get program name for error msgs. */

  /* --- print usage message --- */
  if (argc > 1) {               /* if arguments are given */
    fprintf(stderr, "%s - %s\n", argv[0], DESCRIPTION);
    fprintf(stderr, VERSION); } /* print a startup message */
  else {                        /* if no arguments given */
    printf("usage: %s [options] infile outfile\n", argv[0]);
    printf("%s\n", DESCRIPTION);
    printf("%s\n", VERSION);
    printf("-m#      minimal number of items per item set "
                    "(default: %d)\n", min);
    printf("-n#      maximal number of items per item set "
                    "(default: %d)\n", max);
    printf("-s#      minimal support of an item set       "
                    "(default: %g%%)\n", supp *100);
    printf("         (positive: percentage, "
                    "negative: absolut number)\n");
    printf("-d#      minimal binary logarithm of support quotient "
                    "(default: none)\n");
    printf("-p#      output format for the item set support "
                    "(default: \"%s\")\n", fmt);
    printf("-a       print absolute support "
                    "(number of transactions)\n");
    printf("-g       write output in scanable form "
                    "(quote certain characters)\n");
    printf("-q#      sort items w.r.t. their frequency (default: %d)\n"
           "         (1: ascending, -1: descending, 0: do not sort,\n"
           "          2: ascending, -2: descending w.r.t. "
                    "transaction size sum)\n", sort);
    printf("-h       organize transactions as a prefix tree\n");
    printf("-j       use quicksort to sort the transactions "
                    "(default: heapsort)\n");
    printf("-i#      ignore records starting with a character "
                    "in the given string\n");
    printf("-b/f/r#  blank characters, field and record separators\n"
           "         (default: \" \\t\\r\", \" \\t\", \"\\n\")\n");
    printf("infile   file to read transactions from\n");
    printf("outfile  file to write frequent item sets to\n");
    return 0;                   /* print a usage message */
  }                             /* and abort the program */
  #endif  /* #ifndef QUIET */

  /* --- evaluate arguments --- */
  for (i = 1; i < argc; i++) {  /* traverse arguments */
    s = argv[i];                /* get option argument */
    if (optarg) { *optarg = s; optarg = NULL; continue; }
    if ((*s == '-') && *++s) {  /* -- if argument is an option */
      while (*s) {              /* traverse options */
        switch (*s++) {         /* evaluate switches */
          case 'm': min    = (int)strtol(s, &s, 0); break;
          case 'n': max    = (int)strtol(s, &s, 0); break;
          case 's': supp   = 0.01*strtod(s, &s);    break;
          case 'd': mindev =      strtod(s, &s);    break;
          case 'p': optarg = &fmt;                  break;
          case 'a': flags |= OF_ABS;                break;
          case 'g': flags |= OF_SCAN;               break;
          case 'q': sort   = (int)strtol(s, &s, 0); break;
          case 'h': tree   = 1;                     break;
          case 'j': heap   = 0;                     break;
          case 'i': optarg = &cominds;              break;
          case 'b': optarg = &blanks;               break;
          case 'f': optarg = &fldseps;              break;
          case 'r': optarg = &recseps;              break;
          default : error(E_OPTION, *--s);          break;
        }                       /* set option variables */
        if (optarg && *s) { *optarg = s; optarg = NULL; break; }
      } }                       /* get option argument */
    else {                      /* -- if argument is no option */
      switch (k++) {            /* evaluate non-options */
        case  0: fn_in  = s;      break;
        case  1: fn_out = s;      break;
        default: error(E_ARGCNT); break;
      }                         /* note filenames */
    }
  }
  if (optarg) error(E_OPTARG);  /* check option argument */
  if (k != 2) error(E_ARGCNT);  /* and the number of arguments */
  if (supp > 1)                 /* check the minimal support */
    error(E_SUPP, supp);        /* (< 0: absolute number) */
  if (min <= 0) error(E_ITEMCNT, min);   /* check the limits */
  if (max <= 0) error(E_ITEMCNT, max);   /* for the set size */
  if (mindev > -DBL_MAX) flags |= OF_DEV;

  /* --- create item set and transaction set --- */
  itemset = is_create();        /* create an item set and */
  if (!itemset) error(E_NOMEM); /* set the special characters */
  is_chars(itemset, blanks, fldseps, recseps, cominds);
  taset = tas_create(itemset);  /* create a transaction set */
  if (!taset) error(E_NOMEM);   /* to store the transactions */
  MSG(fprintf(stderr, "\n"));   /* terminate the startup message */

  /* --- read transactions --- */
  t = clock();                  /* start the timer */
  if (fn_in && *fn_in)          /* if an input file name is given, */
    in = fopen(fn_in, "r");     /* open input file for reading */
  else {                        /* if no input file name is given, */
    in = stdin; fn_in = "<stdin>"; }   /* read from standard input */
  MSG(fprintf(stderr, "reading %s ... ", fn_in));
  if (!in) error(E_FOPEN, fn_in);
  for (tacnt = 0; 1; tacnt++) { /* transaction read loop */
    k = is_read(itemset, in);   /* read the next transaction */
    if (k < 0) error(k, fn_in, RECCNT(itemset), BUFFER(itemset));
    if (k > 0) break;           /* check for error and end of file */
    if (tas_add(taset, NULL, 0) != 0)
      error(E_NOMEM);           /* add the loaded transaction */
  }                             /* to the transaction set */
  if (in != stdin) fclose(in);  /* if not read from standard input, */
  in = NULL;                    /* close the input file */
  n  = is_cnt(itemset);         /* get the number of items */
  MSG(fprintf(stderr, "[%d item(s),", n));
  MSG(fprintf(stderr, " %d transaction(s)] done ", tacnt));
  MSG(fprintf(stderr, "[%.2fs].", SEC_SINCE(t)));
  if ((n <= 0) || (tacnt <= 0)) error(E_NOTAS);
  MSG(fprintf(stderr, "\n"));   /* check for at least one transaction */
  if (supp >= 0)                /* if relative support is given */
    supp = ceil(tacnt *supp);   /* compute absolute support */
  else {                        /* if absolute support is given */
    supp = ceil(-100  *supp);   /* make the support value positive */
    if (!(flags & OF_ABS)) flags = (flags & ~OF_REL) | OF_ABS;
  }                             /* switch to absolute support output */

  /* --- sort and recode items --- */
  MSG(fprintf(stderr, "filtering, sorting and recoding items ... "));
  t   = clock();                /* start the timer */
  map = (int*)malloc(is_cnt(itemset) *sizeof(int));
  if (!map) error(E_NOMEM);     /* create an item identifier map */
  n = is_recode(itemset, (int)supp, sort, map);
  is_trunc(itemset, n);         /* truncate the itemset and */
  tas_recode(taset, map, n);    /* recode the loaded transactions */
  free(map);                    /* delete the item identifier map */
  if (flags & OF_DEV) {         /* if to compute deviation */
    isevl = ise_create(itemset, tacnt);
    if (!isevl) error(E_NOMEM); /* create an item set evaluator */
  }                             /* (to exploit same prefixes) */
  MSG(fprintf(stderr, "[%d item(s)] ", n));
  MSG(fprintf(stderr, "done [%.2fs].", SEC_SINCE(t)));
  if (n <= 0) error(E_NOTAS);   /* print a log message and */
  MSG(fprintf(stderr, "\n"));   /* check the number of items */

  /* --- create a transaction tree --- */
  if (tree) {                   /* if transactions were loaded */
    MSG(fprintf(stderr, "creating transaction tree ... "));
    t = clock();                /* start the timer */
    tatree = tat_create(taset, heap); 
    if (!tatree) error(E_NOMEM);/* create a transaction tree */
    tas_delete(taset, 0);       /* delete transactions */
    taset = NULL;               /* and clear the variable */
    MSG(fprintf(stderr, "done [%.2fs].\n", SEC_SINCE(t)));
  }                             /* print a log message */

  /* --- find frequent item sets --- */
  t = clock();                  /* start the timer */
  if (fn_out && *fn_out)        /* if an output file name is given, */
    out = fopen(fn_out, "w");   /* open the output file */
  else {                        /* if no output file name is given, */
    out = stdout; fn_out = "<stdout>"; }    /* write to std. output */
  MSG(fprintf(stderr, "writing %s ... ", fn_out));
  if (!out) error(E_FOPEN, fn_out);
  isfmt = isf_create(itemset, flags & OF_SCAN);
  if (!isfmt) error(E_NOMEM);   /* create an item set formatter */
  k = (tatree) ? trees(tatree, itemset, (int)supp, min, max, report)
               : vecs (taset,           (int)supp, min, max, report);
  if (k < 0) error(E_NOMEM);    /* search for frequent item sets */
  if (fflush(out) != 0) error(E_FWRITE, fn_out);
  if (out != stdout) fclose(out);
  out = NULL;                   /* close the output file */
  MSG(fprintf(stderr, "[%d set(s)] done ", k));
  MSG(fprintf(stderr, "[%.2fs].\n", SEC_SINCE(t)));

  /* --- clean up --- */
  #ifndef NDEBUG                /* if this is a debug version */
  isf_delete(isfmt);            /* delete the item set formatter */
  if (isevl) ise_delete(isevl); /* and the item set evaluator */
  if (tatree) tat_delete(tatree);
  if (taset)  tas_delete(taset, 0);
  is_delete(itemset);           /* delete the transactions */
  #endif                        /* and the underlying item set */
  #ifdef STORAGE                /* if storage debugging */
  showmem("at end of program"); /* check memory usage */
  #endif
  return 0;                     /* return 'ok' */
}  /* main() */