高效地存儲和更新巨大（和稀疏？）多維數組來計算條件概率

Question

只是爲了好玩，我想計算一個詞（來自自然語言）出現在文本中的條件概率，取決於最後並緊挨着最後一個字。即我會帶一大堆例如英文文本並計算每個組合n(i|jk)和n(jk)出現的頻率（其中j,k,i是成功的詞）。

幼稚的方法是使用三維數組（對於n(i|jk)），使用單詞映射來定位三維。可以使用trie s（至少這是我最好的猜測）有效地完成位置查找，但是對於O（1000）字我已經遇到了內存限制。但是我想這個數組只能填充很少，大多數條目都是零，所以我會浪費大量的內存。所以沒有三維陣列。

什麼樣的數據結構可以更好地適合這樣的用例，並且仍然可以高效地執行大量的小更新，就像我在計算單詞出現時做的那樣。 （也許有這樣做的完全不同的方式？）

（當然，我也需要計數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]++; 

可以理解嗎？你需要更多的細節嗎？