Historique d'une demande

Imaginez votre premier jour à un nouvel emploi. Le bureau est situé dans le quartier de la station de métro Kurskaya qui ne vous est pas familière. Le déjeuner approche. Vous ouvrez l'application de recherche, écrivez «manger à Koursk» et obtenez une sélection d'options où vous pourrez dîner.

Qu'est-ce qui se cache derrière la demande «manger sur Koursk» et comment est-elle traitée pour trouver exactement ce dont vous avez besoin? Dans l'article, je vais vous dire comment l'équipe de recherche 2GIS fait tout son possible pour rendre la vie dans les villes plus pratique et confortable pour les utilisateurs.

Il est important de comprendre que le texte de la requête de recherche n'est que la pointe de l'iceberg, une petite partie de ce avec quoi l'utilisateur interagit directement. La requête de recherche elle-même, en plus du texte, contient de nombreuses autres données. Ils comprennent des informations personnalisées sur l'emplacement de l'utilisateur, la zone de la carte qu'il voit, un ensemble d'enregistrements de ses favoris et des informations sur les modes de recherche. Par exemple, une recherche sur une carte ou dans un immeuble, ou peut-être une recherche d'itinéraires. Les données sont la clé du succès d'une bonne fonctionnalité de recherche.

Nous accordons une grande attention à nos données et à leur structure. De plus, nous appelons l'algorithme de recherche dans la recherche structurelle 2GIS, car il est affiné par une recherche efficace et rapide dans nos données structurées. Nous préparons spécifiquement l'index de recherche et les données à partir desquelles il est construit. Je n'entrerai pas dans les détails, je peux seulement dire que les données sont organisées de manière à être suffisamment simples à traiter, qu'elles sont bien compressées et, surtout, elles nous permettent de les traiter rapidement même sur des appareils mobiles.

De plus, la recherche peut fonctionner hors ligne et impose donc des exigences particulières sur la vitesse et le volume de l'index de recherche. Nous accordons une grande attention à cette fonctionnalité - nous compressons constamment l'index de recherche, évaluons les performances sur tous les types de plates-formes et accélérons la fonctionnalité lorsque des cas de recherche spécifiques dépassent la limite de temps définie. Soit dit en passant, nous pouvons nous vanter qu'une requête de recherche ordinaire dans 2GIS sur un appareil mobile est plus rapide que l'application dessine une liste déroulante en fonction des résultats.

Ci-dessous je dévoilerai le voile du secret recouvrant la magie de notre recherche. À titre d'exemple, nous prenons la demande mentionnée "manger à Koursk" . Considérez les étapes de son traitement et ce qui se passe à chacune d'elles. Alors allons-y!

Étape 1. Analyse

Paramètres d'entrée: demande "manger sur Koursk"

Tout d'abord, nous devons analyser le texte de la demande. Ceci est important, car après l'analyse, nous pouvons travailler non pas avec le texte de la demande, mais avec l'ensemble de jetons qui le compose. Les jetons sont des mots de demande uniques. Dans notre cas, nous recevrons un ensemble de trois jetons: «manger» , «sur» , «Koursk» . Il semblerait que tout soit simple, mais le diable est dans les détails. Et parfois, ce n'est pas si évident: par exemple, dans les requêtes "wi-fi" ou "2nd", nous devons comprendre que nous devons gérer de telles combinaisons dans leur intégralité.

Les jetons eux-mêmes contiennent des informations sur le texte du mot, sur la position dans la demande, sur la présence d'un séparateur après le mot et une caractéristique du mot - le registre de ses caractères, qu'il s'agisse d'un nombre, d'un nombre ordinal, d'un numéro de téléphone, d'une adresse ou d'autres données.

Étape 2. Recherche de dictionnaire

Paramètres d'entrée: jetons "manger" , "sur" , "Koursk"


Avec une liste prête de jetons de demande, nous passons à l'étape de recherche de dictionnaire, c'est-à-dire à l'étape à laquelle pour chaque jeton nous trouvons une liste de formes de mots à partir de nos données. Une forme de mot est une information codée sur la racine d'un mot et sa fin.

