ℹ️ 🌓 ↘️ TextRadar Fuzzy-Suchalgorithmus. Artefakte (Teil 2) ✖️ 🖖🏻 👧🏿

In einer früheren Veröffentlichung wurde der TextRadar Fuzzy Search-Algorithmus verwendet. Die Hauptansätze (Teil 1) werden als Hauptansätze betrachtet. Bei der Lösung praktischer Probleme wurden Situationen identifiziert, in denen die Verwendung nur der grundlegenden Methodik nicht die erforderliche Qualität der Suche bietet. Als Ergebnis wurden Add-Ons (Algorithmusoptionen) erstellt, die diskutiert werden.

Fragmente eines Wortes einer Suchzeichenfolge befinden sich in mehreren Wörtern einer Datenzeichenfolge

Die Suchzeichenfolge sei ABCD und die Datenzeichenfolge ABCE DFG.

Bild

Die Anwendung des Basisalgorithmus ergibt das folgende Ergebnis:

Bild

Wenn solche Kollisionen auftreten, werden zusätzliche Gruppen gelöscht. Die Auswahl der zu löschenden Gruppen ist eine separate, komplexe Frage. Infolgedessen sollten die wichtigsten Gruppen erhalten bleiben. Im obigen Beispiel liegt die Antwort auf der Hand - die kleinste der Gruppen sollte gelöscht werden.

Bild

Das Startfragment des Suchzeichenfolgenworts befindet sich innerhalb des Datenzeichenfolgenworts

Betrachten Sie das Beispiel zum Finden der Zeichenfolge ABC in der Zeichenfolge XYZAB.

Bild

Der grundlegende Algorithmus erzeugt Folgendes:

Bild

In der Regel hat ein solches Ergebnis keinen praktischen Wert und sollte verworfen werden.

Unzureichende Abdeckung eines Wortes in einer Datenzeile mit gefundenen Fragmenten

Wenn wir in der Zeile ABCDEF nach dem Wort ABXYZ suchen, erhalten

Bild

wir:

Dieses Ergebnis hat ebenfalls keinen Wert und sollte verworfen werden.

Übergruppen

Gegeben die Suchzeichenfolge ABCXEF und die Datenzeichenfolge ABCEF ABCDEF.

Bild

Aus Sicht des Basisalgorithmus sind beide Wörter der Datenzeichenfolge äquivalent, aber das erste von ihnen hat Priorität (wenn ceteris paribus das erste Wort ausgewählt wird, das angetroffen wird), und das Suchergebnis lautet dann wie folgt:

Bild

Wenn wir das Konzept einer Supergruppe als eine Vereinigung von Wortgruppen auf derselben Diagonale einführen (oder verschieben, siehe die vorherige Veröffentlichung, in der die Grundlagen des Algorithmus erläutert werden) und die Priorität der in der Supergruppe enthaltenen Gruppen durch den Parameter erhöhen, wird die Größe der für jede Gruppe berechneten Supergruppe angenommen Wenn die Gruppe nicht Teil der Supergruppe ist, entspricht die Größe der Supergruppe der Größe der Gruppe selbst. In unserem Beispiel erhalten wir das folgende Ergebnis:

Bild

Überbewertete lange Wörter

Bei der Suche nach einer Phrase, die ein langes und ein kurzes Wort enthält, können gefundene Fragmente eines langen Wortes Fragmente eines kurzen Wortes „verdecken“. Dies ist auf die Verwendung einer quadratischen Funktion bei der Berechnung des Relevanzkoeffizienten zurückzuführen.

Bild

Darüber hinaus ist aus Sicht der Suchqualität ein längeres Wort nicht immer aussagekräftiger.

Betrachten Sie ein Beispiel. Angenommen, Sie müssen die Zeichenfolge ABCDEFG XYZ in einem Text finden, der aus zwei Seiten besteht:

1.

Bild

ABCDEFG ... QWE 2. ABCDEFO ... XYZ

Bild

Der Zähler des Gruppenzusammensetzungskoeffizienten (der Nenner hat keinen qualitativen Einfluss auf das Ergebnis, siehe obige Formel) für die erste Seite ist 49, für die zweite - 36 + 9 = 45. Das heißt, wenn wir den Einfluss auf das Längenfaktorergebnis weglassen, das Suchergebnis auf der ersten Seite wird von größerer Relevanz sein, was nicht den Erwartungen entspricht - in einigen Fällen ist das Suchergebnis auf Seite 2 wertvoller.

Eine der Lösungen kann darin bestehen, Einschränkungen für die maximale Länge von Gruppen einzuführen . Wenn in unserem Beispiel die maximale Gruppenlänge beispielsweise auf 6 begrenzt ist, erhalten wir 36 für die erste Seite und 45 für die zweite, was das erwartete Ergebnis liefert - die Relevanz der zweiten Seite ist höher als die der ersten.

