Verlauf einer Anfrage

Stellen Sie sich Ihren ersten Tag bei einem neuen Job vor. Das Büro befindet sich im Bereich der völlig unbekannten U-Bahn-Station Kurskaya. Das Mittagessen rückt näher. Sie öffnen die Suchanwendung, schreiben "eat on Kursk" und erhalten eine Auswahl an Optionen, in denen Sie speisen können.

Was steckt hinter der Anfrage „Essen auf Kursk“ und wie wird sie verarbeitet, um genau das zu finden, was Sie brauchen? In dem Artikel werde ich Ihnen erklären, wie das 2GIS Search-Team alles tut, um das Leben in den Städten für Benutzer bequemer und komfortabler zu gestalten.

Es ist wichtig zu verstehen, dass der Text der Suchabfrage nur die Spitze des Eisbergs ist, ein kleiner Teil dessen, mit dem der Benutzer direkt interagiert. Die Suchabfrage selbst enthält neben Text viele andere Daten. Dazu gehören personalisierte Informationen über den Standort des Benutzers, den Bereich der Karte, den er sieht, eine Reihe von Einträgen aus seinen Favoriten und Informationen zu den Suchmodi. Zum Beispiel eine Suche auf einer Karte oder in einem Gebäude oder eine Suche nach Wegbeschreibungen. Daten sind der Schlüssel zum Erfolg einer guten Suchfunktion.

Wir achten sehr auf unsere Daten und deren Struktur. Darüber hinaus nennen wir den Suchalgorithmus in der 2GIS-Struktursuche, da er durch eine effektive und schnelle Suche in unseren strukturierten Daten geschärft wird. Wir bereiten speziell den Suchindex und die Daten vor, aus denen er erstellt wird. Ich werde nicht auf Details eingehen, ich kann nur sagen, dass die Daten so organisiert sind, dass sie einfach genug zu verarbeiten sind, gut komprimiert sind und vor allem auch auf Mobilgeräten schnell verarbeitet werden können.

Darüber hinaus kann die Suche offline funktionieren und stellt daher besondere Anforderungen an die Geschwindigkeit und das Volumen des Suchindex. Wir achten sehr auf diese Funktion - wir komprimieren ständig den Suchindex, bewerten die Leistung auf allen Arten von Plattformen und beschleunigen die Funktionalität, wenn bestimmte Suchfälle das festgelegte Zeitlimit überschreiten. Übrigens können wir uns rühmen, dass eine normale Suchabfrage in 2GIS auf einem mobilen Gerät schneller ist, als die Anwendung basierend auf den Ergebnissen eine Dropdown-Liste erstellt.

Im Folgenden werde ich den Schleier der Geheimhaltung enthüllen, der die Magie unserer Suche bedeckt. Als Beispiel nehmen wir die erwähnte Anfrage "Essen auf Kursk" . Betrachten Sie die Phasen der Verarbeitung und was bei jedem von ihnen passiert. Also lass uns gehen!

Stufe 1. Analyse

Eingabeparameter: Anfrage "Essen auf Kursk"

Zunächst müssen wir den Anfragetext analysieren. Dies ist wichtig, da wir nach dem Parsen nicht mit dem Anforderungstext arbeiten können, sondern mit dem Satz von Token, aus denen er besteht. Token sind einzelne Anforderungswörter. In unserem Fall erhalten wir einen Satz von drei Token: "essen" , "ein" , "Kursk" . Es scheint, dass alles einfach ist, aber der Teufel steckt im Detail. Und manchmal ist es nicht so offensichtlich: Zum Beispiel müssen wir bei "Wi-Fi" - oder "2nd" -Abfragen verstehen, dass wir solche Kombinationen in ihrer Gesamtheit behandeln sollten.

Die Token selbst enthalten Informationen über den Worttext, über die Position in der Anforderung, über das Vorhandensein eines Trennzeichens nach dem Wort und einige Merkmale des Wortes - das Register seiner Zeichen, unabhängig davon, ob es sich bei dem Wort um eine Zahl, eine Ordnungszahl, eine Telefonnummer, eine Adresse oder andere Daten handelt.

