eliminate-main.c

Ripper 分类算法

/******************************************************************************
 eliminate-main.c - eliminate redundant conditions from a ruleset
******************************************************************************/


#include <stdio.h>
#include <math.h>
#include "ripper.h"

static BOOL weaker(gsym_t *,gsym_t *) ;
static void eliminate_redundancy(concept_t *);
static void sort_conditions(concept_t *);

/*****************************************************************************/
char *Program="eliminate";
char *Help_str[] = {
    "syntax: eliminate [options] stem",
    "   eliminate redundant conditions from a ruleset",
    "",
    "options are:",
    "  -v#: set trace level to #",
    "  -o: sort conditions",
    NULL
};

/*****************************************************************************/

int main(argc,argv)
int argc;
char *argv[];
{
    char *stem;
    concept_t *hyp;
    int o;
    FILE *fp;
    BOOL sort;

    sort = FALSE;

    while ((o=getopt(argc,argv,"v:oh"))!=EOF) {
	switch (o) {
	  case 'v':
	    set_trace_level(atoi(optarg)); 
	    break;
	  case 'o':
	    sort = TRUE;
	    break;
	  case 'h':
	  case '?':
	  default: 
	    give_help();
	    if (o=='h') exit(0);
	    else fatal("option not implemented");
	}
    }
    if (optind<argc) {
	stem = argv[optind++];
    } else {
	give_help();
	fatal("no file stem specified");
    }
    if (optind<argc) {
	warning("not all arguments were used: %s ...",argv[optind]);
    }
    
    /* now load the hypothesis */
    ld_names(add_ext(stem,".names"));
    if ((fp=fopen(add_ext(stem,".hyp"),"r"))==NULL) {
	fatal("can't open concept file for read");
    }
    hyp = ld_concept(fp);
    trace (SUMM) {
	printf("Initial hypothesis has %d rules, %d conditions:\n",
	       vmax(hyp->rules),concept_size(hyp));
	print_concept(hyp);
	fflush(stdout);
    } 
    fclose(fp);
    eliminate_redundancy(hyp);
    if (sort) sort_conditions(hyp);
    trace (SUMM) {
	printf("Simplified hypothesis has %d rules, %d conditions:\n",
	       vmax(hyp->rules),concept_size(hyp));
	print_concept(hyp);
	fflush(stdout);
    } 
    if ((fp=fopen(add_ext(stem,".hyp"),"w"))==NULL) {
	fatal("can't open concept file for write");
    }
    fshow_concept(fp,hyp);
}

/****************************************************************************/

static int gsym_cmp(char *a1,char *a2) 
{
    int c;
    gsym_t *g1,*g2;

    g1 = (gsym_t *) a1;
    g2 = (gsym_t *) a2;

    /* put deleted conditions first */
    if (g1->nonterm && !g2->nonterm) return 1;
    if (g2->nonterm && !g1->nonterm) return -1;

    /* first sort on attribute */
    c = g1->attr_index - g2->attr_index;  
    if (c!=0) return c;

    /* then on operator */
    if (g1->op==OPGE && g2->op==OPLE) return -1;
    else if (g1->op==OPIN && g2->op==OPOUT) return -1;
    
    /* default--don't reorder */
    return 0;
}    

static void sort_conditions(concept_t *c)
{
    int i;
    rule_t *ri;

    for (i=0; i<vmax(c->rules); i++) {
	ri = vref(rule_t,c->rules,i);
	vsort(gsym_t,ri->antec,gsym_cmp);
    }
}

/****************************************************************************/

static void eliminate_redundancy(concept_t *c)
{
    int i,j,k;
    rule_t *ri;
    gsym_t *gsymj,*gsymk;
    symbol_t *dummy;

    dummy = intern("DELETED");
    for (i=0; i<vmax(c->rules); i++) {
	ri = vref(rule_t,c->rules,i);
	for (j=0; j<vmax(ri->antec)-1; j++ ) {
	    gsymj = vref(gsym_t,ri->antec,j);
	    for (k=j+1; !gsymj->nonterm && k<vmax(ri->antec); k++) {
		gsymk = vref(gsym_t,ri->antec,k);
		if (weaker(gsymj,gsymk)) {
		    gsymj->nonterm = dummy;
		} else if (weaker(gsymk,gsymj)) {
		    gsymk->nonterm = dummy;
		}
	    }
	}
    }
}

static BOOL weaker(gsym_t *g1,gsym_t *g2) 
{
    if (g1->op==OPLE && g2->op==OPLE 
	&& g1->attr_index==g2->attr_index
	&& g1->value.num >= g2->value.num)
    {
	return TRUE;
    }
    if (g1->op==OPGE && g2->op==OPGE 
	&& g1->attr_index==g2->attr_index
	&& g1->value.num <= g2->value.num)
    {
	return TRUE;
    }
    return FALSE;
}