Création d'un regex avancé

Version imprimable

Bonjour,

Actuellement, j'ai une liste de référence produit.
Chaque référence produit est constituée des caractères suivants : lettre en majuscule, chiffres, certains caractères spéciaux (".", "/", "-", "*", "_", "(", ")").
Les références produit ne contiennent pas d'espace.

J'ai créé un système de recherche qui affiche la liste de produits associés en fonction de la valeur d'un champs de recherche renseignée par l'utilisateur.
Bien que les références soient renseignées dans la BDD qu'avec des lettre en majuscule, si l'utilisateur entre des minuscules, la recherche fonctionne quand même.
Bien que les références soient renseignées dans la BDD sans contenir d'espaces, si l'utilisateur entre des espaces, ceux-ci sont ignorés dans la recherche.
Le caractère "µ" est remplacé dans la recherche par le caractère "U".

Par exemple, si on a cette BDD :
Code:

1 2 3 4 AAA-123US AAA-124US BBB-124US BBB-124AS
Si l'utilisateur entre dans le champs de recherche "124 µS", ça affiche :
Code:

1 2 AAA-124US BBB-124US
Voici que le code qui génère le regex :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 function getProductRegex(reference){ //console.log(reference); let newReference = reference.replace('µ', 'U') // remplacement µ par U .toUpperCase() // conversion en majuscule .split(' ').join(''); // suppression des espaces //console.log(newReference); let re = $.ui.autocomplete.escapeRegex(newReference); let matcher; matcher = new RegExp(re); return matcher; }
La BDD (Base De Données) est stockée sous forme de variable dans mon script javascript :

Code:

var bdd = ["AAA-123US", "AAA-124US", "BBB-124US", "BBB-124AS"];

Maintenant, j'aimerai améliorer le système pour que la recherche fonctionne par mots clefs séparés par des espace.
Par exemple si l'utilisateur entre dans le champs de recherche "µS 124 BBB", que ça affiche :

Code:

BBB-124US

... que le regex recherche toutes les chaines de caractères qui contiennent TOUS les mots clef entrés (peu importe l'ordre).

Comment faire cela ?

Merci d'avance

04/05/2023, 12h01
SpaceFrog

Tu parles de BDD
Les données sont dans un table MySQL ?

Il serait peut être plus intéressant de faire la recherche en utilisant le fulltext ?
https://www.w3resource.com/mysql/mys...-functions.php
04/05/2023, 12h05
boboss123

Non les données sont enregistrées dans une variable locale :

Code:

var bdd = ["AAA-123US", "AAA-124US", "BBB-124US", "BBB-124AS"];

... je vais rajouter cette infos dans mon premier message.
04/05/2023, 13h14
SpaceFrog

Ha ok

Donc si on rentre des suites de caractères séparés par des espaces il faudra rechercher selon les "mots" ainsi rentrés ?

Faut il que tous les mots soient présent ou la recherche est elle "ou" ?

Il suffira de récupérer la chaine de recherche, la splitter et constituer une nouvelle regex avec des pipes ...
04/05/2023, 16h44
boboss123

Malheureusement, c'est un "et" que je veux faire. Je pourrais faire autant de passe regex qu'il y a de mots clefs mais on ne peut pas gérer ça directement via un regex ?
... et puis faire plusieurs passes, ça ne marche bien pour la gestion des recouvrements (ex: recherche de "AB BC" va matcher la chaine "ABC" alors que ça ne devrait pas).
04/05/2023, 16h48
SpaceFrog

un et OK mais dans l'ordre ?

du coup tu pourrais faire une reg par mot et ainsi faire un score de match
ceux qui matche tous les mots ... =100%
ceux qui matche tous les mots -1 = nbr mots-1 / nbre mots *100 %
etc ...
04/05/2023, 17h19
boboss123
Désolé mais je n'ai pas compris.

Après j'ai peut-être un début de solution.

Si l'utilisateur entre " US 124 BBB"

Je transforme la requête sous cette forme de regex :
"(US|124|BBB).*(US|124|BBB).*(US|124|BBB)"

ça fonctionne bien avec la liste suivante :
Code:

1 2 3 4 5 AAA-123US AAA-124US BBB-124US BBBUS-124 BBB-124AS
ça me sélectionne bien :
Code:

1 2 3 AAA-123US BBB-124US BBBUS-124
Par contre, ça sélectionne aussi la chaine "BBB-BBBUS"... il faudrait arriver à exclure les chaines déjà trouvées.
04/05/2023, 17h22
SpaceFrog

La reg devrait plutot ressembler à

Code:

/(US)|(124)|(BBB)/
04/05/2023, 17h37
boboss123

Ce n'est pas un OU que je veux faire mais un ET (mais sans recouvrement des chaines trouvée).

ce regex semble fonctionner :

Code:

"(BB.*124.*US)|(BB.*US.*124)|(124.*US.*BB)|(124.*BB.*US)|(US.*BB.*124)|(US.*124.*BB)"

... mais le problème est que ça taille augmente de manière exponentielle en fonction du nombre de mots clefs à rechercher : il y a peut-être une autre manière de l'écrire ?

PS :

Code:

/(US)|(124)|(BBB)/

c'est la même chose que ça ?

Code:

"(US)|(124)|(BBB)"
04/05/2023, 18h38
javatwister

Salut,

Je vois 2 problèmes dans ce que tu essaies de faire:

1) Comment veux-tu obliger le client à taper des mots clés séparés par des espaces? (pas très ergonomique et risque de saisie non conforme)
2) Pourquoi utiliser des regexp alors que le client saisira forcément des caractères standards en clair?

