Sujet Précédent Sujet Suivant

Algorithme Boyer Moore

cs_kam42 Messages postés 12 Date d'inscription mercredi 5 décembre 2007 Statut Membre Dernière intervention 9 mai 2008 - 25 déc. 2007 à 14:40
BruNews Messages postés 21040 Date d'inscription jeudi 23 janvier 2003 Statut Modérateur Dernière intervention 21 août 2019 - 25 déc. 2007 à 16:07
bonjour à tous;
es ce que quelqu'un aurait des codes sources en C++ de l'algorithme de boyer moore pour la recherche de motif ?


merci d'avance

9 réponses

Réponse 1 / 9
BruNews Messages postés 21040 Date d'inscription jeudi 23 janvier 2003 Statut Modérateur Dernière intervention 21 août 2019
25 déc. 2007 à 15:17
des milliers...
http://www.google.fr/search?hl=fr&q=%22boyer+moore%22&btnG=Recherche+Google&meta=lr%3Dlang_fr

ciao...
BruNews, MVP VC++
0
Réponse 2 / 9
cs_kam42 Messages postés 12 Date d'inscription mercredi 5 décembre 2007 Statut Membre Dernière intervention 9 mai 2008
25 déc. 2007 à 15:21
ben en fait, j'en avais trouvé plein sur internet mais c'est que ya des constantes que j'arrive pas à definir
exple: Dans ce code c'est quoi "Asize" ?   "Xsize" ?

source: http://www-igm.univ-mlv.fr/~lecroq/string/node14.html



void preBmBc(char *x, int m, int bmBc[]) {
   int i;

   for (i = 0; i < ASIZE; ++i)
      bmBc[i] = m;
   for (i = 0; i < m - 1; ++i)
      bmBc[x[i]] = m - i - 1;
}

void suffixes(char *x, int m, int *suff) {
   int f, g, i;

   suff[m - 1] = m;
   g = m - 1;
   for (i = m - 2; i >= 0; --i) {
      if (i > g && suff[i + m - 1 - f] < i - g)
         suff[i] = suff[i + m - 1 - f];
      else {
         if (i < g)
            g = i;
         f = i;         while (g >0 && x[g] x[g + m - 1 - f])
            --g;
         suff[i] = f - g;
      }
   }
}

void preBmGs(char *x, int m, int bmGs[]) {
   int i, j, suff[XSIZE];

   suffixes(x, m, suff);

   for (i = 0; i < m; ++i)
      bmGs[i] = m;
   j = 0;
   for (i = m - 1; i >= 0; --i)
      if (suff[i] == i + 1)
         for (; j < m - 1 - i; ++j)
            if (bmGs[j] == m)
               bmGs[j] = m - 1 - i;
   for (i = 0; i <= m - 2; ++i)
      bmGs[m - 1 - suff[i]] = m - 1 - i;
}

void BM(char *x, int m, char *y, int n) {
   int i, j, bmGs[XSIZE], bmBc[ASIZE];

   /* Preprocessing */
   preBmGs(x, m, bmGs);
   preBmBc(x, m, bmBc);

   /* Searching */
   j = 0;
   while (j <= n - m) {
      for (i = m - 1; i >= 0 && x[i] == y[i + j]; --i);
      if (i < 0) {
         OUTPUT(j);
         j += bmGs[0];
      }
      else
         j += MAX(bmGs[i], bmBc[y[i + j]] - m + 1 + i);
   }
}

meric d'avance
0
Réponse 3 / 9
BruNews Messages postés 21040 Date d'inscription jeudi 23 janvier 2003 Statut Modérateur Dernière intervention 21 août 2019
25 déc. 2007 à 15:27
Elles doivent être définies là où tu as pris le listing sinon il ne servirait à rien.

ciao...
BruNews, MVP VC++
0
Réponse 4 / 9
cs_kam42 Messages postés 12 Date d'inscription mercredi 5 décembre 2007 Statut Membre Dernière intervention 9 mai 2008
25 déc. 2007 à 15:30
s'il te plait jette un coup d'oeil sur la page en question ou une autre page d'algorithme boyer moore;  tu verras qu'ils le definissent pas !

c prcke je n'y suis pas arrivé que j'ai posté sur le forum
0

Vous n’avez pas trouvé la réponse que vous recherchez ?

Posez votre question
Réponse 5 / 9
BruNews Messages postés 21040 Date d'inscription jeudi 23 janvier 2003 Statut Modérateur Dernière intervention 21 août 2019
25 déc. 2007 à 15:32
Regarde ici
http://fr.wikipedia.org/wiki/Algorithme_de_Boyer-Moore
code et explications.

