出現数が最大の単語を検索する

ドキュメント内で最大の出現数を持つ単語を検索するのに最も最適な方法（アルゴリズム）は何ですか？出現数が最大の単語を検索する

出典

2011-09-24 Saket

何回の最大発生回数ですか？ – DeCaf

その文書内の**単語**の最大出現回数 – Saket

文書内で最も多く出現する単語をお探しですか？単純なヒストグラムがO（n）でトリックを行います。 – amit

単純histogramによりO（N）で行うことができる[ハッシュベース】問題は明らかにオメガ（n）の問題です、それはbig O notationの点で最適です。

出典

2011-09-24 16:54:19 amit

とにかく、最適な予想ケース。 –

ハッシュマップの代わりに[trie]（http://ja.wikipedia.org/wiki/Trie）は決定的なO（n）ワーストケースを与えますが、実際には遅くなる可能性があります。 – comco

一意のすべての単語を何回見たのか（おそらくハッシュテーブルまたはこれを行うツリーを使用して）、ドキュメントを一度スキャンしてください。

手順1を実行している間に、これまでに見られたすべての単語の中で最も多くカウントされている単語を追跡します。

histogram <- new map<String,int> 
for each word in document: 
    if word in histogram: 
     histogram[word] <- histogram[word] + 1 
    else: 
     histogram[word] <- 1 
max <- 0 
maxWord<- "" 
for each word in histogram: 
    if histogram[word] > max: 
    max <- histogram[word] 
    maxWord <- word 
return maxWord

これはO（n）の溶液、及び以降：文書の中で最も時間をoccures単語を見つける

出典

2011-09-24 16:51:55 NPE

出現数が最大の単語を検索する

答えて

関連する問題