Finden Sie passende Sätze in einer Gruppe von Wörtern

Question

Ich habe ein Programm erstellt, um einige Textdateien zu parsen und die Anzahl der Wörter zu zählen und sie dann absteigend zu sortieren. Das funktioniert großartig, aber ich möchte es auf ein anderes Level bringen.

Ich möchte in der Lage sein, irgendwelche Wortphrasen im Text zu finden, der wiederholt, und ich bin nicht sicher, wie man es macht.

Mein aktueller Algorithmus ist es, zuerst den Text aufgeteilt in Worte dann eine Hash-Tabelle mit dem Wort erstellen und wie dieser Wert zählen: key

hash: 
    "word":3, 
    "test":12, 
    ..... 

dann nur ich irgendwie die auf Schlüssel stützt und Ausgang und Ich bin fertig.

Lasst uns sagen, dass ich dieses alles Gute zum Geburtstag Lied:

Happy Birthday to You 
Happy Birthday to You 
Happy Birthday Dear (name) 
Happy Birthday to You. 

From good friends and true, 
From old friends and new, 
May good luck go with you, 
And happiness too. 

Alternative ending: 
How old are you? 
How old are you? 
How old, How old 
How old are you? 

Ich kann das Wort zählt ganz gut erhalten, aber was ist, wenn ich wollte alle Sätze passen?

beispielsweise auf 6 Wortphrase könnte gesagt werden zweimal abgestimmt werden:

happy birthday to you happy birthday 

ein Paar 5 Wortphrase match:

birthday to you happy birthday 
happy birthday to you happy 

einig 4 Wortphrase übereinstimmt

how old are you 
happy birthday to you 
to you happy birthday 
how old how old 
birthday to you happy 

und so weiter bis zu zwei Wortphrasen, die übereinstimmen.

Ich bin mehr besorgt über die Übereinstimmung der gesamten Phrase sogar über die Zeilen, weil ich sowieso über die Ausgabe für die weitere Verarbeitung schauen müssen.

Welche Art von Algorithmus würde mir erlauben, dieses Ziel zu erreichen?

Answer 1

Zuerst möchten Sie die Passage mit einem kurzen Regex in Token bringen, um die Wörter ein wenig einfacher zu durchlaufen, z. B. indem Sie die Sprache verwenden String.split-Methode für alle Whitespace-/Newline-Zeichen. Das sollte Sie mit einem String-Array wie folgt verlassen: ["Happy", "birthday", "to", "you", "happy", ...]. Sie müssen die Zeichenfolgen nicht verkleinern, wenn Sie später reguläre Ausdrücke verwenden, was ich in dieser Antwort vorschlage.

Im Anschluss daran müssen Sie Sätze aus dem Kanal extrahieren, die Sie durch die Schaffung eines start und end Zeiger und iteriert wie so erreichen kann:

for (var start = 0; start < tokens.length; start+=1) { 
    for (var end = start; end < tokens.length; end+=1) { 
     var phrase = tokens.slice(start, end) 
     // Count occurrences of phrase ... 
    } 
} 

Die obige jedes Wort als Startpunkt verwenden würde für Extraktion und jedes folgende Wort als Endpunkt für die Extraktion, wodurch einzelne Wörter und ganze Phrasen in phrase aufgenommen werden können. Beachten Sie, dass es (wenn meine Mathematik korrekt ist) (n + n^2)/2 dieser Sätze, so dass dieses Ding ein exponentielles Wachstum hat. Wenn Sie alle Phrasen bis zum Ende aktiv speichern, kann die Speicherauslastung für große Daten ziemlich hoch werden.

Die Übereinstimmung des regulären Ausdrucks selbst kann die Anzahl der Vorkommen einer bestimmten Phrase finden, sodass Sie nicht auf die Verwendung einer Hashtabelle zum Speichern der Ergebnisse Ihrer Arbeit beschränkt sind. Sie können Speicher sparen, indem Sie nur solche Sätze mit mehr als einem Vorkommen in der Passage speichern.

Answer 2

Sie könnten den gleichen Algorithmus mit Wortkombinationen verwenden. Wenn Sie eine Warteschlange mit der maximalen Größe n verwenden, können Sie die letzten n Wörter, die überprüft wurden (z. B. über einen Iterator), zusammenfügen und sie zu Ihrer Hashtabelle hinzufügen. diese Wiederholen für n = 2 bis n> (Ihr #words/2) oder keine Wiederholung gefunden wurde

Beispiel „W1 w2 w3, W3 w1 w2.“

Sollte eine Hash-Tabelle geben mit .. Hash2: „w1 w2“ : 2 „w2 w3“ : 1 „w3 w3“ : 1 „w3 w1“ : 1 ..for n = 2 (ohne Berücksichtigung von Großbuchstaben und Komma) Für n = 3 Ihre höchste Zählung wäre 1 und Sie könnten brechen

Cle Wenn Sie eine neue Zeile aus Ihrer Wortliste hinzufügen und einen zusätzlichen Leerraum verwenden möchten, können Sie