Parsing viel Text basiert auf einem konstanten Satz von Suchbegriffen

Question

ich eine Reihe von Suchbegriffe haben wie [+ Hund - „Jack Russels“ + „Foxterrier“], [+ cat + persisch - tabby]. Diese könnten ziemlich lang sein mit vielleicht 30 Unterbegriffen, die für jeden Begriff stehen.

Ich habe jetzt einige Online-Nachrichten Artikel Extrakte wie [„Mein Foxterrier ist der süßeste Hund der Welt ...“] und [„Hat jemand meine verlorene persische Katze gesehen? Er vermisst ... "]. Sie sind nicht zu lang, vielleicht höchstens 500 Zeichen pro Stück.

In traditionellen Suchmaschinen erwartet man eine große Anzahl von Artikeln, die zu Indizes vorverarbeitet werden, was die Suche nach "Suchbegriffen" beschleunigt, indem man Mengenlehre/Boolesche Logik verwendet, um Artikel auf nur solche zu reduzieren die Phrasen. In dieser Situation ist die Reihenfolge meiner Suchbegriffe jedoch ~ 10^5, und ich möchte in der Lage sein, einen einzelnen Artikel auf einmal zu bearbeiten, um ALLE Sätze von Suchbegriffen zu sehen, mit denen dieser Artikel verglichen werden würde (dh alle + Begriffe sind im Text und keiner der - Begriffe).

Ich habe eine mögliche Lösung mit zwei Karten (eine für die positiven Sub-Sätze, eine für die negativen Sub-Sätze), aber ich denke nicht, dass es sehr effizient sein wird.

Der erste Preis wäre eine Bibliothek, die dieses Problem löst, der zweite Preis ist ein Schritt in die richtige Richtung zur Lösung dieses Problems.

Mit freundlichen Grüßen

Answer 1

Unter der Annahme, alle positiven Unter Begriffen sind für ein Spiel benötigt:

Setzen Sie alle Unterbegriffe aus Ihren Suchbegriffe in eine Hash-Tabelle. Die Teilzeit ist der Schlüssel, ist der Wert ein Zeiger auf die vollen Suchbegriffs Datenstruktur (die eine eindeutige ID und eine Karte von Unter Bezug auf eine boolean umfassen soll).

Darüber hinaus, wenn eine Nachricht verarbeiten, eine „Kandidaten“ Karte, indiziert durch den Begriff ID erstellen. Jede Kandidatenstruktur hat einen Zeiger auf die Begriffsdefinition, einen Satz, der die gesehenen Unterbegriffe enthält, und einen "Zurückgewiesen" -Flag.

Iterieren Sie über die Wörter des Nachrichtenartikels.

Suchen Sie für jeden Treffer den Kandidateneintrag. Wenn nicht, erstellen und fügen Sie einen leeren hinzu.

Wenn der Kandidat Ablehnung Flag gesetzt ist, sind Sie fertig.

Andernfalls suchen Sie den Unterbegriff aus dem Begriff Datenstruktur. Wenn negativ, setzen Sie das Zurückweisungs-Flag. Wenn positiv, fügen Sie den Unterbegriff zu der Menge der gesehenen Unterbegriffe hinzu.

Am Ende iterieren Sie über die Kandidaten. Alle Kandidaten, die nicht abgelehnt werden und deren Größe der Anzahl positiver Unterbegriffe dieses Begriffs entspricht, sind Ihre Treffer.

Implementation: https://docs.google.com/document/d/1boieLJboLTy7X2NH1Grybik4ERTpDtFVggjZeEDQH74/edit

Laufzeit ist O (n * m), wobei n die Anzahl der Worte in dem Artikel ist, und m die maximale Anzahl der Begriffe die gleiche Teilterm (voraussichtlich relativ klein) teilen .

Answer 2

Zunächst einmal denke ich, dass ein Suffix Tree des Dokuments macht die Suche viel schneller macht, da Sie es einmal gebaut benötigen, aber Sie können es so oft wie die Länge der Abfrage verwenden ist.

Zweitens müssen Sie alle der Suchbegriffe (beide + und - sind) zu wiederholen, um sicherzustellen, wenn die Antwort ja ist (dh das Dokument die Abfrage übereinstimmt). Aber für eine "Nein" Antwort, Sie nicht! Wenn die Antwort nein ist, ist die Reihenfolge der Übereinstimmung der Suchbegriffe mit dem Dokument wirklich wichtig. Das heißt, eine Bestellung kann Ihnen ein schnelleres "Nein" als eine andere Bestellung geben. Jetzt ist die Frage "Was ist die optimale Reihenfolge, um ein schnelles NEIN zu bekommen?". Es hängt wirklich von der Anwendung, aber ein guter Ausgangspunkt ist, dass Mehrwortbegriffe wie „red big cat“ sind weniger häufig in den Dokumenten wiederholt im Vergleich zu kurzen Begriffen wie „cat“ und umgekehrt. Also, gehen Sie mit + "Loo ooo ooo ooo ooo ong" und - "kurzen" Begriffen zuerst.