C Racine commune

C Racine commune - C - Programmation

Marsh Posté le 17-04-2016 à 23:28:19    

Bonjour,
 
Je suis à la recherché d'une function en C ou d'un algorithme qui permettrait de garder seulement les racines communes dans une liste classé par ordre alphabetique.
J'ai essayé avec un strtok mais sans success.
 
Par exemple: bonjour, bonsoir => racine commune bon
Pour info: MaListe est une variable globale contenant les mots bonjour, bonsoir ... etc
 

Code :
  1. void RootCommon(void)
  2. {
  3.     unsigned int MyLen1, MyLen2, MyLen;
  4.     unsigned int MyFlg;
  5.     unsigned char MyChar1, MyChar2;
  6.     unsigned int MyIdx;   
  7.     unsigned char MyRoot[20];
  9.     // Init.
  10.     MyLen = 0;
  11.     MyLen1 = 0;
  12.     MyLen2 = 0;
  13.     MyFlg = 0;
  14.     MyIndex = 0;
  15.     MyChar1 = 0;
  16.     MyChar2 = 0;
  18.     printf("\n" );
  20.     while (MyFlg == 0)
  21.     {
  22.         MyPtr1 = *(MaListe + MyIndex);
  23.         MyPtr2 = *(MaListe + MyIndex+1);
  25.         MyLen1 = strlen(MyPtr1);
  26.         MyLen2 = strlen(MyPtr2);
  28.         if (MyLen1 > MyLen2)
  29.             MyLen = MyLen2;
  30.         else
  31.             MyLen = MyLen1;
  33.         memset((void*) MyRoot,'\0', sizeof(unsigned char)*20);
  36.         for(MyIdx=0; MyIdx < MyLen; MyIdx++)
  37.         {
  38.             MyChar1 = *(MyPtr1+MyIdx);
  39.             MyChar2 = *(MyPtr2+MyIdx);
  41.             if (MyChar1 != MyChar2)
  42.             {
  43.                 if (strlen((const char*)MyRoot)>0)
  44.                     printf("Racine commune:%s\n",MyRoot);
  45.                 break;
  46.             }
  47.             else
  48.             {
  49.                 MyRoot[MyIdx]=MyChar1;
  50.                 printf(" |_Mot %02d - Lettre %c - Mot %02d - Lettre %c\n",
  51.                         MyIndex, MyChar1, MyIndex+1, MyChar2);
  52.             }
  54.             if (MyIdx == (MyLen-1))
  55.             {
  56.                 memset((void*) MyRoot, '\0', sizeof(unsigned char)*20);
  57.                 printf("  |_Mot %s entierement contenu dans mot %s\n", MyPtr1, MyPtr2);
  58.             }
  59.         }
  60.         printf("\n" );
  61.        
  62.         MyIndex++;
  64.         if ((MyIndex+1) > NbrMot)
  65.             MyFlg = 1;
  66.     }

Reply

Marsh Posté le 17-04-2016 à 23:28:19   

Reply

Marsh Posté le 18-04-2016 à 13:57:18    

Si tu veux de l'aide c'est toujours bien de faciliter la tâche aux gens en donnant un exemple complet et compilable.
 

Code :
  1. > "gcc" "tst.c" -Wall -O3 -c
  2. tst.c: In function 'RootCommon':
  3. tst.c:13:2: error: 'MyIndex' undeclared (first use in this function)
  4. tst.c:13:2: note: each undeclared identifier is reported only once for each function it appears in
  5. tst.c:16:2: warning: implicit declaration of function 'printf' [-Wimplicit-function-declaration]
  6. tst.c:16:2: warning: incompatible implicit declaration of built-in function 'printf' [enabled by default]
  7. tst.c:19:3: error: 'MyPtr1' undeclared (first use in this function)
  8. tst.c:19:14: error: 'MaListe' undeclared (first use in this function)
  9. tst.c:20:3: error: 'MyPtr2' undeclared (first use in this function)
  10. tst.c:21:3: warning: implicit declaration of function 'strlen' [-Wimplicit-function-declaration]
  11. tst.c:21:12: warning: incompatible implicit declaration of built-in function 'strlen' [enabled by default]
  12. tst.c:27:3: warning: implicit declaration of function 'memset' [-Wimplicit-function-declaration]
  13. tst.c:27:3: warning: incompatible implicit declaration of built-in function 'memset' [enabled by default]
  14. tst.c:53:21: error: 'NbrMot' undeclared (first use in this function)
  15. tst.c:55:1: error: expected declaration or statement at end of input


 
Certes, c'est des choses faciles à corriger, mais bon...
 
Ceci étant, les signed/unsigned char c'est pour des nombres, pour des caractères on utilise simplement char. Pourquoi tu as mis un cast void* dans l'appel de memset()? Et pour strlen() si tu déclares ton MyRoot simplement comme char[] pas besoin de cast non plus (testé avec GCC 4.7.2 -Wall).

Reply

Marsh Posté le 18-04-2016 à 20:47:54    

Bon, je m'ennuais, c'est ce genre de truc dont tu as besoin? A completer...
 

Code :
  1. #include <stdio.h>
  2. #include <string.h>
  4. #define SZ_BUF 20
  6. int main(void)
  7. {
  8.     char *mot1="abcdefghjklhfdsdcpogrdaa";
  9.     char *mot2="abcdefghjklhfdsdcpogrdbb";
  10.    
  11.     char racine[SZ_BUF];
  12.    
  13.     if(strcmp(mot1, mot2)==0)
  14.     {
  15.         printf("(1) et (2) sont identiques\n" );
  16.     }
  17.     else if(strstr(mot1, mot2))
  18.     {
  19.         printf("%s (2) est contenu dans %s (1)\n", mot2, mot1);
  20.     }
  21.     else if(strstr(mot2, mot1))
  22.     {
  23.         printf("%s (1) est contenu dans %s (2)\n", mot1, mot2);
  24.     }
  25.     else
  26.     {
  27.         int i;
  28.         for(i=0;mot1[i]&&mot2[i]&&mot1[i]==mot2[i]&&i<(SZ_BUF-1);i++)
  29.             racine[i]=mot1[i];
  30.         racine[i]='\0';
  31.        
  32.         if(i)
  33.         {
  34.             printf("racine commune: %s\n", racine);
  35.         }
  36.     }
  37.    
  38.     return 0;
  39. }

Message cité 2 fois
Reply

Marsh Posté le 19-04-2016 à 23:09:35    

rat de combat a écrit :

Bon, je m'ennuais, c'est ce genre de truc dont tu as besoin? A completer...
 

Code :
  1. #include <stdio.h>
  2. #include <string.h>
  4. #define SZ_BUF 20
  6. int main(void)
  7. {
  8.     char *mot1="abcdefghjklhfdsdcpogrdaa";
  9.     char *mot2="abcdefghjklhfdsdcpogrdbb";
  10.    
  11.     char racine[SZ_BUF];
  12.    
  13.     if(strcmp(mot1, mot2)==0)
  14.     {
  15.         printf("(1) et (2) sont identiques\n" );
  16.     }
  17.     else if(strstr(mot1, mot2))
  18.     {
  19.         printf("%s (2) est contenu dans %s (1)\n", mot2, mot1);
  20.     }
  21.     else if(strstr(mot2, mot1))
  22.     {
  23.         printf("%s (1) est contenu dans %s (2)\n", mot1, mot2);
  24.     }
  25.     else
  26.     {
  27.         int i;
  28.         for(i=0;mot1[i]&&mot2[i]&&mot1[i]==mot2[i]&&i<(SZ_BUF-1);i++)
  29.             racine[i]=mot1[i];
  30.         racine[i]='\0';
  31.        
  32.         if(i)
  33.         {
  34.             printf("racine commune: %s\n", racine);
  35.         }
  36.     }
  37.    
  38.     return 0;
  39. }



 
Bonsoir,
 
Merci pour votre réponse et désolé pour le programme qui ne compile pas, j'ai fait un copier-coller brutal.
Effectivement votre code marche cependant je pense que l'analyse de mon problème n'est pas la bonne.
 
Mon besoin est de pouvoir isoler des termes afin de définir une racine commune
Par exemple; j'ai les mots suivants classés de façon alphabetique donc sans doublon:
- adverb
- adverbial
- adverbially
- adversary
- adverse
- adversity
 
Le résultat que je souhaite obtenir aprés le passage de ma fonction est le suivant:
- adverb car adverb, adverbial et adverbially ont pour racine commune seulement adverb
- advers car adversary, adverse et adversity ont pour racine commune seulement advers
 
C'est là que je commence à bloquer, je ne sais pas comment procéder soit je parcours chaque mot lettre par lettre: la 1ere lettre, la 2e lettre et la 3e lettre et j'isole ...
J'ai repris votre programme et en modifiant les mot1, mot2 en les liant à un tableau contenant mes exemples ... mais sans succès

Reply

Marsh Posté le 19-04-2016 à 23:10:38    

rat de combat a écrit :

Bon, je m'ennuais, c'est ce genre de truc dont tu as besoin? A completer...
 

Code :
  1. #include <stdio.h>
  2. #include <string.h>
  4. #define SZ_BUF 20
  6. int main(void)
  7. {
  8.     char *mot1="abcdefghjklhfdsdcpogrdaa";
  9.     char *mot2="abcdefghjklhfdsdcpogrdbb";
  10.    
  11.     char racine[SZ_BUF];
  12.    
  13.     if(strcmp(mot1, mot2)==0)
  14.     {
  15.         printf("(1) et (2) sont identiques\n" );
  16.     }
  17.     else if(strstr(mot1, mot2))
  18.     {
  19.         printf("%s (2) est contenu dans %s (1)\n", mot2, mot1);
  20.     }
  21.     else if(strstr(mot2, mot1))
  22.     {
  23.         printf("%s (1) est contenu dans %s (2)\n", mot1, mot2);
  24.     }
  25.     else
  26.     {
  27.         int i;
  28.         for(i=0;mot1[i]&&mot2[i]&&mot1[i]==mot2[i]&&i<(SZ_BUF-1);i++)
  29.             racine[i]=mot1[i];
  30.         racine[i]='\0';
  31.        
  32.         if(i)
  33.         {
  34.             printf("racine commune: %s\n", racine);
  35.         }
  36.     }
  37.    
  38.     return 0;
  39. }



 
Bonsoir,
 
Merci pour votre réponse et désolé pour le programme qui ne compile pas, j'ai fait un copier-coller brutal.
Effectivement votre code marche cependant je pense que l'analyse de mon problème n'est pas la bonne.
 
Mon besoin est de pouvoir isoler des termes afin de définir une racine commune
Par exemple; j'ai les mots suivants classés de façon alphabetique donc sans doublon:
- adverb
- adverbial
- adverbially
- adversary
- adverse
- adversity
 
Le résultat que je souhaite obtenir aprés le passage de ma fonction est le suivant:
- adverb car adverb, adverbial et adverbially ont pour racine commune seulement adverb
- advers car adversary, adverse et adversity ont pour racine commune seulement advers
 
C'est là que je commence à bloquer, je ne sais pas comment procéder soit je parcours chaque mot lettre par lettre: la 1ere lettre, la 2e lettre et la 3e lettre et j'isole ...
J'ai repris votre programme et en modifiant les mot1, mot2 en les liant à un tableau contenant mes exemples ... mais sans succès

Message cité 1 fois
Reply

Marsh Posté le 20-04-2016 à 10:22:20    

Je fais ce genre de chose avec un arbre n-aire. (eg: http://www.chambily.com/recursivite/chap_VII_4.htm )

 

Bon ça peut sembler énorme à mettre en place pour ce que tu veux faire, mais c'est très puissant!


Message édité par h3bus le 20-04-2016 à 10:22:38

---------------
sheep++
Reply

Marsh Posté le 20-04-2016 à 10:27:42    

Certes, mais c'est pas ça qui va donner les racines. Il lui faut une heuristique pour déterminer quand on considère que la terminaison d'un mot ne fait plus partie de la racine commune, et pour le moment, je n'ai pas vu qu'il en propose une.
 
A+,


---------------
There's more than what can be linked! --    Iyashikei Anime Forever!    --  AngularJS c'est un framework d'engulé!  --
Reply

Marsh Posté le 20-04-2016 à 11:58:42    

Effectivement, il faut un critère.
 
Je m'ennuyais donc j'ai fait un exemple en python

Code :
  1. class Wordstree():
  2.     def __init__(self, word="" ):
  3.         self.children = {}
  4.         self.isword = False
  5.        
  6.         if len(word) == 0:
  7.             self.value = ''
  8.            
  9.         else:
  10.             self.value = word[0]
  11.            
  12.             if len(word) > 1:
  13.                 self.children[word[1]]= Wordstree(word[1:])
  14.             else:
  15.                 self.isword = True
  16.    
  17.     def append(self, word):
  18.         if len(word) == 0:
  19.             return
  20.            
  21.         elif word[0] in self.children:
  22.             self.children[word[0]].append(word[1:])
  23.        
  24.         else:
  25.             self.children[word[0]] = Wordstree(word)
  26.        
  27.         if len(word) == 1:
  28.             self.isword = True
  29.    
  30.     def isRoot(self):
  31.         return len(self.children) > 1
  32.    
  33.     def getChildRoots(self, root="" ):
  34.         roots = []
  35.        
  36.         if self.isRoot():
  37.             for key in self.children.iterkeys():
  38.                 roots += [root+self.value+key]
  39.            
  40.         for key, value in self.children.iteritems():
  41.             roots += value.getChildRoots(root + self.value)
  42.        
  43.         return roots
  45. words = [
  46.     "adverb",
  47.     "adverbial",
  48.     "adverbially",
  49.     "adversary",
  50.     "adverse",
  51.     "adversity"
  52.     ]
  54. tree = Wordstree();
  56. for word in words:
  57.     tree.append(word)
  59. print tree.getChildRoots()


 
Résultat:

Code :
  1. >python wordtree.py
  2. ['advers', 'adverb', 'adversa', 'adversi', 'adverse']


---------------
sheep++
Reply

Marsh Posté le 20-04-2016 à 14:30:02    

sined40 a écrit :

Effectivement votre code marche cependant je pense que l'analyse de mon problème n'est pas la bonne.


Je me disais bien que c'était trop facile... Désolé, je sèche...

Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed