Amélioration de la fonction Pos()

piette
Messages postés
68
Date d'inscription
jeudi 11 décembre 2008
Statut
Membre
Dernière intervention
16 juin 2019
- 27 mai 2015 à 23:28
piette
Messages postés
68
Date d'inscription
jeudi 11 décembre 2008
Statut
Membre
Dernière intervention
16 juin 2019
- 15 sept. 2015 à 20:04
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.

https://codes-sources.commentcamarche.net/source/101045-amelioration-de-la-fonction-pos

Re-bonjour,

Pour en savoir plus sur l'astuce à la base de la vitesse d'exécution de BMHPascalC5T voir ici

http://www.developpez.net/forums/d1530223-2/environnements-developpement/delphi/algorithme-boyer-moore/

Voir le message d'Aujourd'hui 13/07/2015 à 11h09 (message n°#35) qui commence par "Le projet de Brute force de Rekin85 m'a donné une idée d'un Boyer-Moore "brutal" qui utilise un coulisseau à 5 Trous"

Je pense que l'amélioration est susceptible de vous intéresser.

Cordialement, et à +.
piette
Messages postés
68
Date d'inscription
jeudi 11 décembre 2008
Statut
Membre
Dernière intervention
16 juin 2019
> cs_pseudo3
16 juil. 2015 à 19:56
Bonjour,
J'ai regardé, c'est une autre façon de 'voir les choses'.
Une autre approche.
Mais plus rapide sans aucun doute, bravo.
Je vais rester sur une approche binaire, ce sera intéressant de voir de combien la différence entre ces 2 approches se réduit en ms avec l'ASM?
Il est aussi possible de 'fouiller' avec votre méthode et ensuite de confirmer octets après octets la validité absolue de la 'trouvaille', ce qui marierai les 2 approches!
je retourne sur la plage.
cs_pseudo3 > piette
Messages postés
68
Date d'inscription
jeudi 11 décembre 2008
Statut
Membre
Dernière intervention
16 juin 2019

17 juil. 2015 à 09:42
Bonjour,

>> "J'ai regardé, c'est une autre façon de 'voir les choses'. Une autre approche.Mais plus rapide sans aucun doute, bravo."

A noter en plus que cette autre approche rend l'algo "tolérant certaines fautes de frappe" susceptibles de polluer les Textes dans lesquels on fait une recherche comme par exemple : je cherche "Yellow submarine" et l'un des textes contient "Yallow submarine" et l'autre "Yellow submarime"
Dans un tel cas l'algo trouve l'occurrence alors qu'un algo "strict" tel que PosEx ne la trouve pas.

>> "Je vais rester sur une approche binaire, ce sera intéressant de voir de combien la différence entre ces 2 approches se réduit en ms avec l'ASM?" :

Ce serait effectivement intéressant.

>> "Il est aussi possible de 'fouiller' avec votre méthode et ensuite de confirmer octets après octets la validité absolue de la 'trouvaille', ce qui marierai les 2 approches! " :

Bin comme ma méthode est tolérante à un certain nombre de fautes de frappe cela supposerait qu'il soit possible de confirmer par une logique :
- soit que les occurrences trouvées contiennent de simples fautes de frappe,
- soit qu'il s'agit d'occurrences parasites.

>> "je retourne sur la plage." :

Bonne baignade...

Cordialement, et à +.
piette
Messages postés
68
Date d'inscription
jeudi 11 décembre 2008
Statut
Membre
Dernière intervention
16 juin 2019
> cs_pseudo3
1 sept. 2015 à 22:46
Bonsoir,
Les baignades sont terminées, hélas.


Salutations.
Bonjour,

J'ai enfin trouvé la cause de la Violation d'accès : c'est l'instruction if BM.Par2chars <> nil then FreeMem(BM.Par2chars, BM.Volar2chars) qui la causait :
function Fab_Sauts(var BM: TreBMH2C): boolean;
var I: integer;
begin
ShowMessage('Fab_Sauts Deb');
Result := length(BM.mot) > 1; if not Result then exit;
BM.jusqua := 0; BM.Depuis := 1;
BM.Lmot := length(BM.mot); BM.ForceBrut := BM.Lmot < ctposDJ;
if BM.ForceBrut then begin showmessage('exit Fab_Sauts'); exit; end;

fillchar(BM.arNchars, succ(ctNchar), 0);
//comptage Nb lettres <>
for I := 1 to BM.Lmot do BM.arNchars[ord(BM.mot[I])] := 1;
BM.NcharDiff := 1;
ShowMessage('Fab_Sauts 1');
for I := 0 to Pred(ord(BM.mot[1])) do if BM.arNchars[I] <> 0 then
begin inc(BM.NcharDiff); BM.arNchars[I] := BM.NcharDiff; end;
ShowMessage('Fab_Sauts 2');
for I := Succ(ord(BM.mot[1])) to ctNchar do if BM.arNchars[I] <> 0 then
begin inc(BM.NcharDiff); BM.arNchars[I] := BM.NcharDiff; end;
ShowMessage('Fab_Sauts 3');
//normalisation 2^n
BM.NbLignes := Succ(BM.NcharDiff);
//if BM.Par2chars <> nil then FreeMem(BM.Par2chars, BM.Volar2chars); < ici la cause de la V.A.
BM.Volar2chars := (BM.NbLignes * BM.NbLignes * sizeof(Word));
GetMem(BM.Par2chars, BM.Volar2chars);
ShowMessage('Fab_Sauts 4');
fillWord(BM.Par2chars^, BM.NbLignes * BM.NbLignes, BM.Lmot);
fillWord(BM.Par2chars^, BM.NbLignes * 2, Pred(BM.Lmot));
fillWord(BM.Par2chars^, BM.NbLignes, BM.Lmot);
ShowMessage('Fab_Sauts 5');
//remplissage de la table
for I := 1 to BM.Lmot - 2 do
BM.Par2chars^[BM.arNchars[ord(BM.mot[I])] +
BM.arNchars[ord(BM.mot[Succ(I)])] * BM.NbLignes] := Pred(BM.Lmot) - I;
ShowMessage('Fab_Sauts Fin');
end;


Résultats du test :

TEXTE : -Bonjour de Bretagne ou il fait beau et reBonjour de Bretagne ou il fait beau, bonnes vacances!-Bonjour de Bretagne ou il fait beau et reBonjour de Bretagne ou il fait beau, bonnes vacances!-Bonjour de Bretagne ou il fait beau et reBonjour de Bretagne ou il fait beau, bonnes vacances!-Bonjour de Bretagne ou il fait beau et reBonjour de Bretagne ou il fait beau, bonnes vacances!

len V2C.texte : 380

MOT : Bonjour de Bretagne ou il fait beau et reBonjour de Bretagne ou il fait beau, bonnes vacances!

2000000 trouvailles en ---------------78 ms

MOT : Bon
len V2C.texte : 380

4000000 trouvailles en ---------------125 ms

Cordialement, et à +.
Afficher les 115 commentaires