Nous présentons la recherche par dictionnaire comme un algorithme d'analyse d'un dictionnaire, présenté sous la forme d'un graphique. Les nœuds qu'il contient sont des lettres, ou plutôt des symboles. Un graphique se compose de nœuds de symboles et de transitions entre ces nœuds. Le résultat de la navigation dans notre graphique de dictionnaire est un grand nombre de formes de mots que nous pouvons obtenir en fonction des jetons transférés de l'étape précédente. Nous essayons donc de trouver dans notre dictionnaire une séquence de caractères qui correspond au prochain jeton de la requête. Dans le même temps, comme nous le savons tous, les utilisateurs font des fautes de frappe, manquent des lettres ou font même des erreurs dans la disposition du clavier. Par conséquent, lorsque nous parcourons le dictionnaire, nous appliquons certaines manipulations afin de prendre en compte un facteur humain possible ou d'essayer de deviner ce qu'une personne gagne en ce moment. Diverses transformations de la chaîne de caractères sont utilisées: insertions, remplacements, ajout de caractères, etc.

Par conséquent, pour chaque jeton de demande du graphique, nous extrayons un ensemble de formes de mots avec des informations sur la racine et la fin du mot, des informations sur le nombre de caractères dans la forme de mot et une estimation du trouvé. Estimation d'une conclusion - une évaluation caractérisant la distance de vocabulaire d'une séquence de caractères trouvée à la séquence souhaitée. L'évaluation caractérise la différence entre la chaîne de caractères trouvée et le jeton de demande.

Donc, pour les jetons, nous trouvons des formes de mots:

• 13 formes pour "manger" : "manger", "manger", "paese", "payot", ...
• 3 formes pour "on" : "na", "nu", "on"
• 48 formulaires pour "Kursk" : "Kursk", "Kursk", "Kursk", "Kursk", "Kurako", ...

Ensuite, les formes de mots trouvées sont filtrées en fonction de leur évaluation. Les meilleurs d'entre eux, c'est-à-dire le plus près possible des mots de la requête, entrent dans la liste des termes. Par le terme, nous entendons la forme du mot et l'estimation de la conclusion. De plus, en plus des formes de mots trouvées, les termes ajoutés à l'aide des règles de morphologie sont ajoutés à la liste. Une étape importante du traitement morphologique est l'ajout d'une évaluation morphologique. Le fait est que notre recherche utilise un mécanisme de traitement morphologique puissant qui nous permet non seulement de trouver des mots similaires dans le dictionnaire, mais selon les règles du langage naturel, il est plus précis de trouver ce qui intéresse exactement l'utilisateur par le sens, et pas seulement par la similitude des mots.

Ainsi, pour les jetons, les termes seront créés:

• «Manger» : «manger», «manger», «manger», «manger», «manger»
• «On» : «on», «na», «nu»
• «Kursk» : «Kursk», «Kursk», «Kursk», «Kursk», «Kursk»

À ce stade, la recherche par dictionnaire se termine. Nous avons traité la demande et avons pour chaque jeton une liste de termes qui feront l'objet d'un traitement ultérieur. Ces termes contiennent toutes les informations sur le mot qu'ils représentent et permettent d'évaluer comment chacun d'eux a été trouvé.

Étape 3. Recherche d'entrées de données

Entrée: un ensemble de termes pour chaque partie de la demande

• «Manger» : «manger», «manger», «manger», «manger», «manger»
• «On» : «on», «na», «nu»
• «Kursk» : «Kursk», «Kursk», «Kursk», «Kursk», «Kursk»

Ayant reçu de l'étape précédente un ensemble de termes pour chacune des parties de la demande, nous procédons à leur recherche par notre index. Chaque document dans les données a plusieurs titres et est écrit dans l' index inverse afin que nous puissions facilement trouver toutes les références au terme souhaité dans des documents spécifiques représentant des organisations, des adresses ou tout autre.

Pour chacune des parties de la demande et pour chacun des termes de ces parties, nous recherchons des documents contenant des mots codés en termes. Ainsi, pour certaines parties de la demande, les entrées seront trouvées dans tous les termes:

• «Manger» : 18 entrées
• Sur : 4304 entrées
• Koursk : 79 entrées

De toute évidence, la préposition «on» se produit plusieurs fois et tombe donc dans de nombreux titres de documents - «café à emporter», «jouer sur la console», «enregistrement de la machine». "Eat" et "Kursk" sont également utilisés à plusieurs reprises. Le deuxième mot avec ses termes se retrouve dans nos données beaucoup plus souvent que le premier.


Par hit, nous considérons la correspondance d'un mot d'une requête de recherche à un mot d'un document spécifique. Ces résultats sont enregistrés dans la liste, qui sera analysée à l'étape suivante. Lors de l'ajout d'un hit, nous copions non seulement des données sur le mot dans le document à partir du terme, mais calculons également la meilleure estimation de la façon dont le mot peut être trouvé. En d'autres termes, nous choisissons une évaluation morphologique du terme, ou une évaluation de la façon dont le terme a été trouvé dans le dictionnaire, en fonction de la note la plus proche du jeton de demande.

Cette étape est un prélude au début de la recherche elle-même. Nous avons préparé un ensemble de résultats dans des documents spécifiques, sur la base desquels l'algorithme suivant sélectionnera et évaluera ce qui doit être donné à l'utilisateur en conséquence.

Étape 4. Le cœur de la recherche

Entrée: liste de résultats

• «Manger» : 18 entrées
• Sur : 4304 entrées
• Koursk : 79 entrées

En fait, la liste des résultats dans notre implémentation est un conteneur assez délicat. Il est important de comprendre que lors de l'ajout de hits, des nœuds spéciaux sont créés où les hits eux-mêmes sont enregistrés, et un lien vers le document dans lequel ces hits sont tombés.

Par conséquent, il sera plus correct d'afficher les données d'entrée comme suit:
Entrée: conteneur de nœuds de document

• document1: {hits, ...}
• document2: {hits, ...}
• document3: {hits, ...}
• document4: {hits, ...}
• ...

Tout d'abord, la recherche commence à contourner l'arborescence de documents et chaque nœud l'envoie à l'analyseur, qui évalue si le document de ce nœud est approprié pour être le résultat pour entrer dans la sortie. Pour comprendre avec quels volumes l'analyseur doit travailler, je dirai qu'au début le conteneur contient plus de 3000 nœuds! Mais des nœuds peuvent être ajoutés pendant le processus d'analyse, par conséquent, ils sont en fait encore plus traités. Il n'est pas exagéré de dire que l'analyse est la partie la plus coûteuse de la recherche et en même temps l'une des fonctions les plus complexes et les plus importantes du projet. Néanmoins, il fonctionne extrêmement rapidement même sur les appareils mobiles.

Étape 5. Analyse

Entrée: noeud du document: {hits, ...}


L'analyse commence par l'obtention d'une liste de titres à partir du nœud. Le titre est un titre et une liste de hits qui tombent dans ce titre du document. Ces rubriques seront évaluées dans un premier temps. Il est important pour nous de découvrir l'utilité de chaque titre. L'utilité peut être bonne, faible et indésirable.

Pour chacun des titres, les meilleurs de la chaîne de succès sont sélectionnés - le meilleur en termes de longueur et de vocabulaire, composé de la similitude des succès. En fonction de la meilleure chaîne, le titre sera évalué pour son utilité. Pour déterminer l'utilité de la chaîne, nous utilisons également un mécanisme basé sur la fréquence des mots dans les documents. En gros, plus un mot apparaît souvent dans un document, plus il est important ( TF-IDF ). Donc, si la chaîne contient un mot important du titre du document sans fortes différences morphologiques, par exemple un excellent nombre ou sexe, nous considérons le titre utile. Un titre peut également être utile si ses hits couvrent complètement les mots du titre du document.

À l'aide de l'utilitaire, tous les titres forment un masque d'utilité pour le nœud. Ce masque nous donne une idée des jetons de requête couverts par le nœud analysé. Et avec son aide, nous déterminons en grande partie s'il convient d'analyser davantage le nœud.

Par conséquent, nous n'avons pas seulement un document de l'index, mais un ensemble de données structurelles représentant un résultat potentiel avec des informations sur la façon dont il peut être trouvé.

Étape 6. Évaluation

Entrée: noeud du document: {hits, ...}


En fonction du masque utilitaire, nous traiterons le nœud ou passerons immédiatement au suivant. Parmi les nombreux nœuds traités, nous accumulons diverses informations sur leur totalité. Par exemple, beaucoup de titres de nœuds, de relations entre les nœuds et d'autres données.

