1

楽しみのために、最後の単語と最後の単語の次の単語に応じて、（自然言語からの）単語がテキストに表示される条件付き確率を数えたいと思います。つまり、たとえば英語のテキストを大量に取得し、各組み合わせが出現する頻度を数えn(i|jk)ますn(jk)（j,k,i連続する単語はどこにありますか）。

n(i|jk)素朴なアプローチは、3次元での位置への単語のマッピングを使用して、（の）3D配列を使用することです。位置検索はsを使用して効率的に実行できますがtrie（少なくともそれが私の最善の推測です）、すでにO（1000）ワードの場合、メモリの制約に遭遇します。しかし、この配列はまばらにしか埋められず、ほとんどのエントリはゼロであるため、大量のメモリを浪費すると思います。したがって、3D配列はありません。

どのようなデータ構造がそのようなユースケースに適していて、単語の出現を数えるときに行うように、多くの小さな更新を効率的に行うことができますか？（多分これを行うための完全に異なる方法がありますか？）

（もちろん、私も数える必要がありますn(jk)が、それは2Dしかないので、簡単です:)選択する言語はC++だと思います。

4

1 に答える 1

3

C++ コード:

struct bigram_key{
    int i, j;// words - indexes of the words in a dictionary

    // a constructor to be easily constructible
    bigram_key(int a_i, int a_j):i(a_i), j(a_j){}

    // you need to sort keys to be used in a map container
    bool operator<(bigram_key const &other) const{
        return i<other.i || (i==other.i && j<other.j);
    }
};

struct bigram_data{
    int count;// n(ij)
    map<int, int> trigram_counts;// n(k|ij) = trigram_counts[k]
}

map<bigram_key, bigram_data> trigrams;

辞書は、次のような見つかったすべての単語のベクトルである可能性があります。

vector<string> dictionary;

しかし、より良いルックアップの単語 - >インデックスのために、それはマップになる可能性があります:

map<string, int> dictionary;

新しい単語を読むとき。それを辞書に追加してその index を取得すると、前の 2 つの単語のインデックスkが既にあるので、次のようにします。ij

trigrams[bigram_key(i,j)].count++;
trigrams[bigram_key(i,j)].trigram_counts[k]++;

パフォーマンスを向上させるために、バイグラムを 1 回だけ検索できます。

bigram_data &bigram = trigrams[bigram_key(i,j)];
bigram.count++;
bigram.trigram_counts[k]++;

それは理解できますか？詳細が必要ですか？

于 2010-12-10T22:15:46.783 に答える