RECHERCHE DE CHAINES EN PRENANT COMPTE DU WILDCARD (*) ET DU ? , Source N°26787

Information sur la source

Catégorie :Texte Niveau : Initié Date de création : 12/10/2004 Date de mise à jour : 16/10/2004 10:48:06 Vu : 7 539

Auteur : Emandhal

Ecrire un message privé

Note :

6,33 / 10

1
2
3
4
5
6
7
8
9
10

Commentaire sur cette source (11)

Ajouter un commentaire et/ou une note

Description

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

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;

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;

Historique

13 octobre 2004 11:57:20 :: Correction d'un commentaire
14 octobre 2004 19:14:15 :: Correction d'un cas particulier oublié :s
15 octobre 2004 10:47:31 :: Modification apparament pas prise en compte, je la refais donc ;)
15 octobre 2004 17:57:36 :: Un "end;" oublié lors de la dernière correction
16 octobre 2004 10:48:07 :: Légère amélioration du code :) (Il faudrait que j'arrete d'y toucher...)

Sources du même auteur

[COMPOSANT] DIGITS, AFFICHAGE DE TEXTE EN ÉCRITURE AVEC DES SEGMENTS (7, 14 ET 16 SEGMENTS)

Toutes les sources de Emandhal

Sources de la même categorie

Toutes les sources de la catégorie Texte

Commentaires

Commentaire de taye78 le 13/10/2004 17:15:05

Très interessant.
Commentaire de MAURICIO le 13/10/2004 19:05:19

J' ai fait la meme fonction mais sans les points d' interrogation. Je regarderai mieux le code demain!
Commentaire de Delphiprog le 14/10/2004 12:39:12 administrateur CS

Delphi fournit, dans l'unité Masks, une fonction très performante qui se nomme MatchesMask et qui remplit la même fonction que le code ci-dessus :
function MatchesMask(const Filename, Mask: string): Boolean
Contrairement à ce que l'on pourrait croire, cette fonction n'est absolument pas réservée au traitement des noms de fichiers.
J'ai déjà eu l'occasion, à plusieurs reprises de parler de cette fonction sur le forum.

Dommage pour Emandhal...mais c'était un bon exercice quand même. ;o)
Commentaire de Emandhal le 14/10/2004 14:45:26

Je ne savais pas pour la fonction de l'unité Masks (J'ai du mal faire mes recherche sur ce sujet).

Je me suis lancé dans une rapide comparaison histoire de savoir si j'ai perdu mon temps (ou pas) et/ou valoriser ma fonction (Oui des fois je cherche les points forts) :)

La fonction MatchesMask permet plus de choses que la mienne, c'est un fait. Il y a quand même un point que j'aimerai soulever : la vitesse
Oui bon je dois passer mon un maniac de la rapidité, mais j'avais besoin de quelquechose de très rapide et là ma fonction surpasse très largement celle fourni par Delphi.

Dans l'aide de Delphi il est bien stipulé en remarque que la function MatchesMask ne s'applique pas forcément qu'au traitement de fichier. La mienne non plus.

Je suis donc assez soulage de ne pas avoir fait ça pour rien. La prochaine fois j'essaierai de mieux chercher au cas où ;o)

Je te remercie Delphiprog pour cette remarque pertinente.
Cet exemple de code que j'ai fait peut servir d'exemple à l'utilisation des PChar et de la récurcivité.

S'il y en a un qui a un code plus performant je ne suis pas contre son étude pour améliorer mon codage :)
Commentaire de Delphiprog le 14/10/2004 15:01:17 administrateur CS

Je précise également que ma remarque n'enlève absolument rien à la qualité de ton code qui est un des meilleurs depuis quelques temps.
Contrairement à ce que j'ai pu lire très récemment, les commentaires facilitent bien la compréhension et la maintenance.
Du travail de pro : 10/10.

Je vais procéder à des tests unitaires (avec Dunit) et je vous tiens au courant des performances respectives des trois formules proposées. Que le meilleur gagne !
Commentaire de Emandhal le 14/10/2004 21:04:28

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?
Commentaire de Delphiprog le 15/10/2004 00:25:32 administrateur CS

Les 3 formules sont :
- version avec le premier code ci-dessus
- version avec le code ASM
- fonction MatchesMask fournie avec Delphi
Commentaire de alvaro le 26/10/2004 03:59:31

Je pense que cette fonction est encore plus rapide que la tiene, je viens de l'adapter d'une fonction que j'ai faite en c. Justement il fallait que je la fasse (très utile), par contre moi je ne m'emmerde pas avec des '/'. Ca allourdit le code (donc la vitesse) et ca ne sert à rien. Pour rechercher  "ale*re?w" ya qu'a utiliser le pattern "ale?re?w"
Si ca peu t'aider.

{**
*     RavageMatch   par alvaro Hermo (alvaro.h@ifrance.com) 26/10/2004
*
* Compare une chaine avec un Pattern pouvant contenir des wilcards ('*' et '?')
* Delphi fournit,  dans l'unité Masks,  la fonction MatchesMask.  Mais elle est
* moins rapide.
*
* PChar            Str        chaine a tester
* PChar            Pattern    chaine de comparaison
*
* Retourne la valeur vrai si la chaine correspond avec le Pattern
*}

function RavageMatch (Str, Pattern: PChar): Boolean;
var
  p1 : PChar;
begin
  p1 := nil;
  result := False;
  while (Str^<>#0) And ((Pattern^='?') Or (Pattern^='*') Or (Pattern^=Str^))
  do  // Le patern correspond à la chaine à tester
  begin
    if Pattern^ <> '*' then
Inc(Pattern) // caractère du pattern validé: passe au caractère suivant.
    else           // chaine du pattern vérouillé sur '*'
      while  (Pattern+1)^ = '*' do Inc(Pattern); // étoiles redondantes zapées
    Inc(Str); // passe au caractère suivant pour la chaine à tester.
    if (Pattern^ ='*') And (Str^ = (Pattern+1)^) then
    begin     // ici possibilité de déverouillage du pattern.
p1 := Pattern;  // sauvegarde de la position de l'étoile
      Inc(Pattern);   // déverouillage du pattern
    end;
    if (nil <> p1) And (Pattern^ <> Str^) And (Pattern^ <> '*')  then
    begin  // déverouillage anticipé => reverouillage à la position p1
      Pattern := p1;  // restauration de la position du Pattern
if Str^ = (Pattern+1)^  // teste le caractère dans la nouvelle position
      then
        Inc(Pattern)  // si le caractere correspond, on redéverouille.
      else
        p1 := Nil;    // sinon, on reste vérouillé.
    end;
  end;
  // à la fin si tout est ok, les deux chaines sont terminées.
  if (Str^ = #0) And (Pattern^=#0) then result := True;
end;
Commentaire de jerimanea le 31/10/2004 14:52:48

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.
Commentaire de alvaro le 31/10/2004 22:40:27

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.
Commentaire de Emandhal le 02/11/2004 12:30:23

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.