/********************************************************************** * * module : Index * commande : IndexClusterFromAssoc * fichier : IndexClusterFromAssoc.c * Auteur : Emmanuel NAUER * Date : 05.11.96 * $Id: ClusterFromAssoc.c,v 1.3 2003/03/17 16:24:55 parmentf Exp $ * ***********************************************************************/ #include "ctype.h" #include "SxmlNode.h" #include "SxPath.h" #include "StrDict.h" #define inputMot1 inputItem1->mot #define inputMot2 inputItem2->mot #define inputF1 inputItem1->f #define inputF2 inputItem2->f #define inputId1 inputItem1->id #define inputId2 inputItem2->id int atoi(); int getopt(); /*********************************************************************** * Description des structures de donnees * ***********************************************************************/ struct descMot { char *mot; struct descCluster *dCluster; struct descMot *suivant; }; struct descAsclu { SxmlNode *assoc; struct descCluster *dCluster; struct descAsclu *suivant; }; struct descCluster { SxmlNode *cluster; SxmlNode *lMot; SxmlNode *lAssoc; SxmlNode *lClu; struct descAsclu *lAsclu; struct descCluster *suivant; struct descCluster *precedent; }; struct inputStruct { char *mot; char *f; char *id; struct descMot *dMot; int new; }; /*********************************************************************** * Environnement de travail * ***********************************************************************/ struct descMot *listMot; struct descCluster *listCluster; struct inputStruct *inputItem1, *inputItem2; char *pathF, *pathMcl, *pathId, *pathFij, *inputF12, *inputP12; char *pathTi, *pathTiMcl, *pathTiF, *pathTiId; char *pathTj, *pathTjMcl, *pathTjF, *pathTjId; char *NomCluster[1000]; int traceLevel; /*********************************************************************** * Parametres de la clusterisation * ***********************************************************************/ int paramCluster_MaxMot; int paramCluster_MinMot; int nbMaxCluster; int nbCluster; int withname; /*********************************************************************** * fonctions de traitement des listes * ***********************************************************************/ /******************************* listMot ******************************/ struct descMot *pMot(mot) char *mot; { struct descMot *p; p=listMot; while (p) { if (strcmp(p->mot,mot)==0) return(p); else p=p->suivant; } return(0); } struct descMot *addMotToListMot(mot,dCluster) char *mot; struct descCluster *dCluster; { struct descMot *dMot; if (!(dMot=pMot(mot))) { dMot=(struct descMot *)malloc(sizeof(struct descMot)); dMot->mot=malloc(strlen(mot)+1); strcpy(dMot->mot,mot); dMot->dCluster=dCluster; dMot->suivant=listMot; listMot=dMot; } return(dMot); } /********************************* Asclu ******************************/ void addAsclu(c1,c2,mot1,mot2) struct descCluster *c1; struct descCluster *c2; char *mot1; char *mot2; { struct descAsclu *desc1, *desc2; /* ajout dans le cluster c1 */ desc1=(struct descAsclu *)malloc(sizeof(struct descAsclu)); desc1->assoc=SxmlElementCreate("lassoc"); SxmlAppendChild(desc1->assoc,SxmlLeafCreate("m1",mot1)); SxmlAppendChild(desc1->assoc,SxmlLeafCreate("m2",mot2)); desc1->dCluster=c2; desc1->suivant=c1->lAsclu; c1->lAsclu=desc1; /* ajout dans le cluster c2 */ desc2=(struct descAsclu *)malloc(sizeof(struct descAsclu)); desc2->assoc=SxmlElementCreate("lassoc"); SxmlAppendChild(desc2->assoc,SxmlLeafCreate("m1",mot2)); SxmlAppendChild(desc2->assoc,SxmlLeafCreate("m2",mot1)); desc2->dCluster=c1; desc2->suivant=c2->lAsclu; c2->lAsclu=desc2; } void changeAsclu(c,oldCluster,newCluster) struct descCluster *c; struct descCluster *oldCluster; struct descCluster *newCluster; { struct descAsclu *p, *q; p=c->lAsclu; while(p) { q=p->dCluster->lAsclu; while(q) { if (q->dCluster==oldCluster) q->dCluster=newCluster; q=q->suivant; } p=p->suivant; } } void appendlAsclu(c1,c2) struct descCluster *c1; struct descCluster *c2; { struct descAsclu *p, *q; /* positionnement en queue de lAsclu de c1 */ q=0; p=c1->lAsclu; while (p) { q=p; p=p->suivant;} /* ajout de lAsclu de c2 en queue de c1 */ if (!q) c1->lAsclu=c2->lAsclu; else q->suivant=c2->lAsclu; } /******************************* clusters *****************************/ struct descCluster *lastCluster() { struct descCluster *p, *q; q=0; p=listCluster; while (p) { q=p; p=p->suivant; } return(q); } void addMotToCluster(d,l,itemMot) struct descCluster *d; SxmlNode *l; struct inputStruct *itemMot; { SxmlNode *w; char *m; m=itemMot->mot; w=SxmlLeafCreate("mot",m); SxmlAppendChild(l,w); SxmlSetAttribute(w,"f",itemMot->f); if (itemMot->id)SxmlSetAttribute(w,"id",itemMot->id); } void addAssocToListAssoc(l,itemMot1,itemMot2,f,p) SxmlNode *l; struct inputStruct *itemMot1; struct inputStruct *itemMot2; char *f; char *p; { SxmlNode *ass; SxmlNode *localMot; if(traceLevel>3) printf("--- addAssocToListAssoc ---\n"); ass=SxmlElementCreate("assoc"); SxmlAppendChild(l,ass); SxmlAppendChild(ass,SxmlLeafCreate("f",f)); SxmlAppendChild(ass,SxmlLeafCreate("p",p)); SxmlAppendChild(ass,localMot=SxmlLeafCreate("m1",itemMot1->mot)); if(itemMot1->id)SxmlSetAttribute(localMot,"id",itemMot1->id); SxmlAppendChild(ass,localMot=SxmlLeafCreate("m2",itemMot2->mot)); if(itemMot2->id)SxmlSetAttribute(localMot,"id",itemMot2->id); if(traceLevel>3) {SxmlPrint(ass); putchar('\n');} } void deleteMot(c,mot) struct descCluster *c; char *mot; { SxmlNode *n; int fin; fin=0; n=SxmlFirstChild(c->lMot); while((n)&&(!fin)) { if (strcmp(SxmlGetFirstText(n),mot)==0) { SxmlRemoveChild(n); fin=1; } else n=SxmlNextSibling(n); } } void deleteAssocInt(c) struct descCluster *c; { int fin; fin=0; SxmlRemoveChild(SxmlFirstChild(c->lAssoc)); } void deleteCluster(c) struct descCluster *c; { if (c->suivant) c->suivant->precedent=c->precedent; if (c->precedent) c->precedent->suivant=c->suivant; else listCluster=c->suivant; SxmlFree(c->cluster); free(c); } void supprimeCluster() { struct descCluster *p, *q; struct descAsclu *a1, *a2, *a3; int supprime; /* suppression des clusters ayant un nombre de mot inferieur a MinMot */ p=listCluster; while (p) { supprime=0; if ((SxmlLength(p->lMot))lAsclu; while (a1) { /* boucle sur les associations externes du cluster lie */ a2=a1->dCluster->lAsclu; a3=0; while (a2) { if (a2->dCluster==p) { /* suppression de l'association externe */ if (a3) a3->suivant=a2->suivant; else a1->dCluster->lAsclu=a2->suivant; } a3=a2; a2=a2->suivant; } a1=a1->suivant; } /* suppression du cluster */ } if (supprime) { q=p->suivant; deleteCluster(p); p=q; } else p=p->suivant; } } void determineClusterName() { struct descCluster *p; StrDict *PAssoc; SxmlNode *n, *n1; char *val, *mot, *tc, *m1, NewValue[10]; int f,f1,f2,max,cid; p=lastCluster(); while (p) { PAssoc=NewStrDict(); /* ponderation provenant des frequences d'asscoiations */ n1=p->lAssoc; n=SxmlGetFirstChildByTagName(n1, "assoc"); while(n) { mot=SxmlLeafText(SxmlGetFirstChildByTagName(n, "m1")); if ((val=StrDictSearch(PAssoc,mot))) f=atoi(val)+1; else f=1; sprintf(NewValue,"%d",f); StrDictAddNewDatum (PAssoc,strdup(mot),strdup(NewValue)); mot=SxmlLeafText(SxmlGetFirstChildByTagName(n, "m2")); if ((val=StrDictSearch(PAssoc,mot))) f=atoi(val)+1; else f=1; sprintf(NewValue,"%d",f); StrDictAddNewDatum(PAssoc,strdup(mot),strdup(NewValue)); n=SxmlNextSibling(n); } /* determination du terme central */ StrDictIteratorReset(PAssoc); max=0; while ((mot=StrDictNext(PAssoc))) { f=atoi(StrDictValue(PAssoc)); if (f>max) { max=f; tc=strdup(mot); } else { if (f==max) { /* ambiguite => choix grace a la frequence des mots */ n1=p->lMot; n=SxmlGetFirstChildByTagName(n1, "mot"); while(n) { m1=SxmlGetFirstText(n); if (strcmp(m1,tc)==0) f1=atoi(SxmlGetAttribute(n,"f")); if (strcmp(m1,mot)==0) f2=atoi(SxmlGetAttribute(n,"f")); n=SxmlNextSibling(n); } if(f2>f1) { tc=strdup(mot); } } } } /* printf("========= tc[%s]\n",tc); */ /* ajout du nom du cluster dans le noeud "name" et dans NomCluster[] */ SxmlAppendChild(p->cluster, SxmlLeafCreate("name",tc)); cid=atoi(SxmlGetAttribute(p->cluster,"i")); NomCluster[cid]=strdup(tc); /* cluster suivant */ p=p->precedent; } } void completeAscluName() { struct descCluster *p; SxmlNode *son, *cluster, *n; char *data; int cid; p=listCluster; while (p) { cluster=p->cluster; /* NomCluster[cid]; */ n=SxmlGetFirstChildByTagName(cluster,"lclu"); son=SxmlGetFirstChildByTagName(n,"asclu"); while(son) { data=SxmlLeafText(SxmlGetFirstChildByTagName(son,"cid")); cid=atoi(data); SxmlAppendChild(son,SxmlLeafCreate("name",strdup(NomCluster[cid]))); son=SxmlGetNextSiblingByTagName(son, "asclu"); }; /* cluster suivant */ p=p->suivant; } } void completeCluster() { struct descCluster *p; struct descAsclu *a; SxmlNode *n, *lkw, *kw, *son; char buffer[4]; int i, genere; /* renumerotation des clusters */ /* + ajout d'un element "nmot" (nombre de mots */ i=1; p=lastCluster(); while (p) { /* rajout de l'attribut i="Numero de Cluster" */ sprintf(buffer,"%d",i++); SxmlSetAttribute(p->cluster,"i",buffer); /* rajout du noeud Numero de Cluster */ if (withname) SxmlAppendChild(p->cluster,SxmlLeafCreate("code",strdup(buffer))); /* rajout du noeud Nombre de mots dans le Cluster */ sprintf(buffer,"%d",SxmlLength(p->lMot)); SxmlAppendChild(p->cluster,SxmlLeafCreate("nmot",buffer)); /* rajout du noeud */ SxmlAppendChild(p->cluster,lkw=SxmlElementCreate("lkw")); /* rajout des noeuds termefrequence */ if (withname) { SxmlNode *lmot; lmot=SxmlGetFirstChildByTagName(n, "lmot"); SxmlReset(lmot); n=p->cluster; while ((son=SxmlNextNode(lmot))) /* SgmlPathStrDo(n,"lmot/mot", son, */ { if (SxmlNodeHasName(son,"mot")) { SxmlAppendChild(lkw,kw=SxmlElementCreate("kw")); SxmlAppendChild(kw,SxmlLeafCreate("t",SxmlGetFirstText(son))); SxmlAppendChild(kw,SxmlLeafCreate("f",SxmlGetAttribute(son,"f"))); } } } p=p->precedent; } nbCluster=i; /* creation des listes d'associations externes */ p=listCluster; while (p) { for(i=1;ilAsclu; genere=1; while (a) { if (atoi(SxmlGetAttribute(a->dCluster->cluster,"i"))==i) { if (genere) { SxmlAppendChild(p->lClu,n=SxmlElementCreate("asclu")); SxmlAppendChild(n, SxmlLeafCreate("cid", SxmlGetAttribute(a->dCluster->cluster,"i"))); genere=0; } SxmlAppendChild(n, a->assoc); } a=a->suivant; } } p=p->suivant; } /* determination du nom du cluster */ if (withname) { determineClusterName(); completeAscluName(); } } void writeListCluster() { struct descCluster *p; p=listCluster; while (p) { SxmlPrint(p->cluster); putchar ('\n'); p=p->suivant; } } void writeListInverseCluster() { struct descCluster *p; p=lastCluster(); while (p) { SxmlPrint(p->cluster); putchar ('\n'); p=p->precedent; } } /*********************************************************************** * Traitement des donnees entrantes * ***********************************************************************/ void initPath() { pathTi ="assoc/ti"; pathTj ="assoc/tj"; pathFij ="assoc/fij"; pathF ="f"; pathMcl ="kw"; pathId ="id"; } void computePath() { Buffer *internalBuffer=BufferCreate(16,16); BufferStrcpy(internalBuffer,pathTi); BufferStrcat(internalBuffer,"/"); BufferStrcat(internalBuffer,pathMcl); pathTiMcl=BufferSave(internalBuffer); /* TODEL */ BufferStrcpy(internalBuffer,pathTj); BufferStrcat(internalBuffer,"/"); BufferStrcat(internalBuffer,pathMcl); pathTjMcl=BufferSave(internalBuffer); /* TODEL */ BufferStrcpy(internalBuffer,pathTi); BufferStrcat(internalBuffer,"/"); BufferStrcat(internalBuffer,pathF); pathTiF =BufferSave(internalBuffer); /* TODEL */ BufferStrcpy(internalBuffer,pathTj); BufferStrcat(internalBuffer,"/"); BufferStrcat(internalBuffer,pathF); pathTjF =BufferSave(internalBuffer); /* TODEL */ BufferStrcpy(internalBuffer,pathTi); BufferStrcat(internalBuffer,"/"); BufferStrcat(internalBuffer,pathId); pathTiId =BufferSave(internalBuffer); BufferStrcpy(internalBuffer,pathTj); BufferStrcat(internalBuffer,"/"); BufferStrcat(internalBuffer,pathId); pathTjId =BufferSave(internalBuffer); /* TODEL */ /* pathTjId =BufferSaveCat3(pathTj,"/",pathId); */ } void splitInputRecord() { inputMot1=SxPathEasyGetFirstText(SxmlInputDocument, pathTiMcl); if(traceLevel>1) printf("===== new pair ====\n term1 = %s\n", inputMot1); inputMot2=SxPathEasyGetFirstText(SxmlInputDocument, pathTjMcl); if(traceLevel>1) printf(" term2 = %s\n", inputMot2); inputF1=SxPathEasyGetFirstText(SxmlInputDocument, pathTiF); if(traceLevel>1) printf(" f1 = %s\n", inputF1); inputF2=SxPathEasyGetFirstText(SxmlInputDocument, pathTjF); if(traceLevel>1) printf(" f2 = %s\n", inputF2); inputId1=SxPathEasyGetFirstText(SxmlInputDocument, pathTiId); if(traceLevel>1) printf(" id1 = %s\n", inputId1); inputId2=SxPathEasyGetFirstText(SxmlInputDocument, pathTjId); inputF12=SxPathEasyGetFirstText(SxmlInputDocument, pathFij); if(traceLevel>1) printf(" f12 = %s\n", inputF12); inputP12=SxmlInputRecordKey; if(traceLevel>1) printf(" w12 = %s\n", inputP12); } SxmlNode *nextValidInputRecord() { while (SxmlInputNextRecord()) { splitInputRecord(); if (!inputMot1)continue; if (!inputMot2)continue; if (strcmp(inputMot1, inputMot2)!=0)return SxmlInputRecord; } return NULL; } /*********************************************************************** * Fonction(s) d'initialisation * ***********************************************************************/ void newCluster() { SxmlNode *clu; SxmlNode *lMot; SxmlNode *lAssocInt; SxmlNode *lAssocExt; struct descCluster *desc; char bufNumber[10]; desc=(struct descCluster *)malloc(sizeof(struct descCluster)); clu=SxmlElementCreate("clu"); desc->cluster=clu; sprintf(bufNumber,"%d",nbMaxCluster); SxmlSetAttribute(clu,"i",bufNumber); SxmlAppendChild(clu, lMot=SxmlElementCreate("lmot")); desc->lMot=lMot; addMotToCluster(desc,lMot,inputItem1); addMotToCluster(desc,lMot,inputItem2); if ((inputItem1->dMot=pMot(inputMot1))) { inputItem1->new=1; } else { inputItem1->new=0; inputItem1->dMot=addMotToListMot(inputMot1,desc); } if ((inputItem2->dMot=pMot(inputMot2))) { inputItem2->new=1; } else { inputItem2->new=0; inputItem2->dMot=addMotToListMot(inputMot2,desc); } SxmlAppendChild(clu, lAssocInt=SxmlElementCreate("lassoc")); addAssocToListAssoc(lAssocInt, inputItem1, inputItem2, inputF12, inputP12); desc->lAssoc=lAssocInt; SxmlAppendChild(clu, lAssocExt=SxmlElementCreate("lclu")); desc->lClu=lAssocExt; desc->lAsclu=0; /* insertion en tete de la liste des clusters */ desc->suivant=listCluster; desc->precedent=0; if (listCluster) listCluster->precedent=desc; listCluster=desc; } void append(c1,c2) /* ajoute le cluster c2 au cluster c1) */ struct descCluster *c1, *c2; { int a,b,i; struct descCluster *p; struct descMot *dMot; SxmlNode *n; i=1; p=listCluster; while (p) { if (p==c1) { a=i; } if (p==c2) { b=i; } i++; p=p->suivant; } if (asuivant; } /*************** concatenation des listes de mots ********************/ SxmlReset(c2->lMot); while ((n=SxmlNextNode(c2->lMot))) { dMot=pMot(SxmlGetFirstText(n)); if (dMot->dCluster==c2) { dMot->dCluster=c1; SxmlAppendChild(c1->lMot,SxmlClone(n)); } } /*************** concatenation des listes d'associations internes ****/ SxmlReset(c2->lAssoc); while ((n=SxmlNextNode(c2->lAssoc))) { SxmlAppendChild(c1->lAssoc,SxmlClone(n)); } /*************** concatenation des listes d'associations externes ****/ appendlAsclu(c1,c2); /**** modifications des clusters pointant le cluster a supprimer *****/ changeAsclu(c2,c2,c1); /*************** liberations memoires ********************************/ deleteCluster(c2); } void aggregate() { int nb, nb1, nb2; struct descCluster *ClusterToDelete, *ClusterToKeep; char *MotToDelete; if ((inputItem1->new)||(inputItem2->new)) { if ((inputItem1->new)&&(inputItem2->new)) { if (inputItem1->dMot->dCluster==inputItem2->dMot->dCluster) { /* printf("***** CAS : les 2 mots appartiennent au meme cluster\n"); rajouter l'association */ append(inputItem2->dMot->dCluster,listCluster); } else { /* printf("***** CAS : les 2 mots appartiennent a des clusters differents\n"); */ nb1=SxmlLength(inputItem1->dMot->dCluster->lMot); nb2=SxmlLength(inputItem2->dMot->dCluster->lMot); if ((nb1+nb2)>paramCluster_MaxMot) { /* printf(" => sous-cas : lien entre les 2 clusters\n"); rajouter le lien externe */ addAsclu(inputItem1->dMot->dCluster,inputItem2->dMot->dCluster, inputItem1->dMot->mot, inputItem2->dMot->mot); } else { /* printf(" => sous-cas : concatener les 2 clusters\n"); ajout de l'association des 2 mots dans 1 des clusters */ SxmlAppendChild(inputItem1->dMot->dCluster->lAssoc,SxmlClone(SxmlFirstChild(listCluster->lAssoc))); /* concatener les 2 clusters */ append(inputItem1->dMot->dCluster,inputItem2->dMot->dCluster); } /* destruction du 1er cluster */ deleteCluster(listCluster); } } else { /* printf("***** CAS : 1 mot appartiennent deja a un cluster\n"); */ if (inputItem1->new) { nb=SxmlLength(inputItem1->dMot->dCluster->lMot); ClusterToDelete=inputItem2->dMot->dCluster; ClusterToKeep=inputItem1->dMot->dCluster; MotToDelete=inputMot1; } else { nb=SxmlLength(inputItem2->dMot->dCluster->lMot); ClusterToDelete=inputItem1->dMot->dCluster; ClusterToKeep=inputItem2->dMot->dCluster; MotToDelete=inputMot2; } if (nb sous-cas : concatener les 2 clusters\n"); */ append(inputItem1->dMot->dCluster,inputItem2->dMot->dCluster); } else { /* printf(" => sous-cas : cluster a 1 mot et 1 relation externe\n");*/ deleteMot(ClusterToDelete,MotToDelete); deleteAssocInt(ClusterToDelete); addAsclu(inputItem1->dMot->dCluster,inputItem2->dMot->dCluster, inputItem1->dMot->mot, inputItem2->dMot->mot); } } } } /***********************************************************************/ void usage() { fprintf (stderr,"usage:[-i pathTi][-j pathTj][-f pathF][-k pathMcl][-F pathFij]\n"); fprintf (stderr," [-M paramCluster_MaxMot][-m paramCluster_MinMot][-n]\n"); exit(1); } extern char *optarg; extern int optind; int main(argc,argv) int argc; char **argv; { int cod_arg,i ; nbMaxCluster=300; nbCluster=0; paramCluster_MaxMot=8; paramCluster_MinMot=3; withname=0; traceLevel=0; initPath(); while ((cod_arg = getopt(argc,argv,"i:j:f:F:k:M:m:n:T:"))!=EOF) { switch(cod_arg) { case 'f': pathF=optarg; break; case 'i': pathTi=optarg; break; case 'j': pathTj=optarg; break; case 'k': pathMcl=optarg; break; case 'M': paramCluster_MaxMot=atoi(optarg); break; case 'm': paramCluster_MinMot=atoi(optarg); break; case 'n': withname=1; break; case 'F': pathFij=optarg; break; case 'T': traceLevel=atoi(optarg); break; default: usage(); } } computePath(); inputItem1=(struct inputStruct *)malloc(sizeof(struct inputStruct)); inputItem2=(struct inputStruct *)malloc(sizeof(struct inputStruct)); listCluster=0; listMot=0; i=1; if (nextValidInputRecord()) { newCluster(); i++; while(nextValidInputRecord()) { /* printf("============================= Etape : %d ============================\n",i++); */ newCluster(); aggregate(); } supprimeCluster(); completeCluster(); writeListInverseCluster(); } return 0; }