Bonjour,

Mes amis, j'ai besoin d'un test de confirmation. J'ai voulu, comme beaucoup d'autres, implémenter MA version de l'algorithme de Boyer-Moore pour effectuer des recherches d'occurences dans des collections d'Octets. Je me suis placé dans deux problématiques :

1 - Rester dans du générique; il s'agit de chercher une collection d'octets dans une autre collection d'octets plus grande, quels que soient les conteneurs (buffers, streams, strings, array of byte... etc) et quelles ques soient les types de collections (Texte, octets divers...)

2 - Dépasser la limite des 256 octets pour l'occurence à chercher

Bref, j'ai donc développé ma petite dll perso qui tourne magnifiquement bien chez moi (D7-Windows XP). Mais avant d'en publier les codes du source, j'aimerais savoir si véritablement elle tourne aussi bien ailleurs.

PosBM.zip

Pour l'utiliser il faut déposer cette dll dans le répertoire du programme appelant. Puis placer les routines appelables en implémentation :

Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
procedure InitSkipBuf(SStr : Pointer; LenSStr: longword); StdCall; external'PosBM';
function PosBM_KR(SStr, Str : Pointer; LSStr, LStr, Depuis :longWord): longword; stdcall; external'PosBM';
PosBM_KR s'utilise comme Pos() de Delphi. Mais auparavant, il convient d'appeler au moins une fois la procedure InitSkipBuf qui permet de remplir la fameuse table des sauts du Boyer-Moore.

Voici comment je l'ai testée chez moi :
(il faut une fenêtre avec un TButton et un TMemo)
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
 
unit Unit1;
 
interface
 
uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, StdCtrls;
 
type
  TForm1 = class(TForm)
    Memo1: TMemo;
    Button1: TButton;
    procedure Button1Click(Sender: TObject);
  private
    { Déclarations privées }
  public
    { Déclarations publiques }
  end;
 
var
  Form1: TForm1;
 
implementation
 
{$R *.dfm}
// Dll PosBM *******************************************************************
 
procedure InitSkipBuf(SStr : Pointer; LenSStr: longword); StdCall; external'PosBM';
function PosBM_KR(SStr, Str : Pointer; LSStr, LStr, Depuis :longWord): longword; stdcall; external'PosBM';
 
// GILBERT *********************************************************************
 
const MNA: array[Char] of Char
  = #0#1#2#3#4#5#6#7#8#9#10#11#12#13#14#15 +
    #16#17#18#19#20#21#22#23#24#25#26#27#28#29#30#31 +
    ' !"#$%&''()*+,-./0123456789:;<=>?' +
    '@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_' +
    '`ABCDEFGHIJKLMNOPQRSTUVWXYZ{|}~'#127 +
    '€'#129'‚ƒ„…†‡ˆ‰S‹Œ'#141'Z'#143#144'‘’“”•–—˜™S›Œ'#157'ZY' +
    #160'¡¢£¤¥¦§¨©ª«¬*®¯°±²³´µ¶·¸¹º»¼½¾¿' +
    'AAAAAAÆCEEEEIIIIDNOOOOO×OUUUUYÞß' +
    'AAAAAAÆCEEEEIIIIDNOOOOO÷OUUUUYÞY';
 
function StrAleatoireMinus(Len: LongWord): AnsiString;
var i: longWord; R: Integer;
begin
  SetLength(Result, Len);
  for i := 1 to Len do begin
    R := random(123 - 97); R := R + 97; Result[i] := Chr(R);
  end;
end;
 
function StrAleatoireMajus(Len: LongWord): AnsiString;
var i: longWord; R: Integer;
begin
  SetLength(Result, Len);
  for i := 1 to Len do begin
    R := random(91 - 65); R := R + 65; Result[i] := Chr(R);
  end;
end;
 
// ***************************************************************************
 
procedure TForm1.Button1Click(Sender: TObject);
    var Texte, Mot,Separ : string;
    NbTours,i,j,Occ,Depuis:longword;
    Gtc1,Gtc2 : Int64;
    procedure Trace(S : string);
    begin
         Memo1.Lines.Add(S);
    end;
begin
  Randomize;
  Mot :=StrAleatoireMajus(400);
  Separ :=StrAleatoireMajus(1020);
  Texte := '';
  initskipBuf(@Mot[1],length(Mot));
  NbTours:=100000;
  for i := 1 to 10 do Texte :=  Mot +  Separ + Texte;
  Trace('Texte : '+Texte); Trace(' ');
  Trace('Mot : '+Mot); Trace(' ');
  Trace('Mot de '+IntToStr (length(Mot))+' Chr');
  Trace('Texte de '+IntToStr(length(Texte))+' Chr');
  Trace('pour '+IntToStr(NbTours)+' tours :'); trace(' ');
  Gtc1 := GetTickCount;
  for i:=1 to NbTours do begin
    Depuis:=1; j:=0; Occ:=0;
    repeat
        j:=PosBM_KR(@Mot[1],@Texte[1],length(Mot),length(Texte),Depuis);
        if j>0 then begin
         inc(Occ); Depuis:=j+Length(Mot);
        end;
    until j=0;
  end;
  Gtc2:=GetTickCount;
  Trace(IntToStr(Occ)+' occurences trouvées en '+IntToStr(Gtc2-Gtc1)+ ' ms');
  Trace(' ');
end;
 
end.
Merci de me dire si ça tourne comme il faut...