小規模データで単語の数を数えてみた (1) - ny23の日記
大規模データで単語の数を数える - ny23の日記 で書いた Count-Min Sketch で，誤差を減らすヒューリスティクス (conservative update) New directions in traffic measurement and accounting (SIGCOMM Comput. Commun. Rev., 32(4), 2002) を実装して，動的ダブル配列を使って Wikipedia のテキスト処理を高速化 - ny23の日記 の小規模データ（1.5GiB の Wikipedia 本文）の単語カウントでその効果を見てみた．考えるところはハッシュ関数に何を使うかぐらいで（キーを陽に保持しない限りは）実装はとても簡単． // GNU GPL version 2 copyright@ny23 #include <cstdio> #include <cstdl
大規模データで単語の数を数える - ny23の日記
大規模データから one-pass で item（n-gram など）の頻度を数える手法に関するメモ．ここ数年，毎年のように超大規模な n-gram の統計情報を空間／時間効率良く利用するための手法が提案されている．最近だと， Storing the Web in Memory: Space Efficient Language Models with Constant Time Retrieval (EMNLP 2010) とか．この論文では，最小完全ハッシュ関数や power-law を考慮した頻度表現の圧縮など，細かい技術を丁寧に組み上げており，これぐらい工夫が細かくなってくるとlog-frequency Bloom filter (ACL 2007) ぐらいからから始まった n-gram 頻度情報の圧縮の研究もそろそろ収束したかという印象（ちょうど論文を読む直前に，この論文の7節の
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
