Passende Teilstrings von einem Wörterbuch zu anderen String: Vorschläge?

Question

Hellow Stack Überlauf Menschen. Ich hätte gerne Vorschläge zum folgenden Problem. Ich benutze Java.

Ich habe ein Array # 1 mit einer Reihe von Strings. Zum Beispiel könnten zwei der Saiten sein: "Ein Apfel fiel auf Newtons Kopf" und "Äpfel wachsen auf Bäumen".

Auf der anderen Seite habe ich ein anderes Array # 2 mit Begriffen wie (Früchte => Apfel, Orange, Pfirsich; Items => Stift, Buch; ...). Ich würde dieses Array mein "Wörterbuch" nennen.

Durch den Vergleich von Elementen von einem Array zum anderen muss ich sehen, in welche "Kategorie" die Elemente von # 1 aus # 2 fallen. Z.B. Beide von # 1 würden unter "Früchte" fallen.

Meine wichtigste Überlegung ist die Geschwindigkeit. Ich muss diese Operationen schnell erledigen. Eine Struktur, die eine konstante Zeitabfrage ermöglicht, wäre gut.

Ich betrachtete ein Hashset mit der contains() -Methode, aber es erlaubt keine Teilstrings. Ich habe auch versucht Regex wie (Apfel | Orange | Pfirsich | ... etc) mit Groß-und Kleinschreibung beachten Flag, aber ich lese, dass es nicht schnell sein wird, wenn die Begriffe in der Anzahl (mindestens 200 zu erwarten) zu erhöhen. Schließlich habe ich gesucht und erwäge, eine ArrayList mit indexOf() zu verwenden, aber ich weiß nicht über seine Leistung. Ich muss auch wissen, welche der Begriffe tatsächlich übereinstimmen, also wäre es in diesem Fall "Apple".

Bitte geben Sie Ihre Ansichten, Ideen und Vorschläge zu diesem Problem.

Ich sah Aho-Corasick-Algorithmus, aber die Schlüsselwörter/Begriffe werden sich sehr wahrscheinlich oft ändern. Also ich glaube nicht, dass ich das benutzen kann. Oh, ich bin kein Experte in Text Mining und Mathe, also bitte erarbeiten Sie komplexe Konzepte.

Vielen Dank, Stack Overflow Menschen, für Ihre Zeit! :)

Answer 1

Würde eine suffix tree oder ähnliche Datenstruktur für Ihre Anwendung funktionieren? Es bietet O (m) string lookup, wobei m die Länge der Suchzeichenfolge nach einem O (n) - oder besser mit ein paar Tricksereien - anfängliche Einrichtung, und mit etwas mehr Aufwand, die Sie zuordnen können beliebige Daten, z. B. ein Verweis auf eine Kategorie, mit vollständigen Wörtern in Ihrem Wörterbuch. Wenn Sie es nicht selbst kodieren wollen, glaube ich, dass die BioJava Bibliothek eine Implementierung enthält.

Sie können nach der anfänglichen Einrichtung auch Zeichenfolgen zu einem Suffixbaum hinzufügen, obwohl die Kosten immer noch ungefähr 0 sind (n). Das ist wahrscheinlich keine große Sache, wenn Sie kurze Wörter hinzufügen.

Answer 2

Wenn Sie ein Multimap von Google Collections verwenden, haben diese eine Funktion zum Invertieren der Map (Sie können also mit einer Map wie {"Fruits" => [Apple]} beginnen und eine Map mit {"Apple" erstellen => ["Fruits"]}. So können Sie das Wort suchen und eine Liste von Kategorien dafür finden, in einem Anruf auf die Karte.

Ich würde erwarten, dass ich die Strings selbst teilen und die Suche nach Wörter in der Karte einzeln, so dass ich stemming (Anpassung für verschiedene Wortendungen) und Stopword-Filterung. Verwenden der Karte sollte gute Nachschlagen Zeiten, und es ist einfach zu testen.

Answer 3

Wenn Sie haben nur 200 Begriffe zu suchen, regexps könnte tatsächlich für Sie arbeiten egular Ausdruck ist groß, aber wenn Sie es einmal kompilieren und nur dieses kompilierte Muster verwenden, ist die Nachschlagezeit wahrscheinlich linear in der kombinierten Länge aller Zeichenfolgen in Array # 1 und ich sehe nicht, wie Sie hoffen können, besser zu sein .

Also wäre der Algorithmus: Verketten Sie die Wörter des Arrays # 2, nach denen Sie suchen möchten, in den regulären Ausdruck, kompilieren Sie sie und suchen Sie dann die Übereinstimmungen in Array # 1.

(Reguläre Ausdrücke werden in eine Zustandsmaschine kompiliert - das heißt für jedes Zeichen der Zeichenkette wird nur eine Nachschlagetabelle für den nächsten Zustand gesucht. Wenn der reguläre Ausdruck kompliziert ist, kann die Rückverfolgung die Zeit erhöhen Regulärer Ausdruck hat eine sehr einfache Struktur.)