Ich würde gerne einen Konsens in der Community über ein gutes Design finden, um die Häufigkeit von Worthäufigkeiten speichern und abfragen zu können. Ich baue eine Anwendung, in der ich Texteingaben analysieren und speichern muss, wie oft ein Wort (im Laufe der Zeit) erschienen ist. So gegeben die folgenden Eingaben:
Würde die folgenden Werte speichern:
%Vor%Und später in der Lage sein, schnell nach dem Zählwert eines beliebigen Wortes zu suchen.
Mein derzeitiger Plan ist, einfach die Wörter und Zählungen in einer Datenbank zu speichern und auf die Zwischenspeicherung von Wortzählwerten zu vertrauen ... Aber ich vermute, dass ich nicht genügend Cache-Treffer bekommen werde, um dies langfristig zu einer brauchbaren Lösung zu machen.
Kann jemand Algorithmen, Datenstrukturen oder andere Ideen vorschlagen, die diese Lösung zu einer guten Lösung machen?
Ich verstehe nicht, warum Sie meinen, eine Datenbank wäre keine geeignete Lösung. Sie werden wahrscheinlich nur ungefähr 100000 Zeilen haben und die kleine Größe der Tabelle bedeutet, dass sie vollständig im Speicher gespeichert werden kann. Machen Sie das Wort zum Primärschlüssel und die Suche wird sehr schnell.
Wortzählung ist das kanonische Beispiel eines MapReduce Programms (Pseudocode aus Wikipedia):
%Vor%Ich bin nicht sage, dass dies der Weg ist, aber es ist definitiv eine Option, wenn Sie etwas brauchen, das gut skaliert, wenn die Anzahl der einzelnen Wörter übergroß ist der verfügbare Speicher auf einer einzelnen Maschine. Solange Sie in der Lage sind, unter dem Speicherlimit zu bleiben, sollte eine einfache Schleife, die eine Hash-Tabelle aktualisiert, den Zweck erfüllen.
Wenn Leistung das Hauptziel ist, können Sie eine Hash-basierte oder Trie-basierte Struktur nur im RAM verwenden. Angenommen, Sie führen trotzdem eine nützliche Filterung durch (um Begriffe mit Nicht-Wort-Zeichen nicht zu zählen), liegt die maximale Anzahl der Wörter in Ihrer Tabelle im Bereich von 10⁶ bis 10⁷ (auch wenn mehrere Sprachen betroffen sind) passen in den Speicher eines aktuellen PC (und vermeiden Sie die gesamte Datenbankbehandlung).
Andererseits, wenn Sie die Details der Hash-Tabelle selbst implementieren müssen, gibt es einfach mehr Code, den Sie falsch machen können (während die Datenbank-Leute hoffentlich ihren Code auf das Maximum optimiert haben). So können selbst kleine Details in Ihrer eigenen Implementierung wieder zu Leistungseinbußen führen.
Dieses Dilemma zeigt uns also klar die erste und zweite Optimierungsregel: 1. Nicht vorzeitig optimieren. 2. Messen Sie, bevor Sie optimieren.
:)
Ihre Lösung klingt gut. Wenn der Cache auf der letzten Nutzungszählung basiert, wird er die Wortanzahl für die häufigsten Wörter enthalten. (Wortverteilung ist etwas wie die ersten 100 Wörter deckt 90% der Wortinstanzen ab), so dass Sie keinen sehr großen Cache benötigen.
Wenn Sie die Leistung verbessern und die db löschen möchten, können Sie die Wörter als Trie codieren und die Nutzungszahlen in den Blattknoten speichern. Inessenz, das tut die Datenbank, wenn Sie auf Word-Text indexieren, so dass Sie wirklich nur die db-Latenz vermeiden. Wenn dies das Ziel ist, gibt es andere Möglichkeiten, die Latenz von Datenbanken zu vermeiden, z. B. die Verwendung paralleler Suchvorgänge.
Tags und Links algorithm indexing word-frequency