저장 및 업데이트 거대한 (스파 스?) 다차원 그냥 재미를 위해 나는 (자연 언어에서) 단어가 텍스트에 표시되는 조건부 확률을 계산하려는

Question

조건부 확률을 계산하기 위해 효율적으로 배열, 마지막에 따라 그리고 마지막 단어 옆에. 나는. 나는 엄청난 무리를 짊어 질 것이다. 영어 텍스트는 카운트 얼마나 자주 (j,k,i이 sucsessive 단어) 각 조합 n(i|jk) 및 n(jk) 나타납니다.

순진 방법은 3 차원 위치에 단어의 매핑을 사용하여, (n(i|jk) 용) 3-D 배열을 사용하는 것이다. 위치 검색은 trie을 사용하여 효율적으로 수행 할 수 있지만 적어도 O (1000) 단어의 경우 메모리 제약 조건에 부딪 힐 수 있습니다. 하지만이 배열은 희박하게 채워질 것입니다. 대부분의 항목이 0이므로 나는 많은 메모리를 낭비 할 것입니다. 그래서 3-D 어레이는 없습니다. 단어의 모습을 계산 할 때 내가 그들을처럼 작은 업데이트를 많이 할 효율적으로 여전히 사용 사례에 더 적합 할 것이다 어떤 데이터 구조

?

가 (물론 나는 또한 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]++; 

은 이해할 수 있습니까? 더 자세한 정보가 필요하십니까?