Recherche de mots dans texte explications
piette
Messages postés
68
Date d'inscription
jeudi 11 décembre 2008
Statut
Membre
Dernière intervention
16 juin 2019
-
11 oct. 2015 à 15:16
cs_pseudo3 Messages postés 268 Date d'inscription mardi 24 juillet 2007 Statut Membre Dernière intervention 2 février 2021 - 28 nov. 2015 à 10:58
cs_pseudo3 Messages postés 268 Date d'inscription mardi 24 juillet 2007 Statut Membre Dernière intervention 2 février 2021 - 28 nov. 2015 à 10:58
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/101204-recherche-de-mots-dans-texte-explications
https://codes-sources.commentcamarche.net/source/101204-recherche-de-mots-dans-texte-explications
27 nov. 2015 à 10:24
A+
Modifié par piette le 27/11/2015 à 22:32
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
28 nov. 2015 à 10:58
>> "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 à +.
27 nov. 2015 à 10:22
25 nov. 2015 à 13:42
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 à +.
Modifié par piette le 25/11/2015 à 17:42
je viens de relire ma fonction, je la trouve peu explicite.
Il y a une mauvaise définition de P (Word au lieu de Integer)
Attention il vous faut respecter l'entrée de table suivante:
Table[DerChar,AvantDerChar] pour définir ChercheDans().
J'espère être plus clair ci dessous?
-------------------------------------------------------------
function Fabrique_Sauts(Const mot : ansiString; var Table : TTable_BMH2C): boolean;
//accepte mot avec length(mot) > 65535 char
Type Dummy = array[Char] of Byte;
Const DimLigne = sizeof(Dummy);
DimTable = DimLigne * DimLigne;
MaxWord = high(Word);
var Saut,LenTest : Word;
LM : integer;
begin
Result:=Length(mot) > 2; if not Result then exit;
//calibrage de LenTest si length(mot) est > à MaxWord
LM:=length(mot);
if LM > MaxWord then LenTest:=MaxWord else LenTest:=LM;
//Préparation du fond de table
FillWord(Table,DimTable,LenTest);
//Préparation de la zone Saut 1 C
FillWord(Table[mot[1],#0],DimLigne,Pred(LenTest));
//Calcul des sauts = Table[DerChar,AvantDerChar]
Saut:=LenTest - 2;
for LM := Succ(LM-LenTest) to LM - 2 do
begin
Table[Mot[Succ(LM)],Mot[LM]]:=Saut; dec(Saut);
end;
end;
--------------------------------------------------------------------
concernant vos essais, ne regardez plus R := ChercheDans(V2C) car
il y avait 2 tables (pourquoi faire simple quand on peut faire compliqué?)
lors des 1° essais.
Utilisez donc le programme ci dessous pour tester vos doutes:
--------------------------------------------------------------------
program Demo_cs_pseudo3;
{$APPTYPE CONSOLE}
//IMPORTANT : il faut aciver {$DEFINE VoirBMSauts} dans BMH2CASM
uses
sysutils,
BMH2CASM in '..\BMH2CASM.pas';
var C2 : TreBMH2C;
T,M : string;
R : integer;
procedure montreK(Const BM: PreBMH2C); Pascal;
//affiche la progression de la recherhe
var I : integer;
begin
writeln(BM^.Texte);
for I := 1 to Pred(BM^.rpPosAvantSaut) do write(' ');
write(M,'+',BM^.rpSautBMH);
readln;
end;
procedure demo(tableSaut : boolean = false);
var Mm : integer;
begin
C2.MaxCharForceBrute:=4;
if not C2.pvVoirBMSauts then
begin
writeln('activer la directive de compilation {$DEFINE VoirBMSauts}');
writeln('pour cette demonstration');
readln;
abort;
end;
C2.RappeldeBMH:=montreK; C2.mot:=M; C2.texte:=T;
writeln('length(mot): ',length(M));
if Fab_Sauts(C2) then
Repeat
R:=chercheDans(C2);
if R <> 0 then
begin
writeln;
writeln('trouve:',R,' depuis:',C2.Depuis,' (',C2.infoArevoir,')');
writeln('NB sauts: ',C2.rpNbSauts,' NB recherches mot: ',C2.rpNbrecherchesMot);
Mm:=(C2.volPTexte-C2.volPmot)DIV C2.rpNbSauts;
writeln('avance moyenne: ',Mm,' char par saut ');
C2.rpNbSauts:=0; C2.rpNbrecherchesMot:=0;
writeln;
end;
Until R = 0;
writeln('fin recherche Depuis:',C2.Depuis);
readln;
if tableSaut then visualise_table_mot(C2);
Cloturer(C2);
writeln('==============================================================');
writeln;
end;
begin
// Insérer le code utilisateur ici
writeln('appuyer sur la touche <retour>'); writeln;
writeln('recherche mot dans texte algo BMH 2 chars'); writeln;
//////////////////////////////////////////////////////////////////////
M:='abracaabbra'; //votre mot ici
T:='aaaaaaaaaaaaaaaaaerrdacrababracaabbraxxxxxxxxx'; //votre texte
/////////////////////////////////////////////////////////////////////
init_TreBMH2C(C2);
demo(true);
writeln('fin');
readln;
end.
----------------------------------------------------------------
dans l'exemple ci dessus (voir M et T)
Saut 1 = 4 char
Saut 2 = 4 char
Saut 3 = 11 char
Saut 4 = 7 char et trouve en 27 avec avance moyenne par saut de 8 char.
Je suis sûr que BMH2C ne s'attarde pas à regarder les moutons, il a bien
tort.
j'ai testé Il marchait toujours, rê........... dans zola
voici les infos collectées pour 1° trouvaille:
longueur du mot = 92 char
pos du mot dans zola : 1009684 char
Nombre de sauts = 15248
saut moyen = 68 char soit 73% de la longueur du mot
Il y a eu 30 tentatives d'identification du mot.
Salutations
26 nov. 2015 à 11:32
1) Vous dites "concernant vos essais, ne regardez plus R := ChercheDans(V2C) car
il y avait 2 tables (pourquoi faire simple quand on peut faire compliqué?)
lors des 1° essais.
Utilisez donc le programme ci dessous pour tester vos doutes" :
Depuis mon message d'hier 25 nov. 2015 à 13:42 je n'ai plus aucun doute puisque j'ai écrit "OK avec Fabrique_Sauts ça marche à merveille donc mieux qu'avec Fab_Sauts(var BM: TreBMH2C) qui était utilisée par ChercheDans." et depuis hier j'ai aussi viré ChercheDans et sa table puisque j'utilise maintenant ma routine BMH2E pour les recherches car elle, au moins, j'en comprends son fonctionnement.
Par contre j'utiliserai aussi la function Fabrique_Sauts(Const mot : ansiString; var Table : TTable_BMH2C): boolean; qui accepte mot avec length(mot) > 65535 char
2) Il y a aussi un sujet intéressant à creuser et que je me suis amusé à faire récemment : De la recherche indexée.
J'avais il y a une dizaine d'années pour ma soeur qui collectionne des recettes de cuisine et moi qui collectionne des recettes Delphi, créé une petite appli aide-mémoire qui nous permet de retrouver rapidement dans des fichiers subdivisés chacun en fiches se terminant chacune par un séparateur de fin de fiche, les fiches qui contiennent Mot1 ET/OU Mot2, ça a commencé en utilisant la fonction pos, puis mis à jour avec un Boyer-Moore, et le mois dernier j'ai remplacé ça en indexant chaque paire IndiceFichier, IndiceFiche dans les Objets d'une Stringlist(Mot, Objet) avec Objet =.IndiceFichier, IndiceFiche.
Cela oblige à commencer par extraire le vocabulaire présent dans les fichiers chargés ainsi que la paire IndiceFichier, IndiceFiche associée à chaque Mot et ça ne ralentit qu'un peu le chargement d'un fichier, mais ensuite le résultat des recherches s'affiche en un clin d'oeil puisqu'elles ne s'effectuent que dans la StringList du vocabulaire beaucoup moins volumineux (10 millisecondes pour retrouver Mot1 ET Mot2 placés à la fin d'un fichier de 2 Mo).
Dans un deuxième temps ça oblige aussi à actualiser cette StringList en cas de saisie manuelle, en cas de copier-coller d'une nouvelle fiche et en cas de suppression d'une fiche mais ça s'exécute avant d'avoir pu cligner des yeux.
Comme pour éviter un casse-tête j'ai opté pour la solution-StringList mais il y a certainement des ruses de sioux qui permettraient de faire la même chose plus rapidement.
Je dis ça bien entendu sans vouloir vous pousser dans un 2ième chaudron (lol).
Cordialement, et à +.
Modifié par piette le 27/11/2015 à 01:05
Je ne vous suivrai pas, car je ne comprends même pas le titre!
Je ne pense pas utiliser BMH, j'en ai jamais eu le besoin.
Je recherche souvent des mots de 8 à 10 char dans des phrases d'une
centaine et le pos() amélioré fait cela très bien.
Pour un moment je vais changer de loisir ( sieste ).
Merci pour ces nombreux échanges sympathiques.
Salutations.
27 nov. 2015 à 10:18
A propos de : "Je ne vous suivrai pas, car je ne comprends même pas le titre!" :
Vous ne comprenez pas quel titre ??? vu que je n'ai mis aucun titre
"Pour un moment je vais changer de loisir ( sieste )"
Idéal pour décontracter les neurones.
"Merci pour ces nombreux échanges sympathiques."
De même.
Cordialement et à +.
24 nov. 2015 à 13:58
Oups j'ai validé mon message précédemment trop vite, il faut lire :
Si je cherche le mot : Dahfahrytehfatzdh
dans le texte : xxxxxxxDahfahrytehfatzdhxxxx
et dans la configuration ci-après :
_______Dahfahrytehfatzdh
xxxxxxxxxxxxxxxxxxxxxxDahfahrytehfatzdhxxxx
car c'est dans cette position que le D est exactement sous le h terminal
Cordialement et à +.
Modifié par piette le 25/11/2015 à 00:24
Vous allez pouvoir retourner sur le champs de course avec vos nouveaux poulains à 2 entrées.
Je pense que vous avez intérêt à adopter l'entrée de la table comme suit:
Table[DerChar,AvantDerChar]
car c'est plus rapide et le code plus compact.
Regardez l'unité Fabrique pour vous en convaincre, j'ai relu mon code asm et retranscrit en Pascal. Cette fabrique est adaptée au mot > 65535 char.
-------------------------------------------------------------------------------------------
unit fabrique;
interface
Type TTable_BMH2C = array[char,char] of Word;
function Fabrique_Sauts(Const mot : ansiString; var Table : TTable_BMH2C): boolean;
implementation
procedure fillWord(var X; Count: Integer; Value: Word); Register;
asm
PUSH EDI
MOV EDI,EAX //var X
MOV AX,CX //Value
MOV ECX,EDX //Count
CLD
REP STOSW
POP EDI
end;
function Fabrique_Sauts(Const mot : ansiString; var Table : TTable_BMH2C): boolean;
Const MaxChar = high(Word);
var Saut,P,Nchar : Word;
LM : integer;
begin
Result:=Length(mot) > 2; if not Result then exit;
//calibrage de Nchar au cas ou mot est > à MaxChar
LM:=length(mot);
if LM > MaxChar then Nchar:=MaxChar else Nchar:=LM;
//Préparation du fond de la table
FillWord(Table,sizeof(Table) DIV sizeof(Word),Nchar);
//Préparation de la zone Saut 1 C
FillWord(Table[mot[1],#0],ord(high(Char)),Pred(Nchar));
//Calcul des sauts = Table[DerChar,AvantDerChar]
Saut:=Nchar - 2;
for P := Succ(LM-Nchar) to LM - 2 do
begin
Table[Mot[Succ(P)],Mot[P]]:=Saut; dec(Saut);
end;
end;
-------------------------------------------------------------------------------------------
aplatira aplatira aplatira ????
"Le Boyer-Moore en un saute-mouton qui loupe quelques occurrences.
Reste à trouver une astuce qui évite ceci."
Je ne comprend pas ce que vous m'expliquez? c'est un BMH2C fou que vous me décrivez?
j'ai mis aplatira dans mon programme démo, il est aplati en 1 Saut et ne saute pas les moutons.
"
_aplatira
ooo aplatira ooooo
le saut de 8 - 1 = 7 m'amènera dans la position ci-après :"
EN FAIT LE SAUT EST DE 4 car [la] du texte au dessous du mot coïncidera avec ap[la] du mot
____aplatira --> saut de 4 et trouve
ooo aplatira ooooo
-------------------------------------------------------------------------------------------
program Demo_aplatira;
{$APPTYPE CONSOLE}
//IMPORTANT : il faut aciver {$DEFINE VoirBMSauts} dans BMH2CASM
uses
sysutils,
BMH2CASM in '..\BMH2CASM.pas';
var C2 : TreBMH2C;
T,M : string;
R : integer;
procedure montreK(Const BM: PreBMH2C); Pascal;
//affiche la progression de la recherhe
var I : integer;
begin
writeln(BM^.Texte);
for I := 1 to Pred(BM^.rpPosAvantSaut) do write(' ');
write(M,'+',BM^.rpSautBMH);
readln;
end;
procedure demo(tableSaut : boolean = false);
var Mm : integer;
begin
C2.MaxCharForceBrute:=4;
if not C2.pvVoirBMSauts then
begin
writeln('activer la directive de compilation {$DEFINE VoirBMSauts}');
writeln('pour cette demonstration');
readln;
abort;
end;
C2.RappeldeBMH:=montreK; C2.mot:=M; C2.texte:=T;
writeln('length(mot): ',length(M));
if Fab_Sauts(C2) then
Repeat
R:=chercheDans(C2);
if R <> 0 then
begin
writeln;
writeln('trouve:',R,' depuis:',C2.Depuis,' (',C2.infoArevoir,')');
writeln('NB sauts: ',C2.rpNbSauts,' NB recherches mot: ',C2.rpNbrecherchesMot);
Mm:=(C2.volPTexte-C2.volPmot)DIV C2.rpNbSauts;
writeln('avance moyenne: ',Mm,' char par saut ');
C2.rpNbSauts:=0; C2.rpNbrecherchesMot:=0;
writeln;
end;
Until R = 0;
writeln('fin recherche Depuis:',C2.Depuis);
readln;
if tableSaut then visualise_table_mot(C2);
Cloturer(C2);
writeln('==============================================================');
writeln;
end;
begin
// Insérer le code utilisateur ici
writeln('appuyer sur la touche <retour>'); writeln;
writeln('recherche mot dans texte algo BMH 2 chars'); writeln;
M:='aplatira';
T:='oooooo aplatira ooooo';
init_TreBMH2C(C2);
demo(true);
writeln('fin');
readln;
end.
-------------------------------------------------------------------------------------------
Salutations.
25 nov. 2015 à 00:55
il faut lire :
//Préparation de la zone Saut 1 C
FillWord(Table[mot[1],#0],Succ(ord(high(Char))),Pred(Nchar));
soit la valeur 256
à la place de:
//Préparation de la zone Saut 1 C
FillWord(Table[mot[1],#0],ord(high(Char)),Pred(Nchar));
qui ne représente que 255 alors qu'il y a 256 colonnes dans la ligne
Salutations
25 nov. 2015 à 11:53
>> A propos de "aplatira aplatira aplatira ???? et du saute-moutons :
Je viens d'essayer tout simplement de trouver
le mot : abracaabbra avec de nombreux a intermédiaires
dans le texte : aaaaaaaaaaaaaaaaaerrdacrababracaabbraxxxxxxxxx:
et en utilisant votre ancienne routine R := ChercheDans(V2C) mais qui utilise votre table à deux entrées et ChercheDans ne le trouve pas car les sauts obtenus avec :
C := mot[1];
for Ligne := Low(Char) to High(Char) do Skip2E[Ligne, C] := length(Mot) - 1 qui font bien entendu avancer le mot-coulisant par sauts mais placent celui-ci en des positions successives sans détecter sa présence dans le texte car, :
dans le texte, le mot est précédé par dacrab qui se trouve être une combinaison de caractères présents dans le mot et qui font que l'on ne se trouve jamais dans la configuration ci-après :
_____________________abracaabbra
aaaaaaaaaaaaaaaaaerrdacrababracaabbraxxxxxxxxx
... configuration dans laquelle la "Préparation de la zone Saut 1 C" agit
Même problème si je cherche le même mot dans le texte :
aaaaaaaaaaaaaaaaaabracaabbraxxxxxxxxx
où le mot est précédé par la série de a qui sont identiques au 1ier caractère du Mot.
Mais bon, comme j'ai utilisé ChercheDans(V2C) je vais essayer de voir ce que ça donne avec votre unit fabrique.
Cordialement et à +.
24 nov. 2015 à 13:48
Merci pour votre réponse. En fait je viens de piger le pourquoi du
C := mot[1];
for Ligne := Low(Char) to High(Char) do Skip2E[Ligne, C] := length(Mot) - 1;
Si je cherche le : Dahfahrytehfatzdh
dans le texte : xxxxxxxDahfahrytehfatzdhxxxx
dans la configuration ci-après :
___Dahfahrytehfatzdh
xxxxxxxxxxxxxxxxxxxxxxDahfahrytehfatzdhxxxx
dans cette configuration où le h terminal du mot coulissant se trouve pile au-dessus du D du texte et qui correspond au premier caractère du mot cherché, vu que la table à 2 entrées nécessite de vérifier la concordance simultanée des deux derniers caractères du mot (ici dh) avec les deux chr du texte placés sous lui(ici xD) le saut associé au xD est égal à length(Mot) - Un.ce qui explique qu'avec mon ancienne table je ne trouvais,pas la totalité des mots présents dans le texte de Zola
Et comme la série des x du texte de cet exemple représente n'importe quel chr.il est logique d'affecter la valeur de ce saut à toutes les lignes de la table.
J'ai aussi constaté que dans mon code corrigé avec la mention "correctif de Piette" les quatre lignes suivantes :
Saut := LM - 2;
for P := 1 to Saut do begin
Skip2E[Mot[P], Mot[P + 1]] := Saut; dec(Saut);
end;
sont superflues car elles font la même chose que mon ancien code ... sauf que mon ancien code le faisait avec toute une tartine de lignes alors qu'avec vos quatre lignes le tour est joué : chapeau
En bref il ne ma manquait que ces deux lignes :
C := mot[1];
for Ligne := Low(Char) to High(Char) do Skip2E[Ligne, C] := length(Mot) - 1;
Par contre si maintenant je cherche le mot : aplatira qui contient un a au début et au milieu avec legt(Mot) = 8
dans le texte : ooooo aplatira ooooo
et dans la configuration ci-après :
_____aplatira
oooooo aplatira ooooo
le saut de 8 - 1 = 7 m'amènera dans la position ci-après :
____________aplatira
ooooooo aplatira ooooo
ce qui transforme le Boyer-Moore en un saute-mouton qui loupe quelques occurrences.
Reste à trouver une astuce qui évite ceci...
Cordialement, et à +.
23 nov. 2015 à 15:30
En remplaçant simplement ma table à deux entrées par la vôtre Table_BMH2C(const mot: ansiString; var Table: TTable_BMH2C) mon code de recherche s'est mis à fonctionner correctement.
Puis dans un deuxième temps il a suffit d'ajouter à la fin du code de ma table les 7 lignes (en gras ci-dessus) piquées dans votre code et du coup ma table fonctionne également sauf que j'ai beaucoup de mal à piger ces 7 lignes (lol) C'est quoi cette idée bien rusée ???
(dans ma table ci-dessous les lignes et colonnes sont inversées par rapport aux vôtres)
type tSkip2E = array[char, Char] of Word;
var Skip2E: tSkip2E;
procedure InitSkip2E(const Mot: string; visu: boolean);
var slPaires2Chr: tStringList;
LM, kT, kP, i, j, Index: integer;
c1, c2 : char; // c1 = Chr situé chaque fois à gauche de c2 dans Mot
// Correctif de Piette :
Ligne, C: char;
saut, P: word;
function SautDe(cP, cT: char): Word;
var i: word;
begin
i := LM + 1;
repeat dec(i);
until (i - 1 = 1) or ((Mot[i - 1] = cP) and (Mot[i] = cT));
Result := LM - i; if Result = 0 then Result := LM;
end;
begin
LM := Length(Mot);
//Préparation du fond de la table :
for c2 := low(Char) to high(Char) do begin
for c1 := low(Char) to high(Char) do Skip2E[c1, c2] := LM;
end;
//Extraction des Paires de caractères consécutifs du Mot :
with slPaires2Chr do begin
slPaires2Chr := tStringList.Create; Sorted := true; CaseSensitive := true;
Duplicates := DupIgnore;
end;
for i := 1 to LM - 1 do begin
c1 := Mot[i]; c2 := Mot[i + 1]; //s := c1 + c2;
slPaires2Chr.Add(c1 + c2);
end;
//Calcul du saut associé à chaque Paire de Chr :
for i := 0 to slPaires2Chr.count - 1 do begin
c1 := slPaires2Chr[i][1]; c2 := slPaires2Chr[i][2];
Skip2E[c1, c2] := SautDe(c1, c2);
if visu then begin // Affichage éventuel dans le RichEdit des sauts associés à chaque paire de Chr
trace2('[' + c1 + c2 + ']' + #09 + ' ' + intToStr(SautDe(c1, c2)));
if (c1 = #13) or (c2 = #13) then trace2('#13');
if (c1 = #10) or (c2 = #10) then trace2('#10');
end;
end;
slPaires2Chr.Free;
//Correctif de Piette : Préparation de la zone Saut 1 C
C := mot[1];
for Ligne := Low(Char) to High(Char) do Skip2E[Ligne, C] := LM - 1;
Saut := LM - 2;
for P := 1 to Saut do begin
Skip2E[Mot[P], Mot[P + 1]] := Saut; dec(Saut);
end;
end;
Cordialement, et à +.
24 nov. 2015 à 00:05
Je vous propose d'utiliser le programme DemoVoirSauts.exe
Regardez la 1° démonstration qui utilise le texte et le mot ci-dessous :
M:='OaObOcOO';
T:='------xO-----aO---bO-cO-------bc---'+M+'---';
Ce texte et mot, c'est mon contrôleur, une table à 2 entrées doit trouver M dans T
autrement la table n'est pas efficace.
Avant de faire chaque saut, imaginez ce qu'il se passerait avec une table à une entrée?
Vous trouverez là tout ce qui diffère entre les 2 tables et le pourquoi de
"Préparation de la zone Saut 1 C".
Il est tellement plus plaisant de trouver.
Ce qu'il s'est passé pour moi suite à votre "pression!".
Dans un prochain courrier je vous communiquerai la règle a observer pour fabriquer cette
table à 2 entrées.
Salutations
22 nov. 2015 à 16:40
J'ai comparé vos sauts aux miens et j'y trouve une bizarrerie :
A) Vos sauts obtenus avec Visualise_table (V2C)
FICHIER A 2 ENTREES
Masque = char1 dans colonne char2 dans ligne 0=inconnus
table [0..12,0..12] of Word
Mot:[Hello World Bonjour] longueur = 19 chars et 12 chars différents
0 H B W d e j l n o r u
0 19 19 19 19 19 19 19 19 19 19 19 19 19
H 18 18 18 18 18 18 18 18 18 18 18 18 18 <- Pourquoi ces sauts de 18 ?
19 19 19 19 19 07 19 19 19 19 13 19 19
B 19 19 06 19 19 19 19 19 19 19 19 19 19
W 19 19 12 19 19 19 19 19 19 19 19 19 19
d 19 19 19 19 19 19 19 19 08 19 19 19 19
e 19 17 19 19 19 19 19 19 19 19 19 19 19
j 19 19 19 19 19 19 19 19 19 03 19 19 19
l 19 19 19 19 19 19 16 19 15 19 19 09 19
n 19 19 19 19 19 19 19 19 19 19 04 19 19
o 19 19 19 05 11 19 19 02 14 19 19 19 19
r 19 19 19 19 19 19 19 19 19 19 10 19 19
u 19 19 19 19 19 19 19 19 19 19 01 19 19 <- OK pour les sauts de 19 et les autres
Char1-colonne = chr de gauche dans SubStr et char2 = celui à sa droite
B)Mes sauts à moi pour [Hello World Bonjour]
[ B] 6
[ W] 12
[Bo] 5
[d ] 7
[el] 16
[He] 17
[jo] 2
[ld] 8
[ll] 15
[lo] 14
[nj] 3
[o ] 13
[on] 4
[or] 10
[ou] 1
[rl] 9
[ur] 19
[Wo] 11
Mise à part la ligne des sauts de 18 j'ai des résultats identiques aux vôtres mais les 18 je ne pige pas.
Cordialement, et à +.
22 nov. 2015 à 19:24
J'ai écrit le code que vous me demandez car je n'ai rien gardé de nos échanges.
Pour ne pas alourdir cette réponse je vous proposerai ensuite de rentrer dans le détail de la fabrication de cette table dans une autre réponse.
La procédure Table_BMH2C est pour vous.
le passage suivant :
//Préparation de la zone Saut 1 C
C:=mot[1];
for Colonne:=Low(Char) to High(Char) do Table[C,Colonne]:=Pred(Length(mot));
est le plus difficile à trouver et mettre au point (pas le code mais l'idée)!!! J'en avais fait part dans nos échanges.
program table2entreesPascal;
{$APPTYPE CONSOLE}
{ fabrication de la table de sauts BMH2C avec la procédure Table_BMH2C à partir
de Mot.
1° une table est fabriquer en ASM afin d'initialiser Paquet
2° une autre table est fabriquer avec Table_BMH2C
3° les pointeurs des 2 tables sont échangés ce qui permet d'utiliser les
outils de visualisation dépendant de Paquet
}
uses
sysutils,Dialogs,
BMH2CASM in '..\BMH2Casm.pas';
/////////FABRICATION DE LA TABLE A 2 ENTREES DES SAUTS/////////////////////////
Type TTable_BMH2C = array[char,char] of Word;
Procedure Table_BMH2C(Const mot : ansiString; var Table : TTable_BMH2C);
var Ligne,Colonne,C : Char;
Saut,P : Word;
begin
if Length(Mot) < 3 then
Begin ShowMessage('Le mot doit avoir 3 char mini'); abort; end;
//Préparation du fond de la table
for Ligne:=Low(Char) to High(Char) do
for Colonne:=Low(char) to High(Char) do Table[Ligne,Colonne]:=length(mot);
//Préparation de la zone Saut 1 C
C:=mot[1];
for Colonne:=Low(Char) to High(Char) do Table[C,Colonne]:=Pred(Length(mot));
//Calcul des sauts = Table[DerChar,AvantDerChar]
Saut:=Length(mot)-2;
for P := 1 to Saut do
begin
Table[Mot[Succ(P)],Mot[P]]:=Saut; dec(Saut);
end;
end;
////////////////////////////////////////////////////////////////////////////////
var Mot : AnsiString;
Paquet : TreBMH2C;
Table : TTable_BMH2C;
Sauve : TPar2chars;
begin
// fabrication de la table à 2 entrées en Pascal
Mot:='tabledeuxentrees'; //doit être > 4 char pour déclencher BMH2C
//création de la table en ASM afin de préparer les drapeaux dans Paquet
init_TreBMH2c(Paquet); //initialisation
Paquet.MaxCharForceBrute:=ctMiniBMH2C; // force BMH2C
Paquet.mot:=Mot;
writeln('le mot de test est : ',Paquet.mot);
if Fab_sauts(Paquet) then
if not Paquet.pvForceBrute then
begin
//----------------------------------------------------------------
Table_BMH2C(Mot,Table); //ici fabrication de la table en Pascal
//----------------------------------------------------------------
//échange des pointeurs la Table Pascal Remplace la Table ASM
Sauve:=Paquet.pvPar2chars; Paquet.pvPar2chars:=@Table;
writeln('table de sauts');
visualise_table_mot(Paquet); //en fait visualise la table Pascal
write('appuyer sur enter pour suite'); readln;
writeln('liste des sauts');
Liste_Sauts_BMH2C(Paquet); //toujours la table Pascal
Paquet.pvPar2chars:=sauve; //restitution du pointeur pour la cloture
end else ShowMessage('Placer ctMiniBMH2C dans MaxCharForceBrute');
cloturer(Paquet);
end.
23 nov. 2015 à 10:44
Ok, mille fois merci.
Cordialement, et à +.
20 nov. 2015 à 13:29
Cela fait un moment que cette histoire de table de sauts à 2 entrées m'intrique.
Et pire encore car malgré vos explications je n'ai toujours pas pigé comment elle fonctionne..
Pour simplifier, et y voir plus clair, vous serait-il possible de fournir une version Pascal de code qui initialise cette table à deux entrées S.V.P (car je suis nul en ASM).
Il me semble que vous en aviez fourni une dans cette discussion : http://codes-sources.commentcamarche.net/forum/affich-10050229-amelioration-de-la-fonction-pos , mais quand on clique sur Afficher les 115 commentaires on n'en retrouve que cinq.
Cordialement, et à +.
21 nov. 2015 à 18:53
-Comme vous je suis intrigué, n'oubliez pas que c'est vous qui m'avez poussé
dans le chaudron à double entrée.Tranquilement avec le tuto de KR85 j'allignais quelques
codes en force brute (je ne connaissais même pas cette expression associée aux codes!)...
-Il est possible de voir tous les messages mais il faut insister:
Clicker une 1° fois sur "Afficher les 115 commentaires"
puis ensuite une seconde fois être patient,
puis une 3° fois attendre et c'est bon.
Le début de discussion de la table à double entrée commence ici ---->
piette 27 juin 2015 à 16:41
Je vous livre une version à 2 chars qui fonctionne bien (à tester plus profondément).
Il y avait une difficulté avec le masque à deux chars en particulier le second char,
j'ai résolu ceci sans test en modifiant la table (que l'on peut voir).
Je fais ceci avec D5 (qui ne veut plus dépasser XP).
j'utilise W8+OracleVirtualBox+XP
-----------------------------------------------------------------------
unit _T2charsCL;
//recherche type BMH avec 2 caractéres 1° char=colonne 2° char=ligne
interface
uses SysUtils;
Const ctNchar = 255;
type
TarNchar = array[0..ctNchar] of Byte;
Tar2chars = array[0..ctNchar*ctNchar] of Word;
TPar2chars = ^Tar2chars;
T2chars = class(Tobject)
private
arNchar : TarNchar;
Par2chars : TPar2chars;
SubSTR : string;
LsubSTR,Nlignes : Word;
Volar2chars : integer; // en octets
procedure visualise_table;
public
Ndiff : Byte; //Nb char différents
function Fab_Sauts(Const Mot : string): boolean; //Mot = 2 char mini
function chercheDans(Const Texte : string; var Depuis: Cardinal; jusqua: Cardinal=0) : integer;
Destructor Destroy; override;
end;
implementation
{ T2chars }
procedure fillWord(var X; Count: Integer; Value: Word); Register;
asm
PUSH EDI
MOV EDI,EAX //var X
MOV AX,CX //Value
MOV ECX,EDX //Count
CLD
REP STOSW
POP EDI
end;
destructor T2chars.Destroy;
begin
if Par2chars <> NIL then FreeMem(Par2chars,Volar2chars);
inherited;
end;
function T2chars.Fab_Sauts(const Mot: string): boolean;
var I : integer;
begin
Result:=length(Mot) > 1; if not Result then exit;
SubSTR:=Mot; LsubSTR:=length(SubSTR);
fillchar(arNchar,succ(ctNchar),0);
//comptage Nb lettres <>
for I := 1 to LsubSTR do arNchar[ord(SubSTR[I])]:=1;
Ndiff:=1;
for I := 0 to Pred(ord(SubSTR[1])) do if arNchar[I] <> 0 then
begin inc(Ndiff); arNchar[I]:=Ndiff; end;
for I := Succ(ord(SubSTR[1])) to ctNchar do if arNchar[I] <> 0 then
begin inc(Ndiff); arNchar[I]:=Ndiff; end;
Nlignes:=Succ(Ndiff);
if Par2chars <> NIL then FreeMem(Par2chars,Volar2chars);
Volar2chars:=(Nlignes*Nlignes*sizeof(Word));
GetMem(Par2chars,Volar2chars);
fillWord(Par2chars^,Nlignes*Nlignes,LsubSTR);
fillWord(Par2chars^,Nlignes*2,Pred(LsubSTR));
//remplissage de la table
for I := 1 to LsubSTR-2 do
Par2chars^[arNchar[ord(subSTR[I])]+
arNchar[ord(subSTR[Succ(I)])]*Nlignes]:=Pred(LSubSTR)-I;
//visualise_table;
end;
function T2chars.chercheDans(const Texte: string; var Depuis: Cardinal; jusqua: Cardinal=0): integer;
var LT,P,I,K : integer;
begin
Result:=0; LT:=length(Texte);
if (Jusqua > Depuis) and (jusqua < LT) then LT:=jusqua;
K:=0; K:=Pred(Depuis);
while (LsubSTR+K)<= LT do
begin
P:=LsubSTR;
Repeat
if SubSTR[P]=Texte[P+K] then dec(P) else P:=-1;
Until P <= 0;
if P = 0 then
begin Result:=Succ(K); Depuis:=Result+LsubSTR; exit; end; //trouve
K:=K+Par2chars^[arNchar[ord(Texte[Pred(LsubSTR)+K])]+
arNchar[ord(Texte[LsubSTR+K])]*Nlignes];
end;
end;
procedure T2chars.visualise_table;
var I,J : integer;
S : string;
function A2(W:Word): string;
begin
Result:=intToSTR(W); if length(Result) = 1 then Result:='0'+Result;
end;
begin
writeln('Masque = char1 dans colonne char2 dans ligne 0=inconnus');
writeln(SubSTR); writeln(Ndiff,' chars'); SetLength(S,Ndiff);
for I := 0 to ctNchar do if arNchar[I] <> 0 then S[arNchar[I]]:=chr(I);
write(' 0 ');
for I := 1 to Ndiff do write(S[I],' '); writeln;
//scrute table
for I := 0 to Ndiff do
Begin
if I = 0 then write('0 ') else write(S[I],' ');
for J := 0 to Ndiff do
write(A2(Par2chars^[I*Nlignes+J]),' ');
writeln;
end;
readln;
end;
end.
Puis le testeur avec explication du dernier char du maque:
---------------------------------------------------------------------------------
program test_2charsCL;
{$APPTYPE CONSOLE}
uses
sysutils,windows,
_T2charsCL in '_T2charsCL.pas';
var v2c : T2chars;
I,N: integer;
D,J : Cardinal;
SubSTR , STR : string;
G:longInt;
Function MyGetTickCount: Int64;
Var
lpPerformanceCount,
lpFrequency : Int64;
Begin
If Not QueryPerformanceCounter(lpPerformanceCount) Then
lpPerformanceCount := GetTickCount Else
Begin
QueryPerformanceFrequency(lpFrequency);
lpPerformanceCount := (lpPerformanceCount * 1000) Div lpFrequency
End;
result := lpPerformanceCount;
End;
begin
// Insérer le code utilisateur ici
V2C:=T2chars.Create;
SubSTR:='-xEabc';
V2C.Fab_Sauts(SubSTR);
//PARTICULARITES DU TRAITEMENT SECOND CHAR DU MASQUE
//masque W- : Masque inconnu dans SubSTR mais second char peut être connu
// comme ici donc saut: len-1
D:=5; J:=11;
write('pos:',V2C.chercheDans('-xEaW-xEabc',D,J)); writeln(' D:',D);
//masque E- : Masuqe avec lettres connus dans subSTR mais dans mauvais ordre avec
// second char = début de SubSTR donc saut : len-1
D:=4;
write('pos:',V2C.chercheDans('-xEaE-xEabc',D)); writeln(' D:',D);
//masque bx : Masque avec lettres connus mais second char différent du premier
//de subSTR donc saut : len
D:=2;
write('pos:',V2C.chercheDans('xEabEx-xEabc',D)); writeln(' D:',D);
SubSTR:='Bonjour de Bretagne ou il fait beau';
SubSTR:=SubSTR+' et re'+SubStr+', bonnes vacances';
writeln('len SubSTR : ',length(SubSTR));
if V2C.Fab_Sauts(SubSTR) then
begin
SubSTR:='-'+SubSTR+'-'+SubSTR+'-'+SubSTR+'-'+SubSTR;
writeln('len STR : ',length(SubSTR));
N:=0;
G:=MyGetTickCount;
for I := 1 to 1000000 do
begin
D:=1; while V2C.chercheDans(SubSTR,D) <> 0 do inc(N);
end;
G:=MyGetTickCount-G;
writeln(N,' trouvailles en ',G,' ms');
end;
readln;
V2C.Free;
end.
Salutations
22 nov. 2015 à 14:24
Je m'apprêtais à vous dire qu'entre temps j'ai retrouvé le code Pascal de Fab_Sauts(var BM: TreBMH2C) : mille excuses de vous avoir dérangé pour cela.
Par contre, à propos de "-Il est possible de voir tous les messages mais il faut insister:
Clicker une 1° fois sur "Afficher les 115 commentaires"
puis ensuite une seconde fois être patient,
puis une 3° fois attendre et c'est bon." :
En fait j'ai retrouvé le code en suivant les instructions de KR85 : il suffit de se connecter avant de pénétrer dans la page concernant un code (bouton situé en haut et à droite : il suffit de s'identifier et d'entrer son mot de passe)
A propos de "-Comme vous je suis intrigué, n'oubliez pas que c'est vous qui m'avez poussé dans le chaudron à double entrée." :
Je ne pense quand même pas que vous soyez intrigué au sujet de la compréhension du fonctionnement de votre code et de sa table à double entée comme c'est mon cas. Pour le reste j'admets vous avoir un peu poussé dans ce chaudron. J'ai essayé de mettre au point une routine de recherche avec une table à deux entrées pour apprécier les gains mais elle ne détecte pas encore la SubStr recherchée dans toutes les positions où elle est présente dans le texte (lol) donc inutile pour l'instant de faire des tests comparatifs de gains .. et je galère pour en trouver la cause...donc silence radio pour un moment...
Cordialement, merci, et à +.
11 oct. 2015 à 19:36
Au lieu de calculer les sauts sur 1 seul caractère, on les calcule sur les combinaisons d'un caractère avec les autres possibles dans le mot. Il me semblait bien qu'un énorme concept d'anticipation des sauts était sous-jacent dans le fameux tableau à double entrée (je l'avais demandé dans un autre post, merci pour l'explication)... GENIAL, cela mériterait de s'appeler "Boyer-Moore-Piette".
L'inconvénient (mineur grâce à l'asm), c'est l'alourdissement du temps de calcul du tableau des sauts.
Chapeau !
12 oct. 2015 à 15:10
Cela dépend de la configuration du tableau, les tableaux avec 2^n positions sont favorables en vitesse de
calcul et si vous coïncidez vos entrées avec la position de celles-ci dans le registre c'est le même temps
d'accés pour un tableau à 2 ou 1 entrée
- Ci dessous:
Au début ESI pointe le texte et charge 4 char dans EAX, à la fin EAX contient la valeur du saut
ci dessous extrait du programme ligne 504, c'est le calcul d'accès à la table 2 entrées.
MOV EAX,[ESI]
CMP EAX,ECX
JE test l'entier du mot
XOR AX,AX
SHR EAX,$F
MOVZX EAX,WORD ptr[EDX+EAX]
ADD ESI,EAX //saut
ci dessous code pour l'accès d'une table de longInt à 1 entrée.
MOV EAX,[ESI]
CMP EAX,ECX
JE test l'entier du mot
SHR EAX,$18
SHL EAX,$2
MOVZX EAX,WORD ptr[EDX+EAX]
ADD ESI,EAX //saut
C'est très certainement le même temps (horloge) de calcul.
La différence entre l'utilisation de ces 2 types de table c'est l'espace utilisé:
C'est le choix classique entre rapidité et occupation de l'espace.
Salutations
17 oct. 2015 à 18:41
Et vous possédez une sacrée maîtrise des manipulations calculatoires sur bits. Moi-même je n'aurais jamais songé à cela. N'est-ce pas bien l'ASM quand un problème est bien posé et bien solutionné ?
Certes 256² x 2 octets c'est beaucoup plus que 256 x 4 ; quand les machines n'avaient que 64 ko de Ram, c'était rédhibitoire, maintenant c'est peanuts !
Encore bravo. Génial...
Salutations