Stufe 2. Wörterbuchsuche

Eingabeparameter: Token "essen" , "ein" , "Kursk"


Mit einer fertigen Liste von Anforderungstoken fahren wir mit der Phase der Wörterbuchsuche fort, dh mit der Phase, in der wir für jedes Token eine Liste von Wortformen aus unseren Daten finden. Eine Wortform ist eine verschlüsselte Information über die Wurzel eines Wortes und sein Ende.

Wir präsentieren die Wörterbuchsuche als Algorithmus zur Analyse eines Wörterbuchs, dargestellt in Form eines Diagramms. Die Knoten darin sind Buchstaben oder vielmehr Symbole. Ein Graph besteht aus Symbolknoten und Übergängen zwischen diesen Knoten. Das Ergebnis des Umgehens unseres Wörterbuchdiagramms sind viele Wortformen, die wir basierend auf den übertragenen Token aus der vorherigen Phase erhalten können. Deshalb versuchen wir, in unserem Wörterbuch eine Folge von Zeichen zu finden, die mit dem nächsten Token aus der Anfrage übereinstimmt. Gleichzeitig machen Benutzer, wie wir alle wissen, Tippfehler, verpassen Buchstaben oder machen sogar Fehler im Tastaturlayout. Wenn wir uns im Wörterbuch umsehen, wenden wir daher einige Manipulationen an, um einen möglichen menschlichen Faktor zu berücksichtigen oder um zu erraten, was eine Person gerade gewinnt. Es werden verschiedene Transformationen der Zeichenkette verwendet: Einfügungen, Ersetzungen, Anhängen von Zeichen und dergleichen.

Als Ergebnis extrahieren wir für jedes Anforderungstoken aus dem Diagramm eine Reihe von Wortformen mit Informationen über die Wurzel und das Ende des Wortes, Informationen über die Anzahl der Zeichen in der Wortform und eine Schätzung der gefundenen. Schätzung eines Befundes - eine Bewertung, die den Wortschatzabstand einer gefundenen Zeichenfolge zur gewünschten Folge charakterisiert. Die Auswertung gibt an, um wie viel sich die gefundene Zeichenfolge vom Anforderungstoken unterscheidet.

Für Token finden wir also Wortformen:

• 13 Formen für "essen" : "essen", "essen", "paese", "payot", ...
• 3 Formen für "on" : "na", "nu", "on"
• 48 Formulare für "Kursk" : "Kursk", "Kursk", "Kursk", "Kursk", "Kurako", ...

Als nächstes werden die gefundenen Wortformen abhängig von ihrer Bewertung gefiltert. Die besten von ihnen, dh so nah wie möglich an den Wörtern aus der Abfrage, fallen in die Liste der Begriffe. Mit dem Begriff meinen wir die Wortform und die Schätzung des Befundes. Zusätzlich zu den gefundenen Wortformen werden der Liste die Begriffe hinzugefügt, die nach den Regeln der Morphologie hinzugefügt wurden. Ein wichtiger Schritt in der morphologischen Verarbeitung ist die Hinzufügung einer morphologischen Bewertung. Tatsache ist, dass unsere Suche einen starken morphologischen Verarbeitungsmechanismus verwendet, der es uns ermöglicht, nicht nur ähnliche Wörter aus dem Wörterbuch zu finden, sondern nach den Regeln der natürlichen Sprache auch genauer zu finden, was den Benutzer genau durch Bedeutung und nicht nur durch Ähnlichkeit von Wörtern interessiert.

Für Token werden also die Begriffe erstellt:

• "Essen" : "essen", "essen", "essen", "essen", "essen"
• "Ein" : "Ein", "na", "nu"
• "Kursk" : "Kursk", "Kursk", "Kursk", "Kursk", "Kursk"

