IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Delphi Discussion :

Algorithme de Boyer-Moore


Sujet :

Delphi

  1. #21
    Membre éprouvé
    Avatar de Cirec
    Profil pro
    Inscrit en
    Octobre 2010
    Messages
    467
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Octobre 2010
    Messages : 467
    Points : 1 072
    Points
    1 072
    Par défaut
    Bonjour,

    Citation Envoyé par Rekin85

    Vu et pris note, j'ai lu et testé. C'est très bien, ça marche et rapide, très ingénieux. Cela corrobore bien ce que je pensais des recherches d'occurences d'une string dans une string par une fonction faite pour cela.
    oula, je constate que tout cela te perturbe un peu.
    Je vais essayer de réexpliquer plus clairement (d'ailleurs le source a été mis à jour dans cette optique)
    1. il faut faire abstraction du fait que les string ne peuvent contenir que des chaines de caractères
      il faut voir le type string comme un conteneur et du coup on y met ce que l'on veut
      à condition de ne pas essayer de les afficher dans un TMemo
    2. et c'est bien une recherche binaire dans un fichier binaire avec des variables et des méthodes prévues pour les string


    Citation Envoyé par Rekin85

    Petite question : Les octets en question passent par des MemoryStreams, pourquoi avoir besoin de les recopier dans des strings de longueurs allouées (writebuffer...), alors qu'on les a déjà sous la main ? Bien pointés et bien comptés ?
    Ici aussi il y a confusion
    1. oui les données passent par des MemoryStream mais on aurait pu utiliser une autre méthode
      utiliser les pointeurs "Memory^" n'est pas une bonne idée il faudrait laisser les deux MemoryStream ouvert pour faire la recherche
      avec le risque de ne plus pouvoir les fermer en cas de plantage lors de la recherche!!! c'est pas très propre.
    2. oui on les places dans des string de longueurs allouées
      Forcément on veut utiliser des méthodes qui demandent des string en entrée ...
      et si on en fixe la taille avant c'est que ça évite les problèmes de Bytes à valeur 0
      mais surtout c'est la bonne manière de faire ^^
    3. que le contenu soit placé dans une string ou un pointeur (Pointer, PByte, PChar) ou même array of Byte il te faudra allouer l'espace nécessaire
      avant Soit avec SetLength ou avec GetMem mais les string ainsi allouées n'ont pas besoin d'être libérées ... Delphi s'en charge
      contrairement au pointeurs qu'il faut libérer par un FreeMem.
    4. Dernier point: le WriteBuffer sert ni à la comparaison ni à l'affectation mais uniquement à afficher l'image trouvé
      ceci prouve que les données binaires qui transitent par des string ne sont pas altérées et restent utilisable.


    ensuite comme dit plus haut la source est mise à jour j'y ai ajouté des sons toujours dans des string mais les données sont stockés avec MoveMemory afin de varier les exemples d'utilisation
    avec MoveMemory on fait un déplacement d'octets d'un bloc ...
    pour bien montrer que même si on utilise une variable de type string on la traite comme un pointeur sur Byte

    Enfin le reste est dans le code et j'espère que c'est un peu plus claire cette fois.


    @Gilbert Geyer
    je m'attendais à ce résultat
    mais ce n'est pas directement CompareMem qui est en cause
    tout autre procédure à sa place (aussi rapide qu'elle soit) aurait donnée le même résultat
    c'est l'appel à une méthode externe qui est très couteux en temps et là dessus vient s'ajouter le temps d'exécution de la méthode !!

    Quand les performances sont importantes il faut supprimer, autant que possible, les appels aux méthodes extérieurs ... les ré-incorporer au code
    et c'est aussi valable pour les méthodes imbriquées
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
     
    function gourmande(const x, y : string): string;
      function teste(s1, s2: string): Boolean;
      begin
        Result := S1 = S2;
      end;
    begin
     
    ...
      if teste (x, y) then
     
    end;
    ca aussi ça plombe les résultats
    il faudrait faire:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
     
    function gourmande(const x, y : string): string;
    begin
     
    ...
      if S1 = S2 then
     
    end;
    Forcément il n'y a pas que ça ... l'optimisation de code est un vaste sujet et un gain de temps tient parfois à pas grand chose ...

    Cordialement,
    @+ Cirec

  2. #22
    Modérateur

    Homme Profil pro
    Ingénieur retraité
    Inscrit en
    Octobre 2005
    Messages
    2 396
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Rhône (Rhône Alpes)

    Informations professionnelles :
    Activité : Ingénieur retraité

    Informations forums :
    Inscription : Octobre 2005
    Messages : 2 396
    Points : 3 263
    Points
    3 263
    Par défaut
    Re-salut,

    Cirec : je m'attendais à ce résultat
    Je n'en doute pas sinon tu ne l'aurais pas suggéré.

    mais ce n'est pas directement CompareMem qui est en cause
    tout autre procédure à sa place (aussi rapide qu'elle soit) aurait donnée le même résultat
    c'est l'appel à une méthode externe qui est très couteux en temps et là dessus vient s'ajouter le temps d'exécution de la méthode !!
    Quand les performances sont importantes il faut supprimer, autant que possible, les appels aux méthodes extérieurs ... les ré-incorporer au code
    et c'est aussi valable pour les méthodes imbriquées
    OK, merci, c'est bon à savoir. Mais dans la pratique on ne peut pas ou ne souhaite pas toujours rapatrier dans le code toutes les routines distantes qui sont planquées dans les rubriques citées dans le uses
    Et puis il y a les cas où l'on ne peut pas accéder aux *.pas avec certaines versions de Delphi livrées uniquement avec des *.dcu
    Par contre ça reste au moins valable pou les méthodes externes qu'on est susceptible de créer soi-même.

    Forcément il n'y a pas que ça ... l'optimisation de code est un vaste sujet et un gain de temps tient parfois à pas grand chose ...
    Il est d'autant plus vaste qu'avec Delphi on peut généralement répondre à un besoin de "36" façon différemment codées et différentes en temps d'exécution,
    ce qui complique le schmillblik en multipliant les tests comparatifs par "36".
    Mais ça explique aussi pourquoi il existe tant d'applications professionnelles non ou peu optimisées... (faut livrer au plus vite au client)

    je ne peux que vous conseiller l'excellent tuto de Caribensila sur le sujet
    Vu, merci beaucoup.

    Cordialement, et à +.
    N'oubliez pas de consulter les FAQ Delphi et les cours et tutoriels Delphi

  3. #23
    Membre éprouvé
    Avatar de Cirec
    Profil pro
    Inscrit en
    Octobre 2010
    Messages
    467
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Octobre 2010
    Messages : 467
    Points : 1 072
    Points
    1 072
    Par défaut
    re,
    Citation Envoyé par Gilbert Geyer
    OK, merci, c'est bon à savoir. Mais dans la pratique on ne peut pas ou ne souhaite pas toujours rapatrier dans le code toutes les routines distantes qui sont planquées dans les rubriques citées dans le uses
    Et puis il y a les cas où l'on ne peut pas accéder aux *.pas avec certaines versions de Delphi livrées uniquement avec des *.dcu
    Par contre ça reste au moins valable pou les méthodes externes qu'on est susceptible de créer soi-même.
    Attention je crois que je me suis fait mal comprendre !!!
    quand je parle de rapatrier les méthodes externes je ne pensais pas recopier les procédures en question plus près du code qui l'utilise.
    Mais de faire ce que tu as fait avec comparemem ... c'est à dire en lieu et place de l'appel à CompareMem tu reproduis par code le comportement de CompareMem. Donc pas besoin d'avoir les sources
    Le mot rapatrier n'est meilleur choix dans ce contexte

    c'est pourquoi j'avais choisi ré-incorporer ce qui sous-entend la ré-écriture de la méthode

    Mais tout ceci n'est valable que pour des routines très gourmandes en temps ou susceptibles d'être appelées
    un grand nombre de fois consécutivement.


    Pour toutes les autres ça n'a aucun intérêt


    Cordialement,
    @+ Cirec

  4. #24
    Modérateur

    Homme Profil pro
    Ingénieur retraité
    Inscrit en
    Octobre 2005
    Messages
    2 396
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Rhône (Rhône Alpes)

    Informations professionnelles :
    Activité : Ingénieur retraité

    Informations forums :
    Inscription : Octobre 2005
    Messages : 2 396
    Points : 3 263
    Points
    3 263
    Par défaut
    Re-salut,

    Cirec : Attention je crois que je me suis fait mal comprendre !!!
    quand je parle de rapatrier les méthodes externes je ne pensais pas recopier les procédures en question plus près du code qui l'utilise.
    Mais de faire ce que tu as fait avec comparemem ... c'est à dire en lieu et place de l'appel à CompareMem tu reproduis par code le comportement de CompareMem. Donc pas besoin d'avoir les sources
    Le mot rapatrier n'est meilleur choix dans ce contexte c'est pourquoi j'avais choisi ré-incorporer ce qui sous-entend la ré-écriture de la méthode
    OK, mais pour reproduire par code le comportement d'une routine dont on n'a pas les sources ce n'est pas toujours évident.
    Pour le cas présent c'était assez facile, mais pour d'autres ça peut être la galère...

    Mais tout ceci n'est valable que pour des routines très gourmandes en temps ou susceptibles d'être appelées un grand nombre de fois consécutivement. Pour toutes les autres ça n'a aucun intérêt
    Absolument d'accord...

    Cordialement, et à +.
    N'oubliez pas de consulter les FAQ Delphi et les cours et tutoriels Delphi

  5. #25
    Membre actif

    Homme Profil pro
    Inscrit en
    Mars 2009
    Messages
    128
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Vendée (Pays de la Loire)

    Informations forums :
    Inscription : Mars 2009
    Messages : 128
    Points : 203
    Points
    203
    Par défaut
    Bonsoir à tous

    Bien, je me retire de cette discussion qui ne me mènera plus à ce que j'avais demandé : savoir si ma dll tournait bien.

    Une solution est une solution, pour avoir écrit en partenariat avec Gilbert Geyer tout un ensemble de routines de calculs sur très grands entiers contenus dans des strings Delphi, je crois très bien savoir ce que l'on peut faire avec.

    Je souhaite à ShaïLeTroll de réussir parfaitement dans sa tentative d'implémentation du Boyer-Moore.

  6. #26
    Modérateur

    Homme Profil pro
    Ingénieur retraité
    Inscrit en
    Octobre 2005
    Messages
    2 396
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Rhône (Rhône Alpes)

    Informations professionnelles :
    Activité : Ingénieur retraité

    Informations forums :
    Inscription : Octobre 2005
    Messages : 2 396
    Points : 3 263
    Points
    3 263
    Par défaut
    Bonjour,


    Rekin85 : Bien, je me retire de cette discussion qui ne me mènera plus à ce que j'avais demandé : savoir si ma dll tournait bien.
    Dommage car le sujet est passionnant...

    Entre-temps j'ai créé la routine suivante BMH_PosEX(...) qui bénéficie à la fois des performances du BMHPascalNaif (Recherche de Mot long ou Phrase longue) et de celles de PosEX (Recherche de Mot court) :
    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
    type tSkip2 = array[char] of longWord;
    var Skip2: tSkip2;
     
    procedure InitSkip2(const Mot: string);
    var LM, k: integer; Cara: char;
    begin
      LM := Length(Mot);
      for Cara := low(Char) to high(Char) do Skip2[Cara] := LM;
      for k := 1 to LM - 1 do Skip2[Mot[k]] := LM - k;
    end;
     
    function BMH_PosEX(const Mot, Texte: AnsiString; var Depuis: integer): integer;
    // Utilisation de PosEx à la façon de Boyer-Moore-Horspool
    const Seuil: integer = 18;
    var it, ik, LM, LM1, LT, Po, PoP: integer;
    begin
      Result := 0; LM := Length(Mot); LT := length(Texte);
      if (LM = 0) or (LT = 0) then EXIT;
      if LM < Seuil then begin // Appel direct de PosEx pour la recherche d'un Mot court
        if Depuis < 1 then Depuis := 1;
        Result := PosEx(Mot, Texte, Depuis);
        EXIT;
      end;
      // Cas des recherches d'un Mot long avec Boyer-Moore :
      if (LM >= Seuil) and (Depuis = 1) then Depuis := 0;
      ik := Depuis + LM; LM1 := LM - 1;
      while (ik <= LT) do begin
        it := ik;
        if (Texte[it] = Mot[LM]) then begin // Appel de PosEx uniquement si Boyer-Moore pense que ça vaut le coup dans cette position
          PoP := it - LM1;
          Po := PosEx(Mot, Texte, PoP);
          if Po > 0 then begin Result := Po; Depuis := Po + LM; EXIT; end;
        end;
        Inc(ik, skip2[Texte[ik]]);
      end;
      Result := 0; Depuis := 0;
    end;
    Pour l'utiliser :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
      GTC := GetTickCount; InitSkip2(Mot); Count := 0;
     
      for i := 1 to nbTours do begin
        Depuis := 1;
        Po := BMH_PosEX(Mot, Texte, Depuis);
        while Po > 0 do begin
          inc(Count);
          Depuis := Po + LM + 1;
          if Depuis >= LT then break;
          Po := BMH_PosEX(Mot, Texte, Depuis);
        end;
      end;
      Trace(Format('- Avec %s => Trouvé : %.0n  fois, Mis : %.0n  ms', ['BMH_PosEX (Case Sensitive)',
        Count / 1, (GetTickCount - GTC) / 1]));
    Résultats de tests comparatifs :

    A) Pour 100 000 Recherches de Mot de 175 caractères aléatoires dans Texte de 97 344 caractères aléatoires et Mot présent 16 fois dans chaque texte

    - Avec StrUtils.PosEx ASM version => Trouvé : 1 600 000 fois, Mis : 1 934 ms

    - Avec BMHPascalNaif (Case Sensitive) => Trouvé : 1 600 000 fois, Mis : 437 ms

    - Avec BMH_PosEX (Case Sensitive) => Trouvé : 1 600 000 fois, Mis : 312 ms

    - Avec PosBM_KR => Trouvé : 1 600 000 fois, Mis : 530 ms

    - Avec BMHSearchBinaryInBinary => Trouvé : 1 600 000 fois, Mis : 436 ms

    B) Pour 1 000 000 Recherches de Mot de 510 caractères aléatoires dans Texte de 15 300 caractères aléatoires et Mot présent 10 fois dans chaque texte

    - Avec StrUtils.PosEx ASM version => Trouvé : 10 000 000 fois, Mis : 3 541 ms

    - Avec BMHPascalNaif (Case Sensitive) => Trouvé : 10 000 000 fois, Mis : 2 902 ms

    - Avec BMH_PosEX (Case Sensitive) => Trouvé : 10 000 000 fois, Mis : 1 466 ms

    - Avec PosBM_KR => Trouvé : 10 000 000 fois, Mis : 2 949 ms

    - Avec BMHSearchBinaryInBinary => Trouvé : 10 000 000 fois, Mis : 2 917 ms

    C) Pour 10 000 Recherches de Mot de 8 caractères 'MOTFINAL' dans Texte de ZOLA de 1 048 838 caractères et Mot présent 1 fois à la fin du texte

    - Avec StrUtils.PosEx ASM version => Trouvé : 10 000 fois, Mis : 2 137 ms

    - Avec BMHPascalNaif (Case Sensitive) => Trouvé : 10 000 fois, Mis : 4 087 ms

    - Avec BMH_PosEX (Case Sensitive) => Trouvé : 10 000 fois, Mis : 2 106 ms

    - Avec BMHSearchBinaryInBinary => Trouvé : 10 000 fois, Mis : 4 103 ms

    En fait, si BMH_PosEX arrive en tête dans les 3 cas (Mot long ou court) c'est uniquement parce que BMH_PosEX n'appelle PosEx que dans les positions où le Boyer-Moore suspecte la présence du Mot grâce à la détection dans le Texte
    du Chr Terminal du Mot.
    En fait ce n'est peut-être pas "uniquement" pour cette raison, car comme BMH_PosEX utilise PosEX comme routine externe il se trouve que j'évite le handicap signalé par Cirec à propos de CompareMem tout simplement à cause du fait que j'utilise D6 (qui ne dispose pas de PosEX) en conséquence de quoi ma PosEX est logée dans une unit de l'application.
    Mais en cas de besoin similaire PosEX peut être récupérée dans mon message n°#20

    Cordialement, et à +.
    N'oubliez pas de consulter les FAQ Delphi et les cours et tutoriels Delphi

  7. #27
    Expert éminent sénior
    Avatar de ShaiLeTroll
    Homme Profil pro
    Développeur C++\Delphi
    Inscrit en
    Juillet 2006
    Messages
    13 429
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 42
    Localisation : France, Seine Saint Denis (Île de France)

    Informations professionnelles :
    Activité : Développeur C++\Delphi
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Juillet 2006
    Messages : 13 429
    Points : 24 794
    Points
    24 794
    Par défaut
    Citation Envoyé par Rekin85 Voir le message
    Bien, je me retire de cette discussion qui ne me mènera plus à ce que j'avais demandé : savoir si ma dll tournait bien.

    N'as-tu pas eu la réponse dès le début par les 1er tests comparatifs de Gilbert Geyer sous Delphi 6 ?!
    Avec le mien, cela fonctionne en XE2 Pro sur Win Seven

    Normalement, je ne test JAMAIS un binaire compilé, on ne sait jamais ce qu'il y a dedans !
    Mais je fais un effort, j'espère que cela t'encouragera à fournir le code !


    J'ai juste forcé AnsiString au lieu de string et AnsiChar au lieu de Chr dans le code d'appel du sujet d'ouverture de la discussion

    Memo1
    Texte : YTPON...WVXM

    Mot : YTPON...OPFR

    Mot de 400 Chr
    Texte de 14200 Chr
    pour 100000 tours :

    10 occurences trouvées en 749 ms
    Tu peux donc marquer puisque tu as à la réponse en Delphi

    Si tu veux avoir une assistance sur l'intégration et le bon fonctionnement avec d'autres langages,
    il faut aller sur les forums appropriés.
    N'ayant plus C++Builder, je ne peux pas donc pas essayer d'autres langages.

    Installe Visual Studio Express, c'est gratuit et intègre du C++, du C# ...
    Cela me semble un outil pratique pour tester !
    Utilise même une machine virtuelle comme VirtualBox pour isoler ton test de ton installation Delphi


    Citation Envoyé par Rekin85 Voir le message
    Je souhaite à ShaïLeTroll de réussir parfaitement dans sa tentative d'implémentation du Boyer-Moore.
    Merci !
    J'ai tant de chose plus urgente à faire avant
    Aide via F1 - FAQ - Guide du développeur Delphi devant un problème - Pensez-y !
    Attention Troll Méchant !
    "Quand un homme a faim, mieux vaut lui apprendre à pêcher que de lui donner un poisson" Confucius
    Mieux vaut se taire et paraître idiot, Que l'ouvrir et de le confirmer !
    L'ignorance n'excuse pas la médiocrité !

    L'expérience, c'est le nom que chacun donne à ses erreurs. (Oscar Wilde)
    Il faut avoir le courage de se tromper et d'apprendre de ses erreurs

  8. #28
    Membre actif

    Homme Profil pro
    Inscrit en
    Mars 2009
    Messages
    128
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Vendée (Pays de la Loire)

    Informations forums :
    Inscription : Mars 2009
    Messages : 128
    Points : 203
    Points
    203
    Par défaut
    Merci beaucoup Shai, sachant que cela venait de moi (Kr85) , le binaire n'aurait ps dû te faire peur. Mais je comprends ta préoccupation. Donc ça tourne... sous Seven avec XE2 et bien je suis plus que satisfait. J'ai donné le code plus haut, libre à tous ceux qui voudraient l'utiliser de s'en servir.

    Maintenant, si je marque résolu, je risque de détourner d'éventuels amateurs et faire cesser les évolutions des codes proposés par les développements que cette discussion a déclenchés...

    Merci encore

  9. #29
    Expert éminent sénior
    Avatar de ShaiLeTroll
    Homme Profil pro
    Développeur C++\Delphi
    Inscrit en
    Juillet 2006
    Messages
    13 429
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 42
    Localisation : France, Seine Saint Denis (Île de France)

    Informations professionnelles :
    Activité : Développeur C++\Delphi
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Juillet 2006
    Messages : 13 429
    Points : 24 794
    Points
    24 794
    Par défaut
    Citation Envoyé par Rekin85 Voir le message
    Merci beaucoup Shai, sachant que cela venait de moi (Kr85) , le binaire n'aurait ps dû te faire peur. Mais je comprends ta préoccupation.
    C'est bien pour cela que je l'ai fait

    Citation Envoyé par Rekin85 Voir le message
    J'ai donné le code plus haut, libre à tous ceux qui voudraient l'utiliser de s'en servir.

    Je ne l'avais pas vu celui là !
    Je cherchais un code Delphi, je suis passé à côté

    Ah je reconnais effectivement ton style de l'ASM !
    Quand j'aligne 5 mnémoniques, je suis déjà fier, mais ton code impose le respect


    Citation Envoyé par Rekin85 Voir le message
    Maintenant, si je marque résolu, je risque de détourner d'éventuels amateurs et faire cesser les évolutions des codes proposés par les développements que cette discussion a déclenchés....
    Je ne suis pas sûr que l'on aura plus de participants mais oui laissons une chance aux curieux
    Aide via F1 - FAQ - Guide du développeur Delphi devant un problème - Pensez-y !
    Attention Troll Méchant !
    "Quand un homme a faim, mieux vaut lui apprendre à pêcher que de lui donner un poisson" Confucius
    Mieux vaut se taire et paraître idiot, Que l'ouvrir et de le confirmer !
    L'ignorance n'excuse pas la médiocrité !

    L'expérience, c'est le nom que chacun donne à ses erreurs. (Oscar Wilde)
    Il faut avoir le courage de se tromper et d'apprendre de ses erreurs

  10. #30
    Membre éprouvé
    Avatar de Cirec
    Profil pro
    Inscrit en
    Octobre 2010
    Messages
    467
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Octobre 2010
    Messages : 467
    Points : 1 072
    Points
    1 072
    Par défaut
    re,

    @Rekin85: tout comme shail j'ai pour habitude de ne jamais tester un code déjà compilé ...
    et tout comme Shail je suis passé à coté du code de la DLL

    Voici donc les résultats sous XP pro sp3:

    Code D'appel compilé sous D7pro & Dll compilé sous D7pro
    Mot de 400 Chr
    Texte de 14200 Chr
    pour 100000 tours : 10 occurences trouvées en 1391 ms

    Code D'appel compilé sous D7pro & Dll compilé sous D2009pro
    Mot de 400 Chr
    Texte de 14200 Chr
    pour 100000 tours : 10 occurences trouvées en 1703 ms

    Code D'appel compilé sous D2009pro & Dll compilé sous D2009pro
    Mot de 400 Chr
    Texte de 14200 Chr
    pour 100000 tours : 10 occurences trouvées en 1453 ms

    Code D'appel compilé sous D2009pro & Dll compilé sous D7pro
    Mot de 400 Chr
    Texte de 14200 Chr
    pour 100000 tours : 10 occurences trouvées en 1312 ms

    Bien sur j'ai du faire les mêmes modifications que Shail sur le code d'appel pour compiler avec D2009 qui est unicode

    Donc tout fonctionne parfaitement et la DLL compile sur les deux versions de Delphi sans aucune modification


    Cordialement,
    @+ Cirec

  11. #31
    Membre actif

    Homme Profil pro
    Inscrit en
    Mars 2009
    Messages
    128
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Vendée (Pays de la Loire)

    Informations forums :
    Inscription : Mars 2009
    Messages : 128
    Points : 203
    Points
    203
    Par défaut
    Merci beaucoup Cirec pour ces tests.

    Je suis rassuré : ça tourne comme il faut ailleurs que sur mon petit portable (Xp, pentium M).

    Mais, " Cent fois sur le métier remettez votre ouvrage" , de fil en aiguille je me suis rendu compte que mon algorithme de Boyer-Moore qui utilisait deux sous-routines pour faire ses comparaisons : une en byte à byte et une en dword à dword avec un seuil de basculement de l'une à l'autre aux alentours de 512; n'en avait finalement pas besoin car le procédé en dwords est bien obligé aussi de faire du byte à byte. J'ai donc remanié et ainsi allégé mon code :

    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
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    167
    168
    169
    170
    171
    172
    173
    174
    175
    176
    177
    178
    179
    180
    181
    182
    183
    184
    185
    186
    187
    188
    189
    190
    191
    library PosBM;
     
    uses
      windows;
     
    // Routines et variables internes **********************************************
     
    type  TSkip = array[0..255] of longword;
    var   SkipBuf: TSkip;           // Table des sauts du Boyer-Moore
          NbDw,NbBy : longWord;     // Répartition Dwords et bytes
    const Seuil : longword = 4;     // Basculement Bytes <-> Dwords
     
    // Compare SStr à Str depuis la position de ecx dans Str
    // comparaisons faites en dwords et/ou bytes avec NbDw et NbBy
    // Entrée :
    // 1 - esi pointe sur la Str et edi sur la SStr
    // 2 - ecx contient l'indice de la borne
    // 3 - edx contient la longueur de la collection SStr
    // Retour :
    // 1 - CarryFlag à 1 si occurence trouvée et à 0 sinon
    // 2 - ecx renvoie la position du byte d'arrêt sur Str
    procedure CompBM_BD; register;
    asm
       push    edi
       push    esi            // adresse départ Str
       add     esi,ecx        // placer esi sur la borne de départ
       mov     ecx,edx        // edx garde length(SStr)
       // comparaison descendante
       add     esi,ecx        // pointer fin Str + 1
       add     edi,ecx        // pointer fin SStr + 1
       // Byte à Byte
       @Bytes:
       mov     ecx,NbBy
       test    ecx,ecx
       jz      @DWords
       @RBytes:
         dec     esi          // se placer sur dernier byte
         dec     edi
         mov     al,byte ptr[edi]
         cmp     al,byte ptr[esi]
         jne     @FinNon      // byte discordant
         dec     ecx
         jnz     @Rbytes
       // DWord à DWord
       @DWords:
       mov     ecx,NbDw       // combien de DWords entiers ?
       test    ecx,ecx
       jz      @FinOui        // aucun
       @RDWords:
         sub     esi,$4       // se placer dword en dessous
         sub     edi,$4
         mov     eax,DWord ptr[edi]
         cmp     eax,DWord ptr[esi]
         jne     @ByteD       // si pas égaux, aller au byte défaillant
         dec     ecx
         jnz     @RDWords
       jmp     @FinOui        // tous DWords bons
       @ByteD:                // cas d'un Dword défaillant
       mov     ecx,$4         // rattraper le décalage
       add     esi,ecx        // et chercher le byte défaillant
       @RByteD:
         dec     esi
         cmp     al,byte ptr[esi]
         jne     @FinNon
         shr     eax,$8
         dec     ecx
         jnz     @RByteD
       // Retours de routine
       @FinNon:               // retour false
       xor     eax,eax
       jmp     @Fin
       @FinOui:               // retour true
       mov     eax,$1
       @Fin:
       mov     ecx,esi
       pop     esi            // remise adresse Départ
       sub     ecx,esi        // calcul place du byte d'arrivée
       pop     edi
       shr     eax,$1          // positionnement du carry flag
    end;
     
    // Routines exportables ********************************************************
     
    // initialise le seuil de basculement Bytes <=> DWords
    procedure InitSeuil(Nb : longword); Stdcall;
    asm
      mov     eax,[ebp]+$08
      mov     Seuil,eax
    end;
     
    // Initialise le tableau Skip des sauts du Boyer-Moore
    // en fonction de la collection à rechercher
    procedure InitSkipBuf(SStr : Pointer; LenSStr: longword); StdCall;
    asm
      push    edi
      lea     edi,[SkipBuf]           // edi pointe SkipBuf
      push    esi
      mov     esi,[ebp]+$08           // esi pointe SStr
      mov     eax,[ebp]+$0C           // eax = len(SStr)
      // FillInt
      cld                             // remplissage en montant
      mov     ecx,$100                // 256 itérations
      rep     stosd                   // remplissage total avec lenSub
      sub     edi,$400                // remise edi au début de SkipBuf
      // boucle des sauts
      mov     ecx,eax                 // eax contient toujours len SStr
      @RSkip:
              dec    ecx
              jle    @Fin
              xor    eax,eax
              mov    al,byte ptr[esi]   // al contient le byte
              shl    eax,$2             // valeur du byte x 4
              mov    DWord ptr[edi+eax],ecx
              inc    esi
              jmp    @RSkip
      @Fin:
      pop     esi
      pop     edi
    end;
     
    // Algorithme de Boyer-Moore pour la recherche d'occurence
    // d'une collection de bytes dans une autre collection de bytes plus grande
    // L'occurence peut avoir une capacité de plus de 256 octets
    // Retourne le rang de la 1ère occurence trouvée à partir de Depuis
    // Retourne 0 si aucune trouvée
    // Routine orientée recherche par Bytes si LSStr<4 et DWords Si >5
    function PosBM_KR(SStr, Str : Pointer; LSStr, LStr, Depuis :longWord): longword; stdcall;
    var  PosMax,Depart : longWord;
    asm
      push     ebx
      lea      ebx,[SkipBuf]           // ebx pointe la Table de sauts
      push     edi
      mov      edi,[ebp]+$08           // edi pointe SStr
      push     esi
      mov      esi,[ebp]+$0C           // esi pointe Str
      mov      edx,[ebp]+$10           // edx garde la longueur de SStr
      test     edx,edx                 // SStr vide ?
      jz       @FinNulle
      mov      eax,[ebp]+$14
      sub      eax,edx
      jl       @FinNulle               // si SStr>Str
      mov      PosMax,eax              // AMax = Borne supérieure extrême
      mov      ecx,[ebp]+$18
      dec      ecx                     // ecx = variable Depuis
      cmp      edx,Seuil               // seuil basculement bb ww
      ja       @DW                     // chargement des variables globales
      mov      NbBy,edx
      mov      NbDw,$0
      jmp      @While
      @DW:                             // calculs des itérations
      mov      eax,edx
      and      eax,$3
      mov      NbBy,eax                // pour les bytes
      mov      eax,edx
      shr      eax,$2
      mov      NbDw,eax                // pour les Dwords
      @While:                          // algorithme de recherche Boyer-Moore
        mov      Depart,ecx
        cmp      ecx,PosMax
        ja       @FinNulle               // Fin de Str
        call     CompBM_BD               // ecx = rang occurence si CF=1
        jc       @FinBonne               // CF indicateur oui - non
        xor      eax,eax                 // pas trouvée, on saute en BM
        mov      al,byte ptr[esi]+ecx    // byte défaillant
        shl      eax,$2                  // indice x 4 pour DWord
        mov      ecx,DWord ptr[ebx]+eax  // décalage par SkipBuf[byte d'arrêt]
        add      ecx,Depart
        jmp      @While
      @FinNulle:
      xor      eax,eax
      jmp      @Fin
      @FinBonne:
      inc      ecx
      mov      eax,ecx                 // retour du rang de l'occurence trouvée
      @Fin:
      pop      esi
      pop      edi
      pop      ebx
    end;
     
    // *****************************************************************************
     
    exports
          InitSeuil,
          InitSkipBuf,
          PosBM_KR;
     
    // *****************************************************************************
     
    begin
    end.
    Une petite routine exportable (initSeuil) permet maintenant de fixer justement ce seuil de basculement.

    Mon but étant de faire une implémentation de l'algorithme de Boyer-Moore, j'y suis parvenu. Maintenant, cette implémentation si elle se révèle intéressante en vélocité pour les grandes et très grandes occurences, elle ne le sera que beaucoup moins pour les très petites... Dans ce cas il serait préférable d'utiliser ce qu'il y a sous la main en Delphi (PosEx) ou de faire une entrée de choix entre les deux selon la longueur de l'occurence à rechercher.

  12. #32
    Modérateur

    Homme Profil pro
    Ingénieur retraité
    Inscrit en
    Octobre 2005
    Messages
    2 396
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Rhône (Rhône Alpes)

    Informations professionnelles :
    Activité : Ingénieur retraité

    Informations forums :
    Inscription : Octobre 2005
    Messages : 2 396
    Points : 3 263
    Points
    3 263
    Par défaut
    Bonjour,

    Rekin85 : Maintenant, cette implémentation si elle se révèle intéressante en vélocité pour les grandes et très grandes occurences, elle ne le sera que beaucoup moins pour les très petites... Dans ce cas il serait préférable d'utiliser ce qu'il y a sous la main en Delphi (PosEx) ou de faire une entrée de choix entre les deux selon la longueur de l'occurence à rechercher.
    C'est vraiment dommage de ne pas avoir encapsulé une PosEx dans le code de la DLL de sorte que soit dans la PosBM_KR que le choix se fasse entre les deux suivant que la longueur de l'occurrence à rechercher est faible ou grande.
    Car après tout l'objectif de la manœuvre est de remédier aux points faibles des deux et de façon à bénéficier des points forts des deux.
    Après tout cela ne mangerait que peu de place dans la DLL et éviterait d'avoir à se souvenir que l'une rame pour la recherche de Mots courts et que l'autre rame pour les Mots et les Phrases longues.
    Et puis concernant PosEx vu que l'appel à Boyer-Moore constitue une correction du défaut de jeunesse de PosEx , l'encapsuler dans la DLL ne constituerait donc aucunement un plagiat.
    Et au moins cela donnerait une routine performante en speed quelle que soit la longueur du Mot à chercher.

    Cordialement, et à +.
    N'oubliez pas de consulter les FAQ Delphi et les cours et tutoriels Delphi

  13. #33
    Membre actif

    Homme Profil pro
    Inscrit en
    Mars 2009
    Messages
    128
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Vendée (Pays de la Loire)

    Informations forums :
    Inscription : Mars 2009
    Messages : 128
    Points : 203
    Points
    203
    Par défaut
    Gilbert : C'est vraiment dommage de ne pas avoir encapsulé une PosEx dans le code de la DLL de sorte que soit dans la PosBM_KR que le choix se fasse entre les deux suivant que la longueur de l'occurrence à rechercher est faible ou grande.
    Car après tout l'objectif de la manœuvre est de remédier aux points faibles des deux et de façon à bénéficier des points forts des deux.
    Mon objectif personnel à moi était d'implémenter un Boyer-Moore. C'est fait. Remédier aux points faibles des deux procédés, c'est un autre challenge. Et incorporer PosEx() dans la dll quoi qu'on en dise, serait quand même un plagiat, ou tout au moins un détournement d'une routine de Delphi... Je préfèrerais de beaucoup créer Ma routine. Question de principe.

    Je vais donc réfléchir à une brute force de mon cru... Mais, faire mieux que les développeurs de Delphi...

  14. #34
    Modérateur

    Homme Profil pro
    Ingénieur retraité
    Inscrit en
    Octobre 2005
    Messages
    2 396
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Rhône (Rhône Alpes)

    Informations professionnelles :
    Activité : Ingénieur retraité

    Informations forums :
    Inscription : Octobre 2005
    Messages : 2 396
    Points : 3 263
    Points
    3 263
    Par défaut
    Bonjour,

    René : Mon objectif personnel à moi était d'implémenter un Boyer-Moore. C'est fait. Remédier aux points faibles des deux procédés, c'est un autre challenge. Et incorporer PosEx() dans la dll quoi qu'on en dise, serait quand même un plagiat, ou tout au moins un détournement d'une routine de Delphi...
    "Plagiat, ... détournement d'une routine de Delphi" moi je diras plutôt une utilisation intelligente de l'association d'une routine de Delphi et d'une routine à Toi.
    Car en l'état actuel, sans vouloir te vexer, ça ressemble un peu à un boulot inachevé ...

    Je préfèrerais de beaucoup créer Ma routine. Question de principe.
    Je vais donc réfléchir à une brute force de mon cru...
    "Ma ... mon" : Ah je commence à piger : c'est juste une question d'orgueil ! Sacré René...
    Mais l'idée de créer un brute force de ton cru est excellente...

    Mais, faire mieux que les développeurs de Delphi...
    Faut pas te décourager à l'avance : Ne vient-on pas de monter que les développeurs de PosEX ont pondu un truc inachevé qui rame lors de recherches de Mots ou Phrases longues ?

    Cordialement, et à +.
    N'oubliez pas de consulter les FAQ Delphi et les cours et tutoriels Delphi

  15. #35
    Modérateur

    Homme Profil pro
    Ingénieur retraité
    Inscrit en
    Octobre 2005
    Messages
    2 396
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Rhône (Rhône Alpes)

    Informations professionnelles :
    Activité : Ingénieur retraité

    Informations forums :
    Inscription : Octobre 2005
    Messages : 2 396
    Points : 3 263
    Points
    3 263
    Par défaut StrPos Boyer-Moore tolérant à certaines fautes de frappe
    Bonjour,

    Le projet de Brute force de Rekin85 m'a donné une idée d'un Boyer-Moore "brutal" qui utilise un coulisseau à 5 Trous :

    OxxxxOxxxxOxxxxOxxxxO < Pochoir-Mot-Coulissant à 5 Trous fonctionnant avec EXIT direct en cas de concordance sur les 5 trous verts quelle que soit length(Mot)

    Justification : Si je cherche Mot1, la probabilité qu'il existe un Mot2 qui a simultanément :
    - le même Dernier Chr,
    - et le même Premier Chr,
    - et le même Chr sous le Deuxième Trou,
    - et le même Chr sous le Trou du Milieu,
    - et le même Chr sous l'Avant Dernier Trou,
    - et positionnés de la même façon
    est quasi-nulle, et donc ça évite de perdre du temps avec les autres caractères x intermédiaires.
    Pour l'ensemble des 5 trous cette probabilité est de (1/255)^5 = 9 x 10^(-13) soit environ 10^(-12) autrement dit le risque de ratisser une occurrence parasite est pico-scopique dans le cas de recherche de Mots d'un langage courant dans du Texte (mais faut éviter d'utiliser un tel algo dans la cas de la recherche d'une séquence d'ADN dans un "Texte" formé uniquement par des combinaisons des 4 Chr : CTAG, de même que dans le cas de recherche d'une chaîne numérique).
    Par contre dans le cas de recherches dans du texte en langage courant le principe d'un coulisseau réduit à N trous présente en plus l'avantage d'être "tolérant" à un certain nombre de fautes de frappe pouvant être présentes dans le Texte : celles qui sont susceptibles de se trouver dans les positions comprises entre les trous du coulisseau et qui ne modifient pas la longueur du Mot comme par exemple : Je cherche "Yellow submarine" dans un Texte qui comporte "Yallow submarime" et cet algo tolérant me renverra quand même cette occurrence alors qu'un algo qui teste tous le Chr du Mot la loupera.
    Bien entendu si la faute de frappe tombe pile sur l'un des trous du coulisseau elle ne fera pas mieux qu'un algo strict mais dans tous les autres cas cette tolérance aux erreurs de frappe peut être appréciée et en plus l'amplitude de cette tolérance augmente avec la longueur du Mot ou de la Phrase recherchée.

    J'ai donc créé la routine BMHPascalC5T (voir code plus bas) basée sur ce principe dont voici les résultats comparatifs :

    A) Pour 100 000 Recherches de Mot de 175 caractères aléatoires dans Texte de 97 345 caractères aléatoires et Mot présent 16 fois dans chaque texte
    - Avec StrUtils.PosEx ASM version => Trouvé : 1 600 000 fois, Mis : 1 919 ms
    - Avec BMHPascalNaif (Case Sensitive) => Trouvé : 1 600 000 fois, Mis : 453 ms
    - Avec BMH_PosEX (Case Sensitive) => Trouvé : 1 600 000 fois, Mis : 327 ms
    - Avec PosBM_KR => Trouvé : 1 600 000 fois, Mis : 437 ms
    - Avec BMHSearchBinaryInBinary => Trouvé : 1 600 000 fois, Mis : 483 ms
    - Avec BMHPascalC5T => Trouvé : 1 600 000 fois, Mis : 297 ms

    B) Pour 1 000 000 Recherches de Mot de 1 000 caractères aléatoires dans Texte de 20 200 caractères aléatoires et Mot présent 10 fois dans chaque texte
    - Avec StrUtils.PosEx ASM version => Trouvé : 10 000 000 fois, Mis : 4 353 ms
    - Avec BMHPascalNaif (Case Sensitive) => Trouvé : 10 000 000 fois, Mis : 5 413 ms
    - Avec BMH_PosEX (Case Sensitive) => Trouvé : 10 000 000 fois, Mis : 1 560 ms
    - Avec PosBM_KR => Trouvé : 10 000 000 fois, Mis : 1 654 ms
    - Avec BMHSearchBinaryInBinary => Trouvé : 10 000 000 fois, Mis : 5 491 ms
    - Avec BMHPascalC5T => Trouvé : 10 000 000 fois, Mis : 140 ms

    C) Pour 10 000 Recherches de Phrase de 554 caractères dans Texte de ZOLA de 1 048 838 caractères aléatoires et Phrase présente 1 fois en fin de texte
    - Avec StrUtils.PosEx ASM version => Trouvé : 10 000 fois, Mis : 2 059 ms
    - Avec BMHPascalNaif (Case Sensitive) => Trouvé : 10 000 fois, Mis : 718 ms
    - Avec BMH_PosEX (Case Sensitive) => Trouvé : 10 000 fois, Mis : 1 982 ms
    - Avec PosBM_KR => Trouvé : 10 000 fois, Mis : 1 061 ms
    - Avec BMHSearchBinaryInBinary => Trouvé : 10 000 fois, Mis : 827 ms
    - Avec BMHPascalC5T => Trouvé : 10 000 fois, Mis : 764 ms

    D) Pour 10 000 Recherches de Mot de 9 caractères 'Catherine' dans Texte de ZOLA de 1 048 838 caractères aléatoires et Mot présent ? fois dans chaque texte
    - Avec StrUtils.PosEx ASM version => Trouvé : 2 390 000 fois, Mis : 12 137 ms
    - Avec BMHPascalNaif (Case Sensitive) => Trouvé : 2 390 000 fois, Mis : 5 881 ms
    - Avec BMH_PosEX (Case Sensitive) => Trouvé : 2 390 000 fois, Mis : 12 137 ms
    - Avec BMHSearchBinaryInBinary => Trouvé : 2 390 000 fois, Mis : 6 224 ms
    - Avec BMHPascalC5T => Trouvé : 2 390 000 fois, Mis : 5 975 ms

    E) Pour 10 000 Recherches de Mot de 12 caractères 'MOTFINALZOLA' dans Texte de ZOLA de 1 048 838 caractères aléatoires et Mot présent 1 fois en fin de texte
    - Avec StrUtils.PosEx ASM version => Trouvé : 10 000 fois, Mis : 2 059 ms
    - Avec BMHPascalNaif (Case Sensitive) => Trouvé : 10 000 fois, Mis : 2 730 ms
    - Avec BMH_PosEX (Case Sensitive) => Trouvé : 10 000 fois, Mis : 2 044 ms
    - Avec PosBM_KR => Trouvé : 10 000 fois, Mis : 4 805 ms
    - Avec BMHSearchBinaryInBinary => Trouvé : 10 000 fois, Mis : 2 746 ms
    - Avec BMHPascalC5T => Trouvé : 10 000 fois, Mis : 2 948 ms

    F) Pour 10 000 Recherches de Mot de 22 caractères 'Un débordement de sève' dans Texte de ZOLA de 1 048 838 caractères aléatoires et Mot présent ? fois dans chaque texte
    - Avec StrUtils.PosEx ASM version => Trouvé : 20 000 fois, Mis : 12 496 ms
    - Avec BMHPascalNaif (Case Sensitive) => Trouvé : 20 000 fois, Mis : 3 198 ms
    - Avec BMH_PosEX (Case Sensitive) => Trouvé : 20 000 fois, Mis : 12 527 ms
    - Avec BMHSearchBinaryInBinary => Trouvé : 20 000 fois, Mis : 3 338 ms
    - Avec BMHPascalC5T => Trouvé : 20 000 fois, Mis : 3 245 ms

    Résumé :
    - Les tests comparatifs A, B et C montrent que BMHPascalC5T se débrouille très bien et vite lors de la recherche de Mots Longs.
    - Le test E semble révéler que le brute force PosEx se débrouille le plus rapidement lors de la recherche de Mots courts en Majuscules
    - Et les tests D et F montrent que même avec des Mots relativement courts en Minuscules PosEx rame entre 2 et 3,8 fois plus lentement que BMHPascalC5T

    Le code :
    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
    type tSkip2 = array[char] of longWord;
    var Skip2: tSkip2;
     
    procedure InitSkip2(const Mot: string);
    var LM, k: integer; Cara: char;
    begin
      LM := Length(Mot);
      for Cara := low(Char) to high(Char) do Skip2[Cara] := LM;
      for k := 1 to LM - 1 do Skip2[Mot[k]] := LM - k;
    end;
     
    function BMHPascalC5T(const Mot, Texte: AnsiString; var Depuis: longWord; LT, LM, LM1, E1, E2, E3: LongWord; C1, C2, C3, C4, C5: Char): longWord;
    var it: longWord;
    begin
      Result := 0;
      it := Depuis + LM1;
      while (it <= LT) do begin
        if (Texte[it] = C5) // Priorité n° 1 : Concordance sur Dernier Trou
          and (Texte[it - LM1] = C1) // Priorité n° 2 : Concordance sur Premier Trou
          and (Texte[it - E2] = C3) // Priorité n° 3 : Concordance sur Trou du Milieu
          and (Texte[it - E1] = C4) // Concordance sur Avant Dernier Trou
          and (Texte[it - E3] = C2) // Concordance sur Deuxième Trou
          then begin
          Result := it - LM1; Depuis := it; EXIT; // Occurrence Trouvée
        end;
        Inc(it, skip2[Texte[it]]);
      end;
      Result := 0; Depuis := 0;
    end;
    Et le code pour un test de bon fonctionnement (nécessite une TForm, un TRichEdit, un tEdit et un Bouton) :
    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
    procedure TForm1.bBMH_C5TClick(Sender: TObject);
    const nTrous: byte = 5; // Coulisseau à 5 Trous
    var Mot, Texte: string; count: integer;
      nbTours, i, Depuis, LM, LM1, LT, E1, E2, E3, Po, GTC: longWord;
      C1, C2, C3, C4, C5: Char; //<= Les 5 caractères des 5 Trous du pochoir coulissant
    begin
      Texte := trim(RE.Text); // Texte  placé dans RichEdit RE
      Mot := trim(edMot.text); // Mot à chercher placé dans un TEdit
      // Petits pré-calculs
      LT := length(Texte); LM := length(Mot);
      if LM<4 then begin ShowMessage('Le Mot à chercher doit comporter au moins 4 caractères'); EXIT; end;
      LM1 := LM - 1; E1 := LM1 div (nTrous - 1);  E2 := 2 * E1; E3 := 3 * E1;
      // Ruse pour fonctionner avec des Mots de 4 Chr
      if E1<1 then begin E1:=1; E2:=2; E3:=3; end;
      // E1, E2, E3 = écarts entre Trous intermédiaires et Dernier Trou du coulisseau
      C5 := Mot[LM]; C4 := Mot[LM - E1]; C3 := Mot[LM - E2]; C2 := Mot[LM - E3]; C1 := Mot[1];
      GTC := GetTickCount;
      nbTours := 1;  // nbTours := 1 pour test de bon fonctionnement avec coloriage des Mots trouvés
      InitSkip2(Mot); Count := 0;
      with RE do begin
        for i := 1 to nbTours do begin
          Depuis := 1;
          Po := BMHPascalC5T(Mot, Texte, Depuis, LT, LM, LM1, E1, E2, E3, C1, C2, C3, C4, C5);
          while Po > 0 do begin
            inc(Count);
            // Repérage dans le RichEdit en Couleur des Mots trouvés :
            SelStart := Po - 1;
            SelLength := LM;
            SelAttributes.Style := [fsBold];
            SelAttributes.Color := clFuchsia;
            if Depuis >= LT then break;
            Po := BMHPascalC5T(Mot, Texte, Depuis, LT, LM, LM1, E1, E2, E3, C1, C2, C3, C4, C5);
          end;
        end;
      end;
      Trace('Pour nb-Recherches = ' + intToStr(nbTours) + ' :');
      Trace('- Avec BMHPascalC5T => Trouvé : ' + intToStr(Count) + ' fois, Mis : ' + IntToStr(GetTickCount - GTC) + ' ms');
    end;
    EDIT : Bien entendu en cas d'angoisse de ratisser une occurrence supplémentaire parasite, rien n'interdit d'ajouter un 6ième trou au coulisseau et la probabilité de la ratisser descend de 10^(-12) à 3,6 x 10^(-15) et une probabilité aussi minuscule ça s'appellerait plutôt une improbabilité.... Sans oublier que si la recherche vise à trouver une information il est toujours préférable d'en trouver davantage que de louper des occurrences à cause de quelques fautes de frappe.


    Cordialement, et à +.
    N'oubliez pas de consulter les FAQ Delphi et les cours et tutoriels Delphi

  16. #36
    Modérateur

    Homme Profil pro
    Ingénieur retraité
    Inscrit en
    Octobre 2005
    Messages
    2 396
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Rhône (Rhône Alpes)

    Informations professionnelles :
    Activité : Ingénieur retraité

    Informations forums :
    Inscription : Octobre 2005
    Messages : 2 396
    Points : 3 263
    Points
    3 263
    Par défaut StrPos Boyer-Moore tolérant à certaines fautes de frappe : version coulisseau à 6 trous
    Bonjour,

    Voici une version basée sur le même principe que celui du code du message précédent mais cette fois-ci avec un coulisseau à 6 trous qui fait descendre la probabilité de ratisser une occurrence supplémentaire parasite à 3,6 x 10^(-15) en cas de recherche d'un Mot ou d'une Phrase dans du Texte rédigé en langage courant :
    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
    type tSkip = array[char] of longWord;
     
    type tPosBMHTol = object // StrPos à la façon Boyer-Moore-Horspool tolérante à certaines erreurs de frappe
        Mot, Texte: AnsiString;
        Skip: tSkip;
        LM, LM1, LT: longWord; // Longueurs
        E1, E2, E3, E4: longWord; // E1, E2, E3, E4 = écarts entre Trous intermédiaires et Dernier Trou du coulisseau
        C1, C2, C3, C4, C5, C6: Char; // Les 6 caractères des 6 Trous du Pochoir-Mot-Coulissant à 6 trous
        function Intitilisations(const iMot, iTexte: AnsiString): boolean;
        function BMH_C6T(var iDepuis: longWord): longWord;
      end;
     
    function tPosBMHTol.Intitilisations(const iMot, iTexte: AnsiString): boolean;
    const nTrous: byte = 6; // Pochoir-Mot-Coulissant à 6 trous : OxxxOxxxOxxxOxxxOxxxO
    var k: integer; Cara: char;
    begin
      Mot := iMot; Texte := iTexte; Result := False;
      LM := Length(Mot);
      if LM < 5 then begin ShowMessage('Le Mot à chercher doit comporter au moins 5 caractères'); EXIT; end;
      // Initialisation de la SkipTable :
      for Cara := low(Char) to high(Char) do Skip[Cara] := LM;
      for k := 1 to LM - 1 do Skip[Mot[k]] := LM - k;
      // Petits pré-calculs :
      LT := length(Texte); LM1 := LM - 1;
      E1 := LM1 div (nTrous - 1); E2 := 2 * E1; E3 := 3 * E1; E4 := 4 * E1;
      // Ruse pour fonctionner avec des Mots de 5 Chr
      if E1 < 1 then begin E1 := 1; E2 := 2; E3 := 3; E4 := 4; end;
      C6 := Mot[LM]; C5 := Mot[LM - E1]; C4 := Mot[LM - E2]; C3 := Mot[LM - E3]; C2 := Mot[LM - E4]; C1 := Mot[1];
      Result := True;
    end;
     
    function tPosBMHTol.BMH_C6T(var iDepuis: longWord): longWord;
    var it: longWord;
    begin
      Result := 0;
      it := iDepuis + LM1;
      while (it <= LT) do begin
        if (Texte[it] = C6) // Priorité n° 1 : Concordance sur Dernier Trou
          and (Texte[it - LM1] = C1) // Priorité n° 2 : Concordance sur Premier Trou
          and (Texte[it - E3] = C3) // Priorité n° 3 : Concordance sur Trou proche du Milieu
          and (Texte[it - E2] = C4) // Concordance sur Trou 4
          and (Texte[it - E4] = C2) // Concordance sur Trou 2
          and (Texte[it - E1] = C5) // Concordance sur Trou 5
          then begin
          Result := it - LM1; iDepuis := it + 1; EXIT; // Occurrence Trouvée
        end;
        Inc(it, skip[Texte[it]]);
      end;
      Result := 0; iDepuis := 0;
    end;
    Pour utiliser :
    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
    procedure TForm1.bBMH_C6TClick(Sender: TObject);
    // Coulisseau à 6 Trous avec tolérance à certaines erreurs de frappe
    var Mot, Texte: string; count: integer; nbTours, i, LM, LT, Depuis, Po, GTC: longWord;
      PosBMHTol: tPosBMHTol;
    begin
      Texte := trim(RE.Text); LT := length(Texte);
      Mot := trim(edMot.text); LM := length(Mot);
      if PosBMHTol.Intitilisations(Mot, Texte) then begin
        with PosBMHTol do labNTrous.Caption := C1 + ' ' + C2 + ' ' + C3 + ' ' + C4 + ' ' + C5 + ' ' + C6;
        GTC := GetTickCount;
        Count := 0; nbTours := 1; // nbTours := 1 pour test de bon fonctionnement 
        with RE do begin
          for i := 1 to nbTours do begin
            Depuis := 1;
            Po := PosBMHTol.BMH_C6T(Depuis);
            while Po > 0 do begin
              inc(Count);
              // 4 lignes suivantes à placer en commentaires en cas d'utilisation pour tests de vitesse :
              SelStart := Po - 1;
              SelLength := LM;
              SelAttributes.Style := [fsBold];
              SelAttributes.Color := clFuchsia;
              if Depuis >= LT then break;
              Po := PosBMHTol.BMH_C6T(Depuis);
            end;
          end;
        end;
        Trace('Pour nb-Recherches = ' + intToStr(nbTours) + ' :');
        Trace('- Avec PosBMHTol.BMH_C6T => Trouvé : ' + intToStr(Count) + ' fois, Mis : ' + IntToStr(GetTickCount - GTC) + ' ms');
      end;
    end;
    Résultats de tests comparatifs de vitesses :

    A) Pour 1 000 000 Recherches de Mot de 1 000 caractères aléatoires dans Texte de 20 200 caractères aléatoires et Mot présent 10 fois dans texte
    - Avec StrUtils.PosEx ASM version => Trouvé : 10 000 000 fois, Mis : 4 789 ms
    - Avec BMHPascalNaif (Case Sensitive) => Trouvé : 10 000 000 fois, Mis : 5 398 ms
    - Avec PosBM_KR => Trouvé : 10 000 000 fois, Mis : 1 684 ms
    - Avec BMHPascalC5T => Trouvé : 10 000 000 fois, Mis : 125 ms < coulisseau à 5 trous
    - Avec PosBMHTol.BMH_C6T => Trouvé : 10 000 000 fois, Mis : 156 ms < coulisseau à 6 trous

    B) Pour 10 000 Recherches de Bout de Phrase de 36 caractères dans Texte de ZOLA de 1 048 838 caractères et Bout de Phrase présent 1 fois dans texte
    - Avec StrUtils.PosEx ASM version => Trouvé : 10 000 fois, Mis : 12 652 ms
    - Avec BMHPascalNaif (Case Sensitive) => Trouvé : 10 000 fois, Mis : 3 120 ms
    - Avec PosBM_KR => Trouvé : 10 000 fois, Mis : 4 414 ms
    - Avec BMHPascalC5T => Trouvé : 10 000 fois, Mis : 3 151 ms < coulisseau à 5 trous
    - Avec PosBMHTol.BMH_C6T => Trouvé : 10 000 fois, Mis : 3 385 ms < coulisseau à 6 trous

    Conclusion : Vu que la prise en compte d'un 6ième trou ne réduit la vitesse que faiblement autant en profiter pour faire descendre la probabilité de ratisser une occurrence supplémentaire parasite à 3,6 x 10^(-15) en cas de recherche d'un Mot ou d'une Phrase dans du Texte rédigé en langage courant susceptible de comporter certaines erreurs de frappe.
    Mais ne pas utiliser BMHPascalC5T ou PosBMHTol.BMH_C6T pour la recherche d'une séquence d'ADN dans un "Texte" formé uniquement par des combinaisons des 4 Chr : CTAG, de même que dans le cas de recherche d'une chaîne numérique : dans ces cas utiliser un algo strict même s'il est plus lent.

    Cordialement, et à +.
    N'oubliez pas de consulter les FAQ Delphi et les cours et tutoriels Delphi

  17. #37
    Membre actif

    Homme Profil pro
    Inscrit en
    Mars 2009
    Messages
    128
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Vendée (Pays de la Loire)

    Informations forums :
    Inscription : Mars 2009
    Messages : 128
    Points : 203
    Points
    203
    Par défaut Epilogue
    Bonjour,

    Bravo Gilbert ! J'ai essayé ton coulisseau à 6 trous, c'est super ! c'est d'une vélocité étonnante; et étant donné les probabilités d'une erreur réduites à epsilon, cela constitue un outil de recherche dans les textes incomparable. Chapeau !

    Pour ma part, j'ai tenu compte de tes suggestions pour améliorer la célérité de mes routines de recherches en dll. Voici donc le nouveau source :

    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
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    167
    168
    169
    170
    171
    172
    173
    174
    175
    176
    177
    178
    179
    180
    181
    182
    183
    184
    185
    186
    187
    188
    189
    190
    191
    192
    193
    194
    195
    196
    197
    198
    199
    200
    201
    202
    203
    204
    205
    206
    207
    208
    209
    210
    211
    212
    213
    214
    215
    216
    217
    218
    219
    220
    221
    222
    223
    224
    225
    226
    227
    228
    229
    230
    231
    232
    233
    234
    235
    236
    237
    238
    239
    240
    241
    242
    243
    244
    245
    246
    247
    248
    249
    250
    251
    252
    253
    254
    255
    256
    257
    258
    259
    260
    261
    262
    263
    264
    265
    266
    267
    268
    269
    270
    271
    272
    273
    274
    275
    276
    277
    278
    279
    280
    281
    282
    283
    284
    285
    286
    287
    288
    289
    290
    291
    292
    293
    294
    295
    296
    297
    298
    299
    300
    301
    302
    303
    304
    305
    306
    307
    308
    309
    310
    311
    312
    313
    314
    315
    316
    317
    318
    319
    320
    321
    322
    323
    324
    325
    326
    library PosBM;
     
    uses windows;
     
    // Routines et variables internes **********************************************
     
    type  TSkip = array[0..255] of longword;
    var   SkipBuf: TSkip;           // Table des sauts du Boyer-Moore
    const SeuilEx_BM : longword = $6;
     
    // Compare SStr à Str depuis la position de ecx dans Str
    // comparaisons faites en dwords et/ou bytes avec NbDw et NbBy
    // Entrée :
    // 1 - esi pointe sur la Str et edi sur la SStr
    // 2 - ecx contient l'indice de la borne
    // 3 - edx contient la longueur de la collection SStr
    // Retour :
    // 1 - CarryFlag à 1 si occurence trouvée et à 0 sinon
    // 2 - ecx renvoie la position du byte d'arrêt sur Str
    // 3 - eax toujours =0
    procedure CompBM_BD; register;
    asm
       push    edi
       push    esi            // adresse départ Str
       add     esi,ecx        // placer esi sur la borne de départ
       mov     ecx,edx        // edx garde length(SStr)
       // comparaison descendante
       add     esi,ecx        // pointer fin Str + 1
       add     edi,ecx        // pointer fin SStr + 1
       // Byte à Byte
       @Bytes:
       mov     ecx,edx
       and     ecx,$3
       jz      @DWords
       @RBytes:               // shunter si un des derniers discordant
         dec     esi          // se placer sur dernier byte
         dec     edi
         mov     al,byte ptr[edi]
         cmp     al,byte ptr[esi]
         jne     @FinNon      // byte discordant
         dec     ecx
         jnz     @Rbytes
       // DWord à DWord
       @DWords:
       mov     ecx,edx       // combien de DWords entiers ?
       shr     ecx,$2
       jz      @FinOui        // aucun
       @RDWords:
         sub     esi,$4       // se placer dword en dessous
         sub     edi,$4
         mov     eax,DWord ptr[edi]
         cmp     eax,DWord ptr[esi]
         jne     @ByteD       // si pas égaux, aller au byte défaillant
         dec     ecx
         jnz     @RDWords
       jmp     @FinOui        // tous DWords bons
       @ByteD:                // cas d'un Dword défaillant
       mov     ecx,$4         // rattraper le décalage
       add     esi,ecx        // et chercher le byte défaillant
       @RByteD:
         dec     esi
         cmp     al,byte ptr[esi]
         jne     @FinNon
         shr     eax,$8
         dec     ecx
         jnz     @RByteD
       // Retours de routine
       @FinNon:               // retour false
       xor     eax,eax
       jmp     @Fin
       @FinOui:               // retour true
       mov     eax,$1
       @Fin:
       mov     ecx,esi
       pop     esi            // remise adresse Départ
       sub     ecx,esi        // calcul place du byte d'arrivée
       pop     edi
       shr     eax,$1          // positionnement du carry flag
    end;
     
    // Routines exportables ********************************************************
     
    // permet d'initialiser le seuil de basculement des deux Pos
    // En deçà c'est pour PosEx_KR, au delà c'est pour PosBM_KR
    // Renseigne donc la constante SeuilEx_BM
    procedure InitSeuil(Seuil: longword); StdCall
    asm
       mov    eax,[ebp]+$08
       mov    SeuilEx_BM,eax
    end;
     
    // Algorithme de Boyer-Moore pour la recherche d'occurence
    // d'une collection de bytes dans une autre collection de bytes plus grande
    // L'occurence peut avoir une capacité de plus de 256 octets mais au minimum 5
    // Retourne le rang de la 1ère occurence trouvée à partir de Depuis
    // Retourne 0 si aucune trouvée
    function PosBM_KR(SStr, Str : Pointer; LSStr, LStr, Depuis :longWord): longword; stdcall;
    var PosMax,Depart: longWord;
    asm
       push    ebx              //pointeur sur SkipBuf
       lea     ebx,[SkipBuf]
       push    edi
       mov     edi,[ebp]+$08    // edi pointe Texte
       push    esi
       mov     esi,[ebp]+$0C    // esi pointe Mot
       mov     edx,[ebp]+$10    // len Mot
       mov     eax,[ebp]+$14    // len Texte
       sub     eax,edx
       inc     eax              // edx nb max de bytes
       mov     PosMax,eax
       mov     ecx,[ebp]+$18
       dec     ecx              // indice de départ
       mov     Depart,ecx
       @SearchOne:
          cmp     ecx,PosMax
          jae     @FinNulle
          mov     al,byte ptr[esi]+ecx
          cmp     al,byte ptr[edi]
          je      @Compare
          add     ecx,edx
          dec     ecx
          mov     al,byte ptr[esi]+ecx
          and     eax,$FF
          jmp     @Decale
          @Compare:                       // Comparaison et sauts
          call    CompBM_BD
          jc      @FinBonne               // CF indicateur oui - non
          mov     al,byte ptr[esi]+ecx    // byte défaillant
          @Decale:
          shl     eax,$2                  // indice x 4 pour DWord
          mov     ecx,DWord ptr[ebx]+eax  // décalage par SkipBuf[byte d'arrêt]
          add     ecx,Depart
          mov     Depart,ecx
          jmp     @SearchOne
       @FinNulle:
       xor      eax,eax
       jmp      @Fin
       @FinBonne:
       inc      ecx
       mov      eax,ecx                 // retour du rang de l'occurence trouvée
       @Fin:
       pop      esi
       pop      edi
       pop      ebx
    end;
     
    // Algorithme brute force pour la recherche d'occurence
    // d'une collection de bytes dans une autre collection de bytes plus grande
    // L'occurence peut avoir une capacité de plus de 256 octets
    // Retourne le rang de la 1ère occurence trouvée à partir de Depuis
    // Retourne 0 si aucune trouvée
    // Largement inspiré de PosEx de Delphi
    function PosEx_KR(SStr,Str: pointer; LSStr,LStr,Depuis: longword ): longword; StdCall;
    asm
      mov     eax,[ebp]+$08     // adresse SStr
      mov     edx,[ebp]+$0C
      dec     edx               // adresse Str - 1
      mov     ecx,[ebp]+$18     // offset Depuis
      dec     ecx
      push    ebx
      push    edi
      push    esi
      mov     edi,[ebp]+$10     // Length(SStr)
      mov     esi,[ebp]+$14     // Length(Str)
      push    ebp
      push    edx
      add     ecx,edi
      lea     ebp,[eax+edi]     // Pointe dernier byte de SStr + 1
      add     esi,edx           // Pointe dernier byte de S
      mov     eax,[ebp-$1]      // Dernier byte de SStr
      and     eax,$FF
      add     edx,ecx           // Position dans Str du dernier byte
      mov     ah,al
      neg     edi               // - Length(SStr)
      mov     ecx,eax
      shl     eax,$10
      or      ecx,eax
      @BoucleMain:
        add     edx,$4
        cmp     edx,esi
        ja      @Reste            // 1 à 4 Positions en reste
        mov     eax,[edx-$4]      // 4 Bytes suivant de Str
        xor     eax,ecx           // aucun byte
        lea     ebx,[eax-$01010101]
        not     eax
        and     eax,ebx
        and     eax,$80808080
        jz      @BoucleMain       // jusqu'à aucune correspondance du dernier byte
        bsf     eax,eax           // Premier Bit correspondant
        shr     eax,$3            // rang du byte correspondant (0..3)
        lea     edx,[eax+edx-$4]  // Adresse
        @Compare:
        inc     edx
        cmp     edi,-$4
        jle     @Large            // Lenght(SStr) >= 4
        cmp     edi,-$1
        je      @Resultat         // Exit si Lenght(SStr) = 1
        mov     ax,[ebp+edi]
        cmp     ax,[edx+edi]
        jne     @BoucleMain       // pas de correspondance dans les deux premiers bytes
        jmp     @Resultat
      @Reste:
      sub     edx,$4
      @BoucleReste:
        cmp     cl,[edx]
        je      @Compare
        cmp     edx,esi
        jae     @NonTrouve
        inc     edx
        jmp     @BoucleReste
      @Large:
      mov     eax,[ebp-$4]      // Compare les 4 derniers bytes
      cmp     eax,[edx-$4]
      jne     @BoucleMain       // pas de correspondance
      mov     ebx,edi
      @BoucleCompare:             // Compare les bytes du reste
        add     ebx,$4            // Compare 4 bytes à la fois
        jge     @Resultat         // Tous bons
        mov     eax,[ebp+ebx-$4]
        cmp     eax,[edx+ebx-$4]
        je      @BoucleCompare
      jmp     @BoucleMain       // Pas de correspondance
      @NonTrouve:
      pop     edx               // Pas trouvé
      pop     ebp
      pop     esi
      pop     edi
      pop     ebx
      xor     eax,eax           // retour 0
      jmp     @Fin
      @Resultat:                  // correspondance complète
      lea     eax,[edx+edi]     // Calcule et retourne le résultat
      pop     edx
      pop     ebp
      pop     esi
      pop     edi
      pop     ebx
      sub     eax,edx           // soustrait la position de départ
      @Fin:
    end;
     
    // Initialise le tableau Skip des sauts du Boyer-Moore
    // en fonction de la collection à rechercher
    procedure InitSkipBuf(SStr : Pointer; LenSStr: longword); StdCall;
    asm
      push    esi
      mov     esi,[ebp]+$08           // esi pointe SStr
      mov     eax,[ebp]+$0C           // eax = len(SStr)
      push    edi
      lea     edi,[SkipBuf]           // edi pointe SkipBuf
      @FillInt:
      cld                             // remplissage en montant
      mov     ecx,$100                // 256 itérations
      rep     stosd                   // remplissage total avec lenSub
      sub     edi,$400                // remise edi au début de SkipBuf
      mov     ecx,eax                 // eax contient toujours len SStr
      @RSkip:
              dec    ecx
              jle    @Fin
              mov    al,byte ptr[esi]   // al contient le byte
              and    eax,$FF
              shl    eax,$2             // valeur du byte x 4
              mov    DWord ptr[edi+eax],ecx
              inc    esi
              jmp    @RSkip
      @Fin:
      pop     edi
      pop     esi
    end;
     
    // Appel function externe générale
    // Choix du mode Boyer-Moore au delà de 5 bytes en LSStr
    function Pos_KR(SStr,Str: pointer; LSStr,LStr,Depuis : Longword): longword; StdCall;
    asm
        // Cas d'invalidités d'appel
        mov   eax,[ebp]+$10        // LSStr
        mov   edx,[ebp]+$14        // LStr
        mov   ecx,[ebp]+$18        // Depuis
        test  eax,eax
        jz    @Nul                 // LSStr = 0
        test  edx,edx
        jz    @Nul                 // LStr = 0
        cmp   eax,edx
        ja    @Nul                 // LSStr > LStr
        cmp   ecx,$1
        jb    @Nul                 // Depuis < 1
        sub   edx,eax
        cmp   ecx,edx              // Depuis > LStr-LSStr
        jb    @Go
        @Nul:
        xor   eax,eax              // Retour @
        jmp   @Fin
        @Go:                       // Appel des routines
        mov   ecx,[ebp]+$18
        push  ecx
        mov   ecx,[ebp]+$14
        push  ecx
        mov   ecx,[ebp]+$10
        push  ecx
        mov   ecx,[ebp]+$0C
        push  ecx
        mov   ecx,[ebp]+$08
        push  ecx
        cmp   eax,SeuilEx_BM               // Au delà de SeuilEx_BM ?
        ja    @PosBM
        @PosEx:
        call  PosEx_KR
        jmp   @Fin
        @PosBM:
        call  PosBM_KR
        @Fin:
    end;
     
    // *****************************************************************************
     
    exports
          InitSeuil,
          PosBM_KR,
          PosEx_KR,
          InitSkipBuf,
          Pos_KR;
     
    // *****************************************************************************
     
    begin
    end.
    Alors, je me suis inspiré très fortement du PosEx() de Delphi 7 pour créer ma routine PosEx_Kr propre. Si bien que maintenant, selon la longueur en bytes de la collection à rechercher, la routine générale d'appel Pos_KR opte soit pour PosEx_KR, soit pour PosBM_KR . Le Boyer-Moore devient plus efficace que PosEx à partir d'un certain seuil (fixé à 6 d'emblée) qui peut être fixé comme on désire à l'aide de la petite routine InitSeuil.

    Comme d'habitude, compiler la library, placer la dll dans le répertoire de son programme et insérer en implémentation de celui-ci les routines d'appel des fonctions :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    procedure InitSeuil(Seuil : longword);StdCall; external'PosBM';
    procedure InitSkipBuf(SStr : Pointer; LenSStr: longword); StdCall; external'PosBM';
    function Pos_KR(SStr, Str : Pointer; LSStr, LStr, Depuis :longWord): longword; stdcall; external'PosBM';
    Attention, si le seuil est fixé à 6 , il convient pour une recherche qui dépasse 6 bytes d'appeler au moins une fois InitSkipBuf avant Pos_KR pour que le Boyer-Moore soit efficient...

  18. #38
    Modérateur

    Homme Profil pro
    Ingénieur retraité
    Inscrit en
    Octobre 2005
    Messages
    2 396
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Rhône (Rhône Alpes)

    Informations professionnelles :
    Activité : Ingénieur retraité

    Informations forums :
    Inscription : Octobre 2005
    Messages : 2 396
    Points : 3 263
    Points
    3 263
    Par défaut
    Bonjour René,

    Rekin85 :Bravo Gilbert ! J'ai essayé ton coulisseau à 6 trous, c'est super ! c'est d'une vélocité étonnante;
    Pour ma part, j'ai tenu compte de tes suggestions pour améliorer la célérité de mes routines de recherches en dll.
    Merci René pour ce bouquet de fleurs... Et vu que le coulisseau à 6 trous est lui aussi une suggestion peut on déduire que ta nouvelle dll utilise lui aussi l'astuce du coulisseau à 6 trous ???
    Je pose cette question car ta dll est cryptée en ASM ce qui est du "chinois" pour moi.

    Cordialement, et à +.
    N'oubliez pas de consulter les FAQ Delphi et les cours et tutoriels Delphi

  19. #39
    Membre actif

    Homme Profil pro
    Inscrit en
    Mars 2009
    Messages
    128
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Vendée (Pays de la Loire)

    Informations forums :
    Inscription : Mars 2009
    Messages : 128
    Points : 203
    Points
    203
    Par défaut
    Bonjour Gilbert,

    Non, ma nouvelle dll n'utilise pas le coulisseau 6 trous. Je pense pour ma part que ce nouveau concept sur les occurences est nettement fait pour des recherches de texte dans du texte avec des caractères de langages écrits (Français, Anglais... etc). Donc si dll il devait y avoir, elle serait particulière avec des incidences de casse majuscules/minuscules...

    Cela peut s'étudier...

    Cordialement A+

  20. #40
    Modérateur

    Homme Profil pro
    Ingénieur retraité
    Inscrit en
    Octobre 2005
    Messages
    2 396
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Rhône (Rhône Alpes)

    Informations professionnelles :
    Activité : Ingénieur retraité

    Informations forums :
    Inscription : Octobre 2005
    Messages : 2 396
    Points : 3 263
    Points
    3 263
    Par défaut
    Re-salut René,

    Rekin85 : Non, ma nouvelle dll n'utilise pas le coulisseau 6 trous. Je pense pour ma part que ce nouveau concept sur les occurrences est nettement fait pour des recherches de texte dans du texte avec des caractères de langages écrits (Français, Anglais... etc). Donc si dll il devait y avoir, elle serait particulière avec des incidences de casse majuscules/minuscules..
    OK, merci pour l'info... et d'accord avec la suite de ta phrase, j'ajouterais juste "et caractères Accentués" à "incidences de casse majuscules/minuscules".
    Et comme en plus ces incidences ne concernent que les 6 trous du coulisseau alors qu'avec PosEx pour obtenir le même résultat on est obligé de convertir la totalité des Chr des textes de recherche
    le coulisseau à 6 trous en ASM risque tout bonnement à renvoyer le résultat tandis que PosEx vient à peine de quitter ses starting-blocs....

    Cela peut s'étudier...
    Très bonne idée ... car gain de speed en vue en plus de la tolérance aux erreurs de frappe.
    Par contre les routines qui contrôlent la concordance exhaustive des Chr de la sous-chaîne cherchée conservent leur intérêt dans les cas autres que les recherches de texte dans du texte de langages écrits comme par exemple
    pour des recherches de séquences d'A.D.N pour lesquelles la probabilité de ratisser une occurrence parasite est trop élevée car résultant des seuls 4 caractères utilisés C, T, A, et G.

    En attendant voici déjà quelques tests comparatifs (en mode Sensible à la casse) :
    A) Pour 10 000 Recherches de Phrase de 50 caractères aléatoires dans Texte de 1 048 842 caractères aléatoires et Phrase présente 1 fois dans texte
    - Avec StrUtils.PosEx ASM version => Trouvé : 10 000 fois, Mis : 12 074 ms
    - Avec BMHPascalNaif => Trouvé : 10 000 fois, Mis : 2 231 ms
    - Avec Pos_KR => Trouvé : 10 000 fois, Mis : 2 543 ms
    - Avec PosBMHTol.BMH_C6T => Trouvé : 10 000 fois, Mis : 2 449 ms

    B) Pour 10 000 Recherches de Paragraphe de 1 352 caractères aléatoires dans Texte de 1 048 842 caractères aléatoires et Paragraphe présent 2 fois vers la fin du texte
    - Avec StrUtils.PosEx ASM version => Trouvé : 20 000 fois, Mis : 12 075 ms
    - Avec BMHPascalNaif (Case Sensitive) => Trouvé : 20 000 fois, Mis : 686 ms
    - Avec Pos_KR => Trouvé : 20 000 fois, Mis : 796 ms
    - Avec PosBMHTol.BMH_C6T => Trouvé : 20 000 fois, Mis : 718 ms

    C) Pour 10 000 Recherches de Phrase de 1 000 Majuscules aléatoires dans Texte de 1 048 842 Minuscules aléatoires et Phrase présente 10 fois dans texte
    - Avec StrUtils.PosEx ASM version => Trouvé : 100 000 fois, Mis : 2 013 ms
    - Avec BMHPascalNaif (Case Sensitive) => Trouvé : 100 000 fois, Mis : 93 ms
    - Avec Pos_KR => Trouvé : 100 000 fois, Mis : 94 ms
    - Avec PosBMHTol.BMH_C6T => Trouvé : 100 000 fois, Mis : 62 ms

    Globalement les 3 dernières routines se tiennent dans un mouchoir de poche, il n'y a que StrUtils.PosEx qui rame dans la choucroute...

    Cordialement, et à +.
    N'oubliez pas de consulter les FAQ Delphi et les cours et tutoriels Delphi

+ Répondre à la discussion
Cette discussion est résolue.
Page 2 sur 2 PremièrePremière 12

Discussions similaires

  1. Implémentation algo boyer moore
    Par tony1.0 dans le forum C
    Réponses: 0
    Dernier message: 20/05/2010, 15h29
  2. Réponses: 2
    Dernier message: 29/12/2009, 12h57
  3. Boyer-moore VS strstr()
    Par riadh8 dans le forum Bibliothèque standard
    Réponses: 0
    Dernier message: 21/04/2009, 02h24
  4. algo Boyer Moore
    Par t-student dans le forum Algorithmes et structures de données
    Réponses: 8
    Dernier message: 20/04/2008, 11h19
  5. Code Source Boyer-moore
    Par kam42 dans le forum C++
    Réponses: 2
    Dernier message: 26/12/2007, 09h49

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo