1000ページの本の中で出現する上位3つの単語を見つけるためのアルゴリズム。ハッシュテーブルを使用するよりも良い解決策はありますか？
質問する
4140 次
6 に答える
3
潜在的に優れた解決策は、トライベースの辞書を使用することです。トライを使用すると、最悪の場合のO（ n × N）時間でタスクを実行できます。ここで、 Nは単語の数、nは単語の平均の長さです。ハッシュテーブルとの違いは、トライの複雑さはハッシュ関数や本の語彙に依存しないことです。
すべての単語をスキャンする必要があるため、任意の入力に対してO（ n × N ）よりも優れた方法はありません。
于 2012-04-17T23:14:22.773 に答える
3
奇妙なことに、誰もが単語リストに目を通すことに集中し、主要な問題 (最も頻繁に使用される k 個の項目を取り上げる) を忘れていました。実際には、ハッシュ マップは出現回数をカウントするのに十分ですが、この実装には依然としてsortingが必要です。これは事実上 O(n*logn) (最良の場合) です。
したがって、ハッシュ マップの実装では、単語をカウントするために 1 つのパス (保証されていない O(n)) と O(n*logn) を並べ替える必要があります。ここで述べた試行は、カウントのより良い解決策かもしれませんが、ソートは依然として問題です。繰り返しますが、1 パス + ソートです。
実際に必要なのはheap、つまりルートに近い最大 (最小) 要素を保持するツリーベースのデータ構造です。ヒープの単純な実装 (バイナリ ヒープなど) では、新しい要素を挿入するのに O(logn) の時間が必要であり、最上位の要素を取得するのに O(1) の時間が必要です。より洗練された実装 (例: Fibonacci heap ) では、挿入に償却 O(1) 時間がかかるため、結果のアルゴリズムは O(n) 時間かかります。これは、提案されたソリューションよりも優れています。
于 2012-04-18T01:55:43.927 に答える
1
正確な答えを得るには、すべてのページを1語ずつ確認する必要があります。
したがって、ハッシュテーブルインターフェイスを使用してリンクリストのノードへのポインタを格納するリンクリストの実装は、非常にうまく機能します。
リンクリストを動的に拡張し、ハッシュテーブルを使用して適切なノードにすばやくアクセスして、カウントを更新できるようにする必要があります。
于 2012-04-17T23:15:02.213 に答える
-1
ウィキペディアはこれを言います：
「スペルチェックなどの特定の文字列処理アプリケーションでは、ハッシュテーブルは、試行、有限オートマトン、またはJudy配列よりも効率が低い場合があります。また、各キーが十分に少ないビット数で表されている場合は、ハッシュの代わりにテーブルでは、キーを値の配列へのインデックスとして直接使用できます。この場合、衝突は発生しないことに注意してください。」
私もハッシュツリーを推測したでしょう。
于 2012-04-17T23:14:47.000 に答える
-1
簡単なアプローチは、Dictionary<string, int>（。net）またはを使用してHashTable、本全体をスキャンしながら各単語の出現をカウントすることです。
于 2012-04-17T23:09:06.390 に答える
-1
于 2012-04-18T08:42:25.623 に答える