In diesem Stadium endet die Wörterbuchsuche. Wir haben die Anfrage bearbeitet und für jedes Token eine Liste von Begriffen, die weiter verarbeitet werden. Diese Begriffe enthalten alle Informationen zu dem Wort, das sie darstellen, und enthalten eine Einschätzung darüber, wie sie gefunden wurden.

Schritt 3. Dateneinträge suchen

Eingabe: Eine Reihe von Begriffen für jeden Teil der Anforderung

• "Essen" : "essen", "essen", "essen", "essen", "essen"
• "Ein" : "Ein", "na", "nu"
• "Kursk" : "Kursk", "Kursk", "Kursk", "Kursk", "Kursk"

Nachdem wir aus der vorherigen Phase eine Reihe von Begriffen für jeden Teil der Anfrage erhalten haben, suchen wir sie anhand unseres Index. Jedes Dokument in den Daten hat viele Überschriften und ist im umgekehrten Index geschrieben, sodass wir alle Verweise auf den gewünschten Begriff in bestimmten Dokumenten, die Organisationen, Adressen oder andere darstellen, leicht finden können.

Für jeden Teil der Anfrage und für jeden der Begriffe dieser Teile suchen wir nach Dokumenten, die in Begriffen codierte Wörter enthalten. Für Teile der Anfrage werden Einträge in allen Begriffen gefunden:

• "Essen" : 18 Einträge
• Ein : 4.304 Einträge
• Kursk : 79 Einträge

Offensichtlich kommt die Präposition "Ein" oft vor und fällt daher in viele Überschriften von Dokumenten - "Kaffee zum Mitnehmen", " Auf der Konsole spielen", "Registrierung der Maschine". "Eat" und "Kursk" werden ebenfalls wiederholt verwendet. Das zweite Wort mit seinen Begriffen kommt in unseren Daten viel häufiger vor als das erste.


Bei einem Treffer betrachten wir die Übereinstimmung eines Wortes aus einer Suchabfrage mit einem Wort aus einem bestimmten Dokument. Diese Treffer werden in der Liste gespeichert, die im nächsten Schritt analysiert wird. Beim Hinzufügen eines Treffers kopieren wir nicht nur Daten über das Wort im Dokument aus dem Begriff, sondern berechnen auch die beste Schätzung, wie das Wort gefunden werden konnte. Mit anderen Worten, wir wählen eine morphologische Bewertung des Begriffs oder eine Bewertung, wie der Begriff im Wörterbuch gefunden wurde, je nachdem, welche der Bewertungen näher am Anforderungstoken liegt.

Diese Phase ist der Auftakt zum Beginn der Suche. Wir haben eine Reihe von Treffern in bestimmten Dokumenten vorbereitet, auf deren Grundlage der folgende Algorithmus auswählt und bewertet, was dem Benutzer als Ergebnis gegeben werden muss.

Stufe 4. Das Herzstück der Suche

Eingang: Trefferliste

• "Essen" : 18 Einträge
• Ein : 4.304 Einträge
• Kursk : 79 Einträge

Tatsächlich ist die Trefferliste in unserer Implementierung ein ziemlich kniffliger Container. Es ist wichtig zu verstehen, dass beim Hinzufügen von Treffern spezielle Knoten erstellt werden, in denen die Treffer selbst aufgezeichnet werden, und ein Link zu dem Dokument, in das diese Treffer gefallen sind.

Daher ist es korrekter, die Eingabedaten wie folgt anzuzeigen:
Eingang: Container mit Dokumentknoten

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

Zunächst beginnt die Suche mit der Umgehung des Dokumentbaums, und jeder Knoten sendet ihn an den Analysator, der bewertet, ob das Dokument von diesem Knoten als Ergebnis für den Zugriff auf die Ausgabe geeignet ist. Um zu verstehen, mit welchen Volumes der Analysator arbeiten muss, möchte ich sagen, dass der Container zu Beginn mehr als 3000 Knoten enthält! Während des Crawlprozesses können jedoch Knoten hinzugefügt werden, sodass diese sogar noch weiter verarbeitet werden. Es ist keine Übertreibung zu sagen, dass die Analyse der teuerste Teil der Suche und gleichzeitig eine der komplexesten und umfangreichsten Funktionen des Projekts ist. Trotzdem läuft es auch auf mobilen Geräten extrem schnell.

