Mit welchem ​​Algorithmus können Sie doppelte Phrasen in einer Zeichenfolge finden?

Wie die früheren Leute erwähnen, ist der Suffixbaum das beste Werkzeug für den Job. Meine Lieblings-Site für Suffix-Bäume ist Ссылка . Es listet alle nützlichen Verwendungen von Suffixbäumen auf einer Seite auf und enthält eine eingebettete Test js -Anwendung, um Strings zu testen und Beispiele durchzuarbeiten.

In der Theorie

• Ein Suffix-Array ist die beste Antwort, da es implementiert werden kann linearer Raum und Zeit, um doppelte Teilstrings zu erkennen. Allerdings - die naive Implementierung braucht tatsächlich Zeit, um die Suffixe zu sortieren, und es ist nicht ganz offensichtlich, wie man dies auf O (n log n) reduzieren kann, geschweige denn O (n), obwohl man lesen kann die verwandten Papiere, wenn Sie möchten.
• Ein Suffixbaum kann etwas mehr Speicher (immer noch linear) als a Suffix-Array, ist aber einfacher zu implementieren, um schnell zu erstellen, da Sie so etwas wie eine Radix-Sort-Idee verwenden können, während Sie Dinge zum Baum hinzufügen (siehe den Wikipedia-Link aus dem Namen für Details).
• Der KMP-Algorithmus ist auch gut zu wissen, welches ist spezialisiert auf die Suche nach einer bestimmten Teilzeichenfolge innerhalb einer längeren Zeichenfolge sehr schnell. Wenn Sie nur diesen speziellen Fall benötigen, verwenden Sie einfach KMP, und müssen Sie nicht zuerst einen Index der suffices erstellen.

In der Praxis

Ich vermute, Sie analysieren ein Dokument mit natürlichen Wörtern (z. B. Englisch) und Sie möchten etwas mit den gesammelten Daten tun.

In diesem Fall möchten Sie vielleicht einfach eine schnelle n-gram Analyse für ein kleines n machen, wie zum Beispiel n = 2 oder 3. Sie könnten beispielsweise Ihr Dokument in eine Liste von Wörtern zerlegen, indem Sie Zeichensetzung, Großschreibung und Wortstämme ausstreichen (running, läuft beides - & gt; 'run'), um semantische Übereinstimmungen zu erhöhen. Dann erstellen Sie einfach eine Hash-Map (z. B. hash_map in C ++, ein Wörterbuch in Python usw.) für jedes angrenzende Wortpaar bis zur Anzahl der Vorkommen. Am Ende erhalten Sie einige sehr nützliche Daten, die sehr schnell zu programmieren waren, und nicht verrückt langsam zu laufen.

Suffix-Bäume sind eine gute Möglichkeit, dies zu implementieren. Der untere Teil dieses Artikels enthält Links zu Implementierungen in verschiedenen Sprachen.

Wie Jmah sagte, können Sie Suffixbäume / Suffix-Arrays dafür verwenden.

Es gibt eine Beschreibung eines Algorithmus, den Sie hier verwenden können (siehe Abschnitt 3.1).

Sie finden eine ausführlichere Beschreibung in dem von ihnen zitierten Buch (Gusfield, 1997), das tgamblin 17.09.2008 23:33