単語の頻度カウントを保存およびクエリできるようにするための優れた設計について、コミュニティのコンセンサスを得たいと考えています。テキスト入力を解析し、単語が（時間の経過とともに）何回出現したかを保存する必要があるアプリケーションを構築しています。したがって、次の入力が与えられます。
次の値を格納します。
Word Count
-------------
To 1
Kill 1
A 2
Mocking 2
Bird 1
Piano 1
Player 1
後で、任意の単語のカウント値をすばやくクエリできます。
私の現在の計画は、単純に単語とカウントをデータベースに保存し、単語カウント値のキャッシュに依存することです...しかし、これを長期的に実行可能なソリューションにするのに十分なキャッシュヒットが得られないと思います.
アルゴリズム、データ構造、またはこれを優れたソリューションにする他のアイデアを提案できる人はいますか?
単語カウントは、MapReduceプログラムの標準的な例です (Wikipedia の疑似コード)。
void map(String name, String document):
for each word w in document:
EmitIntermediate(w, "1");
void reduce(String word, Iterator partialCounts):
int result = 0;
for each pc in partialCounts:
result += ParseInt(pc);
Emit(AsString(result));
これがその方法だと言っているわけではありませんが、個別の単語の数が 1 台のマシンで使用可能なメモリを超える場合に、適切にスケーリングするものが必要な場合は、間違いなくオプションです。メモリ制限を下回ることができる限り、ハッシュ テーブルを更新する単純なループでうまくいくはずです。
データベースが適切なソリューションではないと感じる理由がわかりません。おそらく約 100000 行しかなく、テーブルのサイズが小さいということは、完全にメモリに格納できることを意味します。単語を主キーにすると、検索が非常に高速になります。
パフォーマンスが主な目標である場合は、RAM のみでハッシュ ベースまたはトライ ベースの構造を使用できます。いずれにせよ（単語以外の文字を含む用語をカウントしないように）何らかの有用なフィルタリングを行うと仮定すると、テーブル内の単語の最大数は 10⁶ から 107 の範囲になるため（複数の言語が関係している場合でも）、これは簡単に現在の PC のメモリに収まります (そして、すべてのデータベース処理を完全に回避します)。
一方、ハッシュ テーブルの詳細を自分で実装する必要がある場合は、間違いを犯す可能性のあるコードが増えます (データベース担当者はコードを最大限に微調整したことを願っています)。そのため、独自の実装のわずかな詳細でさえ、再びパフォーマンスの低下につながる可能性があります。
したがって、このジレンマは、最適化の 1 番目と 2 番目のルールを明確に示しています。 1. 時期尚早に最適化しないでください。2. 最適化する前に測定します。
:)
あなたの解決策はうまく聞こえます。キャッシュが最近の使用回数に基づいている場合、最も頻繁に使用される単語の単語数が保持されます。（単語の分散は、最初の100語が単語インスタンスの90％をカバーするようなものです）ので、非常に大きなキャッシュは必要ありません。
パフォーマンスを向上させてデータベースを削除したい場合は、単語をトライとしてエンコードし、使用回数をリーフノードに保存できます。本質的には、単語のテキストでインデックスを作成する場合、データベースはこれを実行しているため、実際にはデータベースの待ち時間を回避しているだけです。それが目標である場合、並列ルックアップを使用するなど、dbレイテンシーを回避する他の方法があります。
ハッシュ テーブルを使用します。