大規模テキストにおけるN-gram統計
はじめに
大規模なテキストデータでのN-gram統計を取る場合、特にNが大きい場合(N>=3)は、組み合わせの数が多くなり出てくるN-gramをすべてメモリに保持しながら個数をカウントするのが難しい。効率的な方法があるのを知ったのでちょっと試してみた。
大規模テキストにおけるN-gram統計の取り方
- 岩波講座ソフトウェア科学15「自然言語処理」
- 手順
- ngramを取りたい文章を1つの文として扱う
- この文をメモリに読み込み、各文字の先頭アドレスを保持する配列を作成
- その先頭アドレスの場所の文字から文最後までの部分文字列を1つの単語とみる
- この単語を辞書順に並び替える(アドレス配列だけ)
- ソートした単語の順番で、次の単語と「先頭から共通している文字数」を保持する配列を作成
- Ngramをカウントするときは、単語の先頭からN文字を保持しておき、共通している文字数がN未満になるまで単語数をカウントする。
- もし、N未満ならば新しいNgramなので、新たにカウントを始める
- 確保するメモリ
- Nが大きくなるにつれ、文字の組み合わせが多くなり、Ngramの種類が爆発的に増えてしまい保持できなくなる
- しかし、上記の方法ではN-gramを保持しないので、文と配列2つ分で済む(特に共通文字数配列は高々Nまでなので、N=255でも1byteに収まる)
コード
試しにどんな感じになるか適当に書いてみた。
#include <iostream> #include <string> #include <vector> using namespace std; class utf8_string { std::vector<std::string> str; int num_byte(const char &cc){ unsigned char c = static_cast<unsigned char>(cc); if(c <= 0x7f) return 1; if(0xc0 <= c && c <= 0xcf) return 2; if(0xd0 <= c && c <= 0xdf) return 2; if(0xe0 <= c && c <= 0xef) return 3; if(0xf0 <= c && c <= 0xf7) return 4; if(0xf8 <= c && c <= 0xfb) return 5; return 6; } void init_str(const std::string &s){ for(size_t i=0; i<s.length();){ int n = num_byte(s[i]); str.push_back(s.substr(i,n)); i += n; } } public: utf8_string(const std::string &s){ init_str(s); } utf8_string(const char *p){ std::string s(p); init_str(s); } size_t length() const { return str.size(); } std::string operator[](size_t idx) const { return str[idx]; } bool operator==(const utf8_string &s){ if(length() != s.length()) return false; for(size_t i=0; i<length(); i++){ if(str[i] != s[i]) return false; } return true; } std::string substr(size_t begin, size_t len){ std::string ret; for(size_t i=begin; i<begin+len; i++){ if(i>=str.size()) break; ret += str[i]; } return ret; } }; //ソート比較用 class Cmp { utf8_string &ustr; int utf2int(const string &str){ int ret = 0; for(int i=0; i<str.length(); i++){ ret = ret * 256 + (int)str[i]; } return ret; } public: Cmp(utf8_string &ustr):ustr(ustr){} bool operator()(const int &lhs, const int &rhs){ size_t ln = ustr.length(); int l = lhs, r = rhs, lint, rint; while(l < ln && r < ln){ lint = utf2int(ustr[l]); rint = utf2int(ustr[r]); if(lint < rint) return true; if(lint > rint) return false; l++; r++; } if(r >= ln) return false; return true; } }; //それぞれの文字列のprefixで何文字共通しているか int common_prefix_length(const utf8_string &utf, size_t N, const size_t &lhs, const size_t &rhs){ int ret = 0; size_t ln = utf.length(); size_t l = lhs, r = rhs; while(l < ln && r < ln){ if(utf[l] == utf[r]) ret++; else break; if(ret>=N) break; //N以上なので打ち切る l++; r++; } return ret; } int main(){ //N-gramのN const size_t N = 5; string str; getline(cin, str); utf8_string ustr = str; vector<size_t> ptr; //先頭位置を保持するポインタ(のかわりのindex) vector<int> cmn_char; //次の文字との共通文字数 Cmp cmp(ustr); for(size_t i=0; i<ustr.length()-N+1; i++){ ptr.push_back(i); } //辞書順ソート sort(ptr.begin(), ptr.end(), cmp); //共通文字数カウント for(size_t i=0; i<ptr.size(); i++){ if(i+1<ptr.size()){ cmn_char.push_back(common_prefix_length(ustr, N, ptr[i], ptr[i+1])); }else{ cmn_char.push_back(0); } } /*//各配列の中身を表示 for(size_t i=0; i<ptr.size(); i++){ cout << i << "\t" << ustr.substr(ptr[i], ustr.length()-ptr[i]); cout << "\t" << cmn_char[i] << endl; } cout << "-------" << endl; */ //ngramカウント&表示 string tmp = ""; for(size_t i=0; i<ptr.size(); i++){ if(ustr.substr(ptr[i], N) != tmp){ tmp = ustr.substr(ptr[i], N); int cnt = 1; while(i<ptr.size()){ if(cmn_char[i]<N){ break; } cnt++; i++; } cout << tmp << "\t" << cnt << endl; } } return 0; }
結果
- 「すもももももももものうち」の2gram
うち 1 すも 1 のう 1 もの 1 もも 7
ました。 94 飛《と》び 9 集《あつ》 9 進《すす》 9 言《い》う 9 落《お》ち 9 笑《わら》 9 橋《はし》 9 柱《はしら 9 来ました。 9 天の川の水 9 夢《ゆめ》 9 士《はかせ 9 博士《はか 9 包《つつ》 9 丘《おか》 9 ネルラが、 9 を言《い》 9 を見ていま 9 を着《き》 9 りっぱ》な 9 ようになっ 9 ました。［ 9 のように、 9 のです。 9 ...
