StrPos façon Boyer-Moore et tolérant à fautes de frappes Corrigé
Soyez le premier à donner votre avis sur cette source.
Vue 6 076 fois - Téléchargée 2 184 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).
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
- StrPos façon Boyer-Moore et tolérant à fautes de frappes Corrigé
- Strpos ✓ - Forum PHP
- Boyer moore - Forum C++ & C++ .NET
- Faute de syntaxe ✓ - Forum VB.NET
- Qcm javascript corrigé pdf - Forum Javascript / DHTML
- Jeu de la vie corrigé python - Forum Python
23 sept. 2015 à 18:50
Salutations
23 sept. 2015 à 10:17
Merci pour votre compliment.
Cordialement.
23 sept. 2015 à 10:16
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.
21 sept. 2015 à 23:40
superbe présentation.
Bonne vélocité.
Bravo
Salutations
15 août 2015 à 21:03
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.