Principe à tester:

Code:

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
<div id="search">
<input type="text" size="4" />
<input type="text" size="4" />
<input type="text" size="4" />
</div>
<div>
<input id="go" type="button" value="go" />
</div>
<div id="result"></div>
<script>
 
var bdd = ["AAA-123US", "AAA-124US", "BBB-124US", "BBB-124AS"];
 
document.querySelector("#go").addEventListener("click",()=>{
        let req=Array.from(document.querySelector("#search").getElementsByTagName("input"));
        for(i in bdd){
                let win=0,nbr=req.length;
                req.forEach(v=>{
                        if(v.value.replace(/\s/,"")==""){nbr--}
                        else if(bdd[i].search(v.value.toUpperCase())!=-1){win++}
                });
                if(win==nbr){console.log(bdd[i])}
        }
})
</script>

J'adopterais plutôt une méthode consistant à faire en amont un registre mettant en rapport les éléments des références avec les index du tableau de références. Voilà ce que ça donne:

Code:

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
const refs = ["AAA-123US", "AAA-124US", "BBB-124US", "BBBUS-124", "BBB-124AS"];
 
const refs_elts = new Map([
    ["AAA", new Set([0, 1])],
    ["BBB", new Set([2, 3, 4])],
    ["123", new Set([0])],
    ["124", new Set([1, 2, 3, 4])],
    ["US", new Set([0, 1, 2, 3])],
    ["AS", new Set([4])]
]);
 
let usr_input = "US 124 BBB";
let usr_elts = usr_input.split(/ /);
 
let indexes = new Set();
let current_elt = usr_elts.pop();
 
if (refs_elts.has(current_elt)) {
    let elt_indexes = refs_elts.get(current_elt)
    indexes = new Set(elt_indexes);
 
    while (usr_elts.length) {
        current_elt = usr_elts.pop();
 
        if (refs_elts.has(current_elt)) {
            elt_indexes = refs_elts.get(current_elt);
            indexes = new Set([...indexes].filter((index) => elt_indexes.has(index)));
        }
    }
}
 
for (const index of indexes) {
    console.log(refs[index]);
}

De cette manière, on obtient les "candidats potentiels" en faisant l'intersection entre les jeux (sets) d'index.

Bien entendu, ce registre devra être généré dynamiquement.

04/05/2023, 22h30
javatwister

En amont, en amont... Oui mais imagine rien qu'un millier de références à entrer!
Et puis n'oublions pas que la saisie peut être elliptique par rapport aux références. On peut saisir "a" et espérer un résultat comprenant "AAA".
05/05/2023, 09h12
boboss123

Salut,

Citation:

Envoyé par javatwister

1) Comment veux-tu obliger le client à taper des mots clés séparés par des espaces? (pas très ergonomique et risque de saisie non conforme)

