[QR] Comment trouver une chaîne dans un gros fichier avec l'algorithme de Boyer-Moore ?
La principale caractéristique des codes exploitant tout ou partie de l’algorithme de Boyer-Moore réside dans le fait que la position de recherche avance suivant un pas variable compris en 1 et
length(Chaîne) donc plus la chaîne recherchée est longue et plus la recherche avance plus rapidement.
A cet effet le fonctionnement du code ci-après peut se comparer à celui d’un « coulisseau » de longueur égale à
length(Chaîne) que l’on coulisse le long du fichier et percé :
- en sa fin, d’un 1er trou par lequel on cherche la présence du Dernier caractère de la chaîne,
- en son début, d’un 2ème trou par lequel on ne cherche la présence du Premier caractère de la chaîne que si le 1er trou concorde,
- et d’une série de petits trous intermédiaires par lesquels on ne cherche la présence des autres caractères intermédiaires que si Dernier et le Premier caractère coïncident.
Rôle du « trou sur le Dernier caractère » : Quelle que soit la position du coulisseau on sait toujours quelle est la position du fichier sur laquelle est sensée se trouver le Dernier caractère de la chaîne cherchée ainsi si on recherche par exemple le mot « comment » et que l’on voit par le trou placé sous le « t » terminal du coulisseau :
- un « c » : alors sait que le « t » terminal ne peut se trouver que 6 positions plus loin dans le fichier et on fait avancer illico le coulisseau de 6 positions,
- un « m » : alors sait que le « t » ne peut se trouver que 3 positions plus loin,
- un caractère absent de la chaîne cherchée alors sait que le « t » ne peut se trouver que
length(Chaîne) positions plus loin dans le fichier.
Donc, d’entrée de jeu on crée une « JumpTable » qui mémorise pour chacun des chr de la chaîne cherchée la valeur minimale de son décalage par rapport à son Dernier chr, excepté pour son dernier chr et pour tous les autres chr de la table Ascii absents de la chaîne cherchée auxquels on affecte un décalage égal à
length(Chaîne), d’où l’importance du « trou directeur » qui s’intéresse en priorité à la recherche du Dernier chr de la chaîne.
Rôle du « trou sur le Premier caractère » par lequel on recherche, dans un 2ème temps, la présence du Premier chr : Il est évident que si le trou sur le Dernier chr du coulisseau coïncide avec l’un du fichier mais que le trou sur le Premier chr ne coïncide pas il est alors inutile de perdre du temps à comparer les chr intermédiaires, donc on avance le coulisseau d’un bond.
La probabilité de se trouver dans un tel cas est relativement forte. En prenant l’exemple d’un fichier utilisant un alphabet de seulement 29 caractères on a statistiquement 1 seule chance sur 29 de tomber sur une coïncidence avec le Premier chr mais surtout 28 chances sur 29 (probabilité de 96%) de tomber sur une non-concordance qui fait illico-presto avancer le coulisseau d’un bond. Ceci explique également pourquoi il n'est pas utilisé ici une table de suffixes.
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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
| type tAOI64 = array of Int64;
function GetOccPosBoyerMoore2( const NomFichier : String; SubStr : string;
var Positions : tAOI64; memPos, CaseSensitive : boolean;
OccMax : integer; ComptageStrict : boolean) : integer;
// @param SubStr : sous-chaîne à rechercher dans le fichier
// : SubStr doit comporter au moins 2 caractères.
// @param Position et MemPos : Position = table d'entiers renvoyant
// les positions de occurences trouvées si MemPos = True
// @param CaseSensitive : Si True alors distinction minuscules/majuscules
// : Si False alors conversion minuscules en majuscules (plus lent)
// @param OccMax : nombre maxi d'occurrences à chercher avant l'Exit.
// @param ComptageStrict : Si True alors comptage des occurrences séparées
// : Si False alors comptage des occurrences de cheveauchement.
// @Result : renvoie le Nombre d'occurences trouvées.
// Utilisable pour fichiers de plus de 2 Go
// Vitesse maximale obtenue avec memPos = False et CaseSensitive = True et OccMax = 1
// et ComptageStrict = True et Length(SubStr) aussi grand que possible.
label ChrPrecedent, BuffSuivant;
const iBuffMax = 65536;
Grow = 200;
const MNA : array[Char] of Char // Majuscules Non Accentuées
= #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';
var JumpTable : array[char] of byte;
Buff : array[0..iBuffMax] of Char;
Dernier, Premier : char;
i, k, TailleFi, LuFi, Depass, Correc : int64;
Fi, LuBuff, j, lgSS, lgSSMoins1 : integer;
begin Result:=0; lgSS := length(SubStr);
if lgSS < 2 then EXIT;
Fi:=-1;
try Fi := FileOpen(NomFichier, fmOpenRead or fmShareDenyWrite);
if Fi < 0 then begin ShowMessage('Pas pu ouvrir le fichier '+NomFichier); EXIT; end;
TailleFi := FileSeek(Fi, 0, FILE_END);
if TailleFi < lgSS Then EXIT;
if memPos then SetLength(Positions,Grow);
if not CaseSensitive then for j:=1 to lgSS do SubStr[j]:=MNA[SubStr[j]];
// Initialisation de la Jumptable :
// a) Initilalisation de tous les sauts avec valeur maxi = length(SubStr)
FillChar(JumpTable, 256, lgSS);
// b) Correctif pour tous les chr de SubStr excepté son Dernier (décalages minima des chr de SubStr par rapport à son dernier chr)
for j := 1 to lgSS - 1 do JumpTable[SubStr[j]] := lgSS - j;
// Initialisations pour la création d'un "coulisseau" à 2 "trous directeurs" de comparaison
lgSSMoins1 := lgSS - 1;
Premier := SubStr[1];
Dernier := SubStr[lgSS];
k := lgSS-1; // -1 à cause du décalage d'indiçage entre string et array du Buffer
LuFi :=0;
FileSeek(Fi, 0, 0);
while LuFi < TailleFi do
begin LuBuff := FileRead(Fi, Buff[0], iBuffMax+1);
while (k < TailleFi) do
begin i := k; j := lgSS;
// Ici i et k correspondent à la position du fichier à laquelle
// est sensée se trouver le dernier caractère de SubStr
// si SubStr est présente en entier dans le fichier dans cette zone
if CaseSensitive then Inc(k, JumpTable[Buff[k-LuFi]])
else Inc(k, JumpTable[MNA[Buff[k-LuFi]]]);
if i-LuFi > LuBuff-1 then // SubStr éventuellement
// à cheval sur fin de Buff et début de Buff suivant,
// donc on re-positionne le Buff suivant afin que SubStr
// se trouve en entier au début du Buff suivant
begin Depass:=i-LuFi-LuBuff;
Correc:=lgSS-Depass;
k:=i-Correc;
FileSeek(Fi, -Correc, 1);
LuBuff:=LuBuff-Correc;
Goto BuffSuivant;
end;
// Coulisseau à 2 "trous" de comparaison préalable à marche en arrière:
//if Buff[i-LuFi]<>Dernier
if CaseSensitive
then begin if Buff[i-LuFi]<>Dernier then Continue; end // retour immédiat au While pour
else begin if MNA[Buff[i-LuFi]]<>Dernier then Continue; end; // avancer via la JumpTable
// ici le Dernier est testé et bon
if (CaseSensitive and (Buff[i-lgSSMoins1-LuFi]=Premier))
or (not CaseSensitive and (MNA[Buff[i-lgSSMoins1-LuFi]]=Premier)) then
// ici le Premier est également bon donc on peut embrayer une marche arrière
// pour tester la concordance éventuelle des chr situés entre le Dernier et le Premier
begin Dec(j); Dec(i); // un pas en arrière : le Dernier chr étant bon on passe à l'Avant-Dernier
ChrPrecedent:
if (CaseSensitive and (Buff[i-LuFi]=SubStr[j]))
or (not CaseSensitive and (MNA[Buff[i-LuFi]]=SubStr[j])) then
begin if j>1 then begin Dec(j); Dec(i); end; // un pas en arrière : le chr intermédiaire est bon
// on passe à celui qui le précède sauf si j:=1 = Avant-Dernier = Premier = déjà bon quand lgSS = 2
if j = 1 then // SubStr trouvée
begin inc(Result);
if memPos then
begin if Result>Length(Positions)
then SetLength(Positions, Length(Positions) + Grow);
Positions[Result-1]:= i;
end;
if Result=OccMax then
begin if memPos then SetLength(Positions,Result);
EXIT; // inutile de perdre du temps avec les occurrences suivantes
end;
if ComptageStrict then inc(k,lgSS); // bond de lgSS évitant le comptage des occurrences de chevauchement.
Continue ; // retour au while (k < TailleFi)
end;
Goto ChrPrecedent;
end;
end;
end;
BuffSuivant:
Inc(LuFi, LuBuff);
end;
finally
if Fi<>-1 then FileClose(Fi);
if memPos then SetLength(Positions,Result);
end;
end; // GetOccPosBoyerMoore2
{Croquis du "coulisseau comparateur à 2 trous directeurs", positionné au départ sur le début du Texte:
------------------
La SubString à rechercher (ici longue de 8) -> |c o m m e n t é|
Le résumé des "sauts" de la JumpTable -> |7 6 4 4 3 2 1 8|
Les 2 "trous" et le texte sous le coulisseau: -> |O O|ier commenté ensuite
------------------} |
[QR] Comment trouver une chaîne dans un gros fichier avec l'algorithme de Boyer-Moore ?
Répondre avec citation
Partager