StrPos façon Boyer-Moore et tolérant à fautes de frappes Corrigé

Soyez le premier à donner votre avis sur cette source.

Vue 4 865 fois - Téléchargée 1 953 fois

Description

Quand on cherche dans un ensemble de textes par exemple la sous-chaîne « Yellow submarine » et que certains textes contiennent « Yrllow submarine » d'autres « Yellow submaribe » etc, ces fautes de frappe ont comme conséquence qu'en utilisant des fonctions telles que Pos ou PosEX celles-ci ne reconnaissent pas ces occurrences et on loupe complètement les informations contenues dans ces textes à cause de simples erreurs de frappe.
Pour détecter quand même de telles occurrences le code ci-joint propose la fonction tPosBMHTolerant.BMH_C6T qui tolère un certain nombre d'erreurs de frappe susceptibles d'être présentes dans des sous-chaînes de plus de 6 Chr.
A cet effet son algo est basé sur l'utilisation d'un pochoir-coulissant de longueur égale à celle de la sous-chaîne cherchée et percée de « 6 trous » représentés par les O ci-après OxxxxOxxxOxxxOxxxOxxxO qui se déplace le long du texte et qui reconnaît la présence de l'occurence cherchée dès lors qu'il y a concordance entre les Chr des « 6 trous » et les Chr correspondants du texte dans la position couante du coulisseau.
La fiabilité d'un tel algo est plus qu'excellente car : Si je cherche Mot1, la probabilité qu'il existe un Mot2 qui a simultanément :
- le même Chr terminal,
- et le même Premier Chr,
- et le même Chr sous le Deuxième Trou,
- et le même Chr sous le Troisième Trou,
- et le même Chr sous le Quatrième Trou,
- et le même Chr sous le Cinquième Trou,
- et epacé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 le reste l'algo fonctionne comme l'algo basique du type Boyer-Moore-Horspool en utilisant une Table de Sauts)

Pour l'ensemble des 6 trous la probabilité précitée est de (1/255)^6 = 3,6 x 10^(-15) et cette valeur est encore réduite par la condition d'espacement des Chr, autrement dit le risque de ratisser une occurrence parasite est quasiment improbable dans le cas de recherche d'un Mot ou d'une Prase d'un langage courant dans du Texte ... sans oublier qu'il vaut mieux récupérer une occurrence parasite que d'en louper une intéressante.
Comme le nombre de « trous » du coulisseau est constant, la longueur des zones de tolérance aux erreurs de frappe est croissante à partir de 7 Chr et la tolérance peut être augmentée avec l'option qui convertit les seuls Chr testés en Majuscules Non Accentuées MNA.

Eviter toutefois d'utiliser un tel algo dans le 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 : utiliser un algo « exhaustif » tel que PosEx.
Cette 2ième version annule et remplace celle du 22/07/2015

Mise à jour du 11/08/2015 : Ajout du pré-calibrage optionnel des string's de recherche qui débarrasse leur copie de caractères surabondants :
- Pré-calibrage « Léger » : qui remplace des rafales d'Espaces, de Tabulations, Ponctuations, et de Parenthèses par un(e) seul(e),
-.Pré-calibrage « Fort » : qui remplace toute salve de caractères autres que numériques par un seul,
- Avec option « CRLF » : qui élimine toutes les lignes vides.

Mise à jour du 16/08/2015 : Amélioration permettant à l'utilisateur de personnaliser le pré-calibrage précité.

Mise à jour du 21/08/2015 : Amélioration de la vitesse d'exécution de la routine CalibrerStr() de l'unit uDivers utilisable pour le pré-calibrage optionnel des string's de recherche (vitesse environ doublée avec les options proposées par défaut).

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

> thomas_94
Bonjour Thomas_94,

Merci pour votre compliment.

Cordialement.
Messages postés
270
Date d'inscription
mardi 24 juillet 2007
Statut
Membre
Dernière intervention
7 juin 2018

Bonjour,

Une amélioration consisterait à "calibrer" au préalable la SubString ainsi que le Texte de recherche afin d'y remplacer par un Chr "Espace" = #32 unique toute séquence de Chr consécutifs d'Espaces, de Chr de Tabulation et de Chr de Ponctuation car même en l'absence de faute de frappe il suffit que la SubString recherchée soit présente dans le Texte mais contienne par exemple un double Espace alors que la SubString n'en contient qu'un et l'occurrence bien que présente ne serait pas détectée. (ni avec PosEx, ni avec Boyer-Moore)
Comme cette amélioration qualitative s'accompagnerait d'une perte de vitesse il faudrait peser "le pour et le contre" pour trancher entre "priorité à la qualité" ou "à la vitesse" mais il pourrait s'agir d'une option.

Cordialement, et à +.
Messages postés
68
Date d'inscription
jeudi 11 décembre 2008
Statut
Membre
Dernière intervention
16 juin 2019
>
Messages postés
270
Date d'inscription
mardi 24 juillet 2007
Statut
Membre
Dernière intervention
7 juin 2018

Bonsoir,
superbe présentation.
Bonne vélocité.
Bravo
Salutations
>
Messages postés
68
Date d'inscription
jeudi 11 décembre 2008
Statut
Membre
Dernière intervention
16 juin 2019

Bonjour Piette,

Merci pour vos compliments.
Quand j'aurai terminé avec le pain que j'ai sur la planche, je testerai votre "Recherche de mots dans texte".
En attendant rien ne vous interdit de publier une version ASM de "StrPos façon Boyer-Moore et tolérant à fautes de frappes" cela ferait avancer schmillblick...

Cordialement.
Afficher les 10 commentaires

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.