超大規模テキストにおけるN-gram統計
はじめに
超大規模なテキストデータでのN-gram統計を取る場合、そもそもデータがメモリにのらなくてSuffixArrayを使ったカウントも無理だったりする。近似値でよい場合、効率的な方法があると知ったのでちょっとメモ&試してみた。
与えられるデータ
- 大量のデータがストリーム形式で与えられるとする
- 高速にどんどん与えられる
- 例えば、データパケット監視やtwitterなど
- カウントしたいデータの種類が膨大
- 種類をメモリに保持するのが無理
ストリームデータにおける頻度カウント法
- 正確なカウントは難しいが、近似的に頻度カウントを行うことができる
- Sticky Sampling Algorithmは解釈が間違っているかもしれない
Sticky Sampling Algorithm
- カウントする要素をサンプリングで選ぶ方法
- 保持するのは以下の2つのペアの集合
- e : 要素(例えばN-gram)
- f : 要素eの頻度
- r : サンプリングレート。各要素を1/rの確率で選ぶ
- ただし、ライフサイクルt,2t,4t,...ごとにrの数値をr=1,2,4,...と増やす
-
- : 誤り率
- s : 閾値( 0 < s < 1 )
- : 失敗率
S = {}; r = 1; while(要素eが与えられる){ if(新しいライフサイクルになった){ rの値を更新する; foreach( 集合Sの各(e,f) ){ 公平なコインをトスする; //表か裏か50%の一様乱数 while(トスが失敗){ //どちらか決めた方がでなかった場合(例えば裏) fの値を1減らす; if(f==0){ 集合Sからこの(e,f)の組を削除する; } } } } if(要素eが集合Sに含まれている){ その要素eの推定頻度fに1を加える; }else{ if(レートrでサンプリング){ //すなわち0から1の一様乱数randが1/r以下になった時 (e,1)を集合Sに加える; }else{ この要素を無視する; } } }
Lossy Counting Algorithm
- 乱数を使わない方法
- しかもSticky Samplingよりも結果が優れている
- 保持するのは以下の3つのペアの集合
- e : 要素(例えばN-gram)
- f : 要素eの頻度
- Δ : fの持つ最大許容誤差値
- データをバケットに分割(大きさ、整数値とする)
S = {}; while(要素eが与えられる){ if(新しいバケットになった){ foreach( 集合Sの各(e,f,Δ) ){ if(f <= b_current - Δ){ この(e,f,Δ)を集合Sから削除; } } } if(要素eが集合Sに含まれている){ その要素eの推定頻度fに1を加える; }else{ 新しいペアとして(e,1,b_current-1)を集合Sに加える; } }
データの出力
- 処理中、ユーザーからの出力要求があった場合は、集合Sで「f>=(s-ε)*Nである要素eとその頻度f」を表示すればよい
Lossy Counting Algorithmの実装
コード
- 試しにどんな感じになるか適当に書いてみた
#include <iostream> #include <cstdlib> #include <map> using namespace std; class LossyCounter { map<string,pair<int,int> > S; int N; double gamma, epsilon; int b_current; void next_backet(){ map<string,pair<int,int> >::iterator it = S.begin(); while(it!=S.end()){ double f = ((*it).second).first; double d = ((*it).second).second; if(f <= b_current - d){ S.erase(it++); }else{ ++it; } } b_current++; } public: LossyCounter(double gamma, double epsilon):gamma(gamma),epsilon(epsilon){ N = 0; b_current = 1; } void add(const string &str){ if(S.count(str)==0){ S[str] = make_pair(1,b_current-1); }else{ S[str].first++; } N++; if(N%((int)(1.0/epsilon))==0){ next_backet(); } } int get(const string &str){ if(S.count(str)==0) return -1; double f = S[str].first; if(f < (gamma - epsilon) * N) return -1; return S[str].first; } void show(){ map<string,pair<int,int> >::iterator it = S.begin(); while(it!=S.end()){ cout << (*it).first << "\t" << ((*it).second).first << endl; ++it; } } int size(){ return S.size(); } }; class NaiveCounter { map<string,int> S; public: void add(const string &str){ S[str]++; } int get(const string &str){ return S[str]; } void show(){ map<string,int>::iterator it = S.begin(); while(it!=S.end()){ cout << (*it).first << "\t" << (*it).second << endl; ++it; } } int size(){ return S.size(); } //LossyCounterとの比較用 void compare(LossyCounter &lc){ {//LossyCounterの出力には含まれないもの cout << "===============================" << endl; map<string,int>::iterator it = S.begin(); while(it!=S.end()){ if(lc.get((*it).first)==-1){ cout << (*it).first << "\t" << (*it).second << endl; } ++it; } } {//頻度が異なるもの cout << "===============================" << endl; map<string,int>::iterator it = S.begin(); while(it!=S.end()){ int cnt = lc.get((*it).first); if(cnt>=0 && cnt != (*it).second){ cout << (*it).first << "\t" << "nc:" << (*it).second << "\t" << "lc:" << cnt; cout << "\t" << "diff:" << ((*it).second - cnt) << endl; } ++it; } } {//等しいもの cout << "===============================" << endl; map<string,int>::iterator it = S.begin(); while(it!=S.end()){ int cnt = lc.get((*it).first); if(cnt>=0 && cnt == (*it).second){ cout << (*it).first << "\t" << "nc:" << (*it).second << "\t" << "lc:" << cnt << endl; } ++it; } } } }; //Ngramを適当に作る string create_ngram(int N){ static const string alpha = "AAAAAAABBBBBBCCCCCDDDDEEEFFG"; string ret = ""; for(int i=0; i<N; i++){ ret += alpha[rand()%(alpha.length())]; } return ret; } int main(){ srand(0); static const int N = 1000000; //データ数 static const int NGRAM = 3; //ngram LossyCounter lc(0.001, 0.0005); NaiveCounter nc; for(int i=0; i<N; i++){ string str = create_ngram(NGRAM); //cout << str << endl; lc.add(str); nc.add(str); } //違いを表示 cout << "lossy count size = " << lc.size() << endl; cout << "naive count size = " << nc.size() << endl; nc.compare(lc); return 0; }
実行結果
- N=1000000、γ=0.001、ε=0.0005としたので、(イプシロン劣シノプスより)以下を満たさなければならない
- 頻度が1000回以上のものは必ず表示
- 頻度が500回以下は必ず表示しない
- 出力される頻度は、真の頻度との誤差が500以内
lossy count size = 315 naive count size = 343 //7*7*7通り ===============================//lossy conterで表示されない要素 AGG 323 BGF 512 BGG 263 CFG 456 CGF 469 CGG 229 DEG 567 DFG 386 DGF 358 DGG 176 EDG 498 EEG 459 EFG 286 EGE 350 EGF 271 EGG 127 FBG 505 FCG 485 FDG 399 FEF 549 FEG 288 FFF 349 FFG 186 FGB 509 FGC 450 FGD 406 FGE 280 FGF 194 FGG 95 GAG 295 GBF 530 GBG 258 GCF 482 GCG 215 GDF 362 GDG 195 GEE 409 GEF 269 GEG 133 GFB 568 GFC 478 GFD 360 GFE 265 GFF 199 GFG 96 GGA 339 GGB 279 GGC 208 GGD 166 GGE 138 GGF 115 GGG 58 ===============================//頻度が異なるもの AGB nc:1899 lc:1897 diff:2 AGF nc:661 lc:657 diff:4 BDG nc:1095 lc:1088 diff:7 BEG nc:839 lc:838 diff:1 BGD nc:1094 lc:1093 diff:1 BGE nc:787 lc:786 diff:1 CDG nc:901 lc:900 diff:1 CGC nc:1123 lc:1122 diff:1 DAG nc:1286 lc:1285 diff:1 DDG nc:718 lc:717 diff:1 DFC nc:1810 lc:1809 diff:1 DGA nc:1254 lc:1252 diff:2 DGC nc:897 lc:895 diff:2 DGD nc:779 lc:778 diff:1 DGE nc:544 lc:542 diff:2 EBF nc:1596 lc:1595 diff:1 EBG nc:812 lc:809 diff:3 EEF nc:848 lc:840 diff:8 EFA nc:1870 lc:1869 diff:1 EFE nc:809 lc:806 diff:3 EFF nc:572 lc:506 diff:66 EGB nc:791 lc:785 diff:6 EGD nc:542 lc:540 diff:2 FAG nc:646 lc:640 diff:6 FCE nc:1357 lc:1355 diff:2 FDD nc:1436 lc:1435 diff:1 FDF nc:726 lc:723 diff:3 FEC nc:1419 lc:1418 diff:1 FED nc:1116 lc:1115 diff:1 FFA nc:1253 lc:1252 diff:1 FFC nc:909 lc:907 diff:2 FFE nc:556 lc:553 diff:3 FGA nc:632 lc:631 diff:1 GAF nc:620 lc:576 diff:44 GBB nc:1604 lc:1603 diff:1 GCB nc:1349 lc:1348 diff:1 GCD nc:848 lc:837 diff:11 GCE nc:688 lc:681 diff:7 GDB nc:1094 lc:1093 diff:1 GDE nc:560 lc:543 diff:17 GEA nc:930 lc:929 diff:1 GEB nc:794 lc:793 diff:1 GEC nc:688 lc:686 diff:2 GED nc:526 lc:524 diff:2 ===============================//頻度が等しいもの AAA nc:15484 lc:15484 AAB nc:13396 lc:13396 AAC nc:11134 lc:11134 AAD nc:8942 lc:8942 AAE nc:6705 lc:6705 AAF nc:4492 lc:4492 AAG nc:2280 lc:2280 ABA nc:13553 lc:13553 ABB nc:11238 lc:11238 ABC nc:9527 lc:9527 ABD nc:7694 lc:7694 ABE nc:5681 lc:5681 ABF nc:3949 lc:3949 ABG nc:1899 lc:1899 ACA nc:11228 lc:11228 ACB nc:9528 lc:9528 ACC nc:8044 lc:8044 ACD nc:6548 lc:6548 ACE nc:4763 lc:4763 ACF nc:3270 lc:3270 ACG nc:1589 lc:1589 ADA nc:8868 lc:8868 ADB nc:7605 lc:7605 ADC nc:6438 lc:6438 ADD nc:5230 lc:5230 ADE nc:3837 lc:3837 ADF nc:2506 lc:2506 ADG nc:1296 lc:1296 AEA nc:6705 lc:6705 AEB nc:5728 lc:5728 AEC nc:4683 lc:4683 AED nc:3942 lc:3942 AEE nc:2854 lc:2854 AEF nc:1920 lc:1920 AEG nc:935 lc:935 AFA nc:4434 lc:4434 AFB nc:3871 lc:3871 AFC nc:3163 lc:3163 AFD nc:2495 lc:2495 AFE nc:1888 lc:1888 AFF nc:1321 lc:1321 AFG nc:649 lc:649 AGA nc:2200 lc:2200 AGC nc:1640 lc:1640 AGD nc:1352 lc:1352 AGE nc:950 lc:950 BAA nc:13447 lc:13447 BAB nc:11422 lc:11422 BAC nc:9640 lc:9640 BAD nc:7787 lc:7787 BAE nc:5744 lc:5744 BAF nc:3736 lc:3736 BAG nc:1857 lc:1857 BBA nc:11273 lc:11273 BBB nc:9956 lc:9956 BBC nc:8203 lc:8203 BBD nc:6595 lc:6595 BBE nc:4942 lc:4942 BBF nc:3198 lc:3198 BBG nc:1631 lc:1631 BCA nc:9635 lc:9635 BCB nc:8159 lc:8159 BCC nc:6930 lc:6930 BCD nc:5490 lc:5490 BCE nc:4244 lc:4244 BCF nc:2725 lc:2725 BCG nc:1389 lc:1389 BDA nc:7735 lc:7735 BDB nc:6475 lc:6475 BDC nc:5318 lc:5318 BDD nc:4355 lc:4355 BDE nc:3225 lc:3225 BDF nc:2181 lc:2181 BEA nc:5788 lc:5788 BEB nc:4925 lc:4925 BEC nc:4126 lc:4126 BED nc:3374 lc:3374 BEE nc:2491 lc:2491 BEF nc:1661 lc:1661 BFA nc:3754 lc:3754 BFB nc:3253 lc:3253 BFC nc:2759 lc:2759 BFD nc:2194 lc:2194 BFE nc:1726 lc:1726 BFF nc:1175 lc:1175 BFG nc:527 lc:527 BGA nc:1934 lc:1934 BGB nc:1683 lc:1683 BGC nc:1376 lc:1376 CAA nc:11031 lc:11031 CAB nc:9744 lc:9744 CAC nc:7795 lc:7795 CAD nc:6542 lc:6542 CAE nc:4807 lc:4807 CAF nc:3204 lc:3204 CAG nc:1592 lc:1592 CBA nc:9435 lc:9435 CBB nc:8236 lc:8236 CBC nc:6791 lc:6791 CBD nc:5412 lc:5412 CBE nc:4082 lc:4082 CBF nc:2665 lc:2665 CBG nc:1355 lc:1355 CCA nc:8027 lc:8027 CCB nc:6767 lc:6767 CCC nc:5692 lc:5692 CCD nc:4512 lc:4512 CCE nc:3494 lc:3494 CCF nc:2294 lc:2294 CCG nc:1146 lc:1146 CDA nc:6325 lc:6325 CDB nc:5436 lc:5436 CDC nc:4582 lc:4582 CDD nc:3601 lc:3601 CDE nc:2744 lc:2744 CDF nc:1914 lc:1914 CEA nc:4783 lc:4783 CEB nc:4047 lc:4047 CEC nc:3339 lc:3339 CED nc:2755 lc:2755 CEE nc:2084 lc:2084 CEF nc:1341 lc:1341 CEG nc:682 lc:682 CFA nc:3220 lc:3220 CFB nc:2702 lc:2702 CFC nc:2298 lc:2298 CFD nc:1872 lc:1872 CFE nc:1264 lc:1264 CFF nc:868 lc:868 CGA nc:1591 lc:1591 CGB nc:1367 lc:1367 CGD nc:916 lc:916 CGE nc:687 lc:687 DAA nc:9052 lc:9052 DAB nc:7546 lc:7546 DAC nc:6355 lc:6355 DAD nc:5174 lc:5174 DAE nc:3736 lc:3736 DAF nc:2499 lc:2499 DBA nc:7646 lc:7646 DBB nc:6672 lc:6672 DBC nc:5477 lc:5477 DBD nc:4364 lc:4364 DBE nc:3243 lc:3243 DBF nc:2131 lc:2131 DBG nc:1099 lc:1099 DCA nc:6347 lc:6347 DCB nc:5588 lc:5588 DCC nc:4402 lc:4402 DCD nc:3706 lc:3706 DCE nc:2691 lc:2691 DCF nc:1785 lc:1785 DCG nc:892 lc:892 DDA nc:5163 lc:5163 DDB nc:4365 lc:4365 DDC nc:3575 lc:3575 DDD nc:2909 lc:2909 DDE nc:2052 lc:2052 DDF nc:1407 lc:1407 DEA nc:3778 lc:3778 DEB nc:3360 lc:3360 DEC nc:2749 lc:2749 DED nc:2176 lc:2176 DEE nc:1618 lc:1618 DEF nc:1094 lc:1094 DFA nc:2483 lc:2483 DFB nc:2161 lc:2161 DFD nc:1475 lc:1475 DFE nc:1112 lc:1112 DFF nc:694 lc:694 DGB nc:1152 lc:1152 EAA nc:6566 lc:6566 EAB nc:5656 lc:5656 EAC nc:4805 lc:4805 EAD nc:3845 lc:3845 EAE nc:2872 lc:2872 EAF nc:1865 lc:1865 EAG nc:934 lc:934 EBA nc:5733 lc:5733 EBB nc:5042 lc:5042 EBC nc:4202 lc:4202 EBD nc:3374 lc:3374 EBE nc:2541 lc:2541 ECA nc:4713 lc:4713 ECB nc:4118 lc:4118 ECC nc:3328 lc:3328 ECD nc:2777 lc:2777 ECE nc:1979 lc:1979 ECF nc:1382 lc:1382 ECG nc:715 lc:715 EDA nc:3897 lc:3897 EDB nc:3274 lc:3274 EDC nc:2729 lc:2729 EDD nc:2235 lc:2235 EDE nc:1657 lc:1657 EDF nc:1133 lc:1133 EEA nc:2909 lc:2909 EEB nc:2541 lc:2541 EEC nc:2014 lc:2014 EED nc:1691 lc:1691 EEE nc:1252 lc:1252 EFB nc:1662 lc:1662 EFC nc:1351 lc:1351 EFD nc:1070 lc:1070 EGA nc:987 lc:987 EGC nc:726 lc:726 FAA nc:4410 lc:4410 FAB nc:3844 lc:3844 FAC nc:3259 lc:3259 FAD nc:2469 lc:2469 FAE nc:1845 lc:1845 FAF nc:1288 lc:1288 FBA nc:3869 lc:3869 FBB nc:3265 lc:3265 FBC nc:2701 lc:2701 FBD nc:2177 lc:2177 FBE nc:1632 lc:1632 FBF nc:1112 lc:1112 FCA nc:3152 lc:3152 FCB nc:2709 lc:2709 FCC nc:2255 lc:2255 FCD nc:1808 lc:1808 FCF nc:876 lc:876 FDA nc:2519 lc:2519 FDB nc:2223 lc:2223 FDC nc:1751 lc:1751 FDE nc:1090 lc:1090 FEA nc:1928 lc:1928 FEB nc:1631 lc:1631 FEE nc:827 lc:827 FFB nc:1045 lc:1045 FFD nc:792 lc:792 GAA nc:2247 lc:2247 GAB nc:1952 lc:1952 GAC nc:1622 lc:1622 GAD nc:1273 lc:1273 GAE nc:986 lc:986 GBA nc:1923 lc:1923 GBC nc:1400 lc:1400 GBD nc:1044 lc:1044 GBE nc:825 lc:825 GCA nc:1607 lc:1607 GCC nc:1127 lc:1127 GDA nc:1229 lc:1229 GDC nc:907 lc:907 GDD nc:734 lc:734 GFA nc:691 lc:691
- なってるっぽい
- もし頻度にばらつきがないような場合はあまりメモリ節約にならない
- データに合わせてパラメータ調整
参考文献
- アルゴリズム・サイエンスシリーズ 5 数理技法編「オンラインアルゴリズムとストリームアルゴリズム」
- http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.19.8594&rep=rep1&type=pdf
- http://chalow.net/2010-05-12-1.html
- http://diary.overlasting.net/2010-04-23-3.html
- http://ibisforest.org/index.php?lossy%20counting%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0
- http://www.cse.ust.hk/vldb2002/VLDB2002-proceedings/slides/S10P03slides.pdf