Stufe 5. Analyse

Eingabe: Dokumentknoten: {Treffer, ...}


Die Analyse beginnt mit dem Abrufen einer Liste von Titeln vom Knoten. Der Titel ist ein Titel und eine Liste von Treffern, die in diesen Titel des Dokuments fallen. Diese Überschriften werden in der ersten Phase bewertet. Für uns ist es wichtig, die Nützlichkeit jedes Titels herauszufinden. Nützlichkeit kann gut, schwach und Junk sein.

Für jeden der Titel werden die Besten der Treffer-Kette ausgewählt - die besten in Länge und Wortschatz, bestehend aus der Ähnlichkeit der Treffer. Basierend auf der besten Kette wird der Titel auf Nützlichkeit bewertet. Um die Nützlichkeit der Kette zu bestimmen, verwenden wir auch einen Mechanismus, der auf der Häufigkeit von Wörtern in Dokumenten basiert. Grob gesagt ist es umso wichtiger, je öfter ein Wort in einem Dokument vorkommt ( TF-IDF ). Wenn die Kette also ein wichtiges Wort aus dem Titel des Dokuments ohne starke morphologische Unterschiede enthält, z. B. eine hervorragende Anzahl oder ein hervorragendes Geschlecht, halten wir den Titel für nützlich. Ein Titel kann auch nützlich sein, wenn seine Treffer die Wörter aus dem Titel des Dokuments vollständig abdecken.

Mit dem Dienstprogramm bilden alle Titel eine Dienstprogrammmaske für den Knoten. Diese Maske gibt uns eine Vorstellung von den Anforderungstoken, die vom analysierten Knoten abgedeckt werden. Und mit seiner Hilfe bestimmen wir weitgehend, ob der Knoten weiter analysiert werden soll.

Infolgedessen haben wir nicht nur ein Dokument aus dem Index, sondern eine Reihe von Strukturdaten, die ein potenzielles Ergebnis darstellen und Informationen darüber enthalten, wie es gefunden werden kann.

Schritt 6. Bewertung

Eingabe: Dokumentknoten: {Treffer, ...}


Abhängig von der Dienstprogrammmaske verarbeiten wir entweder den Knoten oder fahren sofort mit dem nächsten fort. Von den vielen verarbeiteten Knoten sammeln wir verschiedene Informationen über ihre Gesamtheit. Zum Beispiel viele Knotentitel, Beziehungen zwischen Knoten und einige andere Daten.

Als nächstes beginnt die Analyse der Titel der miteinander verbundenen Knoten. Tatsächlich werden viele Knoten zu einem Knotendiagramm zusammengefasst, das wir auswerten.

Von den Knoten der Diagrammknoten erhalten wir eine Liste der Ranglisten-Titel. Einfach ausgedrückt, erstellen wir aus einer Vielzahl von Knoten eine einzelne Liste von Titeln, in der wir für jedes Element auch eine Schätzung und eine Reihe von Faktoren aus den Treffern der Titel aller teilnehmenden Knoten hinzufügen.

Auswertung - eine Struktur mit Informationen über die Anzahl der Wörter, die an einem Titel aus einer Abfrage beteiligt sind, und vielen anderen Faktoren darüber, wie das Wort gefunden und verarbeitet wurde - beginnend mit der Wörterbuchsuchphase. Es ist wichtig, dass diese Noten aus dem Ranglisten-Titel an der Auswahl der besten Noten teilnehmen. Einige von ihnen werden als ausgewählt markiert und tragen zur endgültigen Bewertung des Ergebnisses bei, das der Benutzer sieht.

Die Gesamtbewertung liefert die Ergebnisinformationen, die für die Sortierung der gesamten Ausgabe von entscheidender Bedeutung sind. Es enthält Faktoren wie beispielsweise fehlende Wörter in einer Abfrage. Diese Kennzahl kennzeichnet die Anzahl der Wörter, die von einem Knoten mit seinen Strukturinformationen nicht abgedeckt wurden.

