Algorithme Boyer Moore

Messages postés
12
Date d'inscription
mercredi 5 décembre 2007
Statut
Membre
Dernière intervention
9 mai 2008
-
Messages postés
21041
Date d'inscription
jeudi 23 janvier 2003
Statut
Modérateur
Dernière intervention
21 août 2019
-
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
A voir également:

9 réponses

Messages postés
21041
Date d'inscription
jeudi 23 janvier 2003
Statut
Modérateur
Dernière intervention
21 août 2019
30
Messages postés
12
Date d'inscription
mercredi 5 décembre 2007
Statut
Membre
Dernière intervention
9 mai 2008

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
Messages postés
21041
Date d'inscription
jeudi 23 janvier 2003
Statut
Modérateur
Dernière intervention
21 août 2019
30
Elles doivent être définies là où tu as pris le listing sinon il ne servirait à rien.

ciao...
BruNews, MVP VC++
Messages postés
12
Date d'inscription
mercredi 5 décembre 2007
Statut
Membre
Dernière intervention
9 mai 2008

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
Messages postés
21041
Date d'inscription
jeudi 23 janvier 2003
Statut
Modérateur
Dernière intervention
21 août 2019
30
Regarde ici
http://fr.wikipedia.org/wiki/Algorithme_de_Boyer-Moore
code et explications.

ciao...
BruNews, MVP VC++
Messages postés
12
Date d'inscription
mercredi 5 décembre 2007
Statut
Membre
Dernière intervention
9 mai 2008

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
Messages postés
21041
Date d'inscription
jeudi 23 janvier 2003
Statut
Modérateur
Dernière intervention
21 août 2019
30
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++
Messages postés
12
Date d'inscription
mercredi 5 décembre 2007
Statut
Membre
Dernière intervention
9 mai 2008

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 !
Messages postés
21041
Date d'inscription
jeudi 23 janvier 2003
Statut
Modérateur
Dernière intervention
21 août 2019
30
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++