Recherche de mots dans texte explications

Messages postés
68
Date d'inscription
jeudi 11 décembre 2008
Statut
Membre
Dernière intervention
16 juin 2019
- - Dernière réponse : cs_pseudo3
Messages postés
270
Date d'inscription
mardi 24 juillet 2007
Statut
Membre
Dernière intervention
7 juin 2018
- 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

Afficher la suite 
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