Wir alle machen Fehler: In diesem Fall handelt es sich um Suchanfragen. Die Anzahl der Websites für den Verkauf von Waren und Dienstleistungen wächst mit den Bedürfnissen der Benutzer, aber sie können nicht immer das finden, wonach sie suchen - nur weil sie den Namen des erforderlichen Produkts falsch eingeben. Die Lösung für dieses Problem wird durch die Implementierung einer Fuzzy-Suche erreicht, dh unter Verwendung des Algorithmus zum Finden der nächstgelegenen Werte unter Berücksichtigung möglicher Fehler oder Tippfehler des Benutzers. Der Umfang einer solchen Suche ist groß genug - wir haben es geschafft, nach einem großen Online-Shop im Lebensmitteleinzelhandel zu suchen.
Anfänglicher Suchstatus
Der Online-Shop wurde auf der Plattform 1C-Bitrix: Site Management entwickelt. Um die Suche zu implementieren, verwendeten wir das Standard-Bitrix-Suchmodul und die Sphinxsearch-Volltext-Engine. In der Sphinxsuche wurde der Echtzeit-Indextyp (RT) verwendet, für den keine statische Datenquelle erforderlich ist, der jedoch jederzeit in Echtzeit ausgefüllt werden kann. Auf diese Weise können Sie den Suchindex flexibel aktualisieren, ohne ihn vollständig neu zu indizieren. Da der RT-Index nur SphinxQL als Abfrageprotokoll verwendet, wurde die Integration über dieses Protokoll durchgeführt. SphinxQL ist ein MySQL-ähnliches Abfrageprotokoll, das die Möglichkeit der Verbindung über Standard-MySQL-Clients implementiert und gleichzeitig die SQL-Syntax mit einigen Einschränkungen und eigenen Besonderheiten bietet. Das Suchmodul verwendet Abfragen zum Auswählen / Einfügen / Ersetzen / Löschen.
Im Bitrix-System wurde die Indizierung von Daten von Waren, Kategorien und Marken durchgeführt. Informationen zu diesen Entitäten wurden an Sphinx übertragen, wodurch der RT-Index aktualisiert wurde. Wenn Daten im Online-Shop aktualisiert werden, wird ein Ereignis ausgelöst, das die Daten in Sphinx aktualisiert. Die Konsistenz der Daten erfolgt über die Entitätskennung im Online-Shop.
Wenn ein Benutzer in einem Online-Shop sucht, stellt das System eine Anfrage mit einem Suchbegriff in Sphinx und erhält Kennungen von Entitäten, wählt aus den Datenbankinformationen auch Entitäten aus und bildet eine Seite mit den Ergebnissen der Suchergebnisse.
Zu Beginn der Lösung des Fuzzy-Suchproblems lautete das allgemeine Schema der Sucharchitektur für das Projekt wie folgt:
Technologieauswahl
Unsere Aufgabe war es, die Anfrage des Benutzers zu erraten, die Tippfehler enthalten kann. Dazu müssen wir jedes Wort in der Anfrage analysieren und entscheiden, ob der Benutzer es richtig geschrieben hat oder nicht. Im Fehlerfall sollten die am besten geeigneten Optionen ausgewählt werden. Die Bestimmung der korrekten Schreibweise von Wörtern ist ohne eine Datenbank mit Wörtern und Wortformen der Sprache, in der wir sie erraten möchten, nicht möglich. Vereinfacht gesagt kann eine solche Datenbank als Wörterbuch bezeichnet werden - er war es, den wir brauchten.
Um Substitutionsoptionen für fehlerhaft eingegebene Wörter auszuwählen, wurde die beliebte Damerau-Levenshtein-Entfernungsberechnungsformel gewählt. Diese Formel ist ein Algorithmus zum Vergleichen von zwei Wörtern. Das Ergebnis des Vergleichs ist die Anzahl der Operationen, um ein Wort in ein anderes umzuwandeln. Anfänglich beinhaltet die Levenshtein-Distanz die Verwendung von 3 Operationen:
Die Damerau-Levenshtein-Distanz ist eine erweiterte Version der Levenshtein-Distanz und fügt eine weitere Operation hinzu: die Transposition, dh eine Permutation zweier benachbarter Zeichen.
Somit wird die Anzahl der empfangenen Operationen zur Anzahl der Fehler, die der Benutzer beim Schreiben des Wortes gemacht hat. Wir haben die Begrenzung auf zwei Fehler gewählt, da eine größere Anzahl keinen Sinn ergab: In diesem Fall erhalten wir zu viele Optionen zum Ersetzen, was die Wahrscheinlichkeit eines Fehlschlags erhöht.
Für eine relevantere Suche nach klangähnlichen Wortvarianten wurde die Metaphonfunktion verwendet - diese Funktion wandelt ein Wort in seine phonetische Form um. Leider funktioniert das Metaphon nur mit den Buchstaben des englischen Alphabets. Bevor wir die phonetische Form berechnen, transliterieren wir das Wort. Der Wert der phonetischen Form wird im Wörterbuch gespeichert und auch in der Benutzeranforderung berechnet. Die resultierenden Werte werden mit der Damerau-Levenshtein-Distanzfunktion verglichen.
Das Wörterbuch wird in der MySQL-Datenbank gespeichert. Um das Wörterbuch nicht in den Anwendungsspeicher zu laden, wurde beschlossen, den Damerau-Levenshtein-Abstand auf der Basisseite zu berechnen.
Die benutzerdefinierte Funktion zur Berechnung der Damerau-Levenshtein-Distanz , die auf der Grundlage
der von Linus Torvalds geschriebenen C-Funktion geschrieben wurde , hat unsere Anforderungen vollständig erfüllt. Erstellt von Diego Torres.
Nach der Berechnung des Damerau-Levenshtein-Abstands mussten die Ergebnisse nach Ähnlichkeitsgrad sortiert werden, um den am besten geeigneten auszuwählen. Dazu haben wir den Oliver-Algorithmus verwendet: Berechnung der Ähnlichkeit zweier Linien. In PHP wird dieser Algorithmus durch die Funktion Similar_text dargestellt. Die ersten beiden Parameter der Funktion akzeptieren die zu vergleichenden Eingabezeilen. Die Reihenfolge des Zeichenfolgenvergleichs ist wichtig, da die Funktion abhängig von der Reihenfolge, in der die Zeilen an die Funktion übergeben werden, unterschiedliche Werte liefert. Dem dritten Parameter sollte die Variable übergeben werden, in die das Ergebnis des Vergleichs gestellt wird. Dies ist eine Zahl von 0 bis 100, was den Prozentsatz der Ähnlichkeit zwischen den beiden Zeilen bedeutet. Nach der Berechnung werden die Ergebnisse in absteigender Reihenfolge der Ähnlichkeit sortiert und anschließend die Optionen mit den besten Werten ausgewählt.
Da die Berechnung der Damerau-Levenshtein-Distanz nach der Transkription des Wortes durchgeführt wurde, fielen die Wörter mit nicht ganz relevanten Bedeutungen in die Ergebnisse. In diesem Zusammenhang haben wir die Auswahl der Optionen mit einem Übereinstimmungsprozentsatz von mehr als 70% eingeschränkt.
Während des Entwicklungsprozesses haben wir festgestellt, dass unser Algorithmus Wörter in verschiedenen Layouts erraten kann. Daher mussten wir das Wörterbuch erweitern, indem wir die Bedeutung von Wörtern im umgekehrten Layout hinzufügten. Die Suchanforderungen umfassten nur zwei Layouts: Russisch und Englisch. Wir haben jedes Wort der Suchanfrage des Benutzers im umgekehrten Layout dupliziert und die Verarbeitung zur Berechnung der Damerau-Levenshtein-Entfernung hinzugefügt. Optionen für direktes und umgekehrtes Layout werden unabhängig voneinander verarbeitet, Optionen mit dem höchsten Prozentsatz an Ähnlichkeit werden ausgewählt. Nur für Optionen für das umgekehrte Layout ist der Wert im direkten Layout der Wert für die korrigierte Suchabfrage.
Fuzzy-Suchalgorithmus
Somit wurde ein Aktionsalgorithmus von 6 Hauptschritten gebildet. Beim Testen haben wir festgestellt, dass nicht alle Wörter in Benutzeranfragen in ihrer ursprünglichen Form oder allgemein verarbeitet werden müssen. Um solche Fälle zu lösen, wurde ein zusätzlicher Schritt eingeführt, den wir als Konverter oder Filter bezeichneten. Infolgedessen bestand der endgültige Algorithmus aus 7 Schritten:
- Teilen Sie die Abfrage in separate Wörter auf.
- Führen Sie jedes Wort durch den Konverter (darüber weiter);
- Erstellen Sie für jedes Wort eine andere Form.
- Verfassen Sie eine Transkription;
- Führen Sie eine Suchabfrage in der Wörterbuchtabelle durch und vergleichen Sie jeden Eintrag über die Entfernung Damerau-Levenshtein.
- Hinterlassen Sie nur Datensätze mit einem Abstand von weniger als oder gleich zwei.
- Lassen Sie durch den Oliver-Algorithmus nur Wörter mit einem Ähnlichkeitsprozentsatz von mehr als 70%
Schematisch ist dieser Algorithmus wie folgt:
Wortkonvertierungs- und Filterfunktionen
Als wir mit dem Testen des ersten Prototyps ohne Konverter begannen, wurde klar, dass nicht versucht werden musste, alle Wörter in der Benutzeranforderung zu erraten. Für diese Einschränkungen wurde ein Konverter erstellt. Sie können Wörter in die von uns benötigte Form konvertieren und diejenigen herausfiltern, die unserer Meinung nach nicht erraten werden müssen.
Zunächst wurde entschieden, dass die minimale Wortlänge, die durch den Algorithmus geleitet werden sollte, mindestens zwei Zeichen betragen sollte. Wenn der Benutzer einen Vorwand oder eine Vereinigung eines Zeichens eingibt, ist die Wahrscheinlichkeit, zu raten, praktisch minimal. Der zweite Schritt bestand darin, die Abfrage in Wörter aufzuteilen. Zunächst haben wir eine Reihe von Zeichen ausgewählt, die Wörter enthalten können: Buchstaben, Zahlen, Punkte und Bindestriche (Bindestrich). Leerzeichen und andere Zeichen sind Worttrennzeichen.
Sehr oft geben Benutzer Zahlen ein, um Volumen oder Menge anzugeben. In diesem Fall ist es falsch, eine solche Anfrage zu korrigieren. Beispielsweise hat ein Benutzer die Abfrage "Wasser 1,1 Liter" eingegeben. Wenn wir seine Anfrage um 1,5 oder 1,0 korrigieren, ist dies falsch. In solchen Fällen haben wir beschlossen, Wörter mit einer Nummer zu überspringen. Sie werden unter Umgehung unseres Algorithmus in die Volltextsuche der Sphinx übertragen.
Eine weitere Konvertierung ist mit Punkten in Markennamen verbunden - zum Beispiel: Dr. Pepper oder Mr.Proper. In Fällen, in denen sich in der Mitte des Wortes ein Punktsymbol befindet, teilen wir es in zwei Teile und fügen ein Leerzeichen hinzu. Der zweite Fall mit einem Punkt in der Mitte des Wortes - hier erinnern wir uns an die Abkürzungsmarken. Zum Beispiel die Marke ROCS - in diesem Fall schneiden wir die Punkte aus und erhalten ein einziges Wort. Diese Konvertierung funktioniert, wenn sich zwischen den Punkten nur ein Buchstabe befindet.
In Fällen, in denen ein Bindestrich (Bindestrich) im Wort vorhanden ist, sollten Sie das Wort in mehrere Teile aufteilen und versuchen, sie einzeln zu erraten, und dann die besten Optionen zusammenkleben.
Infolgedessen wurde ein Konverter entwickelt, um die Anforderung am genauesten zu erkennen. Der größte Teil der Arbeit zum Einrichten aller Funktionen wurde von dieser speziellen Entwicklung übernommen. Vor allem dank ihm wird die Anpassung und Abstimmung der gesamten Fuzzy-Suche durchgeführt. Wiederholen Sie kurz die Regeln, nach denen Screening und Wortkonvertierung durchgeführt werden:
- Das Wort muss länger als 2 Zeichen sein
- Das Wort sollte nur Buchstaben, ein Punkt und einen Bindestrich (Bindestrich) enthalten.
- Wenn sich der Punkt in der Mitte des Wortes befindet, wird danach ein Leerzeichen hinzugefügt
- Wenn es sich um eine Abkürzung handelt, werden die Punkte ausgeschnitten und die Buchstaben zusammengeklebt
- Versuchen Sie nicht, das Wort zu erraten, wenn es eine Zahl enthält
- Wenn das Wort einen Bindestrich (Bindestrich) enthält, teilen Sie ihn in mehrere auf, suchen Sie separat und kleben Sie ihn am Ende fest
Wörterbuchzusammenstellung
Wie bereits erwähnt, muss zur Korrektur der Benutzeranforderung festgestellt werden, welche Wörter falsch geschrieben sind und welche nicht. Zu diesem Zweck wurde im System ein Wörterbuch erstellt, in dem Wörter mit der richtigen Schreibweise enthalten sein sollten.
In der ersten Phase stellte sich die Frage, ob das Wörterbuch ausgefüllt werden sollte. Daher haben wir beschlossen, den Kataloginhalt zum Kompilieren zu verwenden. Da Informationen zu Waren von Zeit zu Zeit aus einem externen System importiert und für das Sphinx-Volltextsuchsystem indiziert wurden, wurde beschlossen, die Wörterbuchkompilierungsfunktion zu diesem Zeitpunkt hinzuzufügen. Wir folgten der folgenden Logik: Wenn das Wort nicht im Inhalt der Waren enthalten ist, warum dann versuchen, es zu erraten?
Produktinformationen wurden zu einem gemeinsamen Text zusammengefasst und über einen Konverter geleitet. Die Betriebsart des Konverters wurde geringfügig geändert: Beim Durchbrechen von Wörtern durch einen Bindestrich (Bindestrich) wurde jeder Teil separat im Wörterbuch gespeichert. Beim Ersetzen von Punkten im Wörterbuch werden die ursprünglichen und geänderten Daten hinzugefügt. Und da beim Vergleichen von Wörtern zur Berechnung der Damerau-Levenshtein-Entfernung die Transkription des Wortes verwendet wird, wird zusätzlich zum Wörterbuch die Transkription hinzugefügt.
Es gab viele Tippfehler im Inhalt der Waren, zu diesem Zweck wurde eine Flagge in das Wörterbuch gesetzt, bei der Installation wird das Wort nicht mehr in der Suche verwendet. Mit Inhalten aus 35.000 Produkten konnte ein Wörterbuch mit 100.000 eindeutigen Wörtern erstellt werden, was letztendlich für einige Benutzeranfragen nicht ausreichte. In dieser Hinsicht war es notwendig, eine Ladefunktion für seine Anreicherung bereitzustellen. Zum Laden von Wörterbüchern wurde ein Konsolenbefehl erstellt. Das Format der Dateien mit den Daten der Wörterbücher sollte csv entsprechen. Jeder Eintrag enthält nur ein Feld mit dem Wörterbuchfeld selbst. Um die heruntergeladenen Daten von den anhand des Wareninhalts generierten Daten zu unterscheiden, wurde ein spezielles Flag hinzugefügt.
Infolgedessen weist die Wörterbuchtabelle das folgende Schema auf:
| Feldname | Feldtyp |
|---|
| Wort | Zeichenfolge |
| Transkription | Zeichenfolge |
| Manuell hinzugefügt | Bool |
| Nicht verwenden | Bool |
Vor der Entwicklung der Fuzzy-Suchfunktion gab es Felder in den Produkten, die eine Reihe von Wörtern mit Tippfehlern enthielten. Beim ersten Durchlauf der Wörterbuchgenerierung kamen sie in den Inhalt. Als Ergebnis wurde ein Wörterbuch mit Tippfehlern erhalten, dessen Inhalt nicht für die ordnungsgemäße Funktion der Funktion geeignet war. Daher wurde ein weiterer Konsolenbefehl hinzugefügt, der über die Funktionalität zur Generierung des inversen Wörterbuchs verfügt. Unter Verwendung des Inhalts eines bestimmten Warenfelds suchte das Team nach Wörtern im Wörterbuch und löschte sie aus dem Wörterbuch. Nach der Reinigung wurden solche Felder von der Indizierung ausgeschlossen.
Bitrix-Integration
Um die minimal erforderliche Funktionalität zu implementieren, wurden drei Klassen erstellt:
- DictionaryTable - Bitrix ORM-Systeme zum Arbeiten mit einem Wörterbuch
- Wörterbuch - Wörterbuchgenerierungsklasse
- Suche - Suchimplementierungsklasse
Für die Integration in Bitrix mussten Änderungen an zwei Komponenten vorgenommen werden:
- bitrix: search.page
- bitrix.search.title
Vor dem Ausführen der Anforderung wird die Verarbeitungsmethode aufgerufen, um Fehler zu erkennen und die entsprechenden Optionen auszuwählen:
Um ein Wörterbuch zu kompilieren, wurde ein Ereignis aufgezeichnet, um die Elemente des Informationsblocks mit Waren durch das Suchmodul zu indizieren (Suche: BeforeIndex).
Zukunftspläne
Dieser Ansatz ist hinsichtlich der Leistung nicht ideal. Mit der Vergrößerung des Wörterbuchs auf über 1 Million Wörter kann sich die Antwortzeit der Datenbank erheblich erhöhen. Während das Wörterbuch klein ist, passt die Leistung zu uns. Möglicherweise muss der Algorithmus in Zukunft über einen Levenshtein-Automaten oder einen Präfixbaum implementiert werden.
Fazit
So bleibt keiner Suchmaschine das Erscheinen von Abfragen erspart, die gegen allgemein anerkannte Rechtschreibregeln verstoßen - sei es ein zufälliger Tippfehler oder ein wirklicher Mangel an Kenntnissen über die Rechtschreibung von Wörtern. Ohne auf die klassischen Fuzzy-Suchoptionen Google oder Yandex zurückgreifen zu müssen, können Sie daher Ihre eigenen erstellen, wodurch sowohl der Benutzer als auch der Websitebesitzer das gewünschte Ergebnis erzielen können.
Der Code unserer Implementierung kann im Repository eingesehen werden:
github.com/qsoft-dev/damlev-bitrix