Recherche de chaines en prenant compte du wildcard (*) et du ?

Soyez le premier à donner votre avis sur cette source.

Snippet vu 10 589 fois - Téléchargée 33 fois

Contenu du snippet

Permet de faire des recherches de chaines en spécifiant certains passage comme le fait la recherche de fichier ('*.exe' ou 'image?.jpg')

Comportement du Pattern :

| ? Indique qu'il doit y avoir un caractère
| * Indique qu'il doit y avoir au moins 0 caractères
| {? et * sont cumulables. Ex:
| ? -> La chaine doit faire 1 caractère
| ?? -> La chaine doit faire 2 caractères
| ???? -> La chaine doit faire 4 caractères
| etc...
| * -> La chaine sera renvoyée (**, ****, etc. a le meme effect)
| {Ex: a*c -> La chaine commence par 'a' et doit finir par 'c'
| Ex: 'avec' est validé mais pas 'aéré'
| tr**c -> La chaine commence par 'tr' et doit finir par 'c'
| Ex: 'truc' est validé mais pas 'dropec'
| *ien -> La chaine doit finir par 'ien'
| Ex: 'tien', 'amphibien', 'ocuyfsgocien' seront validés
| }
| ?* -> La chaine doit faire au moins 1 caractère
| {Ex: a?*c -> La chaine commence par 'a' et doit finir par 'c' avec au moins 1 caractère entre
| Ex: 'avec' est validé mais pas 'aéré', 'ac' ne le sera pas non plus
| tr?**c -> La chaine commence par 'tr' et doit finir par 'c' avec au moins 1 caractère entre
| Ex: 'truc' est validé mais pas 'dropec' ni 'trc'
| ?*ien -> La chaine doit finir par 'ien' avec au moins 1 caractère avant
| Ex: 'tien', 'amphibien', 'ocuyfsgocien' seront validés mais pas 'ien'
| }
| ??*? -> La chaine doit faire au moins 3 caractères
| ***? -> La chaine doit faire au moins 1 caractère
| etc...
| }

Source / Exemple :


Function MatchSearchPattern(aString, aPattern: PChar): Boolean;
Const
  PATTERNCHAR_SINGLE    = '?';
  PATTERNCHAR_MULTIPLE  = '*';
  PATTERNCHAR_DIFFERENT = '/';
Var
  LastPatCharDiff, Wildcard: Boolean;
  Function PosChr(aString: PChar; aChr: Char): PChar;
  // Recherche aChr dans aString.
  // S'il est trouvé, elle renvoie le PChar de la position de aChr dans aString
  // Si aChr existe pas dans aString alors elle renvoie nil
  Begin
    Result := nil;
    While aString^<>#0 do
    begin
      If aString^=aChr Then
      begin Result := aString; Exit; end;
      inc(aString);
    end;
  End;

