Discussion :

[mido1951]

bonjour,
je cherche une fonction en C qui me permet de faire la ressemblance entre deux chaines de caractères
par exemple: chaine1 = "ACDDEF" et chaine2= "OPCDDE" et j'aurai comme résultat: resultat = "CDDE"
est-ce qu'il existe un fonction prédéfini en C qui réalise cette opération ou je dois la développer ??
merci

[Bktero]

Bonjour,

Tu souhaites bien extraire la plus longue sous-chaine commune à deux chaines ?

[mido1951]

oui exactement

[Franck.H]

Je pense que l'idéal est de la coder toi-même cette fonction car de toutes façons tu seras obligé de boucler pour tester les correspondances.

[EDIT]
Et vu que tu ne connais surement pas la longueur de la chaîne de sortie bin une telle fonction n'existe pas en C (standard du moins)

[kwariz]

Bonjour,

trouver la plus longue sous-chaîne commune à deux chaînes est un problème intéressant. La libc n'a pas de fonction permettant de faire cela, il faudra le coder toi-même. Une implémentation efficace n'est pas triviale (cf google). Mais les algorithmes restent accessibles.
Tu aurais un peu plus de problèmes à trouver les sous-séquences communes, mais apparemment ce n'est pas ce que tu veux (heureusement).

[Franck.H]

Un problème que je trouve effectivement aussi intéressant, je vais peut-être m'amuser avec, vu que j'ai un objet String que j'ai adapté à mon projet en cours, ça va le compléter :-D

[Bysbobo]

J'ai peut etre un algo pour ce genre de chose mais soit je passe à coté d'une difficulté, soit vous exagerez un peu sur le mot "difficile". Apres si vous voulez l'optimiser c'est sur que c'est pas le bon algo

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
boucle sur le nombre d'elements de ta chaine (ici 1 à 6)
    boucle sur le nombre de caracteres (2 mini a 6 max)
        boucle sur l'origine de la chaine (0 a 6(max)-nombre de caracteres pris)
            boucle sur l'autre chaine pour le point de depart
                test( chaine1 & chaine2 )
                    oui -> cool!
                    non -> tant pis
                fin test
            fin boucle
        fin boucle
    fin boucle
fin boucle

Bon c'est du pondu en diagonal (je peux pas le tester ou je suis en ce moment) mais je pense que cela prend en compte tout les cas de figures.
Avec une petite variable qui prend tout les resutats possibles, si tu le fais avec des indices croissants, tu return la variable. Si tu veux tenter par décroissance, il faut inverser tous les indices de boucle mais ton programme s'arretera bien plus vite et tu auras juste a return la premiere chaine commune que tu auras trouvé

Voilou, apres je laisse aux pros du site le soin de pourfendre cet algo si il est faux et s'il est bon, bonne chance ^^

[Bktero]

http://en.wikibooks.org/wiki/Algorit...mmon_substring
--> tu peux toujours comparer avec ce qui est fait ici ^^

Tu as quand même 4 boucles imbriquées, avec un test au milieu. C'est loin d'être trivial comme algo

[Bysbobo]

Ouais c'est pas faux mais au moins je constate que tu parles de l'algo et non des fautes, je suis content

[kwariz]

Bonjour,

