第6回 IIR 読書会
- P85-108
- 5 Index compression
- @株式会社DeNA会議室
- 参加者 17 名
- 前回の復習
- 前置き
- 圧縮すると何が嬉しい？
- ディスク容量の節約
- キャッシュにのりやすくなる
- IO が速くなる
- 圧縮すると何が嬉しい？
- 5.1 Statistical properties of terms ininformation retrieval
- 前処理スゲー
- 但し stop words の処理は圧縮との絡みで考える必要がある
- フランス語のwebページとかはステミングやると効く
- 圧縮の仕方: Lossless か Lossy か
- 前処理スゲー
- 5.1.1 Heap's law: Estimating the numbers of terms
- ヒープの法則 c.f. wikipedia:en:Heaps'_law
- ある程度ドキュメントが集まった際に辞書のサイズを予測するのに使える
- ヒープの法則 c.f. wikipedia:en:Heaps'_law
- 5.1.2 Zipf's law: Modeling the distribution of terms
- ジップの法則 c.f. wikipedia:ジップの法則 (or ジフの法則)
- ヒープの法則よりもこっちが有名
- 80:20の法則
- 実は経験則に過ぎない
- e.g. ロングテール, 都市の人口
- 単語の頻度のモデルとしてこれを使って圧縮率などを計算してみる
- ジップの法則 c.f. wikipedia:ジップの法則 (or ジフの法則)
- 5.2 Dictionary compression
- メモリー上に置いておけると幸せ - 小さくしておくと良いこと色々
- 5.2.1 Dictionary-as-a-string
- なんであらかじめ単語ごとに 4byte 確保しとく必要があるのか
- 削る価値ある？
- Dictionary-as-a-string storage
- 辞書は何で固定長?
- 辞書の更新はそれ程頻繁でないので，これで良い.
- B-木とか使うと新しい単語を追加しやすい
- なんであらかじめ単語ごとに 4byte 確保しとく必要があるのか
- 5.2.2 Blocked storage
- 速度はそんなに変わらないのに，ちょっとだけ節約
- 完全最小ハッシュはちょっと無茶ぶりっぽい？
- はてなキーワードは15分に一回更新される. trie で．
- 完全最小ハッシュはちょっと無茶ぶりっぽい？
- 速度はそんなに変わらないのに，ちょっとだけ節約
- 5.3 Postings file compression
- 20ビットはもったいないので postings 間のギャップだけ覚えておけば良い
- 5.3.1 Variable byte codes
- 可変長なのが効率が良い
- 5.3.2 γ codes
- ハサミマーク
- 難易度急上昇
- 最適なコーディングはエントロピーで求まる
- Variable encoding よりもオイシイ数字が出てくる可能性がある
- γ codeで 0 はどうやって表現?
- 1ずらすか1引く
- ハサミマーク
- misc
- オカムラでは椅子をお試し用にかしてくれるらしい
