Discussion :

[sbadecoder]

La question est double tout en recherchant les algorithmes les plus rapides possibles ...

Description :
On dispose d'une liste de "mots" - disons 3 mots - dont chacun peut être représenté par une AnsiString, un array of char ou un array of byte...,
ainsi que d'un "texte fixe" - disons de 150000 "lettres" - pouvant être représenté par une AnsiString, un array of char, ou array of byte...
ex:
> 3 mots= AAAA, RAT, OR
> texte généré au hasard avec la lettre A deux fois plus fréquente= A..V (pas de W X Y Z)

0) Choix des variables
1) Quel est l'algorithme le plus rapide pour la recherche de toutes les occurences de chacun des 3 mots dans le texte (3 recherches successives) ?
2) Existe-t-il un algorithme encore plus rapide permettant la recherche de ces 3 mots en parallèle (1 recherche) ou autre ?

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
 
mot[1] := 'AAAA';
mot[2] := 'RAT';
mot[3] := 'OR';
 
ou
 
...
mot[2][1] := ord('R'); mot[2][2] := ord('A'); mot[2][3] := ord('T');
...
 
 
procedure GenererTexte;
var
  i, r : integer;
  texte : array[0..150000]of char;
  //texte : array[0..150000]of byte;
  s : AnsiString;
begin
  for i := 1 to 150000 do 
  begin
    r := random(23) +65;
    if r = 87 then r := 65;  // A = Chr(65) a deux fois plus de chance !
    texte[i] := Chr(r);
    // texte[i] := r;
    // s := s + Chr(r);
  end;
end;

[Paul TOTH]

en recherche de texte, tu as Boyer Moore qui est d'autant plus efficace que le texte recherché est long.

sans que ce soit un algo de recherche, je sais que simdjson utilise une approche binaire extrêmement poussée pour parser du JSON

[Andnotor]

En matière de recherche de texte, on pense immédiatement aux expressions régulières.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
uses System.RegularExpressions;
 
var Matches := TRegEx.Matches(Texte, 'AAAA|RAT|OR');
 
for var Match in Matches do
  Memo1.Lines.Add(Format('%s à la position %d', [Match.Value, Match.Index]));

[sbadecoder]

Merci pour vos réponses, je ne pense pas que Boyer Moore, ni même les expressions régulières ne soient les plus rapides, je vais tester.
simdjson a l'air très intéressant, à suivre ...

[sbadecoder]

Après quelques tests, il semble que TRegEx.Match ne trouve pas toutes les occurences dans le cas d'un mot palindrome exemple : ETE.

[Andnotor]

Match retourne uniquement la première occurrence alors que Matches les retourne toutes.

[sbadecoder]

Le décompte des solutions de Match (puis commande Next ...) donne au final moins de solutions qu'attendu.
Cela fonctionne bien pour les autres mots.

[ShaiLeTroll]

Au final, quel est le but ?
Ansi ? seulement ASCII ? rien qui déborde en Windows1252 ?
Pas de gestion de la casse ?

Car au final, si il n'y a pas de gestion du caractère à son sens le plus large, rien ne vaut un traitement en binaire pur, traiter la chaine comme un tableau of byte, CompareMem par exemple qui utilise sur un 64Bits les registres 64Bits comparant ainsi 8 "char" à la fois.

et si le Boyer Moore avec ces recherches si petites n'a pas une réelle efficacité du fait des sauts très petits, il peut être inspirant pour une recherche multiple, si les mots recherchés ont ou pas des lettres communes, l'utilisation de saut peut être mutualisé, le A pouvant être dans AAAA et RAT, et le R dans RAT et OR, peut-être exploité cela
Voir le sujet Algorithme de Boyer-Moore, perso, je n'ai toujours pas eu l'occasion de l'implémenter.

[sbadecoder]

Alors, pas de gestion de la casse et ascii suffisant (1 byte en effet, 5 bits même).

Le but, il y en a plusieurs...

1) D'abord trouver, l'algorithme le plus rapide pour cette recherche, je pense qu'il faut partir sur 2 étapes :
- balayer le texte pour trouver toutes les positions de la lettre 1 et toutes les positions de la lettre 2 du mot,
- et tester ensuite les autres lettres du mot.
- sauvegarder toutes les occurrences.

2) Trouver l'algorithme - le plus rapide - permettant de trouver toutes les grilles comme un mot mêlé, disons de 7x7 lettres, renfermant au moins 1 occurrence de chacun des 3 mots précédents.

Cette grille sera définie par la position de sa première lettre dans le texte, la longueur de la ligne (ici 7, soit le nombre de colonnes) et le nombre de lignes du texte (ici 7 aussi) pouvant être noté g(L1, nbCol, nbRow).

Donc, g(1, 7, 7) correspond à la grille commençant à la 1ère lettre du texte et allant jusqu'à la 49e positionnée en colonne 7 et ligne 7.

[Andnotor]

Le décompte des solutions de Match (puis commande Next ...) donne au final moins de solutions qu'attendu.

Si tu trouves plus de résultats par tes tests c'est qu'il y a chevauchement (palindrome ou pas) et que tu n'incrémentes l'index que de un et non de la longueur du texte pour trouver le suivant.

Il est clair que si tu veux trouver deux fois ETE dans ETETE l'expression régulière proposée ne fonctionne pas. Il faut pour cela un positive lookhead (?=) qui va retourner l'index du motif sans pour autant avancer le curseur :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

var Matches := TRegEx.Matches(Texte, '(?=ETE)', [roSingleLine]);

Et c'est plus ou moins le même principe pour trouver l'index d'un texte vertical. En admettant que tu aies un texte de 7 lignes de 7 caractères :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
var Texte := '-------'#13
            +'---E---'#13
            +'---T---'#13
            +'---EE--'#13
            +'---TT--'#13
            +'---EE--'#13
            +'-------';
 
  Matches := TRegEx.Matches(Texte, '(?=E.{7}T.{7}E)', [roSingleLine]);

. représente n'importe quel caractère ou symbole (retour à la ligne compris dû à roSingleLine) et on en compte 7 pour incrémenter d'une ligne.
Plus qu'à faire un DivMod pour retourner ligne/colonne.

[sbadecoder]

Oui c'est certainement cela qui faisait une différence en moins dans le total des occurences trouvées avec les expressions régulières.

Et y a t il un moyen de rechercher aussi en vertical avec l'algo BM ?

[SergioMaster]

Comment est-on passé d'une recherche de mots dans un texte à une sorte de jeu de mots mêlés (et encore que seulement horizontal/vertical) ?
Le "cahier des charges" va t'il encore évolué ?

Il faut pour cela un positive lookhead (?=)

merci, je ne connaissai pas, une bonne journée qui commence. D'un autre côté j'utilise peu les expressions régulières

[sbadecoder]

Je ne souhaitais pas que le descriptif soit trop complexe dès le départ.
Mais en effet, on pourrait ensuite ajouter la recherche en diagonal et pourquoi pas, la recherche à rebours aussi.
Puis généraliser cela, à une grille avec un nombre de colonnes variables (et non fixée à 7 comme dans mon exemple).

[sbadecoder]

Pour la question 1), je reste sur le PosEx compte tenu que les mots sont courts moins de 10 caractères.