je n'ai jamais dit que c'était difficile ou compliqué
Dans la suite je désigne par M et N les 2 chaines, leur longueur respective est notée m et n.
L'implémentation naïve (à ne jamais prendre dans le mauvais sens quand je l'emploie pour un algo) consiste effectivement à générer toutes les sous-chaines de M et à les chercher dans N.
Combien y a-t-il de sous-chaines dans M ? Une sous-chaine est définit de manière unique par son début et sa fin, il y a en a donc autant que de manières possible de choisir un début et une fin parmi m éléments, donc de l'ordre de cnp(2,m), donc en O(m²).
Une implémentation naïve de la recherche d'une chaine M dans une chaine N est en O(mn).
Une estimation à la louche donnera donc pour l'algo considéré une borne sup en O(m³n) puis pour chacune des sous-chaines M on va vérifier son existence dans N, en s'y prenant bien je pense que O(m²n) est réaliste (à vérifier sur un algo, c'est à vue de nez).

C'est une estimation du comportement asymptotique de l'algo. Cela ne signifie pas que pour de petites instances, comme dans l'exemple donné par le primo postant, le temps d'exécution ne soit pas acceptable, ni même meilleur que des algo plus performants asymptotiquement. En revanche cela signifie quand-même qu'il ne le sera pas à partir d'un certain seuil. Ce ne sera certainement jamais un algo utilisé pour trouver la plus grande chaine commune entre l'oeuvre de Hugo et de Balzac, ni pour trouver la plus grande chaine commune d'acides aminés entre les chromosomes Y humains et chimpanzés.

C'est pourquoi j'ai parlé d'efficacité. Ce sont les versions efficaces, mais j'aurais dû parler d'efficience, qui ne sont pas triviales et qui nous poussent à voir le problèmes autrement, à créer de nouvelles approches. Pour le problèmes avec deux chaines très longues il y a la voie des arbres suffixes, pour le cas d'un nombre plus important de chaines on passe par la programmation dynamique.
C'est aussi en ce sens que je les trouve intéressants D'ailleurs une grande majorité des problèmes LCx (longest common quelque chose) sont intéressants à étudier.

[mido1951]

donc selon vous lequel on va le prendre?
je pense l'algorithme qui est sur le lien est mieux optimisé.

[kwariz]

L'important est d'implémenter un algorithme que l'on comprend, avant tout.
Si les instances que tu vas traiter sont petites alors un algorithme naïf est parfait (simple à comprendre, à débuguer, etc.).
Si tu dois traiter des instances plus longues alors oui pourquoi pas ...
Ça va dépendre de l'utilisation et de ton niveau principalement
Mais un conseil ... fais des dessins pour comprendre comment ça se passe.

[imperio]

Un petit conseil pour te faciliter la vie, utilise strncmp.

Après c'est relativement simple (je te donne mon raisonnement) :

Dans ta fonction, on va chercher la plus petite des deux chaînes dans la plus grande (si elles sont de même taille, la logique ne change pas). A chaque passe, on reduit la taille de la chaîne comparée de 1 jusqu'à ce qu'on arrive à 0. Après il suffit de décaler la chaîne de 1 pour comparer.

J'espère que mon explication n'est pas trop brumeuse.

[Bktero]

Notons qu'il existe la fonction strstr() pour chercher une chaine dans une autre : http://linux.die.net/man/3/strstr

[EtherOS]

-> Soit M la longueur d'une sous-chaine A
-> Soit N la longueur d'une sous chaine B

1/ methode naîve :
Chercher itérativement toute les sous chaines dans A et les comparer à celles de B
Mauvaise complexité : O(M.N) plus la chaine est longue plus la complexité tend vers l'infini (complexité exponentielle - très mauvais)

2/ Methode intuitive :

Appliquer l'Algorithme de Boyer-Moore car meilleure complexité :
meilleur des cas : O(M/N) .Quand les longueurs des chaines sont grandes le rapport M/N converge asymptotiquement vers 1
pire des cas : O(M+N) .Quand les longueurs des chaines sont grandes M+N croit peu vers l'infini

comparaison 1/ et 2/ :

O(M+N)/O(M.N) "=" O(1/N + 1/ M) avec N >>1 et M>>1

donc : 1/X -> 0 quand X -> +oo avec X c {M,N}

Ainsi , 1/ est largement et empiriquement inéfficient par rapport à la méthode 2/

Pour savoir utiliser cet algorithme : Aller sur Wikipédia.

[kwariz]

Par curiosité j'ai testé la version naïve et la version programmation dynamique.
La version naïve fonctionne plutôt bien, mais se dégrade surtout quand il n'y a pas de lcs (le pire des cas) à partir de chaines d'environs 500 char chacune.
En comptant le nombre de comparaison de caractères chaines à chaines on obtient :


La version naïve est en O(N^3) alors que la version dp est en O(N^2).

j'ai utilisé (excusez le code .... je n'ai pas essayé de commenter ou de faire propre) :

