Ich habe eine große Sammlung von menschlichen generierten Inhalten. Ich möchte die Wörter oder Sätze finden, die am häufigsten vorkommen. Was ist ein effizienter Weg dies zu tun?Algorithmus zum Generieren einer 'Top-Liste' mit Worthäufigkeit
Das Rad nicht neu erfinden. Verwenden Sie eine Volltextsuchmaschine wie Lucene.
Ich liebe Lucene, aber ich denke, es ist ein bisschen zu viel hier. Wörter zählen ist einfach genug mit einer Hash-Tabelle. –
Woher wissen Sie, dass die Lösung übertrieben ist? Haben Sie ein besseres Verständnis von "großer Sammlung von menschengenerierten Inhalten" als ich? – hobodave
Ich möchte hier kein Wort Krieg beginnen. Es ist gut möglich, dass du recht hast. Ein Grund dafür, dass dies eine gute Lösung sein könnte, ist, dass Lucene einige ausgezeichnete Tokenizer enthält, die hier von Nutzen sein könnten. Auf der anderen Seite: 1. Lucene ist eine ziemlich große Abhängigkeit, die optimiert ist, viel mehr zu tun, als für 2 gefragt ist.Hash-Tabellen sind für mehr oder weniger jede Sprache auf dem Planeten verfügbar, während Lucene auf einige Plattformen beschränkt ist. –
Der einfache/naive Weg ist die Verwendung einer Hashtabelle. Durchlaufen Sie die Wörter und erhöhen Sie die Zählung, während Sie gehen.
Am Ende des Prozesses, durch Zählung der Schlüssel/Wert-Paare sortieren.
Dies wird nicht mit Phrasen helfen. OP fragte speziell nach Wörtern oder Phrasen, was weit weniger trivial ist. – hippietrail
die Grundidee ist einfach - in ausführbarem Pseudo-Code,
from collections import defaultdict
def process(words):
d = defaultdict(int)
for w in words: d[w] += 1
return d
Natürlich ist der Teufel im Detail - wie Sie die große Sammlung in ein Iterator schalte Worte Nachgeben? Ist es groß genug, dass Sie es nicht auf einer einzelnen Maschine verarbeiten können, sondern einen Mapreduce-Ansatz benötigen, z. über Hadoop? Etc etc. NLTK kann mit den sprachlichen Aspekten helfen (Wörter in Sprachen isolieren, die sie nicht sauber trennen).
Bei einer Einzelmaschinenausführung (nach mapreduce) kann ein Problem auftreten, dass die einfache Idee Ihnen viel zu viele Singletons oder ähnliches gibt (Wörter, die einmal oder nur wenige Male vorkommen), die den Speicher füllen. Eine probabilistische Erwiderung darauf ist, zwei Durchläufe zu machen: einen mit zufälliger Stichprobe (nur ein Wort in zehn oder eins in hundert), um eine Reihe von Wörtern zu bilden, die Kandidaten für die obersten Reihen sind, dann einen zweiten Durchlauf, der Wörter auslässt sind nicht im Kandidatensatz. Abhängig davon, wie viele Wörter Sie proben und wie viele Sie im Ergebnis haben möchten, ist es möglich, eine obere Grenze für die Wahrscheinlichkeit zu berechnen, dass Sie auf diese Weise ein wichtiges Wort verpassen (und für vernünftige Zahlen und jede natürliche Sprache) Ich versichere dir, dass es dir gut geht).
Sobald Sie Ihre Wörterbuch Mapping Wörter auf die Anzahl der Vorkommen müssen Sie nur die oberen N Wörter nach Vorkommen auswählen - eine Heap-Warteschlange wird dort helfen, wenn das Wörterbuch ist einfach zu groß nach Vorkommen in seiner Gesamtheit zu sortieren (zB in meinem lieblings ausführbaren Pseudocode, heapq.nlargest wird es zum Beispiel tun).
Dies bezieht sich nur auf den trivialen Fall von Wörtern, während das OP speziell nach Wörtern oder Ausdrücken gefragt hat. – hippietrail
Schauen Sie in die Apriori algorithm. Es kann verwendet werden, um häufige Artikel und/oder häufige Sätze von Artikeln zu finden.
Wie die wikipedia Artikel heißt es, gibt es effizientere Algorithmen, die das gleiche tun, aber dies könnte ein guter Anfang sein zu sehen, ob dies auf Ihre Situation zutreffen wird.
Vielleicht können Sie versuchen, eine PATRICIA trie or practical algorithm to retrieve information coded in alphanumeric trie verwenden?
Warum nicht eine einfache Karte mit Schlüssel als Wort und Zähler als Wert. Es wird die oberen verwendeten Wörter geben, indem Sie den Zähler mit hohem Wert nehmen. Es ist nur eine O (N) -Operation.
Diese Antwort wurde bereits gegeben. Zweimal. – hobodave
Und es ignoriert Sätze, die in der Frage des OP speziell behandelt werden: "Wörter oder Sätze". – hippietrail
Können Sie genauere Angaben machen? Speziell: Was ist eine "große Sammlung" ?, "Was ist effizient?" z.B. Was sind deine Zeitvorstellungen, welche Sprache verwendest du usw. – hobodave