String-Suchalgorithmen in Java

Question

Ich führe eine Zeichenfolgenabgleichung mit einer großen Menge von Daten durch.

EDIT: Ich gleiche Wörter ab, die in einer großen Liste mit einigen Ontologie-Textdateien enthalten sind. Ich nehme jede Datei aus der Ontologie und suche nach einer Übereinstimmung zwischen der dritten Zeichenfolge jeder Dateizeile und einem Wort aus der Liste.

Ich habe einen Fehler gemacht, indem ich übersehen habe, dass das, was ich tun muss, kein reiner Abgleich ist (Ergebnisse sind schlecht), sondern ich eine lockerere Abgleichfunktion benötige, die auch Ergebnisse zurückgibt, wenn die Zeichenfolge in einer anderen Zeichenfolge enthalten ist.

Das habe ich mit einem Radix-Trie gemacht; es war sehr schnell und funktioniert gut, aber jetzt glaube ich, dass meine Arbeit nutzlos ist, weil ein Trie nur genaue Übereinstimmungen zurückgibt. :/

• Welche Art von Algorithmen tun dies, sind es Zeichensuchalgorithmen?
• Kann jemand einige Java-Implementierungen vorschlagen, mit denen er Erfahrung hat?

Der Algorithmus sollte schnell sein, aber dies ist nicht oberste Priorität, würde sich mit Geschwindigkeit und Komplexität abfinden.

Ich bin sehr dankbar für alle Ratschläge/Beispiele/Erklärungen/Links!

Vielen Dank!

Answer 1

Sie könnten Suffix Trees nützlich finden (sie sind ähnlich im Konzept zu Tries).

Jeder String, den Sie mit ^ ergänzen und mit $ beenden und erstellen einen Suffixbaum aller angehängten Strings. Der Speicheraufwand wird O(n) betragen und wird wahrscheinlich schlechter sein als das, was Sie für den Trie hatten.

Wenn Sie jetzt nach einem String s suchen müssen, können Sie dies leicht in O(|s|) Zeit tun, genauso wie bei einem Trie und das Ergebnis, das Sie erhalten, wird eine Teilzeichenfolge sein (im Wesentlichen werden Sie einige Suffixe eines Strings abgleichen).

Entschuldigung, ich habe keine Referenz zu einer Java-Implementierung zur Hand.

Eine nützliche Antwort auf Stackoverflow gefunden: Generalisierte Suffixbaum-Java-Implementierung

Die Folgendes hat: http://illya-keeplearning.blogspot.com/2009/04/suffix-trees-java-ukkonens-algorithm.html

Das hat wiederum: Quellcode: http://illya.yolasite.com/resources/suffix-tree.zip

Answer 2

Sie können den BM-Algorithmus verwenden, um in Textdateien nach einzelnen Mustern zu suchen, und wiederholen Sie diesen Algorithmus für alle Muster, die Sie in Ihrer Liste haben.

Die andere beste Lösung ist die Verwendung von Mehrmusteralgorithmus-Suchalgorithmen wie: Aho–Corasick-Algorithmus zur Zeichenfolgenübereinstimmung

Answer 3

Reguläre Ausdrücke sind definitiv die beste Methode. Sie können etwas unordentlich zu schreiben sein, aber sie sind der einzige Weg, um eine lockerere Übereinstimmung zu haben, ohne eine unverständliche Serie von if/else oder switch-Anweisungen zu haben.

Zusätzlich werden sie viel schneller sein als die Alternative.

Answer 4

Ich bin mir nicht ganz sicher, ob ich die Frage richtig verstanden habe, aber es scheint, als würden reguläre Ausdrücke die Aufgabe erledigen

http://java.sun.com/developer/technicalArticles/releases/1.4regex/

Answer 5

Warum verwenden Sie nicht die indexOf-Methode in Java. Je nach Verfügbarkeit des Speichers den Inhalt lesen. Führen Sie ein indexOf aus und erhalten Sie alle Zeilen, die Sie benötigen. Laden Sie den nächsten Satz von Inhalten.

Wenn Sie aus einer Datei lesen, verwenden Sie NIO-Streams.

Vielleicht ist die Idee schlecht, aber ich glaube an Java. Es wird den besten Algorithmus verwenden.

Besser, wenn Sie reguläre Ausdrücke verwenden.