/* Codice C commentato */
/* Questa pagina contiene il codice C del programma.
Tutti i commenti e ció che non é codice sono stati inseriti come commento, in modo
da facilitare un eventuale utilizzo del codice o di parti di esso. */
/* Inizio codice */
/* File apriori_all_time.h */
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <postgresql/libpq-fe.h> /* libreria front-end di Postgresql */
#include <time.h>
/* Ecco le strutture utilizzate: */
struct transaz{ /* utilizzata per memorizzare le transazioni (struttura a coda) */
int id;
int *n;
int grand;
int freq;
struct transaz *next;
};
struct liv1{ /* utilizzata per i singoli elementi (item-set di grandezza 1) */
int n;
char spiegazione[256];
int freq;
struct liv1 *left;
struct liv1 *right;
};
struct h3{ /* utilizzata per memorizzare gli item-set */
struct transaz *lista;
struct h3 *next[10];
};
struct trin{ /* utilizzata per memorizzare e ordinare per confidenza le transazioni */
int *da;
int *a;
float suppda;
float supptot;
float conf;
struct trin *dx;
struct trin *cen;
struct trin *sx;
};
struct supp{ /* utilizzata per memorizzare e ordinare per supporto le transazioni */
int *elem;
float supp;
struct supp *dx;
struct supp *cen;
struct supp *sx;
};
/* Qui sotto i prototipi delle funzioni: */
struct liv1 *aggliv1(struct liv1 *liv,int l,PGconn *conn2);
void taglia(struct liv1 *liv,int livello);
void cuci(struct liv1 *r1,int a,int livello);
struct h3 *insout(int liv,int a,int fr,struct h3 *out);
void scrivi2(int a,int n);
struct transaz *alltransaz(int n,struct transaz *nex);
struct transaz *prenditr(PGresult *res,struct transaz *t);
void conta(struct transaz *t,struct h3 *n,int i,int l,int dove);
void incrementa(struct transaz *t,struct transaz *l);
struct h3 *unisci(struct h3 *z,int liv,struct h3 *r,int lcorr);
struct h3 *copia(struct h3 *r,struct transaz *a,struct transaz *b,int liv,int lcorr);
struct h3 *scriviout(struct transaz *a,int liv,int lcorr,struct h3 *o);
struct h3 *taglia2(struct h3 *r,int liv,struct h3 *o,int lcorr);
int cerca(struct transaz *f,int liv,struct h3 *o);
int cerca2(struct transaz *f2,struct h3 *o,int liv);
struct h3 *pulisci(struct h3 *t,struct h3 *r);
void pul(struct h3 *t);
struct h3 *isci(struct h3 *r);
struct h3 *suppconf(struct h3 *o);
struct supp *inss(struct transaz *l,struct supp *s);
void insc(struct transaz *l);
int **estrai(int n,int *lista,int grand,int **p,int *corr,int ora);
void cercaconf(int **p,struct transaz *l);
float cercaconf2(int *da,struct h3 *o,int liv);
struct trin *insconf(int *pk,int *a,float suppda,float supptot,float conf,struct trin *t);
struct supp *scrivisupp(FILE *file,struct supp *sup,struct liv1 *r1);
void scriviconf(FILE *file,struct trin *tri,struct liv1 *root1);
char *trovaspiegaz(int n,struct liv1 *r,char *s);
int intlen(int *s);
/* Le principali variabili: */
float limsoglia=0.01; /* limite inferiore (soglia) del supporto (in percentuale) */
int soglia; /* limite inferiore (soglia) del supporto (in numero intero) */
int ntransaz; /* numero totale di transazioni */
float limconf=0.5; /* soglia della confidenza (in percentuale) */
/* parametri di connessione: */
char conninfo[1000]="host=db.stat.unipd.it dbname=daniele user=daniele password=daniele";
/* variabili utili per la connessione al database e la lettura dei risultati */
PGconn *conn;
PGconn *conn2;
PGresult *res;
/* variabili di vario utilizzo */
int nFields,i,j,id,id2,l,last,livello;
/* puntatori alle principali strutture per l'analisi */
struct transaz *t;
struct liv1 *root1;
struct h3 *rooth3;
struct h3 *temp;
struct h3 *outh3; /* lista stabile di output */
struct supp *sup; /* per l'ordinamento secondo il supporto */
struct trin *tri; /* per l'ordinamento secondo la confidenza */
FILE *file; /* per la scrittura su file */
clock_t tp0,tp1; /* per il calcolo del tempo utilizzato */
int discesa[10000]; /* utilizzato nella conta per il problema della sovrapposizione degli hash */
/* File apriori_all.c */
#include "apriori_all_time.h"
int main(int argc,char *argv[])
{
tp0=clock(); /* inizio a contare il tempo */
fprintf(stderr,"\n**********INIZIO ESECUZIONE**********\n");
for(i=1;i<argc;i++) /* utilizzo degli eventuali parametri di input */
{if(strcmp(argv[i],"-h")==0) /* help */
{fprintf(stderr,"\nPossibili parametri in input:\n\t\" -c 300 \" --> indica il limite minimo della confidenza (in millesimi)\n");
fprintf(stderr,"\t\" -s 120 \" --> indica il limite minimo del supporto (in millesimi)\n");
fprintf(stderr,"\t\" -p \"host=db.stat.unipd.it dbname=daniele user=daniele password=daniele\" \" --> indica i nuovi parametri di connessione al db\n\n");
return 1;
}
if(strcmp(argv[i],"-s")==0) /* supporto */
{i++;
limsoglia=((float)atoi(argv[i])/(float)1000);
continue;
}
if(strcmp(argv[i],"-c")==0) /* confidenza */
{i++;
limconf=((float)atoi(argv[i])/(float)1000);
continue;
}
if(strcmp(argv[i],"-p")==0) /* conninfo */
{i++;
strcpy(conninfo,argv[i]);
continue;
}
}
fprintf(stderr,"\nlimite di confidenza: %.3f\n",limconf);
fprintf(stderr,"limite di soglia: %.3f\n",limsoglia);
fprintf(stderr,"informazioni di connessione:\n\t%s\n",conninfo);
conn=PQconnectdb(conninfo); /* Connessione al database */
if(PQstatus(conn)!=CONNECTION_OK)
{fprintf(stderr,"Connessione al database fallita: %s\n",PQerrorMessage(conn));
PQfinish(conn);
return 0;
}
conn2=PQconnectdb(conninfo); /* Seconda connessione al database */
if(PQstatus(conn2)!=CONNECTION_OK)
{fprintf(stderr,"Connessione al database fallita: %s\n",PQerrorMessage(conn));
PQfinish(conn2);
PQfinish(conn);
return 0;
}
res=PQexec(conn,"BEGIN");
if(PQresultStatus(res)!=PGRES_COMMAND_OK)
{fprintf(stderr,"Comando BEGIN fallito: %s\n",PQerrorMessage(conn));
PQclear(res);
PQfinish(conn);
return 0;
}
PQclear(res);
res=PQexec(conn,"DECLARE tr CURSOR FOR SELECT * FROM TRANSAZIONI ORDER BY ID,N");
if(PQresultStatus(res)!=PGRES_COMMAND_OK)
{fprintf(stderr,"Comando CURSOR fallito: %s\n",PQerrorMessage(conn));
PQclear(res);
PQfinish(conn);
return 0;
}
PQclear(res);
res=PQexec(conn,"FETCH ALL in tr"); /* Prendo tutte le transazioni in una sola volta */
if(PQresultStatus(res)!=PGRES_TUPLES_OK)
{fprintf(stderr,"Comando FETCH ALL fallito: %s\n",PQerrorMessage(conn));
PQclear(res);
PQfinish(conn);
return 0;
}
/* ora ho in res le transazioni (pero' nel formato della tabella) --> inizio conta a livello 1 */
if(PQntuples(res)<1)
{fprintf(stderr,"Non ci sono transazioni da analizzare\n\n");
return 0;
}
root1=NULL;
id=atoi(PQgetvalue(res,0,0));
last=atoi(PQgetvalue(res,0,1));
root1=aggliv1(root1,last,conn2);
ntransaz=1;
for(i=1;i<PQntuples(res);i++)
{l=atoi(PQgetvalue(res,i,1));
id2=atoi(PQgetvalue(res,i,0));
if(id2!=id) /* transazione diversa */
{root1=aggliv1(root1,l,conn2);
last=l;
id=id2;
ntransaz++;
continue;
}
/* stessa transazione */
if(l!=last)
{root1=aggliv1(root1,l,conn2);
last=l;
}
}
/* qui ho terminato la conta a livello 1 */
livello=1; /* livello attuale */
soglia=(int)(limsoglia*ntransaz); /* calcolo della soglia per il supporto */
if(soglia<1)
soglia=1; /* voglio che almeno una volta sia presente */
fprintf(stderr,"Soglia = %d\n\n",soglia);
fprintf(stderr,"Conta a livello 1 terminata\n");
taglia(root1,livello); /* faccio "pulizia" nella struttura root1 */
t=alltransaz(10000,NULL);
t->grand=0;
/*
ho le transazioni in *res e la lista degli elementi di livello="livello"
in struct h3 *rooth3
*/
while(rooth3!=NULL)
{livello++;
fprintf(stderr,"Inizio conta a livello %d ",livello);
tp1=clock();
fprintf(stderr,"(Secondi trascorsi: %7.3lf)\n",(tp1-tp0)/(double)CLOCKS_PER_SEC);
t->freq=0; /* utilizzo t->freq (int) per "riga a cui sono arrivato" */
t=prenditr(res,t);
while(1) /* finche' ci sono transazioni */
{if(t->grand<livello)
{if(t->freq>=PQntuples(res))
goto fine;
t=prenditr(res,t);
continue; /* la transazione e' piu' piccola del livello attuale */
}
conta(t,rooth3,0,0,0);
if(t->freq>=PQntuples(res))
goto fine;
t=prenditr(res,t);
}
fine:
/* ora ho la conta a livello="livello" */
temp=rooth3;
rooth3=NULL;
rooth3=unisci(temp,livello,rooth3,0); /* cerco gli item-set candidati per i passi successivi */
rooth3=taglia2(rooth3,livello,outh3,0); /* taglio gli item-set candidati che so non risulteranno frequenti */
rooth3=pulisci(temp,rooth3); /* "pulisce" eventuali liste o transazioni vuote delle due strutture */
}
/* ora chiudo cursori e connessione, e dealloco la memoria occupata dai risultati */
PQclear(res);
res=PQexec(conn,"CLOSE tr");
if(PQresultStatus(res)!=PGRES_COMMAND_OK)
{fprintf(stderr,"Comando CLOSE fallito: %s\n",PQerrorMessage(conn));
PQclear(res);
PQfinish(conn);
return 0;
}
PQclear(res);
res=PQexec(conn,"END");
if(PQresultStatus(res)!=PGRES_COMMAND_OK)
{fprintf(stderr,"Comando END fallito: %s\n",PQerrorMessage(conn));
PQclear(res);
PQfinish(conn);
return 0;
}
PQclear(res);
PQfinish(conn);
PQfinish(conn2);
/*
ora ho in outh3 --> lista stabile di output organizzata a livelli e tagliata per hash,
con supporto > supp.min. (ma non so niente della confidenza)
*/
fprintf(stderr,"\nOrdinamento degli elementi per supporto e confidenza in corso ");
tp1=clock();
fprintf(stderr,"(Secondi trascorsi: %7.3lf)\n",(tp1-tp0)/(double)CLOCKS_PER_SEC);
outh3=suppconf(outh3);
/* ora ho in sup gli elementi ordinati per supporto e in tri le relazioni ordinate per confidenza */
file=fopen("supp.html","w");
if(file==NULL)
{fprintf(stderr,"Problema nell\'apertura del file supp.html\n");
return 0;
}
fprintf(file,"<html>\n<head>\n<META NAME=\"DC.Title\" CONTENT=\"Supporto\">");
fprintf(file,"\n<META NAME=\"description\" CONTENT=\"Output (supporto) del programma");
fprintf(file," per il calcolo di supporto e confidenza di Daniele Rampoldi\">\n");
fprintf(file,"<META NAME=\"keywords\" CONTENT=\"apriori,supporto,daniele rampoldi\">");
fprintf(file,"\n\n<title>Supporti</title>\n\n</head><body>\n\n");
fprintf(file,"<body bgcolor=white text=black link=\"#00aa00\" vlink=\"#606060\" alink=\"#0000aa\">");
fprintf(file,"\n<br><br>\n<h1 align=\"center\">Supporti calcolati</h1>\n<br>\n\n");
fprintf(file,"<TABLE border=1 cellpadding=5 align=center>\n\n");
fprintf(file,"<tr><td align=center><font size=+1><b>Transazione</b></font></td>\n");
fprintf(file,"<td align=center><font size=+1><b>Supporto</b></font></td></tr>\n\n");
fprintf(stderr,"\nScrittura del file supp.html (supporto) in corso ");
tp1=clock();
fprintf(stderr,"(Secondi trascorsi: %7.3lf)\n",(tp1-tp0)/(double)CLOCKS_PER_SEC);
sup=scrivisupp(file,sup,root1); /* scrittura su file degli item-set frequenti con relativo supporto */
fprintf(file,"\n</table>\n</body>\n</html>\n");
fclose(file);
file=fopen("conf.html","w");
if(file==NULL)
{fprintf(stderr,"Problema nell\'apertura del file conf.html\n");
return 0;
}
fprintf(file,"<html>\n<head>\n<META NAME=\"DC.Title\" CONTENT=\"Confidenza\">");
fprintf(file,"\n<META NAME=\"description\" CONTENT=\"Output (confidenza) del programma");
fprintf(file," per il calcolo di supporto e confidenza di Daniele Rampoldi\">\n");
fprintf(file,"<META NAME=\"keywords\" CONTENT=\"apriori,confidenza,daniele rampoldi\">");
fprintf(file,"\n\n<title>Confidenze</title>\n\n</head><body>\n\n");
fprintf(file,"<body bgcolor=white text=black link=\"#00aa00\" vlink=\"#606060\" alink=\"#0000aa\">");
fprintf(file,"\n<br><br>\n<h1 align=\"center\">Confidenze calcolate</h1>\n<br>\n\n");
fprintf(file,"<TABLE border=1 cellpadding=5 align=center>\n\n");
fprintf(file,"<tr><td align=center><font size=+1><b>Regola</b></font></td>\n");
fprintf(file,"<td align=center><font size=+1><b>Supporto Primo Termine</b></font></td>\n");
fprintf(file,"<td align=center><font size=+1><b>Supporto Totale</b></font></td>\n");
fprintf(file,"<td align=center><font size=+1><b>Confidenza</b></font></td></tr>\n\n");
fprintf(stderr,"\nScrittura del file conf.html (confidenza) in corso ");
tp1=clock();
fprintf(stderr,"(Secondi trascorsi: %7.3lf)\n",(tp1-tp0)/(double)CLOCKS_PER_SEC);
scriviconf(file,tri,root1); /* scrittura su file delle regole frequenti con relativa confidenza */
fprintf(file,"\n</table>\n</body>\n</html>\n");
fclose(file);
fprintf(stderr,"\n**********ESECUZIONE COMPLETATA**********\n\n");
return 1;
}
/*
liv --> albero binario di livello 1
l --> prodotto
conn2 --> connessione alternativa al database
*/
struct liv1 *aggliv1(struct liv1 *liv,int l,PGconn *conn2)
{
PGresult *res2;
char richiesta[256];
char t[10];
if(liv==NULL) /* nuovo prodotto */
{strcpy(richiesta,"DECLARE pr CURSOR FOR SELECT SPIEGAZIONE FROM PRODOTTI WHERE N=\0");
sprintf(t,"%d",l);
strcat(richiesta,t);
res2=PQexec(conn2,"BEGIN");
if(PQresultStatus(res2)!=PGRES_COMMAND_OK)
{fprintf(stderr,"Comando BEGIN fallito: %s\n",PQerrorMessage(conn2));
PQclear(res2);
PQfinish(conn2);
return NULL;
}
PQclear(res2);
res2=PQexec(conn2,richiesta);
if(PQresultStatus(res2)!=PGRES_COMMAND_OK)
{fprintf(stderr,"Comando CURSOR fallito: %s\n",PQerrorMessage(conn2));
PQclear(res2);
PQfinish(conn2);
return NULL;
}
PQclear(res2);
res2=PQexec(conn2,"FETCH ALL in pr");
if(PQresultStatus(res2)!=PGRES_TUPLES_OK)
{fprintf(stderr,"Comando FETCH ALL fallito: %s\n",PQerrorMessage(conn2));
PQclear(res2);
PQfinish(conn2);
return NULL;
}
if(PQntuples(res2)>1)
{fprintf(stderr,"Errore: il numero di righe restituite per un prodotto e\' maggiore di 1\n");
return NULL;
}
liv=(struct liv1 *)malloc(sizeof(struct liv1));
liv->left=liv->right=NULL;
liv->freq=1;
liv->n=l;
strcpy(liv->spiegazione,PQgetvalue(res2,0,0));
PQclear(res2);
res2=PQexec(conn2,"CLOSE pr");
if(PQresultStatus(res2)!=PGRES_COMMAND_OK)
{fprintf(stderr,"Comando CLOSE fallito: %s\n",PQerrorMessage(conn2));
PQclear(res2);
PQfinish(conn2);
return NULL;
}
PQclear(res2);
res2=PQexec(conn2,"END");
if(PQresultStatus(res2)!=PGRES_COMMAND_OK)
{fprintf(stderr,"Comando END fallito: %s\n",PQerrorMessage(conn2));
PQclear(res2);
PQfinish(conn2);
return NULL;
}
PQclear(res2);
return liv;
}
/* se sono qua e' perche' non sono arrivato ad una foglia (liv!=NULL) */
if(liv->n==l) /* ho trovato il prodotto nell'albero */
{liv->freq++;
return liv;
}
if(liv->n<l)
{liv->right=aggliv1(liv->right,l,conn2);
return liv;
}
if(liv->n>l)
{liv->left=aggliv1(liv->left,l,conn2);
return liv;
}
fprintf(stderr,"Se sono arrivato qui c\'e\' un errore (funzione aggliv1)\n");
return liv;
}
void taglia(struct liv1 *liv,int livello)
{
if(liv!=NULL)
taglia(liv->left,livello);
else
return;
/* ora sono nella corrente (che non e' NULL) */
if(liv->freq>=soglia)
{cuci(root1,liv->n,livello);
outh3=insout(livello,liv->n,liv->freq,outh3);
}
/* ora cerco nelle maggiori (a destra) */
taglia(liv->right,livello);
}
/*
questa funzione serve per prendere i prodotti frequenti (di livello 1)
e unirli per trovare le transazioni di grandezza 2 candidate ad essere frequenti
*/
void cuci(struct liv1 *r1,int a,int livello)
{
if(r1==NULL)
return;
if(r1->n<a)
{cuci(r1->right,a,livello);
return;
}
if(r1->n>a)
{if(r1->freq>=soglia)
scrivi2(a,r1->n);
cuci(r1->left,a,livello);
}
cuci(r1->right,a,livello);
}
/* inserimento in lista stabile di output a livello 1 */
/* devo inserire a in struct h3 *outh3 al livello="liv-1" */
struct h3 *insout(int liv,int a,int fr,struct h3 *out)
{
struct transaz *li;
int z;
liv--;
if(out==NULL)
{out=(struct h3 *)malloc(sizeof(struct h3));
out->lista=NULL;
for(z=0;z<10;z++)
out->next[z]=NULL;
}
if(liv==0)
{li=out->lista;
out->lista=(struct transaz *)malloc(sizeof(struct transaz));
out->lista->n=(int *)calloc(2,sizeof(int));
out->lista->n[0]=a;
out->lista->n[1]=out->lista->id=0;
out->lista->grand=1;
out->lista->freq=fr;
out->lista->next=li;
return out;
}
fprintf(stderr,"Se sono qui c\'e\' un errore (funzione insout)\n");
return NULL;
}
/* devo scrivere la coppia (a,n) in struct h3 *rooth3 a livello=2 */
void scrivi2(int a,int n)
{
int z,z2;
struct transaz *r;
if(rooth3==NULL)
{rooth3=(struct h3 *)malloc(sizeof(struct h3));
rooth3->lista=NULL;
for(z=0;z<10;z++)
rooth3->next[z]=NULL;
}
z=a%10;
if(rooth3->next[z]==NULL)
{rooth3->next[z]=(struct h3 *)malloc(sizeof(struct h3));
rooth3->next[z]->lista=NULL;
for(z2=0;z2<10;z2++)
rooth3->next[z]->next[z2]=NULL;
}
r=rooth3->next[z]->lista;
rooth3->next[z]->lista=(struct transaz *)malloc(sizeof(struct transaz));
rooth3->next[z]->lista->n=(int *)calloc(3,sizeof(int));
rooth3->next[z]->lista->n[0]=a;
rooth3->next[z]->lista->n[1]=n;
rooth3->next[z]->lista->n[2]=rooth3->next[z]->lista->id=0;
rooth3->next[z]->lista->grand=2;
rooth3->next[z]->lista->freq=0;
rooth3->next[z]->lista->next=r;
}
/* QUI TERMINANO LE FUNZIONI A LIVELLO 1 */
struct transaz *alltransaz(int n,struct transaz *nex)
{
struct transaz *t;
t=(struct transaz *)malloc(sizeof(struct transaz));
t->id=0;
t->n=(int *)calloc(n,sizeof(int));
t->n[0]=0;
t->grand=t->freq=0;
t->next=nex;
return t;
}
struct transaz *prenditr(PGresult *res,struct transaz *t)
{
/* utilizzo t->freq (intero) per riga a cui sono arrivato */
int idd,tra;
t->id=atoi(PQgetvalue(res,t->freq,0));
t->n[0]=atoi(PQgetvalue(res,t->freq,1));
t->freq++;
t->grand=1;
if(t->freq>=PQntuples(res))
{t->n[t->grand]=0;
return t;
}
idd=atoi(PQgetvalue(res,t->freq,0));
while(idd==t->id)
{tra=atoi(PQgetvalue(res,t->freq,1));
if(tra==t->n[t->grand-1]) /* in ogni singola transazione non ci interessano gli elementi doppi */
{t->freq++;
if(t->freq>=PQntuples(res))
{t->n[t->grand]=0;
return t;
}
idd=atoi(PQgetvalue(res,t->freq,0));
continue;
}
t->n[t->grand]=tra;
t->grand++;
t->freq++;
if(t->freq>=PQntuples(res))
{t->n[t->grand]=0;
return t;
}
idd=atoi(PQgetvalue(res,t->freq,0));
}
/* se c'e' una transazione successiva, ma l'id e' diverso */
t->n[t->grand]=0;
return t;
}
/* lucido 32 */
void conta(struct transaz *t,struct h3 *n,int i,int l,int dove)
{
int j,f;
if(n==NULL)
return;
if(l==livello-1) /* se sono in una foglia */
{discesa[dove]=0;
incrementa(t,n->lista);
return;
}
if(i<t->grand)
{for(j=i;j<t->grand;j++)
{f=(t->n[j])%10;
discesa[dove]=t->n[j];
conta(t,n->next[f],j,l+1,dove+1);
}
}
}
/*
t --> transazione
l --> lista
*/
void incrementa(struct transaz *t,struct transaz *l)
{
int i,j=0;
int k;
if(l==NULL)
return;
for(i=0;i<livello-1;i++) /* per il problema della sovrapposizione degli hash */
{if(discesa[i]!=l->n[i])
break;
}
if(i==livello-1) /* devo controllare l'ultimo numero e se e' tutto ok incremento, altrimenti continuo */
{k=0;
for(j=0;j<t->grand;j++)
{if(l->n[i]==t->n[j])
{k=1;
break;
}
}
if(k==1)
l->freq++;
}
incrementa(t,l->next);
/* N.B.:la transazione e' (di solito) piu' lunga della lunghezza di l */
}
/* liv = 2 al primo giro (dopo aver contato le transazioni a livello 2) */
struct h3 *unisci(struct h3 *z,int liv,struct h3 *r,int lcorr)
{
/*
in *z ho le transazioni di livello=liv con relative frequenze.
--> vado in ogni ramo fino a liv-1 --> vado nella lista
--> se gli elementi dallo 0 a liv-2 sono uguali e freq>soglia
--> unisco gli elementi e li metto in *r (per il prossimo livello)
--> contemporaneamente inserisco a livello=liv-1
--> scriviout(liv,int *elem) (lista stabile)
--> inoltre int lcorr (livello corrente) = 0 all'inizio
*/
int i;
struct transaz *a;
struct transaz *b;
struct transaz *c;
if(z==NULL)
return r;
if(lcorr!=liv-1)
{for(i=0;i<10;i++)
{r=unisci(z->next[i],liv,r,lcorr+1);
}
return r;
}
a=z->lista;
while(a!=NULL && a->freq<soglia)
{c=a;
a=a->next;
free(c->n);
free(c);
}
if(a==NULL)
return r;
outh3=scriviout(a,liv,0,outh3); /* scrivo nell'output stabile l'elemento trovato */
b=a->next;
while(b!=NULL && b->freq<soglia)
b=b->next;
if(b==NULL)
return r;
while(a!=NULL)
{while(b!=NULL)
{for(i=0;i<(b->grand)-1;i++)
{if(a->n[i]!=b->n[i])
break;
}
if(i==(b->grand)-1)
{/* sono uguali --> li copio */
r=copia(r,a,b,liv,0);
}
b=b->next;
while(b!=NULL && b->freq<soglia)
b=b->next;
if(b==NULL)
break; /* esci dal while(b) */
} /* fine del while(b) */
c=a;
a=a->next;
free(c->n);
free(c);
while(a!=NULL && a->freq<soglia)
{c=a;
a=a->next;
free(c->n);
free(c);
}
if(a==NULL)
return r;
outh3=scriviout(a,liv,0,outh3);
b=a->next;
while(b!=NULL && b->freq<soglia)
b=b->next;
if(b==NULL)
return r;
} /* fine del while(a) */
}
/*
liv --> livello di *a e *b
lcorr (livello corrente) --> =0 all'inizio
*/
struct h3 *copia(struct h3 *r,struct transaz *a,struct transaz *b,int liv,int lcorr)
{
int i,f;
struct transaz *z;
if(r==NULL)
{r=(struct h3 *)malloc(sizeof(struct h3));
r->lista=NULL;
for(i=0;i<10;i++)
r->next[i]=NULL;
}
if(lcorr!=liv)
{if(b->n[lcorr]<a->n[lcorr]) /* per l'ultimo elemento della lista della transazione */
f=(b->n[lcorr])%10;
else
f=(a->n[lcorr])%10;
r->next[f]=copia(r->next[f],a,b,liv,lcorr+1);
return r;
}
/* se sono qui --> sono arrivato al livello giusto --> devo inserire il nuovo elemento */
z=(struct transaz *)malloc(sizeof(struct transaz));
z->id=z->freq=0;
z->n=(int *)calloc(liv+2,sizeof(int));
z->grand=liv+1;
z->next=r->lista;
r->lista=z;
for(i=0;i<liv-1;i++)
z->n[i]=a->n[i];
if(a->n[liv-1]<b->n[liv-1])
{z->n[liv-1]=a->n[liv-1];
z->n[liv]=b->n[liv-1];
}
else
{z->n[liv-1]=b->n[liv-1];
z->n[liv]=a->n[liv-1];
}
z->n[liv+1]=0;
return r;
}
/* inserisco in struct h3 *outh3 (lista stabile di output) a livello=liv-1 l'elemento a */
struct h3 *scriviout(struct transaz *a,int liv,int lcorr,struct h3 *o)
{
int i,f;
struct transaz *z;
if(o==NULL)
{o=(struct h3 *)malloc(sizeof(struct h3));
o->lista=NULL;
for(i=0;i<10;i++)
o->next[i]=NULL;
}
if(lcorr!=liv-1)
{f=(a->n[lcorr])%10;
o->next[f]=scriviout(a,liv,lcorr+1,o->next[f]);
return o;
}
z=(struct transaz *)malloc(sizeof(struct transaz));
z->id=0;
z->n=(int *)calloc((a->grand)+1,sizeof(int));
z->grand=a->grand;
z->freq=a->freq;
z->next=o->lista;
o->lista=z;
for(i=0;i<a->grand;i++)
{z->n[i]=a->n[i];
}
z->n[z->grand]=0;
return o;
}
/*
devo tagliare --> controllo tutti i sottoins. dei nuovi accoppiamenti
--> devono essere presenti nella lista del livello precedente --> se no -->taglio
n.b.:i nuovi sono generati dai 2 vecchi con i primi "livello" elementi uguali
In particolare tutti i sottoinsiemi di ogni transazione di r a livello=liv
devono essere presenti in o a livello=liv-1
Quindi:
1-prima vado in r a livello=liv (ogni ramo)
2-per ogni transazione in r->foglia --> cerca(transaz,liv,o)
*/
struct h3 *taglia2(struct h3 *r,int liv,struct h3 *o,int lcorr)
{
int i;
struct transaz *f;
struct transaz *f2;
if(r==NULL)
return r;
if(liv!=lcorr)
{for(i=0;i<10;i++)
r->next[i]=taglia2(r->next[i],liv,o,lcorr+1);
return r;
}
inizio:
f=r->lista;
if(f==NULL)
return r;
i=cerca(f,liv,o); /* =0 --> elimina +++++ =1 -->ok */
if(i==0)
{r->lista=f->next;
free(f->n);
free(f);
goto inizio;
}
f2=f;
f=f->next;
while(f!=NULL)
{i=cerca(f,liv,o);
if(i==0)
{f2->next=f->next;
free(f->n);
free(f);
f=f2->next;
}
else
{f2=f;
f=f->next;
}
}
return r;
}
/*
ritorna:
0 --> elimina
1 --> ok
*/
int cerca(struct transaz *f,int liv,struct h3 *o)
{
struct transaz *f2;
int i,j,k;
f2=(struct transaz *)malloc(sizeof(struct transaz));
f2->n=(int *)calloc((f->grand)-1,sizeof(int));
f2->id=f2->freq=0;
f2->next=NULL;
f2->grand=(f->grand)-1;
/* ora per ogni sottoinsieme f2 di f cerco f2 in o a livello=liv-1 */
for(i=0;i<(f->grand)-2;i++)
{/* i rappresenta l'elemento che tolgo */
k=0;
for(j=0;j<(f->grand);j++)
{if(j==i)
continue;
else
{f2->n[k]=f->n[j];
k++;
}
}
j=cerca2(f2,o,liv); /* se =0 --> non trovato */
if(j==0)
{free(f2->n);
free(f2);
return 0;
}
}
free(f2->n);
free(f2);
return 1;
}
/* cerco f2 in o a livello=liv-1 --> se lo trovo --> torna 1 --> altrimenti --> 0 */
int cerca2(struct transaz *f2,struct h3 *o,int liv)
{
int lcorr=0;
int s,i;
struct h3 *z;
struct transaz * f3;
z=o;
while(lcorr!=liv-1)
{if(z==NULL)
return 0;
s=(f2->n[lcorr])%10;
z=z->next[s];
lcorr++;
}
if(z==NULL)
return 0;
f3=z->lista;
while(f3!=NULL)
{for(i=0;i<f2->grand;i++)
{if(f2->n[i]!=f3->n[i])
break;
}
if(i==f2->grand) /* l'ho trovato */
return 1;
f3=f3->next;
}
return 0; /* se f3==NULL sono alla fine */
}
/* devo pulire: t --> no lista, solo next
r --> controlla i *lista */
struct h3 *pulisci(struct h3 *t,struct h3 *r)
{
pul(t);
r=isci(r);
return r;
}
void pul(struct h3 *t)
{
int i;
if(t==NULL)
return;
for(i=0;i<10;i++)
pul(t->next[i]);
free(t);
}
struct h3 *isci(struct h3 *r)
{
int i,j=0;
if(r==NULL)
return NULL;
for(i=0;i<10;i++)
{r->next[i]=isci(r->next[i]);
if(r->next[i]!=NULL)
j=1;
}
if(j==1)
return r;
else /* tutti i figli == NULL */
{if(r->lista!=NULL)
return r;
else
{free(r);
return NULL;
}
}
}
/*
1 - scorro o
2 - per ogni elem. in o --> lo inserisco in s (ordinato per supporto)
--> cerco tutte le relazioni possibili tra gli elementi
(relazioni in cui siano presenti tutti gli elementi)
se ne trovo con conf > sogliac
--> li inserisco in tri (ordinato per confidenza)
*/
struct h3 *suppconf(struct h3 *o)
{
int i;
struct transaz *l;
if(o==NULL)
return o;
for(i=0;i<10;i++)
o->next[i]=suppconf(o->next[i]);
l=o->lista;
if(l==NULL)
return o;
while(l!=NULL)
{sup=inss(l,sup);
insc(l);
l=l->next;
}
return o;
}
struct supp *inss(struct transaz *l,struct supp *s)
{
int i;
float ii;
if(s==NULL)
{s=(struct supp *)malloc(sizeof(struct supp));
s->elem=(int *)calloc((l->grand)+1,sizeof(int));
s->supp=((float)l->freq)/((float)ntransaz); /* calcolo del supporto */
for(i=0;i<l->grand;i++)
s->elem[i]=l->n[i];
s->elem[i]=0;
s->dx=s->sx=s->cen=NULL;
return s;
}
ii=((float)l->freq)/((float)ntransaz); /* calcolo del supporto (per confronto nell'albero binario) */
if(ii<s->supp)
s->sx=inss(l,s->sx);
else
if(ii>s->supp)
s->dx=inss(l,s->dx);
else
s->cen=inss(l,s->cen);
return s;
}
void insc(struct transaz *l)
{
int **p;
int *corr;
int i,k;
p=(int **)calloc(1000,sizeof(int *));
for(i=0;i<1000;i++)
p[i]=NULL;
corr=(int *)calloc(l->grand,sizeof(int));
for(i=1;i<l->grand;i++)
{p=estrai(i,l->n,l->grand,p,corr,0);
cercaconf(p,l);
k=0;
while(p[k]!=NULL)
{free(p[k]);
p[k]=NULL;
k++;
}
}
free(p);
}
/*
n --> quanti devo estrarne
lista --> lista da cui pescare
grand --> grandezza della lista "lista"
p --> output
corr --> lista in cui inserire
ora --> dove inserire in corr
*/
int **estrai(int n,int *lista,int grand,int **p,int *corr,int ora)
{
int i,j,k;
int *l2;
int **p2;
if(grand<1)
return p;
if(n!=1)
{l2=(int *)calloc(grand,sizeof(int));
for(i=0;i<grand;i++)
{corr[ora]=lista[i];
k=0;
for(j=i+1;j<grand;j++)
{l2[k]=lista[j];
k++;
}
p=estrai(n-1,l2,grand-1-i,p,corr,ora+1);
}
free(l2);
return p;
}
/* se n==1 */
corr[ora]=lista[0];
i=k=0;
qui:
while(p[k]!=NULL)
{k++;
if(k%1000==0)
{p2=(int **)calloc(k+1000,sizeof(int *));
for(j=0;j<k;j++)
p2[j]=p[j];
for(j=k;j<k+1000;j++)
p2[j]=NULL;
free(p);
p=p2;
}
}
p[k]=(int *)calloc(ora+2,sizeof(int));
for(j=0;j<=ora;j++)
p[k][j]=corr[j];
p[k][j]=0;
if(grand>1)
{i++;
k++;
corr[ora]=lista[i];
grand--;
goto qui;
}
return p;
}
/*
p --> da
l --> totale
*/
void cercaconf(int **p,struct transaz *l)
{
/*
prima cerco da in outh3 (per ogni elemento in p) --> c'e' sicuramente
poi calcolo la confidenza --> se oltre la soglia della confidenza
--> inserisco il tutto in tri. Se no passo al successivo
*/
int i,j,k,w;
float suppda,conf,supptot;
int *a;
k=0;
a=(int *)calloc(l->grand,sizeof(int));
while(p[k]!=NULL)
{suppda=cercaconf2(p[k],outh3,0); /* supporto del "da" */
supptot=((float)l->freq/(float)ntransaz); /* supporto totale */
conf=supptot/suppda; /* confidenza */
if(conf<limconf) /* il livello di confidenza e' inferiore alla soglia */
{k++;
continue; /* passo al successivo */
}
i=j=0;
for(w=0;w<l->grand;w++)
{if(p[k][i]==l->n[w])
i++;
else
{a[j]=l->n[w]; /* estraggo dal "totale" il "a" */
j++;
}
}
a[j]=0;
tri=insconf(p[k],a,suppda,supptot,conf,tri); /* inserisco in tri da --> a e i valori di supporto e confidenza */
k++;
}
free(a);
}
/* cerco da (fino allo 0) in o e ritorno il supporto (come float) */
float cercaconf2(int *da,struct h3 *o,int liv)
{
int i,f;
float f2;
struct transaz *l;
if(da[liv+1]!=0) /* se lungh=3 --> liv=2 --> liv+1=3 --> da={'a','b','c',0} */
{f=da[liv]%10; /* 0 1 2 3 */
f2=cercaconf2(da,o->next[f],liv+1);
return f2;
}
/* da[liv+1]==0 --> sono arrivato dove volevo */
l=o->lista;
while(l!=NULL)
{for(i=0;i<l->grand;i++)
{if(l->n[i]!=da[i])
break;
}
if(i==l->grand)
{f2=((float)l->freq/(float)ntransaz);
return f2;
}
else
l=l->next;
}
fprintf(stderr,"Se sono arrivato qui e\' perche\' non ho trovato il \"da\" --> E\' UN ERRORE!!!");
fprintf(stderr," (funzione cercaconf2)\n");
return 0;
}
/*
pk --> da
a --> a
suppda --> supporto di "da"
supptot --> supporto totale
conf --> confidenza
t --> albero trinario
*/
struct trin *insconf(int *pk,int *a,float suppda,float supptot,float conf,struct trin *t)
{
int lungh,i;
if(t==NULL)
{t=(struct trin *)malloc(sizeof(struct trin));
lungh=intlen(pk);
t->da=(int *)calloc(lungh+1,sizeof(int));
for(i=0;i<lungh;i++)
t->da[i]=pk[i];
t->da[i]=0;
lungh=intlen(a);
t->a=(int *)calloc(lungh+1,sizeof(int));
for(i=0;i<lungh;i++)
t->a[i]=a[i];
t->a[i]=0;
t->suppda=suppda;
t->supptot=supptot;
t->conf=conf;
t->dx=t->sx=t->cen=NULL;
return t;
}
/* qui t!=NULL */
if(conf<t->conf)
{t->sx=insconf(pk,a,suppda,supptot,conf,t->sx);
return t;
}
if(conf>t->conf)
{t->dx=insconf(pk,a,suppda,supptot,conf,t->dx);
return t;
}
if(conf==t->conf)
{t->cen=insconf(pk,a,suppda,supptot,conf,t->cen);
return t;
}
fprintf(stderr,"Sono qui per errore nella funzione insconf\n");
return t;
}
struct supp *scrivisupp(FILE *file,struct supp *sup,struct liv1 *r1)
{
/* ho appena fatto <table> e chiudo appena prima di </table> */
/* ogni riga sara' del tipo <tr><td align=center> ... </td>
<td align=center> ... </td> ..... <tr> ....... </tr> */
int k;
char *spiegaz;
if(sup==NULL)
return sup;
if(sup->dx!=NULL)
{sup->dx=scrivisupp(file,sup->dx,r1);}
if(sup->cen!=NULL)
{sup->cen=scrivisupp(file,sup->cen,r1);}
/* ora scrivo il corrente */
fprintf(file,"<tr><td align=center>");
k=0;
spiegaz=(char *)calloc(256,sizeof(char));
while(sup->elem[k]!=0)
{spiegaz=trovaspiegaz(sup->elem[k],r1,spiegaz);
if(k==0)
fprintf(file,"{\'%s\'",spiegaz);
else
fprintf(file,",\'%s\'",spiegaz);
k++;
}
free(spiegaz);
fprintf(file,"}</td><td align=center>%.3f</td></tr>\n",sup->supp);
if(sup->sx!=NULL)
sup->sx=scrivisupp(file,sup->sx,r1);
free(sup->elem);
free(sup);
sup=NULL;
return sup;
}
void scriviconf(FILE *file,struct trin *tri,struct liv1 *root1)
{
int k;
char *spiegaz;
if(tri==NULL)
return;
if(tri->dx!=NULL)
scriviconf(file,tri->dx,root1);
if(tri->cen!=NULL)
scriviconf(file,tri->cen,root1);
/* ora scrivo il corrente */
fprintf(file,"<tr><td align=center>");
k=0;
spiegaz=(char *)calloc(256,sizeof(char));
while(tri->da[k]!=0)
{spiegaz=trovaspiegaz(tri->da[k],root1,spiegaz);
if(k==0)
fprintf(file,"{\'%s\'",spiegaz);
else
fprintf(file,",\'%s\'",spiegaz);
k++;
}
fprintf(file,"} --> ");
k=0;
while(tri->a[k]!=0)
{spiegaz=trovaspiegaz(tri->a[k],root1,spiegaz);
if(k==0)
fprintf(file,"{\'%s\'",spiegaz);
else
fprintf(file,",\'%s\'",spiegaz);
k++;
}
free(spiegaz);
fprintf(file,"}</td><td align=center>%.3f</td><td align=center>%.3f</td><td align=center>%.3f</td></tr>\n",tri->suppda,tri->supptot,tri->conf);
if(tri->sx!=NULL)
scriviconf(file,tri->sx,root1);
free(tri->da);
free(tri->a);
free(tri);
}
char *trovaspiegaz(int n,struct liv1 *r,char *s)
{
if(r==NULL)
{strcpy(s,"non trovato");
return s;
}
if(n<r->n)
{s=trovaspiegaz(n,r->left,s);
return s;
}
if(n>r->n)
{s=trovaspiegaz(n,r->right,s);
return s;
}
if(n==r->n)
{strcpy(s,r->spiegazione);
return s;
}
strcpy(s,"Se sono qui e\' perche\' c\'e\' un errore nella funzione trovaspiegaz");
return s;
}
/* ritorna la lunghezza dell'array di interi s (utilizzata nella funzione insconf) */
int intlen(int *s)
{
int i=0;
while(s[i]!=0)
i++;
return i;
}
Data creazione: 17 Settembre 2010
Data ultima modifica: 30 Dicembre 2012