Je m'inspire du système de recherche du logiciel Everything : je n'ai jamais eu besoin de lire la documentation pour comprendre comment il fonctionne, je trouve l'interface plutot intuitive. Tu entres des mots clefs et il t'affiche tous les fichiers qui contiennent ces mots... simple et efficace, je trouve.

Citation:

Envoyé par javatwister

2) Pourquoi utiliser des regexp alors que le client saisira forcément des caractères standards en clair?

L'utilisateur n'entrera pas de regex : je veux juste transformer les mots clefs en regex pour faire la recherche... mais peut-etre que ce n'est pas la bonne solution.
05/05/2023, 09h53
javatwister

Tu peux tester le bout de code ds une page et voir si ça marche?
05/05/2023, 11h49
boboss123
A priori avec cette méthode ça fonctionne (testé avec le moteur de recherche en mode Regex du logiciel Notepad++) : https://stackoverflow.com/questions/...s-in-any-order
... par contre, je n'ai pas bien comprise comment fonctionne ce regex.

Par exemple :

Code:

^(?=.*US)(?=.*124)(?=.*BBB).*$

Match bien :
Code:

1 2 3 BBB-124US BBBUS-124 BBBUSUS-124
Et ne match pas :
Code:

1 2 3 4 AAA-124US AAA-123US AAA-123US BBB-124AS
05/05/2023, 12h06
javatwister

Je ne comprends toujours pas ce que tu fais...

Je me répète mais tu n'as pas besoin de regexp: l'utilisateur tape 2 ou 3 "mots" clés et tu affiches les données qui contiennent ces mots clés...
Donc, à peu près rien à coder;
05/05/2023, 12h35
CosmoKnacki

Citation:

Envoyé par javatwister

En amont, en amont... Oui mais imagine rien qu'un millier de références à entrer!
Et puis n'oublions pas que la saisie peut être elliptique par rapport aux références. On peut saisir "a" et espérer un résultat comprenant "AAA".

Un millier, c'est une broutille!

La génération de l'objet map ne prend que quelques dixièmes de seconde (et encore) et est faite une fois pour toutes: sous nodejs, j'atteint la seconde (génération aléatoire du tableau de références et test avec une entrée utilisateur compris) qu'à partir de 300 000 références!

Quant au temps de recherche lui-même, il est totalement négligeable, même avec des entrées elliptiques.

Il faut bien voir que le nombre de clefs de la map est majorée et ne dépassera pas 19252 entrées quelque soit le nombre de références (19252 = 26^3 + 10^3 + 26^2) et quelles sont associées à des Sets de nombres. Donc l'occupation en mémoire ne coutera à quelque chose près pas plus chère que le tableau d'origine. Pour illustrer, passé 10.000 références, le nombre d'entrées de la map devient inférieur à celui du tableau.

Par contre, le problème de chevauchement des éléments de l'entrée utilisateur reste entier, mais sera plus rapide à régler une fois ce premier filtrage effectué (par exemple pour 1 million de références, j'obtiens ~150 résultats contenant AI et IA).
05/05/2023, 12h52
CosmoKnacki

Citation:

Envoyé par boboss123

A priori avec cette méthode ça fonctionne (testé avec le moteur de recherche en mode Regex du logiciel Notepad++) : https://stackoverflow.com/questions/...s-in-any-order
... par contre, je n'ai pas bien comprise comment fonctionne ce regex.

Par exemple :

Code:

^(?=.*US)(?=.*124)(?=.*BBB).*$

C'est simple cette pattern teste en partant du début de la chaîne (^) pour chaque test avant (?=...) (lookahead) si US, 124 et BBB sont bien présent dans la chaîne. (À noter que .*$ ne sert à rien, on se doute bien que la chaîne va finir un jour).
Par contre ce qu'elle ne fait pas c'est de résoudre le problème de chevauchement: ^(?=.*AB)(?=.*BA) trouvera ABC-123BA mais aussi ABA-123US.

Accessoirement, il serait utile de savoir de quoi on parle: quel est le format précis des références? Est-ce qu'il y en a plusieurs qui coexistent? Quelle est la taille de ton tableau de références? Pourquoi sont-elles en dur dans ton javascript, d'où viennent-elles?
05/05/2023, 14h38
CosmoKnacki

