1

只是为了好玩，我想计算一个单词（来自自然语言）出现在文本中的条件概率，这取决于最后一个单词和最后一个单词。即我会拿一大堆例如英文文本并计算每个组合n(i|jk)和n(jk)出现的频率（j,k,i连续词在哪里）。

天真的方法是使用 3-D 数组 (for n(i|jk))，使用单词到 3 维位置的映射。可以使用 s 有效地完成位置查找trie（至少这是我最好的猜测），但是对于 O(1000) 个单词，我会遇到内存限制。但我猜这个数组只会被稀疏填充，大多数条目为零，因此我会浪费大量内存。所以没有3-D阵列。

哪种数据结构更适合这样的用例，并且仍然可以有效地进行很多小的更新，就像我在计算单词的出现时所做的那样？（也许有一种完全不同的方式来做到这一点？）

（当然我也需要 count n(jk)，但这很容易，因为它只是 2-D :) 我猜选择的语言是 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;

但为了更好地查找 word->index 它可能是一个地图：

map<string, int> dictionary;

当你读到一个新词。您将它添加到字典并获取它的 index k，您已经拥有前两个单词i的j索引，所以您只需执行以下操作：

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]++;

可以理解吗？您需要更多详细信息吗？

于 2010-12-10T22:15:46.783 回答