6

この質問は実際には非常に単純ですが、コーディングに入る前にいくつかのアイデアを聞きたいと思います。各行に単語が含まれるファイルを指定して、最も頻繁にn個の数値を計算します。

私の頭に浮かぶ最初の、そして残念なことに唯一のものは、を使用するために使用しstd::mapます。unordered_map仲間のC++の人たちは、それはとても合理的だと言うでしょう。

アルゴリズム側に何かを追加できるかどうか、またはこれは基本的に「最良のデータ構造を選択した人が勝つ」タイプの質問であるかどうかを知りたいです。インターネットで検索して、ハッシュテーブルと優先度付きキューがO（n）の実行時間のアルゴリズムを提供する可能性があることを読みましたが、実装は複雑になると思います

何か案は？

4

5 に答える 5

6

このタスクに使用する最適なデータ構造は Trie です:

http://en.wikipedia.org/wiki/Trie

文字列をカウントするためのハッシュ テーブルよりも優れています。

于 2012-04-18T01:43:46.813 に答える
2

この質問にはさまざまなアプローチがあります。最終的には、シナリオやファイルのサイズなどの他の要因 (ファイルに 10 億行ある場合) に依存するためHashMap、効率的な方法ではありません。問題に応じて、次のことができます。

  1. 一意の単語の数が非常に限られていることがわかっている場合は、TreeMapまたは を使用できますstd::map。
  2. 単語数が非常に多い場合はtrie、別のデータ構造でさまざまな単語のカウントを作成して保持できます。これは size のヒープ (最小/最大は、何をしたいかによって異なります) である可能性がありますn。したがって、すべての単語を保存する必要はなく、必要なものだけを保存する必要があります。
于 2012-04-17T23:56:12.173 に答える
1

上位N個の最も頻繁に使用される単語に関心があり、正確である必要がない場合は、非常に巧妙な構造を使用できます。ウディ・マンバー経由でこれを聞いた、それは次のように機能します：

N個の要素の配列を作成し、各要素が値とカウントを追跡し、この配列にインデックスを付けるカウンターも保持します。さらに、値からその配列へのインデックスへのマップがあります。構造を値（テキストストリームからの単語など）で更新するたびに、最初にマップをチェックして、その値のカウントをインクリメントする場合は、その値がすでに配列にあるかどうかを確認します。そうでない場合は、カウンターが指している要素のカウントをデクリメントしてから、カウンターをインクリメントします。

これは単純に聞こえます。アルゴリズムについては何も有用ではないように見えますが、一般的な実際のデータの場合は非常にうまくいく傾向があります。通常、上位N個を追跡する場合は、空の値が多数含まれるため、10*Nの容量でこの構造を作成することをお勧めします。欽定訳聖書を入力として使用すると、この構造が最も頻繁に使用される単語として（順不同で）リストされます。

0 : in
1 : And
2 : shall
3 : of
4 : that
5 : to
6 : he
7 : and
8 : the
9 : I

そして、ここに（順番に）トップ10の最も頻繁な単語があります：

0 : the ,  62600
1 : and ,  37820
2 : of ,  34513
3 : to ,  13497
4 : And ,  12703
5 : in ,  12216
6 : that ,  11699
7 : he ,  9447
8 : shall ,  9335
9 : unto ,  8912

上位10語のうち9語が正解であり、50要素のみのスペースを使用して正解したことがわかります。ユースケースによっては、ここでのスペースの節約が非常に役立つ場合があります。また、非常に高速です。

これが私が使用したtopNの実装で、Goで書かれています。

type Event string

type TopN struct {
  events  []Event
  counts  []int
  current int
  mapped  map[Event]int
}
func makeTopN(N int) *TopN {
  return &TopN{
    counts: make([]int, N),
    events: make([]Event, N),
    current: 0,
    mapped: make(map[Event]int, N),
  }
}

func (t *TopN) RegisterEvent(e Event) {
  if index, ok := t.mapped[e]; ok {
    t.counts[index]++
  } else {
    if t.counts[t.current] == 0 {
      t.counts[t.current] = 1
      t.events[t.current] = e
      t.mapped[e] = t.current
    } else {
      t.counts[t.current]--
      if t.counts[t.current] == 0 {
        delete(t.mapped, t.events[t.current])
      }
    }
  }
  t.current = (t.current + 1) % len(t.counts)
}
于 2012-04-18T07:44:40.673 に答える
1

選択肢が多ければ(または)から始めません(他の制約が適用されるかどうかはわかりませんが)。std::mapunordered_map

ここには 2 つのデータ項目があり、一方をある時間のキー部分として使用しますが、もう一方を別の時間のキーとして使用します。そのためには、おそらく Boost Bimap や Boost MultiIndex のようなものが必要になるでしょう。

Bimap を使用する一般的な考え方は次のとおりです。

#include <boost/bimap.hpp>
#include <boost/bimap/list_of.hpp>
#include <iostream>

#define elements(array) ((sizeof(array)/sizeof(array[0])))

class uint_proxy {
    unsigned value;
public:
    uint_proxy() : value(0) {}
    uint_proxy& operator++() { ++value; return *this; }
    unsigned operator++(int) { return value++; }
    operator unsigned() const { return value; }
};

int main() {    
    int b[]={2,4,3,5,2,6,6,3,6,4};

    boost::bimap<int, boost::bimaps::list_of<uint_proxy> > a;

    // walk through array, counting how often each number occurs:
    for (int i=0; i<elements(b); i++) 
        ++a.left[b[i]];

    // print out the most frequent:
    std::cout << a.right.rbegin()->second;
}

今のところ、最も頻度の高い数だけを出力しましたが、最も頻度の高い N を出力するために N 回反復するのは簡単なことです。

于 2012-04-18T00:43:08.170 に答える
0

各行に単語が含まれるファイルを指定して、最頻出数nを計算します。...インターネットで検索して、ハッシュテーブルと優先キューがO(n)のアルゴリズムを提供する可能性があることを読みました

* n * が同じであることを意味する場合は、いいえ、これは不可能です。ただし、入力ファイルのサイズに関して時間の線形を意味するだけの場合は、ハッシュ テーブルを使用した簡単な実装で目的を達成できます。

サブリニア メモリを使用した確率的近似アルゴリズムが存在する場合があります。

于 2012-04-17T23:59:15.503 に答える