何百万もの単語が書かれた本を考えると、一度にすべての単語を記憶に収めることはできません。最も頻繁に使用される 10 の単語を見つけるための効率的なアルゴリズム (空間と時間の両方) を与えてください。
私のアプローチは、ハッシュを使用してすべての単語を保存することです。通常、ハッシュは値を取り、それを素数で乗算します (一意のハッシュを生成する可能性が高くなります)。したがって、次のようなことができます。
int hash=7;
for (int i=0; i < strlen; i++) {
hash = hash*31+charAt(i);
}
単語が既に存在する場合は、対応するカウントを増やします。サイズ 10 の最小ヒープを維持します。単語がスキャンされると、その頻度が検出されます。ヒープ内の最小値より大きい場合は、最小値を削除してヒープを挿入および更新します。最後に、ヒープに最も頻繁に使用される 10 個の単語が残ります。どうしたの？このアプローチは、すべての単語を同時にメモリに格納できる場合にのみ機能します。
本のサイズが物理メモリに比べて大きいため、別のアプローチとして外部ソートを使用する方法があります。並べ替えの後、線形検索が私たちの仕事をすることができます。しかし、ディスクからのアクセス時間はどうでしょうか。シーク時間と待ち時間により、アクセス時間が増加する可能性があります。したがって、このアプローチも効率的ではありません。
I can think of yet another approach: DISTRIBUTED HASHING (will work only when we have n machines). Distribute hashing among n machines. We may perform different strategies, say we have 26 machines, then we may hash all the words staring with alphabet 'a'('A') in machine 1,words starting with 'b'('B') and so on. We can then perform sorting or can use a TRIE data structure.
Is there any better way of finding the top ten most frequent words?