En fait je me suis compliqué la vie pour rien, j'étais tellement persuadé que le parcours du tableau allait être lent que j'ai cherché une solution de rechange qui en plus résoudrait le problème de chevauchement, mais en fait il est rapide même avec beaucoup d'éléments et le problème de chevauchement n'est pas résolu dans le cas de saisies élliptiques avec ma méthode. Je vais chercher autre chose.
05/05/2023, 15h06
boboss123

J'ai beau lire des tutos sur les lookahead, je n'arrive toujours à comprendre ce que ça fait exactement.

Si j'ai bien compris le regex suivant cherche "A" suivit de "B" ou "C" puis suivit de D ?

Code:

A(?=B)(?=C)D

Je ne comprends pas pourquoi il faut que B et C soit présents obligatoirement et l'ordre n'a pas d'importance.

C'est quoi la différence avec ça ?

Code:

A[BC]D

Au final, gérer les chevauchement n'est peut-être pas si important (d'ailleurs, je viens de tester le logiciel Everything dont je me suis servit comme inspiration et il ne gère pas les chevauchements... je vais faire sans alors).
... mais ça peut quand même être intéressant de savoir comment le faire :)

Entre une solution à base de indexOf où l'on fait une boucle pour tester chaque mot clef sur la chaine et ce regex, il y a une différence de performance ? (dans mon cas, je n'ai pas énormément de références à gérer mais autant utiliser la meilleure méthode).
05/05/2023, 15h18
CosmoKnacki

Le lookahead ne consomme pas de caractères contrairement à une classe de caractères ou le point qui consomme un caractère puis avance à la position suivante dans la chaîne. À la fermeture du lookahead on est toujours au même endroit dans la chaîne qu'à son ouverture.
Si tu veux une analogie, un lookahead, c'est un marcheur qui s'arrête pour regarder au loin avec ses jumelles, il sait ce qu'il l'attend sans pour autant s'y être rendu. Si ce qu'il voit lui plait, il continue, sinon il abandonne.
05/05/2023, 15h32
boboss123

Donc pour "A(?=B)(?=C)D" :
Le marcheur s’arrête sur A et regarde s'il y a B puis il regarde s'il y C, c'est ça ? (donc recherche les chaines "AB" et "AC" ?)
Puis une fois les chaines trouvés se déplace à D.
... donc si je suis mon raisonnement, la chaine "ABACD" devrait matcher... ce qui n'est pas le cas : où est mon problème de réflexion ?
05/05/2023, 15h37
CosmoKnacki

Non, A(?=B)(?=C)D échouera toujours quelque soit la chaîne. Car là tu dis qu'immédiatement aprés A il y a B, C et D à la même position (or au max il ne peut y avoir qu'un seul de ces caractères).

Et pour être précis, arrivé au premier lookahead, le "marcheur" ne s'arrête pas sur A, il vient juste de passer A et se trouve à ses pieds le prochain caractère ou la fin de la chaîne.
05/05/2023, 15h53
boboss123

C'est bon je crois que j'ai compris en testant le regex "A(?=.*B)(?=.*C)DE"

Le marcheur veut tester la chaine "ZZZZADEZZZCZZZZB" :
1- Le marcheur avance jusqu’à arriver sur un "A" puis s'arrête.
2- Il regarde si sur la chaine restante ("DEZZZCZZZZB"), il trouve ".*B".
3- Ensuite, il regarde si sur la chaine restante ("DEZZZCZZZZB"... toujours la même), il trouve ".*C".
4- Il redémarre en avançant au caractère suivant et teste "D" sur la chaine "DEZZZCZZZZB".
5- Il passe au caractère suivant et teste "E" sur la chaine "EZZZCZZZZB".

C'est bien le bon raisonnement ?
05/05/2023, 15h56
CosmoKnacki

Oui là c'est correct.

Maintenant, merci de répondre à mes questions.
05/05/2023, 16h12
boboss123

Citation:

Envoyé par CosmoKnacki

quel est le format précis des références?