ciao...
BruNews, MVP VC++
0
Réponse 6 / 9
cs_kam42 Messages postés 12 Date d'inscription mercredi 5 décembre 2007 Statut Membre Dernière intervention 9 mai 2008
25 déc. 2007 à 15:39
En fait y'a un site internet où le Asize etait 256 et le Xsize 100, donc j'ai fait ça
mais quand la longueur de mon motif est inferieure à 3 caracteres; le debug me signale l'erreur suivante:

stack around the variable " tablesuffixes "was corrupted 

est ce  quevous savez d'ou peut venir cette erreur svp ?  j'ai passé des jours à tester en mettant des "cout" entre les instructions mais j'arive pas à trouver.

code:
void calculersauts(string motif, int tablesauts[])
{
int longueurmotif=motif.length();
for(int i=0; i<256; i++)
  tablesauts[i]=longueurmotif;
for(int i=0; i<longueurmotif-1; i++)
  tablesauts[motif[i]]=longueurmotif-i-1;
}
void calculersuffixes(string motif, int suffixes[])
{
 int longueurmotif=motif.length();
 int iprec,index;
 suffixes[longueurmotif-1]=longueurmotif;
 index=longueurmotif-1;
 //cout<<"iprec"<=0;i--)
 {
  if(i>index && suffixes[i+longueurmotif-1-iprec]=0 && motif[index]==motif[index+longueurmotif-1-iprec])
    index--;
   suffixes[i]=iprec-index;
  }
  cout<<"suffixes"<<suffixes[i]<<endl ;
 }
}
void calculertablesuffixes(string motif, int tablesuffixes[])
{


 int suffixes[100];
 int longueurmotif=motif.length();
 calculersuffixes(motif,suffixes);
 for(int i=0;i<longueurmotif;i++){
  tablesuffixes[i]=longueurmotif;
  cout<<"dep"<<tablesuffixes[i]<<endl ;
 }
 int j=0;
 for(int i=longueurmotif-1;i>=-1;i--)
  if(i==-1||suffixes[i]==i+1)
   for(j=0 ; j<longueurmotif-1-i ; j++)
    if(tablesuffixes[j]==longueurmotif)
     tablesuffixes[j]=longueurmotif-1-i;
 for(int i=0; i<=longueurmotif-2;i++){
  tablesuffixes[longueurmotif-1-suffixes[i]]=longueurmotif-1-i;
  cout<<"dernier"<<tablesuffixes[i]<<endl ;
 }
}
int BoyerMoore3(string motif,string texte)
{
 int i ;
 int tablesuffixes[100];
 int tablesauts[256];
 int longueurmotif=motif.length();
 int longueurtexte=texte.length();
 calculersauts(motif,tablesauts);
 calculertablesuffixes(motif,tablesuffixes);
 int j=0;
 while(j<=longueurtexte-longueurmotif)
 {
  for(i=longueurmotif-1;i>=0 && motif[i]==texte[i+j];i--);
  cout<<i ;
  if(i<0)
  {
   return j;
   //j+=tablesuffixes[0] ;
  }
  else
  {
   unsigned char carac=texte[i+j];
   cout<<"carac"<<carac ;
   j += max(tablesuffixes[i],(tablesauts[carac]-longueurmotif+1+i));
   cout<<j<<endl ; ;
   
  }
 }
 return -1;
}

merci
0
Réponse 7 / 9
BruNews Messages postés 21040 Date d'inscription jeudi 23 janvier 2003 Statut Modérateur Dernière intervention 21 août 2019
25 déc. 2007 à 15:55
Voila bien des jours perdus à rien, je n'avais pas fait gaffe que tu employais du 'string'.
Boyer Moore est le sujet de bouquins entiers d'optimisation et on s'en va traiter cela avec ce qui en est le contraire.
Montez dans ma 2cv que je vous explique le pilotage F1, voila ce que je vois au dessus, non merci.

ciao...
BruNews, MVP VC++
0
Réponse 8 / 9
cs_kam42 Messages postés 12 Date d'inscription mercredi 5 décembre 2007 Statut Membre Dernière intervention 9 mai 2008
25 déc. 2007 à 16:00
Mais le string peut avoir quel effet ? la plus part des sites internet font cet algorithme avec du string ! tu penses qu'ne faisant du char* ça va marcher ?
ok, je vais le faire et je te tiens au courant tout de suite !
0
Réponse 9 / 9
BruNews Messages postés 21040 Date d'inscription jeudi 23 janvier 2003 Statut Modérateur Dernière intervention 21 août 2019
25 déc. 2007 à 16:07
Mais le string peut avoir quel effet ?

Un peu de curiosité que diable, décompile et regarde le listing asm produit, tu seras dégouté.

ciao...
BruNews, MVP VC++
0

Discussions similaires

algorithme de Moore Dijktstra
rabalisonelinah -
Renfield -

2 réponses
Rejoignez-nous