条件付き確率を計算するために巨大な（および疎な）多次元配列を効率的に保存して更新する

Question

楽しいことに、最後の文章に基づいて（自然言語の）単語が出現するという条件付き確率を数えたい最後の単語の隣に。私。私は巨大な束を取るだろう。英語のテキストを入力し、それぞれの組み合わせがどれくらいの頻度であるかを数えます（j,k,iはsucsessive wordsです）。n(i|jk)とn(jk)が表示されます。

単純なアプローチは、ワードのマッピングを使用して3次元で配置する3次元配列（n(i|jk)）を使用することです。ポジションルックアップは効率的にtrie（少なくとも私の推測では最も良い）を使用して行うことができますが、すでにO（1000）ワードの場合はメモリの制約に遭遇します。しかし、私はこの配列がまばらに満たされ、ほとんどのエントリがゼロであると推測します。したがって、私はたくさんのメモリを無駄にするでしょう。したがって、3D配列はありません。

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

（もちろん私もn(jk)と数える必要がありますが、それは2-Dであるため簡単です:) 選択する言語は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インデックスを持っているあなただけの操作を行います。より良いパフォーマンスを得るために

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

あなたは一度だけバイグラムを検索することができる。

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

わかりますか？詳細が必要ですか？