Nous faisons tous des erreurs: dans ce cas, nous parlons de requêtes de recherche. Le nombre de sites pour la vente de biens et services augmente avec les besoins des utilisateurs, mais ils ne peuvent pas toujours trouver ce qu'ils recherchent - uniquement parce qu'ils ne saisissent pas correctement le nom du produit nécessaire. La solution à ce problème est obtenue en mettant en œuvre une recherche floue, c'est-à-dire en utilisant l'algorithme pour trouver les valeurs les plus proches, en tenant compte des éventuelles erreurs ou fautes de frappe de l'utilisateur. La portée d'une telle recherche est suffisamment large - nous avons réussi à travailler sur la recherche d'une grande boutique en ligne dans le segment de la vente au détail de produits alimentaires.
État de recherche initial
La boutique en ligne a été développée sur la plateforme 1C-Bitrix: Site Management. Pour implémenter la recherche, nous avons utilisé le module de recherche bitrix standard et le moteur de texte intégral sphinxsearch. Dans sphinxsearch, le type d'index en temps réel (RT) a été utilisé, ce qui ne nécessite pas de source de données statique, mais peut être rempli à tout moment en temps réel. Cela vous permet de mettre à jour de manière flexible l'index de recherche sans le réindexer complètement. Étant donné que l'index RT utilise uniquement SphinxQL comme protocole de requête, l'intégration a été effectuée via celui-ci. SphinxQL est un protocole de requête de type mysql qui implémente la possibilité de se connecter via des clients mysql standard, tout en fournissant la syntaxe sql avec quelques limitations et ses propres particularités. Le module de recherche utilise des requêtes de sélection / insertion / remplacement / suppression.
Dans le système bitrix, le processus d'indexation des données des produits, catégories et marques a été effectué. Les informations sur ces entités ont été transférées à sphinx, qui à son tour a mis à jour l'indice RT. Lorsque les données sont mises à jour dans la boutique en ligne, un événement est déclenché qui met à jour les données dans Sphinx. La cohérence des données est réalisée via l'identifiant d'entité dans la boutique en ligne.
Lorsqu'un utilisateur effectue une recherche dans une boutique en ligne, le système fait une demande avec une expression de recherche dans Sphinx et obtient des identificateurs d'entités, sélectionne également à partir de la base de données des informations sur eux et forme une page avec les résultats de la recherche.
Au moment où la solution au problème de recherche floue a commencé, le schéma général de l'architecture de recherche sur le projet était le suivant:
Sélection de technologies
Notre tâche était de deviner la demande de l'utilisateur, qui peut contenir des fautes de frappe. Pour ce faire, nous devons analyser chaque mot de la demande et décider si l'utilisateur l'a écrit correctement ou non. En cas d'erreur, les options les plus appropriées doivent être sélectionnées. Il est impossible de déterminer l'orthographe correcte des mots sans une base de données de mots et de formes de mots de la langue dans laquelle nous voulons les deviner. Simplement, une telle base de données peut être appelée un dictionnaire - c'est lui dont nous avions besoin.
Pour sélectionner les options de substitution des mots entrés avec une erreur, la formule populaire de calcul de la distance Damerau - Levenshtein a été choisie. Cette formule est un algorithme pour comparer deux mots. Le résultat de la comparaison est le nombre d'opérations pour convertir un mot en un autre. Initialement, la distance Levenshtein implique l'utilisation de 3 opérations:
- insertion
- effacement
- remplacement
La distance Damerau-Levenshtein est une version étendue de la distance Levenshtein et ajoute une autre opération: la transposition, c'est-à-dire une permutation de deux caractères adjacents.
Ainsi, le nombre d'opérations reçues devient le nombre d'erreurs commises par l'utilisateur lors de l'écriture du mot. Nous avons choisi la limitation de deux erreurs, car un plus grand nombre n'avait pas de sens: dans ce cas, nous avons trop d'options de remplacement, ce qui augmente la probabilité d'un échec.
Pour une recherche plus pertinente de variantes de mots similaires dans le son, la fonction métaphone a été utilisée - cette fonction convertit un mot dans sa forme phonétique. Malheureusement, le métaphone ne fonctionne qu'avec les lettres de l'alphabet anglais, donc avant de calculer la forme phonétique, nous translittérons le mot. La valeur de la forme phonétique est stockée dans le dictionnaire et est également calculée dans la demande de l'utilisateur. Les valeurs résultantes sont comparées par la fonction de distance Damerau-Levenshtein.
Le dictionnaire est stocké dans la base de données MySQL. Afin de ne pas charger le dictionnaire dans la mémoire de l'application, il a été décidé de calculer la distance Damerau-Levenshtein côté base.
La fonction définie par l'utilisateur pour le calcul de la distance Damerau-Levenshtein , écrite sur la base
de la fonction C écrite par Linus Torvalds , a pleinement répondu à nos exigences. Créé par Diego Torres.
Après avoir calculé la distance Damerau-Levenshtein, il a été nécessaire de trier les résultats par degré de similitude pour sélectionner le plus approprié. Pour ce faire, nous avons utilisé l'algorithme d'Oliver: calculer la similitude de deux lignes. En php, cet algorithme est représenté par la fonction similar_text. Les deux premiers paramètres de la fonction acceptent les lignes d'entrée qui doivent être comparées. L'ordre de comparaison des chaînes est important, car la fonction donne des valeurs différentes selon l'ordre dans lequel les lignes sont transmises à la fonction. Le troisième paramètre doit être transmis à la variable dans laquelle le résultat de la comparaison est placé. Ce sera un nombre de 0 à 100, ce qui signifie le pourcentage de similitude entre les deux lignes. Après le calcul, les résultats sont triés par ordre décroissant de similitude, puis les options avec les meilleures valeurs sont sélectionnées.
Étant donné que le calcul de la distance Damerau-Levenshtein a été effectué en fonction de la transcription du mot, les mots avec des significations pas entièrement pertinentes sont tombés dans les résultats. À cet égard, nous avons limité la sélection d'options avec un pourcentage de correspondance de plus de 70%.
Au cours du processus de développement, nous avons remarqué que notre algorithme peut deviner des mots dans différentes dispositions. Par conséquent, nous devions étendre le dictionnaire en ajoutant la signification des mots sur la mise en page inversée. Les exigences de recherche ne comportaient que deux mises en page: russe et anglais. Nous avons dupliqué chaque mot de la requête de recherche de l'utilisateur sur la présentation inverse et ajouté un traitement pour calculer la distance Damerau-Levenshtein. Les options de mise en page directe et inverse sont traitées indépendamment l'une de l'autre, les options présentant le pourcentage de similitude le plus élevé sont sélectionnées. Ce n'est que pour les options de mise en page inversée que la valeur dans la mise en page directe sera la valeur de la requête de recherche corrigée.
Algorithme de recherche floue
Ainsi, un algorithme d'actions de 6 étapes principales a été formé. Lors des tests, nous avons constaté que tous les mots des demandes des utilisateurs ne doivent pas être traités dans leur forme d'origine ou traités en général. Pour résoudre de tels cas, une étape supplémentaire a été introduite, que nous avons appelée un convertisseur ou un filtre. En conséquence, l'algorithme final comprenait 7 étapes:
- Divisez la requête en mots séparés;
- Passez chaque mot dans le convertisseur (à ce sujet plus loin);
- Pour chaque mot, faites sa forme sur une mise en page différente;
- Composez une transcription;
- Effectuez une recherche dans le tableau du dictionnaire, en comparant chaque entrée sur la distance Damerau-Levenshtein;
- Ne laisser que des enregistrements avec une distance inférieure ou égale à deux;
- Grâce à l'algorithme Oliver, ne laissez que des mots avec un pourcentage de similitude supérieur à 70%
Schématiquement, cet algorithme est le suivant:
Conversion de mots et fonctionnalité de filtrage
Lorsque nous avons commencé à tester le premier prototype sans convertisseur, il est devenu évident qu’il n’était pas nécessaire d’essayer de deviner tous les mots de la demande de l’utilisateur. Un convertisseur a été créé pour ces restrictions. Il vous permet de convertir les mots dans la forme dont nous avons besoin et de filtrer ceux qui, à notre avis, n'ont pas besoin d'être devinés.
Initialement, il a été décidé que la longueur minimale de mot qui devrait être transmise par l'algorithme devait être d'au moins deux caractères. Après tout, si l'utilisateur a saisi un prétexte ou une union d'un caractère, la probabilité de deviner est pratiquement minime. La deuxième étape consistait à diviser la requête en mots. Tout d'abord, nous avons choisi un ensemble de caractères pouvant contenir des mots: lettres, chiffres, point et trait d'union (tiret). Les espaces et autres caractères sont des délimiteurs de mots.
Très souvent, les utilisateurs entrent des nombres pour indiquer le volume ou la quantité. Dans ce cas, il sera incorrect de corriger une telle demande. Par exemple, un utilisateur a saisi la requête «eau 1,1 litre». Si nous corrigeons sa demande de 1,5 ou 1,0, ce sera faux. Dans de tels cas, nous avons décidé de sauter les mots avec un nombre. Ils, en contournant notre algorithme, sont transférés à la recherche plein texte Sphinx.
Une autre conversion est associée aux points dans les noms de marque - par exemple: Dr. Pepper ou Mr.Proper. Dans les cas où il y a un symbole de point au milieu du mot, nous le divisons en deux, en ajoutant un espace. Le deuxième cas avec un point au milieu du mot - nous rappelons ici les marques d'abréviation. Par exemple, la marque ROCS - dans ce cas, nous coupons les points et obtenons un seul mot. Cette conversion fonctionne s'il n'y a qu'une seule lettre entre les points.
Dans les cas où un trait d'union (tiret) est présent dans le mot, vous devez diviser le mot en plusieurs et essayer de les deviner individuellement, puis coller les meilleures options.
En conséquence, un convertisseur a été développé pour la reconnaissance la plus précise de la demande - la majeure partie du travail de configuration de toutes les fonctionnalités a été prise par ce développement particulier. En grande partie grâce à lui, le réglage et le réglage de l'ensemble de la recherche floue sont effectués. Répétez brièvement les règles de filtrage et de conversion de mots:
- le mot doit comporter plus de 2 caractères
- le mot ne doit contenir que des lettres, un point et un tiret (tiret)
- si le point est au milieu du mot, un espace est ajouté après
- s'il s'agit d'une abréviation, les points sont découpés et les lettres sont collées ensemble
- n'essayez pas de deviner le mot s'il y a un nombre
- si le mot contient un trait d'union (tiret), puis divisez-le en plusieurs, recherchez séparément et collez à la fin
Compilation de dictionnaires
Comme mentionné précédemment, pour corriger la demande d'un utilisateur, il est nécessaire de déterminer quels mots sont mal orthographiés et lesquels ne le sont pas. Pour cela, un dictionnaire a été créé dans le système où les mots avec l'orthographe correcte doivent être contenus.
Lors de la première étape, la question s'est posée de remplir le dictionnaire - en conséquence, nous avons décidé d'utiliser le contenu du catalogue pour le compiler. Étant donné que les informations sur les marchandises étaient importées de temps à autre à partir d'un système externe et indexées pour le système de recherche en texte intégral Sphinx, il a été décidé d'ajouter la fonctionnalité de compilation du dictionnaire à ce stade. Nous avons suivi la logique suivante: si le mot n'est pas dans le contenu de la marchandise, alors pourquoi essayer de le deviner?
Les informations sur les produits ont été combinées dans un texte commun et effectuées via un convertisseur. Le mode de fonctionnement du convertisseur a été légèrement modifié: lors de la coupure des mots à travers un trait d'union (tiret), chacune des parties a été enregistrée dans le dictionnaire séparément, lors du remplacement des points dans le dictionnaire, les données originales et modifiées sont ajoutées. Et puisque lors de la comparaison des mots pour calculer la distance Damerau-Levenshtein, la transcription du mot est utilisée, en plus du dictionnaire, la transcription est ajoutée.
Il y avait beaucoup de fautes de frappe dans le contenu des marchandises, à cet effet un drapeau a été posé dans le dictionnaire, lors de l'installation dont le mot n'est plus utilisé dans la recherche. Le contenu de 35 000 produits a permis de créer un dictionnaire de 100 000 mots uniques, ce qui n'était finalement pas suffisant pour certaines requêtes des utilisateurs. À cet égard, il était nécessaire de prévoir une fonction de chargement pour son enrichissement. Une commande de console a été créée pour charger les dictionnaires. Le format des fichiers avec les données des dictionnaires doit correspondre à csv. Chaque entrée contient un seul champ avec le champ du dictionnaire lui-même. Afin de distinguer les données téléchargées des données générées en fonction du contenu des marchandises, un drapeau spécial a été ajouté.
Par conséquent, la table de dictionnaire a le schéma suivant:
| Nom du champ | Type de champ |
|---|
| Le mot | chaîne |
| Transcription | chaîne |
| Ajouté manuellement | bool |
| Ne pas utiliser | bool |
Avant le développement de la fonctionnalité de recherche floue, il y avait des champs dans les produits qui contenaient un ensemble de mots avec des fautes de frappe. Lors de la première exécution de la génération du dictionnaire, ils sont entrés dans son contenu. En conséquence, un dictionnaire avec des fautes de frappe a été obtenu, dont le contenu n'était pas approprié pour que la fonctionnalité fonctionne correctement. Par conséquent, une autre commande de console a été ajoutée qui avait la fonctionnalité de génération de dictionnaire inverse. En utilisant le contenu d'un domaine de marchandises donné, l'équipe a recherché des mots dans le dictionnaire et les a effacés du dictionnaire. Après le nettoyage, ces champs ont été exclus de l'indexation.
Intégration Bitrix
Pour implémenter la fonctionnalité minimale requise, trois classes ont été créées:
- DictionaryTable - Systèmes Bitrix ORM pour travailler avec un dictionnaire
- Dictionnaire - classe de génération de dictionnaire
- Search - classe d'implémentation de la recherche
Pour l'intégration dans Bitrix, il était nécessaire d'apporter des modifications à 2 composants:
- bitrix: search.page
- bitrix.search.title
Avant d'exécuter la demande, la méthode de traitement est appelée pour détecter les erreurs et sélectionner les options appropriées:
Pour compiler un dictionnaire, un événement a été enregistré pour indexation par le module de recherche des éléments du bloc d'informations avec les biens (recherche: BeforeIndex).
Plans futurs
Cette approche n'est pas idéale en termes de performances. Avec l'augmentation de la taille du dictionnaire à 1M + mots, le temps de réponse de la base de données peut augmenter considérablement. Bien que le dictionnaire soit petit, les performances nous conviennent. Il peut être nécessaire de mettre en œuvre l'algorithme à l'avenir via un automate Levenshtein ou une arborescence de préfixes.
Conclusion
Ainsi, aucun moteur de recherche n'est épargné par l'apparition de requêtes qui violent les règles d'orthographe généralement acceptées - que ce soit une faute de frappe aléatoire ou un réel manque de connaissance de l'orthographe des mots. Par conséquent, sans même recourir aux options de recherche floue classiques Google ou Yandex, vous pouvez créer les vôtres, grâce auxquelles l'utilisateur et le propriétaire du site pourront obtenir le résultat souhaité.
Le code de notre implémentation peut être consulté dans le référentiel:
github.com/qsoft-dev/damlev-bitrix