Эффективно хранить и обновлять огромный (и разреженный?) Многомерный массив для подсчета условных вероятностей - PullRequest
Новая
       34

Эффективно хранить и обновлять огромный (и разреженный?) Многомерный массив для подсчета условных вероятностей

1 голос
/ 11 декабря 2010

Просто для удовольствия я хотел бы подсчитать условные вероятности того, что слово (из естественного языка) появляется в тексте в зависимости от последнего и следующего за последним словом. То есть Я бы взял огромную кучу, например Тексты на английском языке и подсчитайте, как часто появляется каждая комбинация n(i|jk) и n(jk) (где j,k,i - последовательные слова).

Наивный подход заключается в использовании трехмерного массива (для n(i|jk)) с использованием сопоставления слов для позиционирования в 3 измерениях. Поиск позиции мог бы быть эффективно выполнен с использованием trie s (по крайней мере, это мое лучшее предположение), но уже для O (1000) слов я столкнулся бы с ограничениями памяти. Но я предполагаю, что этот массив будет заполнен очень редко, большинство записей равно нулю, и поэтому я потратил бы много памяти. Так что нет трехмерного массива.

Какая структура данных будет лучше подходить для такого варианта использования и при этом будет эффективна для выполнения множества небольших обновлений, как я делаю их при подсчете появления слов? (Может быть, есть совершенно другой способ сделать это?)

(Конечно, мне также нужно сосчитать n(jk), но это легко, потому что это только 2-D :) Язык выбора C ++, я думаю.

1 Ответ

3 голосов
/ 11 декабря 2010

C ++ code: 

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;

Когда вы читаете новое слово.Вы добавляете его в словарь и получаете его индекс 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]++;

Это понятно?Вам нужно больше деталей?

...