Chaque référence produit est constituée des caractères suivants : lettre en majuscule, chiffres, certains caractères spéciaux (".", "/", "-", "*", "_", "(", ")").
Les références produit ne contiennent pas d'espace.
Les références produit sont composée des sous-chaines qui ont une signification... d'où l’intérêt de pouvoir faire une recherche par mots clefs.

Citation:

Envoyé par CosmoKnacki

Est-ce qu'il y en a plusieurs qui coexistent?

Non mais on peut avoir "AAA" et "AAAB".

Citation:

Envoyé par CosmoKnacki

Quelle est la taille de ton tableau de références?

500 éléments au max.

Citation:

Envoyé par CosmoKnacki

Pourquoi sont-elles en dur dans ton javascript, d'où viennent-elles?

Elle sont en dur pour éviter d'avoir à gérer un langage coté serveur (ex: PHP)... et accessoirement de pouvoir aussi l’exécuter en mode hors ligne pour faciliter les tests (pas indispensable). C'est site Web basique qui consiste à afficher des informations sur une référence produit sélectionnée avec un moteur de recherche qui intègre un système d’autocomplétion (affiche la liste des produits en fonction des mots clefs renseignés).
05/05/2023, 17h47
javatwister

Citation:

Envoyé par boboss123

Au final, gérer les chevauchement n'est peut-être pas si important (d'ailleurs, je viens de tester le logiciel Everything dont je me suis servit comme inspiration et il ne gère pas les chevauchements... je vais faire sans alors).
... mais ça peut quand même être intéressant de savoir comment le faire :)

Entre une solution à base de indexOf où l'on fait une boucle pour tester chaque mot clef sur la chaine et ce regex, il y a une différence de performance ? (dans mon cas, je n'ai pas énormément de références à gérer mais autant utiliser la meilleure méthode).

Voilà, on y arrive!

==> le problème du chevauchement n'en est pas vraiment un: si l'utilisateur est assez intelligent, il ne va pas saisir n'importe quoi étant donné ce qu'il veut obtenir;

==> indexOf est toujours plus rapide qu'une regexp;

==> une regexp n'a d'intérêt que si le masque peut correspondre à plusieurs chaînes différentes: ici, ce n'est pas le cas.

Une solution qui gère le chevauchement:

Code:

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
function items_overlap(ref, items) {
    let masks = [ref];
 
    for (const item of items) {
        masks = masks.reduce((c, mask) => [...c, ...build_masks(mask, item)], []);
        if (!masks.length) return true;
    }
    return false;
}
 
function build_masks(ref, item) {
    let mask, masks = [];
    let chunks = ref.split(item);
    const last_index = chunks.length - 1;
 
    for (let i=0; i<last_index; i++) {
        mask = '';
 
        for (let j=0; j<last_index; j++) {
            mask += `${chunks[j]}${i === j ? "\u{001e}" : item}`; 
        }
 
        mask += chunks[last_index];
        masks.push(mask);
    }
    return masks; 
}

Le principe est de splitter une référence avec un des items de l'entrée utilisateur, puis à partir des morceaux de produire des versions masquées de cette référence, exemple avec la référence AIA-123AI et l'item AI: j'obtiens les masques _A-123AI et AIA-123_.

Si aucun de ces deux masques ne contient l'item suivant, c'est soit qu'il n'est pas dans la référence, soit qu'il se chevauche avec le précédent.

Test:

