条件付き確率をカウントするために、巨大な（そしてまばらな）多次元配列を効率的に保存して更新します

Question

楽しみのために、最後の単語に応じて、単語（自然言語から）がテキストに表示される条件付き確率を数えたいと思います。つまり、私は英語のテキストを大量に取り、それぞれの組み合わせの頻度を数えます n(i|jk) と n(jk) 表示されます（ここで j,k,i 困難な言葉です）。

素朴なアプローチは、3D配列を使用することです（ n(i|jk)）、単語のマッピングを使用して3次元に配置します。位置のルックアップは、効率的に使用できます trieS（少なくともそれは私の最良の推測です）が、すでにO（1000）の単語では、メモリの制約に遭遇します。しかし、この配列はまばらに過ぎず、ほとんどのエントリはゼロであるため、私は多くのメモリを無駄にします。したがって、3-Dアレイはありません。

このようなユースケースに適したデータ構造は、単語の外観を数えるときに私が行うような多くの小さな更新を行うのに効率的ですか？ （たぶんこれを行うにはまったく別の方法がありますか？）

（もちろん、私もカウントする必要があります n(jk), 、しかし、それは簡単です。なぜなら、それはたった2Dであるからです:)選択の言語はC ++だと思います。

Answer 1

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;

新しい単語を読んだとき。辞書に追加してインデックスを取得します k, 、あなたはすでに持っています i と j 前の2つの単語のインデックスを使用すると、次のことを行うだけです。

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

パフォーマンスを向上させるために、Bigramを一度だけ検索できます。

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

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