Recherche de mots dans texte explications

Soyez le premier à donner votre avis sur cette source.

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

Rekin85
Messages postés
25
Date d'inscription
dimanche 11 décembre 2011
Statut
Membre
Dernière intervention
17 octobre 2015
-
Bien vu ! Piette... ENORME !

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 !
piette
Messages postés
68
Date d'inscription
jeudi 11 décembre 2008
Statut
Membre
Dernière intervention
16 juin 2019
> Rekin85
Messages postés
25
Date d'inscription
dimanche 11 décembre 2011
Statut
Membre
Dernière intervention
17 octobre 2015
-
"L'inconvénient (mineur grâce à l'asm), c'est l'alourdissement du temps de calcul du tableau des sauts."

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é:
  • 1024 octets pour 1 entrée (array[0..255)f LongInt)
  • 131072 octets pour 2 entrées (array[0..255,0..255] of Word)


C'est le choix classique entre rapidité et occupation de l'espace.
Salutations
Rekin85
Messages postés
25
Date d'inscription
dimanche 11 décembre 2011
Statut
Membre
Dernière intervention
17 octobre 2015
> piette
Messages postés
68
Date d'inscription
jeudi 11 décembre 2008
Statut
Membre
Dernière intervention
16 juin 2019
-
Là, j'admire tout pantois... Dans mon ancien métier, on admettait qu'un jour l'élève finisse par dépasser le maître. C'est le cas, et pas seulement d'une tête. Chapeau !

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
Bonjour,

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 à +.
piette
Messages postés
68
Date d'inscription
jeudi 11 décembre 2008
Statut
Membre
Dernière intervention
16 juin 2019
> cs_pseudo3 -
Bonsoir,

-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

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.