Recherche de mots dans texte explications

Soyez le premier à donner votre avis sur cette source.

Vue 4 004 fois - Téléchargée 963 fois

Description

Recherche de mots dans texte explications:
Recherche de mots dans un texte version inspirée de algorithme Boyer Moore,
(voir https://fr.wikipedia.org/wiki/Algorithme_de_Boyer-Moore).

-Le programme (BMH2Casm.pas) reprend cet algorithme avec une petite modification concernant la
fabrication de la table de sauts.
La table de sauts utilisée ici est une table à 2 entrées.
Les 2 derniers caractères du texte au dessus du mot serviront à calculer si besoin le saut à effectuer.
Cela permet d'avoir une table plus importante et donc de fournir des sauts plus longs à l'intérieur du mot,
(par mot il faut comprendre collection de caractères).

Par exemple avec la table à 2 entrées:
En prenant les 200 premiers caractères d'un texte pour former un mot, les caractères différents sont au nombre
de 47. Le nombre de sauts possible associé aux 2 derniers caractères est de 131.
Dans le texte prenons par exemple le caractère [e]. Suivant ce qui le précède il y a 8 sauts possibles à l'intérieur du
mot, des sauts de 3 à 81 char, et 200 char si le caractère pécédent le [e] n'est pas compris dans les 47 du mot.

Avec la table à une entrée le caractère [e] produit un saut de 3 char, pas plus.
La vitesse de lecture du texte pour trouver un mot est donc plus rapide et d'autant plus rapide que le mot
est composé d'un grand nombre de caractères.

Les 200 caractères sont empreintés à Zola1Mo.txt mis à disposition par cs_pseudo3 :
(http://codes-sources.commentcamarche.net/source/101107-strpos-facon-boyer-moore-et-tolerant-a-fautes-de-frappes-corrige)

Le programme Demo_VoirSauts.dpr visualise les sauts d'un mot dans un texte.
Suivant les modes suivants:
  • Recherche Binaire
  • Recherche sans différence entre MAJ/min
  • Recherche sans différence entre MAJ/min et contrôle du début,milieu et fin du mot
  • Recherche sans différence entre les accents
  • Recherche sans différnce entre les accents et MAJ/min


UNIT CHERCHEMOT :
l'objet TchercheMot encapsule les fonctions de BMH2Casm.pas.
Un exemple d'utilisation montre comment retrouver un mot contenu dans une des lignes d'un fichier texte.
Une partie du mot (en fait un bout de phrase) est proposé pour la recherche.
voir : MotDansLigne.Dpr

PERFORMANCES:
la performance dépend de la longueur du mot recherché, par exemple:
un texte aléatoire de 1 Mo sera exploré 3000 fois en 1300 m/s sans utilisation de la table de sauts et peu importe la
longueur du mot.
Le même texte exploré dans les mêmes conditions le sera en 1300 m/s avec un mot de 13 char et
en 27 m/s avec un mot de 1300 char.
(utilsation de performance.dpr).

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

cs_pseudo3
Messages postés
270
Date d'inscription
mardi 24 juillet 2007
Statut
Membre
Dernière intervention
7 juin 2018
-
4/5 bien que le tour de force mériterait 5/5 (moins un point à cause de la tristesse des applications console : retour à l'époque du DOS)

A+
piette
Messages postés
68
Date d'inscription
jeudi 11 décembre 2008
Statut
Membre
Dernière intervention
16 juin 2019
> cs_pseudo3
Messages postés
270
Date d'inscription
mardi 24 juillet 2007
Statut
Membre
Dernière intervention
7 juin 2018
-
Bonsoir,
Je n'ai rien compris à votre proposition parce qu'il n'y a pas de titre!
Un de mes exemples repond à ce que vous recherchez?
Mais dans un temps > à un clignotement d'œil.
Le DOS, quelle époque joyeuse il était possible de s'interrompre tous les
21h.

Salutations
cs_pseudo3
Messages postés
270
Date d'inscription
mardi 24 juillet 2007
Statut
Membre
Dernière intervention
7 juin 2018
> piette
Messages postés
68
Date d'inscription
jeudi 11 décembre 2008
Statut
Membre
Dernière intervention
16 juin 2019
-
Bonjour,

>> "Je n'ai rien compris à votre proposition parce qu'il n'y a pas de titre! "
En fait la proposition de mon paragraphe 2 qui concerne la "recherche indexée" consiste tout simplement à extraire d'un ensemble volumineux de textes le sous-ensemble du vocabulaire présent dans tous ces textes et de lier chacun des mots de ce vocabulaire à la liste des indices des positions où ce mot est présent dans un ou plusieurs de ces textes. Même dans le cas de textes volumineux, s'ils sont rédigés dans la même langue le sous-ensemble du vocabulaire utilisé étant forcément beaucoup moins volumineux que l'ensemble des textes ... et pour retrouver la position du Mot = "MonTruc" dans tous les textes il suffit de la chercher dans le sous-ensemble au lieu de parcourir inlassablement l'ensemble volumineux des textes.

En bref, pour ma part j'ai utilisé :
- pour le vocabulaire : SLVoc := TStringList.Create : triée et avec DupIgnore,
- pour chaque liste de positions : SLPos := TStringList.Create,
- puis SLVoc .AddObject('MonMot', SLPos);
- ensuite en accédant à l'objet SLPos on l'alimente avec les positions de 'MonMot' dans les textes de la collection : SLPos.Add(intToStr(IndiceFichier) + ':'+intToStr(IndicePositionMot)),
- et ensuite pour retrouver les positions de 'MonMot' je n'ai plus qu'à parcourir ma StringList au lieu de ramer dans la collection de textes.

Les gains de vitesse sont intéressants lorsque on effectue très fréquemment des recherches dans le même ensemble de textes comme dans l'exemple des recettes de cuisine de ma sœur car une fois que cette StringList est créée il ne reste plus qu'à gérer les modifications : ajout, suppression, retouche d'une recette ce qui s'exécute encore plus vite que la création et l'alimentation d'initialisation de la StringList.

>> "Un de mes exemples répond à ce que vous recherchez? " :
Non, vu que j'ai déjà créé mon application.
J'avais simplement évoqué la recherche indexée ayant cru que vous êtes passionné par le sujet des recherches et vous suggérer une idée vu qu'avec Delphi on peut obtenir le même résultat avec "36" codes tous différents.
(exemple au lieu d'utiliser une StringList on peut obtenir les mêmes résultats avec une ObjectList, et j'en oublie les autres solutions).

>> "Le DOS, quelle époque joyeuse il était possible de s'interrompre tous les 21h"
Ou bien d'y passer sa nuit, en essayant de s'en sortir avec la lenteur et 64 Ko de mémoire vive !!!

Cordialement, et à +.
cs_pseudo3
Messages postés
270
Date d'inscription
mardi 24 juillet 2007
Statut
Membre
Dernière intervention
7 juin 2018
-
4/5 bien que le tour de force mériterait 5/5 (moins un point à cause de la tristesse des applications console : retour à l'époque du DOS)
cs_pseudo3
Messages postés
270
Date d'inscription
mardi 24 juillet 2007
Statut
Membre
Dernière intervention
7 juin 2018
-
Re-salut,

OK avec Fabrique_Sauts ça marche à merveille donc mieux qu'avec Fab_Sauts(var BM: TreBMH2C) qui était utilisée par ChercheDans.

Gain de vitesse appréciable notamment dans le cas de recherche d'un bout de phrase relativement long :

Résultats comparatifs pour la recherche de "Il marchait toujours, rêvassant, battant de sa canne de cornouiller les cailloux de la route" dans le texte ZOla1Mo.txt :

- Avec BMH2E : Trouvé : 10000 fois, Mis : 468 ms pour nb-Recherches = 5000 (Sans conversion MNA) (Sans pré-calibrage)
- Avec BMHPascalNaif : Trouvé : 10000 fois, Mis : 1389 ms pour nb-Recherches = 5000 (Sans conversion MNA) (Sans pré-calibrage)
- Avec PosEx : Trouvé : 10000 fois, Mis : 6490 ms pour nb-Recherches = 5000 (Sans conversion MNA) (Sans pré-calibrage)
- Avec PosBMHTol.BMH_C6T : Trouvé : 10000 fois, Mis : 1107 ms pour nb-Recherches = 5000 (Sans conversion MNA) (Sans pré-calibrage)

BMH2E utilise la table à 2 entrées de Fabrique_Sauts..

A côté d'elle PosEx (13,86 fois plus lente) semble rester coincée des ses starting-blocs (lol)

Code de la BMH2E :

function BMH2E(const Mot, Texte: AnsiString; var Depuis: longWord): boolean;
var im, it, ik, LM, LT: integer;
begin
Result := false; LM := Length(Mot); LT := length(Texte);
if (LM < 3) or (LT = 0) then EXIT;
ik := Depuis + LM - 1;
repeat
it := ik;
im := LM;
if (Texte[it] = Mot[im]) and (Texte[it - 1] = Mot[im - 1]) then begin // Si concordance sur 2 derniers caractères alors vérification à reculons
dec(it, 2); dec(im, 2);
repeat
Dec(im);
Dec(it);
until (im = 0) or (Texte[it] <> Mot[im]);
if im = 0 then begin
Result := true; Depuis := it; EXIT; // Occurrence Trouvée
end;
end;
Inc(ik,Table[Texte[ik], Texte[ik - 1]]);
Result := false;
until ik > LT;
Result := false; Depuis := 0;
end; // BMH2E

En tous cas : mille fois merci pour Fabrique_Sauts

Cordialement, et à +.

Vous n'êtes pas encore membre ?

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

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

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

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