Eine andere Möglichkeit, das Problem der Inkonsistenz der Signifikanz der Wörter der Suchphrase im Gesamtergebnis ihrer Länge zu lösen, besteht darin , die Relevanz der Suchphrase als Durchschnitt der Relevanz der darin enthaltenen Wörter zu berechnen, unabhängig berechnet. Hier tritt jedoch das gegenteilige Problem auf - die Notwendigkeit, die Bedeutung kurzer Wörter zu verringern, die auf ähnliche Weise gelöst werden kann -, indem der Schwellenwert auf die Länge der Wörter gesetzt wird, die an der Bildung der Gesamtrelevanz beteiligt sind, jedoch bereits auf den Mindestwert.

Wiederholte Wiederholungen der gewünschten Fragmente

Wie aus der Anweisung hervorgeht, besteht die Aufgabe darin, nach der relevantesten Suchzeichenfolge für eine Reihe von Fragmenten zu suchen. Daher wirkt sich die wiederholte Wiederholung der gewünschten Fragmente im Text nicht auf das Ergebnis aus. Das erste geeignete Fragment wird als Suchergebnis verwendet, der Rest wird während der Verarbeitung verworfen. Betrachten Sie ein Beispiel für das Finden der Zeichenfolge ABC in der Zeichenfolge ABCD ABCE ABCF ABCG.

Bild

Die Anwendung des Basisalgorithmus ergibt das folgende Ergebnis:

Bild

Unter dem Gesichtspunkt der Suche nach der relevantesten Seite ist dies richtig, aber wenn eine detaillierte Darstellung der Suchergebnisse erstellt wird, müssen alle geeigneten Fragmente gefunden und ausgewählt werden. Zu diesem Zweck können Sie den Suchvorgang auf der angezeigten Seite mehrfach wiederholen und die in früheren Iterationen gefundenen Fragmente nacheinander herunterfahren. In unserem Beispiel können wir so alle geeigneten Vorkommen der gewünschten Zeichenfolge finden.

Bild

Datenverarbeitungsgeschwindigkeit

Die On-the-Fly-Datenverarbeitung stellt bestimmte Geschwindigkeitsanforderungen - die Suche sollte nicht zu lange dauern.

Begrenzen der Mindestgröße verarbeiteter Gruppen, Deaktivieren der Suchoptionen

Um die Suchgeschwindigkeit zu erhöhen, können Sie die Mindestlänge verarbeiteter Gruppen begrenzen.

In der Praxis wird der folgende Ansatz angewendet: Zuerst wird der erste „grobe“ Durchgang mit einer Einschränkung der minimalen Gruppengröße durchgeführt und einige Optionen des gesamten Suchdatenarrays deaktiviert und der erste Datenabschnitt identifiziert (die Größe des optimalen Datenabschnitts wird aus dem Kontext des zu lösenden Problems bestimmt), und dann der zweite, gründlichere Umgehen nur die Seiten dieses Abschnitts, bereits ohne Einschränkung der Gruppengröße und unter Einbeziehung aller erforderlichen Optionen.

Parallele Datenverarbeitung

Eine andere Möglichkeit, die Suchgeschwindigkeit zu erhöhen, ist die parallele Datenverarbeitung. Infolgedessen kann mit einer großen Suchdatenbank eine akzeptable Gesamtverarbeitungszeit erreicht werden, indem die Anzahl paralleler Prozesse erhöht wird, was natürlich eine Erhöhung der Kapazität der Ausrüstung erfordert.

Ergebnisse

Die Anwendung der beschriebenen Ansätze ermöglichte es uns, die Qualität der Suche erheblich zu verbessern, die Abhängigkeit der Ergebnisse von verschiedenen Arten von Tippfehlern - überflüssige, fehlende Zeichen, Permutationen usw. - und, was noch wichtiger ist, unabhängig davon, wo sich diese Tippfehler befinden, in der Suchleiste selbst oder im Text zu verringern. welches gesucht wird.

Die Ergebnisse der Anwendung der beschriebenen Ansätze sind auf dem Demostand auf der Website textradar.ru zu sehen . Am Beispiel einer Suche im Text des Romans L.N. Tolstois „Krieg und Frieden“ kann Suchergebnisse mit der Basisversion und der erweiterten Version des Algorithmus vergleichen.

Bild

Laden Sie hier das Demo-Projekt mit erweiterten Funktionen (C # ASP.NET MVC) herunter oder sehen Sie es sich an .

TextRadar Fuzzy-Suchalgorithmus. Artefakte (Teil 2)