lcss_naive.c:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
static int string_n_compare(const char* str1, const char* str2, size_t n, size_t *cmp_count)
{
  size_t i;
  for(i=0; i<n; ++i)
    if (str1[i]!=str2[i])
      break;
  if (i==n) {
    *cmp_count+=i;
    return 0;
  } else {
    *cmp_count+=i+1;
    return 1;
  }
}
 
int lcss_naive(const char *str1, const char *str2, char **lcs, size_t *len)
{
  size_t cmp_count=0;
  size_t len1=strlen(str1);
  size_t len2=strlen(str2);
  size_t needle_len;
  size_t haystack_len;
  const char *needle;
  const char *haystack;
 
  if (len1<len2) {
    needle_len=len1;
    haystack_len=len2;
    needle=str1;
    haystack=str2;
  } else {
    needle_len=len2;
    haystack_len=len1;
    needle=str2;
    haystack=str1;
  }
 
  for(size_t lcss_len=needle_len; lcss_len>0; --lcss_len) {
    for(size_t lcss_start=0; lcss_start+lcss_len<=needle_len; ++lcss_start) {
      for(size_t haystack_start=0; haystack_start+lcss_len<=haystack_len; ++haystack_start) {
        if (string_n_compare(needle+lcss_start,haystack+haystack_start, lcss_len, &cmp_count) == 0) {
          *len=lcss_len;
          *lcs=malloc(lcss_len+1);
          strncpy(*lcs, needle+lcss_start, lcss_len);
          (*lcs)[lcss_len]=0;
          return cmp_count;
        }
      }
    }
  }
 
  return cmp_count;
}

lcss_dp.c:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
size_t lcss_dp(const char *str1, const char *str2, char **lcs, size_t *len)
{
  size_t cmp_count=0;
  size_t len1=strlen(str1);
  size_t len2=strlen(str2);
  size_t needle_len;
  size_t haystack_len;
  const char *needle;
  const char *haystack;
  size_t *buffer[2];
 
  if (len1<len2) {
    needle_len=len1;
    haystack_len=len2;
    needle=str1;
    haystack=str2;
  } else {
    needle_len=len2;
    haystack_len=len1;
    needle=str2;
    haystack=str1;
  }
 
  buffer[0]=malloc(needle_len * sizeof *buffer[0]);
  buffer[1]=malloc(needle_len * sizeof *buffer[0]);
 
  *lcs=NULL;
  *len = 0;
  for(size_t haystack_start=0; haystack_start< haystack_len; ++haystack_start) {
    for(size_t needle_start=0; needle_start<needle_len; ++needle_start) {
      cmp_count++;
      if (haystack[haystack_start] == needle[needle_start]) {
        if ( (needle_start==0) || (haystack_start==0) ) {
          buffer[haystack_start % 2][needle_start] = 1;
        } else {
          buffer[haystack_start % 2][needle_start] = buffer[1 - (haystack_start % 2)][needle_start - 1] + 1;
        }
        if (buffer[haystack_start % 2][needle_start]>*len) {
          *len=buffer[haystack_start % 2][needle_start];
          if (*lcs!=NULL) free(*lcs);
          *lcs=malloc(*len + 1);
          strncpy(*lcs,haystack+haystack_start-*len+1,*len);
        }
      } else {
        buffer[haystack_start % 2][needle_start] = 0;
      }
    }
  }
 
  free(buffer[0]);
  free(buffer[1]);
 
  return cmp_count;
}

Si ça intéresse quelqu'un je peux poster un code un peu plus propre et ce qui m'a permis de créer le graphique.

[mido1951]

merci pour vous les amis c'est très intéressant