Basierend auf den Informationen über die Nützlichkeit der Titel wird die Klarheit des Ergebnisses bestimmt. Klarheit kann gut, schwach und schlecht sein. Und es wird unter Beteiligung aller ausgewählten Titel für den verarbeiteten Knoten berechnet. Alle diese Daten haben einen dramatischen Einfluss auf das Schicksal der Ergebnisse und die Reihenfolge, in der sie veröffentlicht werden.

Allmählich nähern wir uns dem Ende der Analyse des Knotens. Bevor der Knoten den Analysator endgültig verlässt und ein potenzielles Ergebnis darstellt, führen wir einige weitere spezifizierende Manipulationen durch. Zum Beispiel die Kompatibilität ausgewählter Dokumenttitel.

Ein Knoten, der alle Kreise des Analysators passiert hat, bildet ein Ergebnis, das Informationen zu den ausgewählten Kopfzeilen und einem Dokument enthält. Das Ergebnis, das eine gute Abdeckung der Suchabfrage bietet, wird an die Nachbearbeitung gesendet.

Schritt 7. Nachbearbeitung

Eingabe: Ergebnis aus Knoten aufgebaut


Der Analysator filtert viele Datensätze aus dem Index heraus, bevor sie zu Ergebnissen werden. Während der Analyse können jedoch viele potenzielle Ergebnisse ausgewertet und zur Verarbeitung gesendet werden. Um dem Benutzer nur die nützlichsten in der Reihenfolge ihrer Relevanz anzuzeigen, müssen die schlechtesten vom Analysator gefundenen Optionen abgeschnitten werden.

Im vorherigen Schritt wurde eine allgemeine Bewertung des Ergebnisses erwähnt. Eine allgemeine Bewertung ermöglicht es uns, die schlechtesten Ergebnisse in der Nachbearbeitungsphase abzuschneiden. Die Abstufung ist wie folgt. Ergebnisse, die keine Anforderungstoken abdecken, sind offensichtlich schlechter als diejenigen, die die Anforderung des Benutzers vollständig abdecken. Ergebnisse mit schlechterer Klarheit sind offensichtlich weniger wünschenswert als Ergebnisse mit guter Klarheit. Der Postprozessor sammelt Informationen über die eingehenden Ergebnisse und eliminiert diejenigen, die offensichtlich schlechter sind. Der Rest wird der Liste hinzugefügt.

Bevor wir dem hungrigen Benutzer Informationen über das Café geben, führen wir die endgültige Verarbeitung durch - sortieren nach Relevanz. Das Sortieren umfasst viele Faktoren, die in verschiedenen Phasen der Suche berechnet und aggregiert werden. Und letztendlich sind die Suchergebnisse für "eat on Kursk" mehr als 500 Ergebnisse. Viele von ihnen wurden auf die gleiche Weise gefunden und haben daher die gleiche Bewertung. Sie werden nach Benutzerbeliebtheit sortiert.

Fazit

Wir haben die Auslieferung mit vielen Cafés und Restaurants erhalten und gehen freudig zum Abendessen. Wir haben alle Ergebnisse in Sekundenbruchteilen erhalten. Wir brauchen auch keine Internetverbindung.

Die Anwendung speichert Suchindizes auf dem Gerät. Ein solches Schema bietet uns nicht triviale Aufgaben zur Optimierung der Datenkomprimierung und Verarbeitungsgeschwindigkeit - schließlich sollte die Suche auf einer Vielzahl von Mobilgeräten schnell funktionieren! Dies ist jedoch eine ganz andere Geschichte.

Heute habe ich versucht, die Motorhaube unserer Suchmaschine zu öffnen und zu zeigen, wie wir Benutzern helfen, das zu finden, was sie in der Stadt benötigen, und dies schnell und bequem. Ich hoffe es war informativ.