Begin
  Result  := False;
  LastPatCharDiff := False;
  While (aPattern^<>#0) and (aString^<>#0) do // Tant que aPattern ou aString n'est pas fini
  begin
    If LastPatCharDiff Then                   // Si le dernier caractère est l'inhibiteur de '?', '*' ou '/' de façon à les prendre comme de simples caractères
    begin                                     // Ceci permet de rechercher des chaines en spécifiant que ces 3 caractères doivent être les mêmes.
      LastPatCharDiff := False;
      If aPattern^<>aString^ Then Exit else inc(aString); // Si les caractères de aPattern et de aString sont pas les même, on sort
    end else Case aPattern^ of
        PATTERNCHAR_SINGLE,
        PATTERNCHAR_MULTIPLE : begin                      // Si le caractère est '*' ou '?'
                                 Wildcard := False;
                                 While aPattern^ in [PATTERNCHAR_SINGLE, PATTERNCHAR_MULTIPLE] do // Recherche de tous les caractères '*' ou '?' jusqu'à ce qu'il n'y en ai plus
                                 begin
                                   If aPattern^=PATTERNCHAR_SINGLE Then // Si c'est '?'
                                   begin
                                     If aString=#0 Then Exit;           // Il doit forcément y avoir un caractère restant et comme c'est pas le cas on sort
                                     inc(aString);
                                   end else Wildcard := True;           // Indication qu'il y avait un '*'
                                   inc(aPattern);
                                 end;
                                 If Wildcard Then                       // S'il y avait une '*'
                                 begin
                                   If aPattern^=#0 Then                 // Fin du aPattern donc l'étoile valide forcément la fin de la chaine et on sort
                                   begin Result := True; Exit; end;
                                   While aString^<>#0 do                // Tant que l'on est pas à la fin de la chaine aString
                                   begin
                                     aString := PosChr(aString, aPattern^);           // Recherche du caractère pointé par aPattern dans aString
                                     If aString=nil Then Exit;                        // S'il n'y en avait pas, on sort
                                     Result := MatchSearchPattern(aString, aPattern); // Passe en validation de la suite de la chaine encore pour être sûr de couvrir tous les cas possibles (Recursivité)
                                     If Result Then Exit else inc(aString);           // Si la chaine a été validée jusqu'au bout dans la récurcivité alors on valide et on sort
                                   end;
                                 end else begin
                                   If (aPattern^=#0) and (aString^<>#0) Then Exit; // Si aPattern est finit et pas la aString alors on sort
                                   dec(aPattern);                                  // Ceci permet de ne pas sauter de caractères
                                 end;
                               end;
        PATTERNCHAR_DIFFERENT: LastPatCharDiff := True;        // Si le caractère est '/'
      else If aPattern^<>aString^ Then Exit else inc(aString); // Si les caractères de aPattern et de aString sont pas les même, on sort
      end;
    inc(aPattern);
  end;
  If (aPattern^=#0) and (aString^=#0) Then Result := True;     // Si l'on est à la fin de aPattern et de aString alros c'est que tous les caractères ont été validés
End;

Conclusion :


J'ai fait du mieux que j'ai pu. J'ai testé avec et sans optimisations, on perd un peu sans optimisations
(pour 3000 fois 160415 caractères avec mon XP2600+ et 512 de ram je fais (pour un test au hazard donc avec des '*' et des '?') du 1400ms environ avec optimisations et sans 1900ms. La même chose en mettant la même chaine en pattern j'atteint 2850ms et sans optimisations 6400ms)
Je la trouve assez rapide et pour améliorer encore la vitesse changer la sous fonction par celle là (en asm) :

Function PosChr(aString: PChar; aChr: Char): PChar;
// Recherche aChr dans aString.
// S'il est trouvé, elle renvoie le PChar de la position de aChr dans aString
// Si aChr existe pas dans aString alors elle renvoie nil
Asm
@Loop:
mov dh,[eax]
cmp dl,dh
je @Out
inc eax
test dh,dh
jne @Loop
xor eax,eax
@Out:
End;

A voir également

Ajouter un commentaire

Commentaires

Messages postés
194
Date d'inscription
dimanche 2 mars 2003
Statut
Membre
Dernière intervention
10 octobre 2006
2
alvaro :
Ton code est plus rapide que le miens, c'est vrai. Mais elle a pas du tout le même comportement que la mienne.
Le fait que j'ai utilisé le '/' me permet de pouvoir me servir de cette fonction autrepart que dans une recherche de fichier, et ça j'en avais besoin.

jerimanea :
Tu as tout a fait compris le principe, mais spécifier un ordre (??* par exemple) n'aurait pas changé beaucoup le code je pense, donc j'ai laissé comme ça :)

Pour la recherche en spécifiant les caractères, j'y ai pensé, et je travaille sur une version quand même plus précise (permet de ne pas spécifier caractères par caractères). J'avais vu une source pascal l'utilisant mais le code m'a pas plus et elle était lente alors je vais refaire la mienne :)

Merci des ces remarques interessantes.
Messages postés
6
Date d'inscription
vendredi 18 avril 2003
Statut
Membre
Dernière intervention
3 mars 2011

Je pense que ce type de recherche évolulée, n'est pas notre objectif. En tout cas pour moi.
Par contre une recherche syntaxique très poussée, est possible avec les expressions régulière du php!

cf (ecrit en php justement)
http://www.commentcamarche.net/php/phpreg.php3

Le php est un langage serveur internet, et je m'etone que vous n'ayez pas trouvé de site permettant une telle recherche syntaxique en ligne.
Messages postés
1
Date d'inscription
dimanche 31 octobre 2004
Statut
Membre
Dernière intervention
31 octobre 2004

Bonjour,
Si je peux me permettre de faire quelques remarques par rapport à votre description (je vous précise que je n'ai pas de pratique en codage) :

-on peut dire que "? " intervient en tant que quantificateur de nombre de caractères

-"*", dans ce que vous avez fait, signifierait plutôt :
-la chaîne a un nombre quelconque de caractères, quand il n'est pas utilisé avec "?"
-la chaîne a un nombre de caractères > ou au nombre de "?", quand il est utilisé avec "?".
> en tous cas, c'est très pertinent d'utiliser la combinaison * et ? .

-pourquoi ne pas définir une structure unique quand le "*" vient en complément de "?"
par exemple, le "?" toujours en 1er, le "*" en second, ce qui donnerait :
?* : la chaîne doit faire au moins 1 caractère
???* : la chaîne doit faire au moins 3 caractères

Je ne vois pas dans votre description les recherches suivantes :

-recherche sur la présence d'un caractère pouvant prendre plusieurs valeurs. Un "?" peut prendre les valeurs a, e, i, o ([aeio])

-recherche sur l'absence d'un caractère pouvant prendre plusieurs valeurs. Un "?" ne doit pas prendre les valeurs m, n ([^ mn])

En fait, je n'invente rien, je me suis simplement référé aux résultats qu'on trouve sur le site suivant :

http://www.montefiore.ulg.ac.be/~bronne/pivot/trucs.html


Cordialement

nb : je ne suis pas développeur, mais je recherchais ces derniers temps un site qui permette de faire de la recherche syntaxique sur un dictionnaire. Et je suis tombé sur Delphi et vos travaux via moteur de recherche.

Veuillez ne pas prendre en compte mon commentaire si vous estimez qu'ils sont déplacés. Vous avez fait du bon travail, et je ne tiens pas à vous en rajouter.
Mais peut-être le trouverez-vous intéressant et souhaiterez-vous en tenir compte.
Messages postés
4297
Date d'inscription
samedi 19 janvier 2002
Statut
Modérateur
Dernière intervention
9 janvier 2013
28
Les 3 formules sont :
- version avec le premier code ci-dessus
- version avec le code ASM
- fonction MatchesMask fournie avec Delphi
Messages postés
194
Date d'inscription
dimanche 2 mars 2003
Statut
Membre
Dernière intervention
10 octobre 2006
2
Je te remercie Delphiprog.

Je voudrai savoir si c'est normal que ma modification soit encore pas appliquée? (ça fait 1h30 maintenant)

Quelle est la 3ème formule que tu veux tester?
Afficher les 10 commentaires

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.