Recherche de mots dans texte explications

Soyez le premier à donner votre avis sur cette source.

Vue 3 122 fois - Téléchargée 796 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

Commenter la réponse de piette

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.