人間が生成したコンテンツの膨大なコレクションがあります。最も頻繁に出現する単語または語句を見つけたい。これを行う効率的な方法は何ですか？
3304 次
6 に答える
4
車輪を再発明しないでください。Luceneなどの全文検索エンジンを使用します。
于 2009-07-26T05:57:23.037 に答える
3
シンプルで素朴な方法は、ハッシュテーブルを使用することです。単語をウォークスルーし、カウントを増やしていきます。
プロセスの最後に、キーと値のペアをカウント順に並べ替えます。
于 2009-07-26T05:59:46.060 に答える
3
基本的な考え方は単純です -- 実行可能な疑似コードで、
from collections import defaultdict
def process(words):
d = defaultdict(int)
for w in words: d[w] += 1
return d
もちろん、悪魔は細部に潜んでいます。大量のコレクションを単語を生成するイテレータにするにはどうすればよいでしょうか。1 台のマシンでは処理できないほど大きく、Hadoop などによる mapreduce アプローチが必要ですか? などなど 。NLTKは、言語面 (単語を明確に分離していない言語の単語を分離する) に役立ちます。
単一マシンの実行 (mapreduce のネット) で発生する可能性のある問題の 1 つは、単純なアイデアでは、メモリをいっぱいにするシングルトンまたはその付近 (単語が 1 回または数回発生する) が多すぎることです。これに対する確率論的反論は、2 つのパスを実行することです。1 つはランダム サンプリング (10 分の 1、または 100 分の 1 の単語のみを取得) を使用して上位ランクの候補となる一連の単語を作成し、2 番目のパスでは上位ランクの単語をスキップします。候補セットに含まれていません。サンプリングしている単語の数と結果に必要な単語の数に応じて、この方法で重要な単語を見逃す確率の上限を計算することができます (妥当な数と任意の自然言語について)。 、私はあなたが大丈夫であることを保証します）。
単語を出現回数にマッピングする辞書ができたら、出現回数で上位 N 個の単語を選択するだけです。辞書が大きすぎて出現回数全体で並べ替えることができない場合は、ヒープ キューが役立ちます (たとえば、私のお気に入りの実行可能な疑似コード、たとえば、heapq.nlargest がそれを行います)。
于 2009-07-26T06:04:17.533 に答える
1
Apriori アルゴリズムを調べてください。頻繁に使用するアイテムや頻繁に使用するアイテムのセットを見つけるために使用できます。
ウィキペディアの記事にあるように、同じことを行うより効率的なアルゴリズムがありますが、これがあなたの状況に当てはまるかどうかを確認する良い出発点になる可能性があります.
于 2009-07-26T06:04:34.363 に答える
0
パトリシア トライまたは実用的なアルゴリズムを使用して、英数字のトライでコード化された情報を取得してみてはいかがでしょうか。
于 2009-07-26T06:05:47.187 に答える
-1
キーを単語、カウンターを値とする単純なマップではないでしょうか。高い値のカウンターを取得することにより、使用されている上位の単語が表示されます。これは単なる O(N) 操作です。
于 2009-07-26T06:08:52.077 に答える