Welcher Algorithmus können Sie doppelte Sätze in einem String finden verwenden?

Question

eine beliebige Zeichenfolge gegeben, was eine effiziente Methode, doppelte Sätze zu finden? Wir können sagen, dass Sätze müssen länger als eine bestimmte Länge aufgenommen werden.

Im Idealfall würden Sie mit der Anzahl der Ereignisse für jede Phrase enden.

Answer 1

Wie die früheren Leute erwähnen, dass Suffixbaum das beste Werkzeug für den Job ist. Meine Lieblingsseite für Suffix-Bäumen ist http://www.allisons.org/ll/ AlgDS / Baum / Suffix / . Es listet alle geschickte Verwendung von Suffix-Bäumen auf einer Seite und hat einen Test js applicaton eingebetteten Strings zu testen und durch Beispiele zu arbeiten.

Answer 2

In der Theorie

• A Suffixarray ist die 'beste' Antwort, da es implementiert werden kann, linearen Raum und Zeit zu erfassen alle doppelt Strings zu verwenden. Allerdings - die naive Implementierung tatsächlich dauert Zeit O (n ^ 2 log n) die Suffixe zu sortieren, und es ist nicht ganz klar, wie dies auf O reduzieren unten (n log n), geschweige denn O (n), obwohl man lesen die dazugehörigen Papiere, wenn Sie wollen.
• A Suffixbaum kann etwas mehr Speicherplatz verbrauchen (noch linearen obwohl) als ein Suffix-Array, ist aber einfacher zu implementieren schnell zu bauen, da Sie so etwas wie eine Radixsort Idee verwenden können, wie Sie die Dinge zu dem Baum hinzugefügt werden (siehe den wikipedia-Link aus dem Namen für weitere Details).
• Die KMP-Algorithmus ist auch gut zu sich bewusst sein, die für die Suche nach einem bestimmten Teilstrings in einem längeren String sehr schnell spezialisiert. Wenn Sie nur diesen speziellen Fall benötigen, nur KMP verwenden und keine Notwendigkeit zu stören zuerst einen Index von Suffixe zu bauen.

In der Praxis

Ich vermute, Sie ein Dokument der tatsächlichen natürlicher Sprache ist die Analyse (zum Beispiel Englisch) Worte, und Sie wollen tatsächlich etwas mit den Daten tun, die Sie sammeln.

In diesem Fall möchten Sie vielleicht nur eine schnelle n-gram Analyse für einige kleine n, wie nur n = 2 oder 3. Sie können beispielsweise Ihr Dokument in eine Liste von Wörtern durch Strippen aus Zeichensetzung, Groß- und ergeben Worte tokenize konnte (laufen, läuft sowohl -> ‚run‘) zu erhöhen semantische Übereinstimmungen. Dann baut nur eine Hash-Karte (wie hash_map in C ++, in einem Wörterbuch Python, usw.) von jedem benachbarten Paar von Worten zu seiner Anzahl von Vorkommen bisher. Am Ende Sie einige sehr nützliche Daten erhalten, die auf Code sehr schnell war, und langsam laufen nicht verrückt.

Answer 3

Suffix Bäume ist ein guter Weg, dies zu realisieren. Der Boden dieses Artikels hat Links zu Implementierungen in verschiedenen Sprachen.

Answer 4

Wie JMAH sagte, können Sie Suffix Bäume / Suffixarray für diese.

Es gibt eine Beschreibung eines Algorithmus Sie hier nutzen könnten (siehe Abschnitt 3.1 ).

Sie können eine tiefer gehende Beschreibung in dem Buch finden sie zitieren (Gusfield, 1997), das ist auf google Bücher .

Answer 5

Angenommen, Sie sortiert Array A mit n Einträgen angegeben sind (i = 1,2,3, ..., n)

Algo(A(i))
{
  while i<>n
  {
    temp=A[i];
    if A[i]<>A[i+1] then
    {     
      temp=A[i+1];
      i=i+1;
      Algo(A[i])
    }
    else if A[i]==A[i+1] then
      mark A[i] and A[i+1] as duplicates
  }
}

Diese algo läuft bei O (n) Zeit.