Commence ensuite l'analyse des titres des nœuds interconnectés entre eux. En fait, de nombreux nœuds sont combinés dans un graphe de nœuds, que nous évaluons.

À partir des nœuds des nœuds du graphique, nous obtenons une liste de titres classés. En termes simples, à partir d'une variété de nœuds, nous composons une seule liste de titres, dans laquelle pour chaque élément, nous ajoutons également une estimation et une combinaison de facteurs à partir des résultats des titres de tous les nœuds participants.

Évaluation - une structure avec des informations sur le nombre de mots impliqués dans un titre à partir d'une requête et de nombreux autres facteurs sur la façon dont le mot a été trouvé et traité - à partir de l'étape de recherche du dictionnaire. Il est important que ces notes du titre classé participent à la sélection des meilleures notes. Certains d'entre eux seront marqués comme sélectionnés et contribueront à l'évaluation finale du résultat que l'utilisateur voit.

L'évaluation globale donne les informations sur les résultats qui seront cruciales pour trier la sortie entière. Il contient des facteurs tels que, par exemple, des mots manquants dans une requête. Cette mesure caractérise le nombre de mots qui n'étaient pas couverts par un nœud avec ses informations structurelles.

Sur la base des informations sur l'utilité des titres, la clarté du résultat est déterminée. La clarté peut être bonne, faible et mauvaise. Et il est calculé avec la participation de tous les titres sélectionnés pour le nœud traité. Toutes ces données ont un effet dramatique sur le sort des résultats et l'ordre dans lequel ils sont publiés.

Progressivement, nous approchons de la fin de l'analyse du nœud. Avant que le nœud ne quitte finalement l'analyseur et ne devienne un résultat potentiel, nous effectuons quelques manipulations supplémentaires. Par exemple, la compatibilité des titres de documents sélectionnés.

Un nœud qui a passé tous les cercles de l'analyseur forme un résultat qui contient des informations sur les en-têtes sélectionnés et un document. Le résultat, qui donne une bonne couverture de la requête de recherche, est envoyé au post-traitement.

Étape 7. Post-traitement

Entrée: résultat construit à partir du nœud


L'analyseur filtre de nombreux enregistrements de l'index avant qu'ils ne deviennent des résultats. Cependant, au cours de l'analyse, de nombreux résultats potentiels peuvent être évalués et envoyés pour traitement. Pour ne montrer à l'utilisateur que les plus utiles par ordre de pertinence, nous devons supprimer les pires options trouvées par l'analyseur.

À l'étape précédente, une évaluation générale du résultat a été mentionnée. Une évaluation générale nous permet de couper les pires résultats au stade du post-traitement. La gradation est la suivante. Les résultats qui ne couvrent aucun jeton de demande sont évidemment pires que ceux qui couvrent entièrement la demande de l'utilisateur. Des résultats avec une plus grande clarté sont évidemment moins souhaitables que des résultats avec une bonne clarté. Le post-processeur accumule des informations sur les résultats entrants et élimine ceux qui sont évidemment pires. Le reste s'ajoute à la liste.

Avant de donner aux utilisateurs affamés des informations sur le café, nous effectuons le traitement final - triez par pertinence. Le tri implique de nombreux facteurs, calculés et agrégés à différentes étapes de la recherche. Et en fin de compte, les résultats de recherche pour "manger à Koursk" sont plus de 500 résultats. Beaucoup d'entre eux ont été retrouvés de la même manière et ont donc la même note. Ils seront triés par popularité des utilisateurs.

Conclusion

Nous avons reçu l'extradition avec de nombreux cafés et restaurants et, joyeux, nous allons dîner. Nous avons obtenu tous les résultats en une fraction de seconde. Nous n'avons même pas besoin d'une connexion Internet.

L'application stocke les index de recherche sur l'appareil. Un tel schéma nous fournit des tâches non triviales d'optimisation de la compression des données et de la vitesse de traitement - après tout, la recherche devrait fonctionner rapidement sur une grande variété d'appareils mobiles! Cependant, c'est une histoire complètement différente.

Aujourd'hui, j'ai essayé d'ouvrir le capot de notre moteur de recherche et de montrer comment nous aidons les utilisateurs à trouver ce dont ils ont besoin dans la ville, et à le faire rapidement et facilement. J'espère que c'était instructif.