Code:

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
const refs = [
    'AIA-421UM', 'IAI-674LV', 'AIA-905LU', 'IAI-158DL', 'IAI-569ZK', 'IAI-571IW', 'LAI-955IA', 'AIA-774UI', 'IAI-877QK',
    'IAI-423DF', 'AIA-531NO', 'IAI-589KR', 'IAI-272CI', 'IAI-203ZO', 'IAI-886NO', 'AIA-935CN', 'IAI-431WG', 'AIA-875ZG',
    'IAI-149QK', 'IAN-358AI', 'AIA-575OH', 'IAI-008XU', 'IAI-014LM', 'AIA-032VS', 'IAI-128DV', 'AIG-916IA', 'IAI-589XY',
    'IAI-534IK', 'AIA-496AN', 'NAI-754IA', 'AIA-343UM', 'IAI-844QQ', 'AIA-853DM', 'AIA-608VU', 'AIA-431NN', 'AIA-027NS',
    'IAI-097IC', 'AIA-934WJ', 'AIA-537XC', 'IAI-321IF', 'IAI-401QZ', 'AIA-213VC', 'AIA-150XD', 'AIA-892OG', 'IAI-541SH',
    'AIA-687WO', 'IAI-260ZC', 'AIA-192DH', 'AIA-371GA', 'IAR-826AI', 'AIA-732HZ', 'AIA-354TP', 'AIA-945DZ', 'NAI-746IA',
    'AIA-058WR', 'AIA-810VH', 'VIA-637AI', 'IAI-277EP', 'IAI-794KR', 'AIA-769MG', 'AIA-973XC', 'AIA-488ZK', 'AIA-394WQ',
    'AIA-530GO', 'AIA-096CI', 'AIA-832FF', 'AIA-083DS', 'IAI-320QA', 'IAI-947NO', 'AIA-960ZY', 'IAI-085AD', 'AIA-918UD',
    'AIA-760II', 'IAI-699TN', 'AIA-133EI', 'IAI-750YP', 'AIA-146PS', 'IAI-166IR', 'AIA-654PO', 'IAI-405PZ', 'IAI-483YI',
    'IAI-960WO', 'AIA-273IO', 'AIA-398WC', 'AIA-885KP', 'AIJ-780IA', 'IAI-853WC', 'AIA-192MI', 'KAI-139IA', 'AIA-435ZV',
    'AIA-302HV', 'AIA-276PC', 'IAI-016FK', 'AIA-270SL', 'IAI-014PF', 'IAI-590WS', 'AIA-820QC', 'AIA-818DJ', 'IAI-641KA',
    'AIA-947QB', 'AIA-991LU', 'IAI-201FL', 'AIA-180KL', 'AIA-805JL', 'AIA-781PE', 'IAI-217YR', 'IAI-488AZ'
];
 
const usr_input = ['AI', 'IA']; //['8', 'D']; //['A', 'A', 'A'];
 
let result = refs.filter((ref) => !items_overlap(ref, usr_input));
 
console.log(result);
//[ 'LAI-955IA',
//  'IAN-358AI',
//  'AIG-916IA',
//  'NAI-754IA',
//  'IAR-826AI',
//  'NAI-746IA',
//  'VIA-637AI',
//  'AIJ-780IA',
//  'KAI-139IA' ]

09/05/2023, 09h17
boboss123

Merci pour vos réponses, je pense qu'on peu fermer le sujet :)

Pour la gestion de chevauchement, je pense aussi qu'on peut le faire une boucle .remplace sur chaque mots clefs : si la référence a toujours la même longueur après un .replace, c'est qu'elle ne contient pas le mot clef et est donc à filtrer.

Citation:

Envoyé par boboss123

Pour la gestion de chevauchement, je pense aussi qu'on peut le faire une boucle .remplace sur chaque mots clefs : si la référence a toujours la même longueur après un .replace, c'est qu'elle ne contient pas le mot clef et est donc à filtrer.

Malheureusement ça ne marchera pas pour 2 raisons:
tu risques de créer des sous-chaînes qui n'étaient pas là avant:
Code:

1 2 3 4 5 référence: ABC-123DE mots-clefs: B et AC remplacement de B => AC-123DE (ok) remplacement de AC => -123DE (pas ok)
c'est dépendant de l'ordre de remplacement des mots-clefs:
Code:

1 2 3 4 5 6 7 8 9 10 référence: ABC-123AS mots-clefs: AB et A ordre: AB, A remplacement de AB => C-123AS (ok) remplacement de A => C-123S (ok) ordre: A, AB remplacement de A => BC-123AS (ok) remplacement de AB => BC-123AS (pas ok)
C'est pour ces raisons que dans le code que je propose je génère pour chaque mots clef plusieurs références temporaires:
Code:

1 2 ABC-123AS =A> _BC-123AS =AB> introuvable ABC-123_S _C-123_S (il en reste un, ABC-123AS est un résultat pour A, AB)

09/05/2023, 17h32
boboss123

Effectivement, tu as raison :)