超大規模テキストにおける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,...と増やす
    • t=\frac{1}{\epsilon}log(s^{-1}\delta^{-1})
      • \epsilon : 誤り率
      • s : 閾値( 0 < s < 1 )
      • \delta : 失敗率
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の持つ最大許容誤差値
  • データをバケットに分割(大きさw=e^{-1}、整数値とする)
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」を表示すればよい
ε-deficient synopsis(イプシロン劣シノプス)
  • 上記の2つのアルゴリズムは「ε-deficient synopsis」を保持する
  • 保持する場合、これまで入力されたデータに対し、以下を保障する(らしい)
    • 「真の頻度がs*N以上であるデータはすべて出力」
    • 「真の頻度が(s-ε)*N未満であるデータは出力されない」
    • 「頻度の推定値は、(真の頻度-ε*N)から真の頻度の間の値」

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
  • なってるっぽい
  • もし頻度にばらつきがないような場合はあまりメモリ節約にならない
    • データに合わせてパラメータ調整